Problem

Source: INMO 2021 Problem 4

Tags: combinatorics, guessing game, graph theory, cycles, paths, Trees, INMO



A Magician and a Detective play a game. The Magician lays down cards numbered from $1$ to $52$ face-down on a table. On each move, the Detective can point to two cards and inquire if the numbers on them are consecutive. The Magician replies truthfully. After a finite number of moves, the Detective points to two cards. She wins if the numbers on these two cards are consecutive, and loses otherwise. Prove that the Detective can guarantee a win if and only if she is allowed to ask at least $50$ questions. Proposed by Anant Mudgal