Tuesday’s puzzle was hard, though our commenter Bennett Haselton nailed it. In case Bennett has nothing else to work on this weekend, here’s a much harder version.
Once again, Alice, Betty and Carol each has a postive integer stamped on her forehead. They know that two of the numbers add up to the third. This dialogue ensues:
Alice: I don’t know my number.
Betty: I don’t know my number.
Carol: I don’t know my number.
Alice: I still don’t know my number.
Betty: I still don’t know my number.
Carol: I still don’t know my number.
Alice: Now I know my number.
What are all the possible numbers that could be on Alice’s forehead?
Let’s divide up this effort so we can all get out for at least part of the weekend.
Once you get into the second round of “I don’t know”, the number of inequalities becomes unmanageable unless you do the problem mechanically. Here’s the motivation for the algorithm I used:
At each stage, you have a list of inequalities (initially empty) that are known to everyone at the table. (Each inequality takes the form of a ratio between one variable and another which is disallowed.)
Each lady knows she is either the sum or positive difference of the other two. So when she says “I don’t know”, that means she is saying there is no relationship between the other two numbers which, combined with any of the known inequalities, could eliminate her own number being either the sum or positive difference of the other two.
For example, on B’s first turn she knows only that B!=C. When she says “I don’t know”, that means B!=C was not enough information to eliminate the possibility that B=A-C (for example). Formally, we have:
NOT: (B!=C -> B!=A-C)
i.e., NOT: (B=A-C -> B=C) (taking contrapositive of the expression in parentheses)
i.e., NOT: (A=2C)
i.e., A!=2C
So assuming it’s X’s turn and the other ladies are Y and Z. You take each already-known inequality involving X, and rewrite it with X by itself on the left-hand side. Then replace that left-hand side, in turn, with:
Y+Z
Y-Z
Z-Y
which gives you three new known inequalities (some of which you can discard, if they imply a zero variable or a negative ratio).
I wrote a Perl script (possibly not the best choice of language) to crunch the numbers after going around the table twice, and when Alice’s third turn comes up, she knows (in fact, the whole table knows) she is not equal to:
1/4B, 2/7B, 1/3B, 2/5B, 1/2B, 4/7B, 3/5B, 8/13B, 5/8B, 2/3B, 3/4B, 4/5B, B, 4/3B, 3/2B, 2B, 5/2B, 8/3B, 3B, 4B
or:
1/3C, 2/5C, 1/2C, 2/3C, C, 4/3C, 3/2C, 8/5C, 5/3C, 2C, 3C, 4C
B meanwhile knows (and again, the whole table also knows) that she is not equal to 1/3C, 1/2C, 3/5C, 2/3C, C, 2C or 3C.
So either the sum or positive difference of B and C must be equal to one of the things that A can’t be equal to, so when A can eliminate that, she knows she’s the other one.
Not sure if there’s a simple route to take from there. You could solve it, tediously, by going through all possibilities and finding the set of possible numbers to satisfy each one (while making sure you weren’t contradicting any of the B-to-C inequalities), but maybe there’s an elegant shortcut. Need to sleep on it (i.e. let someone else make progress while I’m sleeping).
This puzzle’s demonic.
So maybe one of the numbers on the forehead is 666?
Using a pencil and paper and pretty much the same brute force logic as Bennett I get:
5, 6, 7, 9, 10, 11, 12, 13, 14, 16, 18, 21, 30 and any integer multiple of those.
This of course means that nobody.really is partially correct: Alice may have 666 tattooed on her forehead, in which case Betty likely has 185 and Carol 481.
Given that the numbers are produced by a simple recursive logic operation then I feel that there must be a simple(ish) formula to determine them but I can’t see it yet.
Lastly: Bennett did you take into account that something Alice (and the whole table) knew at her turn cannot be the logical basis to her answer or she would have called it at that point?
I wrote a program to figure this out. It got Monday’s problem right. On this one it generates 25 (three variants), 45, 105, 175, and 225. This is testing numbers up to 500. It’s hard to model this right, so it’s certainly possible that these are wrong! The search tree is too large to manually inspect.
Conjecture: All possible games follow in sequence from the 3 degenerate cases {Alice Betty Carol} = {2,1,1} {1,2,1} and {1,1,2}
Each step of this sequence is a new game. The steps are in order of what turn the first number is called out on, ie 3A means Alice calls first in round 3.
——————————————
1A: {2,1,1} Degenerate case. Alice announces her number. Before she does so, Betty knows she’s either the sum {3} or the difference {1}. If Alice had skipped then Betty would know she wasn’t {1} and would therefore be {3}.
1B: {2,3,1} Alice skips, Betty uses the above logic and announces her number. Before she does so, Carol knows she’s either the sum {5} or the difference {1}. If Betty had skipped then Carol would know she wasn’t {1} and would therefore be {5}.
1C: {2,3,5} Betty skips, Carol uses the above logic and announces her number. Before she does so, Alice knows she’s either the sum {8} or the difference {2}. If Carol had skipped then Alice would know she wasn’t {2} and would therefore be {8}.
2A: {8,3,5} Carol skips, Alice uses the above logic…
2B: {8,13,5} Alice skips twice, Betty uses the above logic…
2C: {8,13,21} Betty skips twice, Carol uses the above logic…
3A: {34,13,21} Carol skips twice, Alice uses the above logic…
——————————————
So the sequence easily follows from Fibonacci and a degenerate case as the initial condition. Here are the other sequences.
——————————————
1B: {1,2,1}
1C: {1,2,3}
2A: {5,2,3}
…
3A: {21,8,13}
——————————————
1C: {1,1,2}
…
3A: {13,5,8}
——————————————
I think these are the only possibilities. Also, games that are proportional to each other play out the same way (the Tuesday puzzle is up there if you didn’t catch it), so my final answer where ‘k’ is any positive integer is:
13k, 21k, and 34k
Hmmm… My post yesterday is incomplete. Here’s a game that terminates that wasn’t generated by my method. {1,3,2}. We can make a sequence that includes this game by starting with the third degenerate case.
—————————-
C1: {1,1,2} Alice and Betty skip, Carol announces her number. Before she does so, Betty knows she’s either the sum {3} or the difference {1}. If Carol had skipped and then Alice had skipped again then Betty would know she wasn’t {1} and would therefore be {3}.
B2: {1,3,2} Alice skips twice, Betty announces her number. Before she does so, Alice knows she’s either the sum {5} or the difference {1}…
//The left-right ascending Fibonacci pattern has been broken.
A3: {5,3,2} Group skips twice, Alice uses the above logic and announces her number…
—————————-
5*k appears to be the minimum solution. Likewise, 34*k from my previous comment appears to be the maximum solution.
The full power of my method seems to be this: We can use the degenerate cases to create games that are won on turns 1A, 1B, or 1C. From there we switch the number of one of the other players so they are now the sum rather than the difference, and in this new game that player will win on their next turn. If my method works then we can do this forever and make a complete list of games.
1A: {2,1,1}
1B: {1,2,1} {2,3,1}
1C: {1,1,2} {2,1,3} {1,2,3} {2,3,5}
2A: {3,2,1} {4,3,1} {3,1,2} {4,1,3} {8,3,5}
2B: {1,3,2} {2,5,3} {1,4,3} {2,7,5} {3,4,1} {4,5,1} {3,5,2}
{4,7,3} {8,13,5}
2C: {3,2,5} {4,3,7} {3,1,4} {4,1,5} {8,3,11} {1,3,4} {2,5,7}
{1,4,5} {2,7,9} {3,4,7} {4,5,9} {3,5,8} {4,7,11} {8,13,21}
3A: {5,3,2} {8,5,3} {7,4,3} {12,7,5} {5,4,1} {6,5,1} {7,5,2}
{10,7,3} {18,13,5} {7,2,5} {10,3,7} {5,1,4} {6,1,5} {14,3,11}
{14,3,11} {7,3,4} {12,5,7} {9,4,5} {16,7,9} {11,4,7} {14,5,9}
{13,5,8} {18,7,11} {34,13,21}
So if Alice wins in the third round her number can only be (5,6,7,8,9,10,11,12,13,14,16,18,34)*k
My proposal (based on the algorithm I explained last time, although maybe not well) is:
She can have any number that has one of the following as a factor:
(5,6,7,8,9,10,11,1,14,15,16,18,21,34)
This list is a bit different than that of Chris above. I have (8,15,34) and Chris has (13,30)
The easiest of these differences to test is 8. In particular, my algorithm gives A = 8, B = 5 and C = 3.
So what happens in this situation? At the beginning, A knows she is either 8 or 2. So she just needs to wait until she can rule out one of those. The combination 2,5,3 is ruled out on turn 5, so A waits until her turn on turn 7 to answer. How is 2,5,3 ruled out on turn 5?
Well, if A was 2, B would have known she was a 5 on turn 5. How? because if A = 2, B would see a 2 and a 3 and know she was either 1 or 5. But the combination 2,1,3 was ruled out on turn 3…
Looks like I had a typo: the 1 in my list should be 12.
Also, I hadn’t compared my list to that of Martin carefully enough. It turns out martin is missing a few important sets in his list, starting with {5,2,3} from 2A, which led to the solution from the original puzzle.
Anyway, looking at his list did help me find an error with mine. So I now believe the list of factors to be:
5,6,7,8,9,10,11,12,14,16,18,21,34
Thanks for the catch! My first comment actually contained {5,2,3} but then I forgot it later. It should be next to 2A as a permutation of {1,2,3}. Every row after the third is supposed to contain as many games as there are in the previous 2 rows, so I should have noticed. Here’s my revised list.
1A: {2,1,1}
1B: {1,2,1} {2,3,1}
1C: {1,1,2} {2,1,3} {1,2,3} {2,3,5}
2A: {3,2,1} {4,3,1} {3,1,2} {4,1,3} {5,2,3} {8,3,5}
2B: {1,3,2} {2,5,3} {1,4,3} {2,7,5} {3,4,1} {4,5,1} {3,5,2}
{4,7,3} {5,8,3} {8,13,5}
2C: {3,2,5} {4,3,7} {3,1,4} {4,1,5} {5,2,7} {8,3,11} {1,3,4}
{2,5,7} {1,4,5} {2,7,9} {3,4,7} {4,5,9} {3,5,8} {4,7,11}
{5,8,13} {8,13,21}
3A: {5,3,2} {8,5,3} {7,4,3} {12,7,5} {5,4,1} {6,5,1} {7,5,2}
{10,7,3} {11,8,3} {18,13,5} {7,2,5} {10,3,7} {5,1,4} {6,1,5}
{9,2,7} {14,3,11} {7,3,4} {12,5,7} {9,4,5} {16,7,9}
{11,4,7} {14,5,9} {13,5,8} {18,7,11} {21,8,13} {34,13,21}
Mike, I notice you don’t include 13. Assuming we’re using the same method, A=13 comes from this progression. {1,1,2} >> {3,1,2} >> {3,5,2} >> {3,5,8} >> {13,5,8}
Here’s my final final answer.
{5,6,7,8,9,10,11,12,13,14,16,18,21,34}*k
@martin 2 in 5
1, 1, 2 is not a solution as 2 can solve it first round 0 being disallowed. This generalizes of course.
Ken B (10): That big list is actually of all games that are won in Alice’s first turn (row 1A), then Betty’s first turn (row 1B), then Carol’s first turn (row 1C), and the solutions to the puzzle are down next to Alice’s third turn (row 3A). All the simpler games up there just to show my work (sorry for being spammy!)
I’ll restate my method, using 1,1,2 as an example. This game is won by Carol in the first round by the double-rule. Now look from, say, Betty’s perspective;
Betty: I can either be 1 or 3, and if I’m 1 then
Carol will win on her first turn. Likewise, if I’m 3 then
Carol won’t be able to use the double-rule and won’t win.
Now we know that if we switch Betty’s number to create the game 1,3,2 then she’ll win on her second turn.
Steve’s puzzle asks for every game Alice wins on her third turn. I think the best way to do this is to generate all of the shorter games first, starting with what I called the “degenerate cases” {1,1,2} {1,2,1} and {2,1,1}.
Ken B (10): That big list is actually of all games that are won in Alice’s first turn (row 1A), then Betty’s first turn (row 1B), then Carol’s first turn (row 1C), and the solutions to the puzzle are down next to Alice’s third turn (row 3A). All the simpler games up there just to show my work (sorry for being spammy!)
I’ll restate my method, using 1,1,2 as an example. This game is won by Carol in the first round by the double-rule. Now look from, say, Betty’s perspective;
—Betty: I can either be 1 or 3, and if I’m 1 then
—Carol will win on her first turn. Likewise, if I’m 3 then
—Carol won’t be able to use the double-rule and won’t win.
Now we know that if we switch Betty’s number to create the game 1,3,2 then she’ll win on her second turn.
Steve’s puzzle asks for every game Alice wins on her third turn. I think the best way to do this is to generate all of the shorter games first, starting with what I called the “degenerate cases” {1,1,2} {1,2,1} and {2,1,1}.
I notice that the number of possible solutions after each round is 1,2,4,6,10,16,26,… Which is Fibinocci X 2 after the first number.
Al V. (13): Fibonacci shows up a lot in this game. In this case it’s because every solution for (n) turns is a permutation of a solution for (n-1) or (n-2) turns. But the simple cases {2,1,1} etc. pop up on their own and mess up the pattern at the beginning, making it a slightly skewed Fibonacci sequence.
Chris Surridge #3, also:
666 555 111
666 111 555
666 148 518
666 296 370
666 259 407
Which leads me to wonder, are there any combinations that are not solvable?