Narrowing It Down

Well, that was quite a while without blogging, huh...Anyway, summer is here agian along with free time, so its time for the solution to the number guessing problem from last time.

When I was solving this on my own, I made a mistake and thought I figured out the solution when I actually hadn't, so then I looked at the real solution and was disappointed to see that I spoiled it for myself. Anyway, what I had figured out was an important piece of the solution, so I will post it anyway.

Essentially, you represent your numbers in binary, and then ask Alice "Is the ones digit of your number a 0?", "Is the twos digit of your number a 0?", "Is the fours digit of your number a 0?", and so on. So, if the first question is answered "no", the second question "yes", the third question "yes", then you know that 3 times Alice has told you the number is not something ending in 110. Extening this to all 10 digits, there will exist some number that Alice has said 10 times that that is not her number, thus you can eliminate it for your list of candidates.

To eliminate the next number, you could just renumber the remaining candidates, but a better way is just to use a series of sets. Assume the set S₀ is your list of possible candidates. Divide S₀ into two equally sized sets and ask if her number is in the first set, you then have S₁, the set of candidates that Alice just said her number is not in. Divide S₁ into two sets also, and take S₂ to be the set that she denies her number being in. Eventually you reach S₁₀ a set of numbers that she has just told you 10 consecutive times that her number is not in. As long as S₁₀ isn't empty, we have made progress. This requires that S₉ have at least 2 memebers, so S₈ has at least 4, moving up to S₁ needing 512 members so S₀ would need at least 1024. We can see this method will eliminate at least one candidate as long as we started with at least 1024. (When I solved this myself, I tried to go through that logic in my head, and miscounted to 512, so I thought I had a solution).

To proceed any further, we essentually do the strategy twice, but using the tail end of the last set of questions in the new questions, since any 10 consecutive questions must have at least 1 truthful answer. The method (as given by the xkcd forums) is:

If there are more than 512 candidates, act as follows: (This procedure will eliminate at least one additional number)
1a) Let C₀ be the set of all candidates. (C_n will be the set of numbers such that, if it is in C_n, she has told n straight lies.)
1b) Divide C₀ in half into A₀ and B₀. (|A₀| >= 256 and |B₀| >= 256.)
1c) Ask whether the number is in A₀.
1d) If she says yes, define C₁ to be B₀; if she says no, define C₁ to be A₀. (|C₁| >= 256)
2) Construct A₁, B₁, and C₂ in the same way. (|C₂| >= 128)
3) Keep going (|C₃| >= 64... |C₉| >= 1.
4) If |C₉| > 1, construct C₁₀ and eliminate all numbers in C₁₀. STOP.
5) Ask again "Is your number in C₉?".
6a) If she says no, you can eliminate all numbers in C₉. STOP.
6b) If she says yes, define D₁ as being C₀ - C₉. |D₁| >= 512. (A number will be in D_n iff it requires her to make at least n lies starting from the question in 5.)
7) Construct D₂, ... similarly. |D₂| >= 256, ... |D₁₀| >= 1.
8) Eliminate D₁₀. STOP.

The first 4 steps are the same as mine, but then switches in the case that the set C₉ has only 1 element (which could happen if C₀ had between 512 and 1023).

Anyway, thats it for that. You can solve the harder problem of trying to restate the initial problem replacing 2000 (the size of Alices initial set) with N, 1000 (the size of Bobs target set) with M and 9 (the maximum number of consecutive lies) with K, but I would suggest you take a look at the thread on the xkcd forums for that stuff, it goes pretty far down the rabbit-hole.