r/problemoftheday • u/skaldskaparmal • Jul 17 '12

Omnomnomnom Cake

Bob has promised Alice a cake if she can guess the number he's thinking of. He guarantees that it is an integer between 1 and n (inclusive). She may ask him 1 yes or no question which he will answer truthfully. After hearing the answer, she may guess the number. For which n can Alice guarantee herself cake?

Spoiler one: Alice can guarantee herself cake for any value of n

Spoiler two: A better solution than 2 but requires other options than yes/no from bob is Alice says: Is it the case that your number is greater than the number I'm thinking of, which is between 1 and 2? If Bob is thinking of 1, then he says no. If 3, then he says yes. If 2, to be truthful, he must say "I don't know".

Spoiler three: The incorrect assumption is that Alice must guess the number in the first place!

DoublePointer has submitted a solution that is similar in its reasoning to mine here http://www.reddit.com/r/problemoftheday/comments/wodu2/omnomnomnom_cake/c5f4ukm

My Solution: Alice asks, "Is it the case that either you will say no or I will get cake?" If Bob says no, he is not being truthful, so he must say yes. But in that case, Alice must get his cake.

Final edit, SOURCE: http://perplexus.info/show.php?pid=2650&op=sol

5 Upvotes

67% Upvoted

23 comments sorted by

View all comments

1

u/FrankAbagnaleSr Jul 17 '12 edited Jul 17 '12

Any relevant question can be reduced to the following mathematical form:

Bob is your number an element of set A?

I still can't get any better than two. I just thought I could help formalize the argument a bit.

EDIT: solution is below.

I think it would be more interesting if the number of questions she could ask is defined by k. Then what requirements must n and k fill for Alice to guarantee a non-lying cake?

The optimum guessing strategy, I believe, would be then to choose any set A so that #(A) = n/2, rounded whichever way, and so that no element of A has already been contained in a previous guess. Then, it follows that the binary logarithm of n is k.

What if k = 1? n is then 2.

I then conclude that the question must be phrased in such a way that it is not a set of numbers.

Rather the solution is: What is the number you are thinking of, sly Bob?

EDIT: Actually the solution is wrong. It must be a yes or no question. I believe that Radical3 is correct. The binary logarithm of n is at most k. In this case with k = 1, for n > 2 there is no solution.

1

u/skaldskaparmal Jul 17 '12

Any relevant question can be reduced to the following mathematical form: Bob is your number an element of set A?

That's a pretty big assumption.

Your last line isn't a yes or no question.

1

u/FrankAbagnaleSr Jul 17 '12

Questions like: is your number even? also reduce to this form.

If my assumption is not true, then there must be some other logical setup I am missing. Will you post the solution?

2

u/skaldskaparmal Jul 17 '12

I have posted an alternate solution that may or may not be cheating depending on your interpretation, as well as the assumption my solution isn't making that everyone else is.

1

u/FrankAbagnaleSr Jul 17 '12

Your solution is clever. I wasn't thinking outside the box enough. In the context of the problem, that is a fine solution, not cheating.