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 in 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 >= 2^k, then Ben can always win. b) For sufficiently large k there exist n >= 1.99^k such that Ben cannot guarantee a win. ------------------------- Future note: Due to incorrect text-copying, I was solving a version where a) n >= 2k b) n >= 1.99k, where the case a) is actually untrue. So Ben can ask repeatedly the same set k-times. But Amy can reply sometimes yes, sometimes no. How can Ben limit the possible set to a bounded number? At least, if he could be certain that the Amy's number is not a certain given number... Then he could iterate the process. If we split the possible numbers to 2^k boxes, then Ben can ask k questions such that any set of answers eliminate one of the boxes: * Boxes numbered by binary (yes-no) sequences of length k. * At i-th step, Ben asks about the set of boxes containing 'no' at i-th position * Let A denote the sequence given by Amy. * Amy's number cannot be in the box numbered by A, she would have lied in every of the k answers. By this elimination process, Ben can get a set of possible candidates down to 2^k. (still significantly bigger than 2k, but at least something) Is it necessary for Ben to take use of the fact that he is asking in a one long sequence (and not just series of k-tuples)? Because the 2^k strategy for Ben seems optimal if we were reduced to (disjoint) k-tuples of questions, such that every such k-tuple contains at least one valid answer. Let's try to come up with a strategy for Amy in the k-tuple variant. And let's suppose that * Amy knows the k-tuple of questions before she gives the answers. * N = 2^k-1 Amy only needs to give answers such that every number is be viable. So she must answer so that every number is covered by at least one set that Amy specified by her answer (Ben's set S, or its complement). She can do that: * At every moment, reduce the uncovered set by at least half. * By this, the uncovered set will reduce to 0 from 2^k-1 in k steps. * This is actually "online" strategy, the additional assumption of knowing the questions beforehand was unnecessary. So it is crucial for reduction 2^k -> 2k that it is a continuous sequence of questions, not just a sequence of k-tuples. So let's play for Ben in the 2^k-1 case with more than k consecutive questions. He could threaten Amy at every step to not reducing of the uncovered step to the necessary size: * At i-th (i = 1..k) move, Ben points to 2^(k-i) uncovered numbers. * If Amy replies yes at any moment, he can continue the splitting strategy on this set of size 2^(k-i), and reduce it by one. * Therefore, Amy must reply 'no' every time. * So after k moves, Amy replied 'no' to a disjoint sets of sizes 1, 2, 4, ..., 2^(k-1) === Unassociated idea: It could be also useful for Ben to force Amy to reply 'yes' on an one-element set (he can do it by asking about the set k-times). I will look at this idea later, now I continue with the current plan. === * Is this state really useful for Ben? Note: Ben could also add any subset of a covered set to his question. * Ben wants a move rendering at least one number unviable. * For this unviability, Ben cannot use the answer1, it will "expire" after question k+1. * So what about any half of the union of the sets from questions 2..k? * It turns the entire quarter of all the numbers unviable. * Good, Ben can proceed, however this strategy relied on the fact that Ben can ask about a set of size 2^(k-1), it is still large. Let's try play for Ben on a specific small case. k=3, N=7. Ben's task is just to eliminate one number out of 7. Let's start with forcing Amy to tell 'yes' about the set {1} Now, the rest is six numbers, Ben can easily eliminate at least one of them in two questions: {2,3}, {2,4} k=3 was still too easy, it was still based on the exponential strategy, k=4, N=9 B: {9} A: yes B: {1,2,3,4} {1,2,5,6} {1,3,5,7} exponential strategy combined with 'ask about one' still viable :-( Let's play for Amy, still Amy loses in our perspective, if one of the numbers become unviable, Something like k=10, N=21 How do we measure the current state? At every moment, every number was admitted by Amy in some last step before, (or we are in the first k steps). So every number has a "score" of in how many consecutive steps Amy denied the number. If a score of a number becomes k, Amy loses. So the game reformulation: * There are n+1 zeroes written on a blackboard. * At every step, Ben points to a set S of the numbers on the blackboard * Amy chooses a set R to be either S, or the complement of S (S') * Every number in R is increased by one, all other numbers are reset to zero. * If a number gets number k, Ben wins, Amy loses (in the original game, Ben eliminates this number and continues with another set of n+1 numbers) Let's try k=6, n=13 0 0 0 0 0 0 0 0 0 0 0 0 0 | | | | | | 1 1 1 1 1 1 0 0 0 0 0 0 0 | | | | | | | 0 0 0 0 0 0 0 1 1 1 1 1 1 (not very useful move for Ben) | | | | | | | 1 1 1 1 1 1 1 0 0 0 0 0 0 | | | | | | | 0 0 0 0 0 0 2 1 1 1 1 1 1 All right, by the 'ask singleton trick', we can get: 1 1 1 1 1 1 1 1 1 1 1 1 0 and continue 1 1 1 1 1 1 1 1 1 1 1 1 0 | | | | | | 2 2 2 2 2 2 0 0 0 0 0 0 0 | | | | | | 3 3 3 0 0 0 1 1 1 0 0 0 0 Amy strategy proposal: always select the set with smaller "score" defined as the sum(2^x for x in R) Now, I play according to this strategy for Amy. (from Ben's perspective, I want to make it as balanced as possible) I will write the powers of two to make it for me easier to calculate. 8 8 8 1 1 1 2 2 2 1 1 1 1 score: 37 | | | 16 16 1 1 1 1 4 1 1 1 1 1 1 score: 46 | | | | | | | | 32 1 2 2 2 2 1 2 2 2 1 1 1 score: 51 | 1 2 4 4 4 4 2 4 4 4 2 2 2 score: 39 (sort) 4 4 4 4 4 4 4 2 2 2 2 2 1 score: 39 | | | | | | 8 8 8 8 1 1 1 4 4 1 1 1 1 score: 47 | | | | | | 16 16 1 1 2 2 2 8 1 1 1 1 1 score: 53 | | | | 32 1 1 1 1 1 1 16 2 2 1 1 1 score: 61 | 1 2 2 2 2 2 2 32 4 4 2 2 2 score: 59 | 2 4 4 4 4 4 4 1 8 8 4 4 4 score: 55 | | | | | | 4 1 1 1 1 1 1 2 16 16 8 8 1 score: 61 | | | | 8 1 1 1 1 1 1 4 32 1 16 1 1 score: 69 | | | | 16 1 1 1 2 2 2 8 1 1 32 2 2 score: 71 | | | | 32 1 1 2 1 4 4 16 2 2 1 4 4 score: 74 | | | | | 1 1 1 1 1 8 8 32 4 4 2 8 8 score: 79 Wait, actually 64 is enough for me. I thought I need more, then it is easy 1 1 1 1 1 8 8 32 4 4 2 8 8 score: 79 | 1 1 1 1 1 1 1 64 1 1 1 1 1 It is kind of true that I (Ben) can increase the numbers. But what is the bound? How to tell that a position is good for Ben / Amy? The "sum 2-powers score" is relatively good but it since increasing since we reset the powers to 1, and not to 0. What about losing positions analysis? Ay loses if: * There is a single 'k' (k ...) * There are at least two 'k-1' (k-1 k-1 ...) * There are at least four k-2 (k-2 k-2 ...) Let's change the notation: i <-> k-i Amy losing positions (again): * 0 ... * 1 1 ... * 2 2 2 2 ... * 1 2 2 ... (-> 0 ... or 1 1 ...) * 1 2 3 3 ... (-> 0 ... or 1 2 2 ...) In general: * 1 2 3 ... i i ... is a losing position for Amy | <- Ben's move, forcing Amy to 1 2 ... i-1 i-1 Since the maximal number is k, a losing position is also * 1 2 3 ... k-1 (because then there are at least two k's) What are other (lex-bigger) losing positions? * If there is just one 1, and no 2, then the next step may lead to no 1 * 2 2 2 3 ... i-1 i i (instead of 0, we can threaten by 1 1) * 1 3 3 3 4 ... i-1 i i * 1 2 4 4 4 ... i-1 i i ... Actually starting with 2 2 2 2 * 1 3 3 3 3 * 1 2 4 4 4 4 ... * 1 2 ... k-2 k k k k It still seems to require exponential size... Further losing position * 2 2 3 3 4 4 ... k-1 k-1 There is just too long journey from the start, to the end. I need a semivariant that Ben could increase every step. But it is not just the sum of powers of 2 of the original numbers: * If there is a single large value 0 0 0 0 0 0 5 then it will be erased in the next step, and only new 1's will appear. Also, selecting the single 5 is the best step for Ben. So v(0 0 0 0 0 0 5) < v(1 1 1 1 1 1 0) or Ben will use such strategy that never leeads to a single large value. Can he avoid it? 1 1 1 1 1 1 0 0 0 0 0 0 0 ^ ^ ^ ^ ^ ^ 1 1 1 1 1 1 1 0 0 0 0 0 0 ^ ^ ^ ^ ^ ^ 2 1 1 1 1 1 1 0 0 0 0 0 0 ^ ^ ^ ^ ^ ^ 3 1 1 1 1 1 1 0 0 0 0 0 0 ^ ^ ^ ^ ^ ^ ... 2 2 2 2 2 2 0 0 0 0 0 0 0 ^ ^ ^ ^ ^ 3 1 1 1 1 1 1 1 0 0 0 0 0 (now, I am not sure if the last step was good) ^ ^ ^ ^ ^ ^ Another attempt 1 0 0 0 0 0 0 0 0 0 0 0 0 ^ 2 0 0 0 0 0 0 0 0 0 0 0 0 ^ ... 1 1 1 1 1 1 1 1 1 1 1 1 0 ^ ^ ^ ^ ^ ^ 2 2 2 2 2 2 0 0 0 0 0 0 0 ^ ^ ^ ^ ^ ^ ^ ^ 3 1 1 1 1 1 1 0 0 0 0 0 0 ^ ^ ^ ^ ^ ^ ^ 2 2 2 2 2 2 0 0 0 0 0 0 0 (I am where I was before) ^ ^ ^ ^ ^ ^ ^ ^ 3 1 1 1 1 1 1 0 0 0 0 0 0 ^ ^ 4 2 0 0 0 0 0 0 0 0 0 0 0 ^ ^ 5 1 0 0 0 0 0 0 0 0 0 0 0 ^ ^ ... 2 1 1 1 1 1 1 1 1 1 1 0 0 ^ ^ ^ 3 2 1 0 0 0 0 0 0 0 0 0 0 ^ ^ ^ 4 2 1 0 0 0 0 0 0 0 0 0 0 ^ ^ ^ ... 3 1 1 1 1 1 1 1 1 1 0 0 0 ^ ^ ^ ^ ^ 4 2 2 1 1 0 0 0 0 0 0 0 0 ^ ^ ^ ^ ^ 5 2 2 1 1 0 0 0 0 0 0 0 0 ^ ^ ^ ^ ^ ... 3 3 1 1 1 1 1 1 0 0 0 0 0 ^ ^ ^ ^ ^ ^ ^ ^ This is really random. How do I use the advantage of having many high values? 3 3 3 3 3 3 3 3 3 3 3 3 3 ^ ^ ^ ^ ^ ^ 4 4 4 4 4 4 0 0 0 0 0 0 0 ^ ^ ^ ^ ^ ^ ^ ^ 5 1 1 1 1 1 1 0 0 0 0 0 0 ... it was not really such an advantage Rather, I may need a consecutive sequence 4 3 2 1 0 0 0 0 0 0 0 0 0 ^ ^ 5 3 0 0 0 0 0 0 0 0 0 0 0 ^ 4 1 1 1 1 1 1 1 1 1 1 1 1 ... not so useful either It looks like Amy can get almost everything to at most 1 in a few steps. 3 3 3 3 3 3 3 3 3 3 3 3 3 ^ ^ ^ ^ ^ ^ 4 4 4 4 4 4 0 0 0 0 0 0 0 ^ ^ ^ ^ ^ ^ 5 5 5 1 1 1 0 0 0 0 0 0 0 ^ ^ 6 2 2 2 0 0 0 0 0 0 0 0 0 ^ 3 3 3 1 1 1 1 1 1 1 1 1 0 ^ ^ ^ 4 4 4 0 0 0 0 0 0 0 0 0 0 ^ ^ 5 1 1 1 1 1 1 1 1 1 1 0 0 ^ 2 2 2 2 2 2 2 2 2 2 1 1 0 Another, even simpler Amy's strategy: Reset the set with higher lex-order (when written in non-increasing order) 0 0 0 0 0 0 0 0 0 0 0 0 0 ^ ^ ^ ^ ^ ^ 1 1 1 1 1 1 0 0 0 0 0 0 0 ^ ^ ^ ^ ^ ^ ^ ^ ^ 2 2 1 1 1 1 1 1 1 0 0 0 0 ^ ^ 2 2 2 2 2 2 2 1 1 1 1 0 0 ^ ^ ^ ^ 3 3 3 2 2 2 2 1 1 0 0 0 0 ^ ^ 4 3 3 3 3 2 2 1 1 1 1 0 0 ^ 4 4 4 4 3 3 2 2 2 2 1 1 0 ^ ^ ^ 5 4 4 3 3 3 3 2 2 1 0 0 0 ^ 5 5 4 4 4 4 3 3 2 1 1 1 0 ^ ^ 5 5 5 5 4 4 3 2 2 2 1 0 0 ^ ^ ^ 6 5 5 4 3 3 3 2 1 1 0 0 0 ^ 6 6 5 4 4 4 3 2 2 1 1 1 0 ^ ^ 6 5 5 5 4 3 3 2 2 2 1 0 0 ^ 6 6 6 5 4 4 3 3 3 2 1 1 0 ^ ^ 7 6 5 5 4 4 4 3 2 2 1 0 0 That is not a good strategy for Amy, easily exploitable. But she could simply play 3 3 3 2 2 2 2 1 1 0 0 0 0 ^ ^ 4 4 0 0 0 0 0 0 0 0 0 0 0 leading to significantly worse position for Ben. So the strategy should be something like: "if the set is small, and the numbers outside are not small, reset the rest" It pretty much resembles the sum(2^x) score. The issue of this type of score is that high value from a single number can be quickly lost. What about: Whenever there is a gap (x < y are present but not z such that x < z < y), we decrease y to fill the gap. Now, it could be easier for Amy to win. Let's follow the sum(2^x) strategy (and denote by powers of 2). 1 1 1 1 1 1 1 1 1 1 1 1 1 ^ 2 1 1 1 1 1 1 1 1 1 1 1 1 ^ ^ 4 2 1 1 1 1 1 1 1 1 1 1 1 ^ ^ ^ 8 4 2 1 1 1 1 1 1 1 1 1 1 ^ ^ ^ ^ 2 2 2 2 2 2 2 2 2 1 1 1 1 ^ ^ ^ ^ 4 4 2 2 1 1 1 1 1 1 1 1 1 ^ ^ ^ ^ ^ ^ 8 4 2 2 2 2 1 1 1 1 1 1 1 ^ ^ ^ ^ 4 4 4 2 2 2 2 2 2 1 1 1 1 ^ ^ ^ ^ ^ ^ ^ 8 4 4 4 2 2 1 1 1 1 1 1 1 ^ ^ ^ ^ 16 8 4 2 1 1 1 1 1 1 1 1 1 ... that does not make much sense either. Whatever move I make now (for Ben), it gets worse. The fundamental question should be something like: How can Ben perform log(k) moves without reseting everything below log(k)? No, it does not make sense. It is not really possible. Let's go back to the k-tuple version of the original game. If we consider (k/2)-tuple version (Amy must tell the truth once in every k/2-tuple), then she must also tell the truth in every k consecutive moves. Since Ben cannot (is not guaranteed to) win the (k/2)-tuple version for any n < 2^(k/2)-1 he will not win the original version either. Perhaps the problem statement was incorrect... Ah, there is 2^k, and 1.99^k, not 2k and 1.99k! ------------------------------------------------------- Continue with correct problem statement. We have already proven that Ben wins if n >= 2^k - 1 by gradual elimination of an individual box from a set of size 2^k. Therefore, the part (a) is done. However, the simple bound for Amy winning I have so far is sqrt(2)^k, not 1.99^k, so I (Amy) need to be smarter here. From the solving process so far, we have seen that "simple" strateies for Amy do not work even for n = 2k. So we should probably take the strategy for sqrt(2)^k, and tune it a bit. Strategy for for Amy for (k/2) tuples: * Select such a set, so that the number of elements not covered in the current tuple is decreased by at least half. That is a pretty weird strategy -- it requires not only the currect state but also the path to it. What about this modification: * Reset the set containing more numbers bigger than k/2. So in theory, all numbers could become k/2, and then they would be eliminated in the following k/2 steps. Not necessarily. Let i denote k/2. i i ... ^ i+1 i ... ^ i+2 i ... ... That does not really work. I also need to take the bigger number somehow. Even in the case i i i ... ^ ^ i+1 i i ... ^ ^ i+2 i i ... ^ ^ ... these 'i's can appear for a long time, and Amy must reset the i+k in the meantime. The only strategy for Amy working at least to some extent (sqrt(2)^k) relies on the history of the game (in particular, in which part of the k/2-tuple I am). It is so weird. Could I detect this information based on the game state only? In the strategy, I am keeping the number of numbers not reseted in the current k/2-tuple under n/2^i after i moves. This points to the strategy "take the biggest number (preferably in bigger amount)" but this one is just a general version of the lex-order which was not working. Why the lex-order is not working? (we got to number 7 on 13 numbers) can te k/2-tuple strategy do better? So the tuple would have size 4 to reduce everything in 13 numbers. ------------- 0 0 0 0 0 0 0 0 0 0 0 0 0 ^ ^ ^ ^ ^ ^ 1 1 1 1 1 1 0 0 0 0 0 0 0 ^ ^ ^ ^ ^ ^ ^ ^ ^ 2 2 0 0 0 0 1 1 1 1 1 1 1 ^ ^ 0 0 2 2 2 2 2 2 2 1 1 1 1 ------------- 0 0 2 2 2 2 2 2 2 1 1 1 1 -- here the tupled strategy differs from the lex-strategy ^ ^ ^ ^ 1 1 0 0 0 0 3 3 3 2 2 2 2 <- tuple-strategy 0 0 3 3 3 3 0 0 0 0 0 0 0 <- lex-strategy Or, could the 2^x-strategy work for large sizes? The problem of the 2^x strategy was that the total 2^x-score can increase by the number of reseted elements. It will decrease only if Ben cannot manage to offer sets with balanced 2^x scores. But maybe, there is some total 2^x-score such that no matter what the distribution is, Ben cannot provide a balanced sets. Well, not really, * any even number can be written as a sum of powers of two such that * every power of two is used even-number-times, and * the size of the decomposition is logarithmic. * This does not proves that the 2^x-strategy does not work but it destroys the easy way to prove it. Again, lets play for Ben given there is big amount of numbers. Let's say Ben plays an analogous strategy to the winning strategy for 2^k. but now, there are only 2^k' numbers. Indexed by binary sequences 1..k' And at i-th step, he chooses all the numbers indexed by a sequence having zero at i % k'. So for example for k' = 3. Let's play for Amy 0 0 0 0 0 0 0 0 ^ ^ ^ ^ 1 1 1 1 0 0 0 0 ^ ^ ^ ^ 2 2 0 0 1 1 0 0 ^ ^ ^ ^ 3 0 1 0 2 0 1 0 ^ ^ ^ ^ 0 0 0 0 3 1 2 1 ^ ^ ^ ^ 0 0 1 1 0 0 3 2 ^ ^ ^ ^ 0 1 0 2 0 1 0 3 and we are basically back at step 4. Actually, since step 4, it is all the same 0 0 0 0 1 1 2 3 could Ben do something better at this step? 3 2 1 1 0 0 0 0 ^ 4 0 0 0 0 0 0 0 -- we already know this, it ultimately leads to 0 1 1 1 1 1 1 1 If we wanted to generalize this step for Amy, it would be "If a small set is selected, reset the rest, and in the following (logarithmically many) steps eliminate the set." So we can assume that Ben is selecting only "big" sets. For example, if k'=5, Ben can get to the state 5 4 3 3 2x4 1x8 0x16 We could consider the set "5 4 3 3" as "small", and numbers 2, 1, 0 as "low" That is not that easy, because we cannot simple ignore the "low" numbers, otherwise Amy could get "non-small" number of "non-low" numbers. But the perception of a state just through numbers of given values is practical. Play a bit more with this notation (0 is on the left) 16 8 4 2 1 1 B: 8 4 2 1 1 0 16 8 4 2 1 1 0 8 4 0 0 1 16 0 0 2 1 I still want to make the 2^x strategy working. Ah, idea!! Instead of 2^x, use another power alpha^x, where alpha is closer to 2 but would guarantee that the score will not increase with large values. In one step, let S denote the original alpha^x score of a position. * There can appear at most n more ones, so the score can be increased by n. * The score of the set with smaller score is at most S/2, and it is multiplied by alpha. * So the new score is at most: n + S * (alpha/2) Therefore, if alpha < 2, there is an upper bound B on the score. To find the bound, I solve: S = n + S * (alpha/2) n = S * (1-alpha/2) S = n / (1-alpha/2). So the bound is B = n / (1-alpha/2) If S < n / (1-alpha/2), then the next state should satisfy this inequality as well: n + S * (alpha/2) < n + (n/(1-alpha/2)) * (alpha/2) = (n*(1-alpha/2) + n*alpha/2) / (1-alpha/2) = n / (1-alpha/2) Good, it is true. Now, I just need to find such values of alpha and k so that the bound will block score alpha^k. alpha^k > n / (1-alpha/2) alpha^k * (1-alpha/2) > 1.99^k Let's set alpha = 1.995 1.995^k * (0.005) > 1.99^k (1.995 / 1.99) ^ k > 1 / 0.005 This is true for sufficiently large k, since (1.995 / 1.99) > 1. QED