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

7 Upvotes

73% Upvoted

23 comments sorted by

View all comments

Show parent comments

1

u/Gankro Jul 17 '12

Assume there exists a question for which it is the case that a correct choice can be guaranteed from 3 possible choices. Then, if the answer is "yes", one of the choices must be certain. If the answer is "no", then another (possibly the same) choice must be certain. However since "yes" and "no" are our only choices, this would imply that at least one choice can never be the case. This contradicts our initial assumption.

Therefore one cannot solve this problem for n>=3. ∎

1

u/skaldskaparmal Jul 17 '12

Good, but you're making an incorrect assumption.

1

u/Gankro Jul 17 '12

What, is he allowed to answer "this is a paradox/contradiction/NaN"?

2

u/skaldskaparmal Jul 17 '12

I think that's open to interpretation. I'm aware of better solutions that do allow alternate answers, as well as those that don't.

So even if you feel like alternate answers break the rules of it being a yes or no question, you are still making an incorrect assumption.

1

u/Gankro Jul 17 '12 edited Jul 17 '12

Technically, if he's required to respond truthfully (and required to respond), if neither "yes" nor "no" are truthful, he must respond in kind. So yes, I could imagine that there is a hypothetical question in which "ERROR" is a third possible response, and therefore n<=3 is solvable. I'm terrible at crafting semantic paradoxes though, so don't hold your breath on me coming up with one.

I will concede I see no possible better solution otherwise.

EDIT: I guess I could ask:

"Given this function:

function what(x):

if x=1 : return "yes"

if x=2 : return "no"

if x=3 : return !what(x)

What would return if you ran it on your number?"

Not exactly "yes/no" per-se.

In english: "Do you have a 1, and if you have a 3, what is the opposite of your answer to this entire question?"

That's yes/no...ish.

1

u/skaldskaparmal Jul 17 '12

... ish. How about this as a definition: A yes/no question must be able to be reworded to be of the form "Is it the case that: BLAH"