“I don't know the numbers”: a math puzzle

That was a fun puzzle. I have another one that is math puzzle:<p>&gt; You are given two eggs, and access to a 100-storey tower. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.<p>&gt; If an egg breaks when dropped from a floor, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.<p>&gt; The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution? (And what is the worst case for the number of drops it will take?)<p>I wrote up a solution for this (along with a generalized analytical solution) on my blog: <a href="https:&#x2F;&#x2F;blog.kdheepak.com&#x2F;the-egg-tower-puzzle" rel="nofollow">https:&#x2F;&#x2F;blog.kdheepak.com&#x2F;the-egg-tower-puzzle</a>

Did I miss it, or does the article not actually explain <i>why</i> we know that at least one pair can be eliminated every round? It seems plausible that the process could get &quot;stuck&quot; in a place where Peter and Sandy both don&#x27;t learn anything new from discovering the other doesn&#x27;t know the answer yet.<p>(The puzzle being solvable means that they can&#x27;t actually get stuck, but that feels like outside information...)

A similar (simpler) well known puzzle<p>&gt; A census taker approaches a woman leaning on her gate and asks about her children. She says, &quot;I have three children and the product of their ages is seventy–two. The sum of their ages is the number on this gate.&quot; The census taker does some calculation and claims not to have enough information. The woman enters her house, but before slamming the door tells the census taker, &quot;I have to see to my eldest child who is in bed with measles.&quot; The census taker departs, satisfied.<p><a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Ages_of_Three_Children_puzzle?wprov=sfla1" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Ages_of_Three_Children_puzzle?...</a>

In case anyone else is confused like I was, the article is wrong about Sandy&#x27;s first round. The article claims she can eliminate (1, 4) on the basis that it&#x27;s the only pair that adds up to 5, but the author forgot about (2, 3), which was not eliminated by Peter&#x27;s first round because it has the same product as (1, 6).<p>The algorithm itself is correct, and the answer it arrives at is correct.

My favorite version of this is a real mind fuck.<p><a href="http:&#x2F;&#x2F;jdh.hamkins.org&#x2F;cheryls-rational-gifts&#x2F;" rel="nofollow">http:&#x2F;&#x2F;jdh.hamkins.org&#x2F;cheryls-rational-gifts&#x2F;</a><p>Two people are told rational numbers of a particular form. They want to know whose number is larger:<p>&gt; Albert I don’t know.<p>&gt; Bernard Neither do I.<p>&gt; Albert Indeed, I still do not know.<p>&gt; Bernard And still neither do I.<p>&gt; Cheryl Well, it is no use to continue that way! I can tell you that no matter how long you continue that back-and-forth, you shall not come to know who has the larger number.<p>&gt; Albert What interesting new information! But alas, I still do not know whose number is larger.<p>They keep saying “No matter how much we do this, we still won’t know” and eventually they know. It’s great and I recommend reading it.

This problem is a variation of this one: <a href="https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Sum_and_Product_Puzzle" rel="nofollow">https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Sum_and_Product_Puzzle</a>, sometimes called “The Impossible Puzzle”

After the elimination of candidates due to Peter&#x27;s first comment, the entry in the product map with value 7920 should also have the candidate (80,99). The whole point of this step is that there should be no single-candidate entries left in product.

Yesterday:<p><a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=31269698" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=31269698</a>

This isn&#x27;t quite right. This does find the solution when the problem is well-formed, but it doesn&#x27;t prove that the solution is valid:<p><pre><code> if round == 15: for product in products: if len(products[product]) == 1: print(&#x27;Peter: I do know the numbers&#x27;) print(products[product][0]) return </code></pre> This should not return - it should continue iterating. If the problem (and the code) is correct, then it <i>should</i> only find one answer - but unless you exhaustively search and find exactly one answer you don&#x27;t know that it&#x27;s correct.<p>Incidentally, I was also a bit surprised by<p><pre><code> candidate_pairs = set() for i in range(1, N): for j in range(1, N): if (i, j) not in candidate_pairs and (j, i) not in candidate_pairs: candidate_pairs.add((i, j)) </code></pre> That first (i, j) check can never return false and should be omitted, right?

This puzzle also exists in a transfinite version, where the two players converge on the correct solution but require longer than infinity for the process:<p><a href="http:&#x2F;&#x2F;jdh.hamkins.org&#x2F;cheryls-rational-gifts&#x2F;" rel="nofollow">http:&#x2F;&#x2F;jdh.hamkins.org&#x2F;cheryls-rational-gifts&#x2F;</a>

I understand it’s a puzzle and it requires some suspension of disbelief, but I think Peter is wrong. He doesn’t <i>know</i> the numbers after 14 tries. He is assuming that Sandy has figured out the trick and is able to correctly keep track of 9801 + 198 = 9999 lists of number pairs in her head. As far as I can tell by how the puzzle is phrased, that’s a totally unreasonable assumption. It’s more likely that she says “I don’t know” because she has no idea how to approach the problem, and the fact that that is even possible means that Peter is not really getting any information from her at all.

An alternate solution guaranteed to work in every case and bounded to a maximum of 14 steps (for each side):<p>both players can just encode the number they know in binary and say “I don’t know” for a zero and “I know” for a 1.

Bonus meta-puzzle: the puzzle as stated is actually unsolvable. Both Sandy and Peter have to know something that the puzzle implies but does not actually stipulate that they know. What is it?

