IMO 2012 Shortlist C6

Category: Combinatorics

Problem

Let k and n be fixed positive integers. In the liar’s guessing game, Amy chooses integers x and N with 1 ≤ x ≤ N. She tells Ben what N is, but not what x is. Ben may then repeatedly ask Amy whether x ∈ S for arbitrary sets S of integers. Amy will always answer with yes or no, but she might lie. The only restriction is that she can lie at most k times in a row. After he has asked as many questions as he wants, Ben must specify a set of at most n positive integers. If x is in this set he wins; otherwise, he loses. Prove that: a) If n ≥ 2k then Ben can always win. b) For sufficiently large k there exist n ≥ 1.99k such that Ben cannot guarantee a win. Solution. Consider an answer A ∈ {yes,no} to a question of the kind “Is x in the set S?” We say that A is inconsistent with a number i if A = yes and i 6∈ S, or if A = no and i ∈ S. Observe that an answer inconsistent with the target number x is a lie. a) Suppose that Ben has determined a set T of size m that contains x. This is true initially with m = N and T = {1,2,...,N}. For m > 2k we show how Ben can find a number y ∈ T that is different from x. By performing this step repeatedly he can reduce T to be of size 2k ≤ n and thus win. Since only the size m > 2k of T is relevant, assume that T = {0,1,...,2k ,...,m−1}. Ben begins by asking repeatedly whether x is 2k . If Amy answers no k + 1 times in a row, one of these answers is truthful, and so x 6= 2k . Otherwise Ben stops asking about 2k at the first answer yes. He then asks, for each i = 1,...,k, if the binary representation of x has a 0 in the ith digit. Regardless of what the k answers are, they are all inconsistent with a certain number y ∈ {0,1,...,2k − 1}. The preceding answer yes about 2k is also inconsistent with y. Hence y 6= x. Otherwise the last k + 1 answers are not truthful, which is impossible. Either way, Ben finds a number in T that is different from x, and the claim is proven. b) We prove that if 1 < λ < 2 and n = (2 − λ)λk+1 −1 then Ben cannot guarantee a win. To complete the proof, then it suffices to take λ such that 1.99 < λ < 2 and k large enough so that n = (2 − λ)λk+1 − 1 ≥ 1.99k . Consider the following strategy for Amy. First she chooses N = n+1 and x ∈ {1,2,...,n+1} arbitrarily. After every answer of hers Amy determines, for each i = 1,2,...,n + 1, the number mi of consecutive answers she has given by that point that are inconsistent with i. To decide on her next answer, she then uses the quantity φ = n+1 X i=1 λmi . No matter what Ben’s next question is, Amy chooses the answer which minimizes φ. We claim that with this strategy φ will always stay less than λk+1 . Consequently no expo- nent mi in φ will ever exceed k, hence Amy will never give more than k consecutive answers inconsistent with some i. In particular this applies to the target number x, so she will never lie more than k times in a row. Thus, given the claim, Amy’s strategy is legal. Since the strategy does not depend on x in any way, Ben can make no deductions about x, and therefore he cannot guarantee a win. It remains to show that φ < λk+1 at all times. Initially each mi is 0, so this condition holds in the beginning due to 1 < λ < 2 and n = (2 − λ)λk+1 − 1. Suppose that φ < λk+1 at some point, and Ben has just asked if x ∈ S for some set S. According as Amy answers yes or no, the new value of φ becomes φ1 = X i∈S 1 + X i/ ∈S λmi+1 or φ2 = X i∈S λmi+1 + X i/ ∈S 1.27 Since Amy chooses the option minimizing φ, the new φ will equal min(φ1,φ2). Now we have min(φ1,φ2) ≤ (φ1 + φ2) = X i∈S 1 + λmi+1 + X i/ ∈S λmi+1

1 ! = (λφ + n + 1). Because φ < λk+1 , the assumptions λ < 2 and n = (2 − λ)λk+1 − 1 lead to min(φ1,φ2) < (λk+2
(2 − λ)λk+1 ) = λk+1 . The claim follows, which completes the solution. Comment. Given a fixed k, let f(k) denote the minimum value of n for which Ben can guarantee a victory. The problem asks for a proof that for large k 1.99k ≤ f(k) ≤ 2k . A computer search shows that f(k) = 2,3,4,7,11,17 for k = 1,2,3,4,5,6.28