My SQL Solution (SQL Server)<p><pre><code> -- Create Table #x(v) from 1..99 WITH x AS (SELECT n FROM (VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) v(n)) SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) AS v INTO #x FROM x ones, x tens ORDER BY 1 ; DELETE FROM #x WHERE v &gt; 99 ; -- Create Candidate #c(x, y, s, p) with pair (x,y) (x &lt;= y) and sum `s` and product `p` SELECT x.v AS x, y.v AS y, x.v + y.v AS s, x.v \* y.v AS p INTO #c FROM #x x, #x y WHERE x.v &lt;= y.v ; -- Peter: I don’t know the numbers. DELETE FROM #c WHERE p IN (SELECT p FROM (SELECT p, COUNT(*) AS n FROM #c GROUP BY p) AS d WHERE n &lt; 2) -- Sandy: I don’t know the numbers. DELETE FROM #c WHERE s IN (SELECT s FROM (SELECT s, COUNT(*) AS n FROM #c GROUP BY s) AS d WHERE n &lt; 2) -- Peter: I don’t know the numbers. DELETE FROM #c WHERE p IN (SELECT p FROM (SELECT p, COUNT(*) AS n FROM #c GROUP BY p) AS d WHERE n &lt; 2) -- Sandy: I don’t know the numbers. DELETE FROM #c WHERE s IN (SELECT s FROM (SELECT s, COUNT(*) AS n FROM #c GROUP BY s) AS d WHERE n &lt; 2) -- Peter: I don’t know the numbers. DELETE FROM #c WHERE p IN (SELECT p FROM (SELECT p, COUNT(*) AS n FROM #c GROUP BY p) AS d WHERE n &lt; 2) -- Sandy: I don’t know the numbers. DELETE FROM #c WHERE s IN (SELECT s FROM (SELECT s, COUNT(*) AS n FROM #c GROUP BY s) AS d WHERE n &lt; 2) -- Peter: I don’t know the numbers. DELETE FROM #c WHERE p IN (SELECT p FROM (SELECT p, COUNT(*) AS n FROM #c GROUP BY p) AS d WHERE n &lt; 2) -- Sandy: I don’t know the numbers. DELETE FROM #c WHERE s IN (SELECT s FROM (SELECT s, COUNT(*) AS n FROM #c GROUP BY s) AS d WHERE n &lt; 2) -- Peter: I don’t know the numbers. DELETE FROM #c WHERE p IN (SELECT p FROM (SELECT p, COUNT(*) AS n FROM #c GROUP BY p) AS d WHERE n &lt; 2) -- Sandy: I don’t know the numbers. DELETE FROM #c WHERE s IN (SELECT s FROM (SELECT s, COUNT(*) AS n FROM #c GROUP BY s) AS d WHERE n &lt; 2) -- Peter: I don’t know the numbers. DELETE FROM #c WHERE p IN (SELECT p FROM (SELECT p, COUNT(*) AS n FROM #c GROUP BY p) AS d WHERE n &lt; 2) -- Sandy: I don’t know the numbers. DELETE FROM #c WHERE s IN (SELECT s FROM (SELECT s, COUNT(*) AS n FROM #c GROUP BY s) AS d WHERE n &lt; 2) -- Peter: I don’t know the numbers. DELETE FROM #c WHERE p IN (SELECT p FROM (SELECT p, COUNT(*) AS n FROM #c GROUP BY p) AS d WHERE n &lt; 2) -- Sandy: I don’t know the numbers. DELETE FROM #c WHERE s IN (SELECT s FROM (SELECT s, COUNT(*) AS n FROM #c GROUP BY s) AS d WHERE n &lt; 2) -- Peter: I do know the numbers. SELECT * FROM #c WHERE p IN (SELECT p FROM (SELECT p, COUNT(*) AS n FROM #c GROUP BY p) AS d WHERE n &lt; 2) &#x2F;* x y s p 77 84 161 6468 *&#x2F;</code></pre>

I like puzzles like this, where it&#x27;s not just &quot;what does each person know?&quot; but also &quot;when did they know it?&quot;<p>Another similar puzzle, with more logic and fewer numbers, is this one which was nicely written up on xkcd: <a href="https:&#x2F;&#x2F;xkcd.com&#x2F;blue_eyes.html" rel="nofollow">https:&#x2F;&#x2F;xkcd.com&#x2F;blue_eyes.html</a>

Is there an OEIS sequence for the N&#x27;s for which this game terminates?

Their code was horrific. My algorithm:<p><pre><code> import itertools import collections candidates = [s for s in itertools.product(range(100), range(100)) if s[0]&lt;=s[1]] def solutions_filter(sols, agg, flip=False): aggregates = [agg(s) for s in sols] d = collections.defaultdict(lambda:0) for s in aggregates: d[s] = d[s]+1 if not flip: return [s for s in sols if d[agg(s)] != 1] else: return [s for s in sols if d[agg(s)] == 1] ns = candidates for i in range(7): ns = solutions_filter(ns, lambda x:x[0]*x[1]) ns = solutions_filter(ns, lambda x:x[0]+x[1]) print(solutions_filter(ns, lambda x:x[0]*x[1], flip=True)) </code></pre> (Usually, next step is variable names, comments, etc.)