That was a fun puzzle. I have another one that is math puzzle:
> 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.
> 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.
> 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?)
> 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. (emphasis added)
The egg doesn't break when dropped out of the window (i.e., instantaneously). It potentially breaks when it hits the floor after a time delay t. So, the answer is 100 and 0 trials.
I was asked this one in a google phone interview in ~2009. I remember deriving that intervals of 10 floors were optimal in the two-egg 100-story case using some simple calculus and getting that far took me most of the hour. Your solution is super nice, but I hope you don't ask candidates to recreate it :P
That's not optimal though, like the blog says. When doing the first egg, as you get up near the top you've already used up many drops, so the gaps need to get correspondingly smaller.
Did I miss it, or does the article not actually explain why we know that at least one pair can be eliminated every round? It seems plausible that the process could get "stuck" in a place where Peter and Sandy both don't learn anything new from discovering the other doesn't know the answer yet.
(The puzzle being solvable means that they can't actually get stuck, but that feels like outside information...)
You’re totally right: there’s no guarantee that the candidate list continues to shrink, and there’s no guarantee that it won’t get stuck. For this problem, we are able to leverage the fact that it ends after 15 rounds, so the problem is less “run it until it finds a solution” and more “find the solution after exactly 15 rounds”.
In fact, if you let it run past 15 rounds (for N=100, at least), and check the number of disqualified candidates between rounds, you’ll find that it does get stuck in after 15 rounds as the candidate list doesn’t change. The flip side of this is that there are also solutions before 15 rounds, too, but with the problem’s original statement, we’re looking at exactly 15.
Yup, without a critical assumption - each "I don't know eliminates a potential solution" - it's not solvable because there is no new information when someone says "I don't know the answer"
The only critical assumptions are that they are aware of the details of what both of them have been given and that if they could have known the answer they would say so (i.e. that they are being perfectly logical and not making a mistake). The fact that this eliminates potential solutions is a consequence of that and the problem as set out. The whole puzzle hinges the fact that one person not knowing the answer from the part they are given (and the knowledge that the other person does not know after each step) constrains (i.e. gives information on) the answer. (but it is correct that as stated you could not derive all pairs of numbers this way: the puzzle gives you a sequence for which the pair is knowable)
For N=100, though, they could know beforehand that potential solutions are eliminated at least the first 15 times someone says "I don't know". For any N, it should be possible to work out the longest such a game could go on (until one of them says, "I don't know, and I don't know any more from your last statement").
> A census taker approaches a woman leaning on her gate and asks about her children. She says, "I have three children and the product of their ages is seventy–two. The sum of their ages is the number on this gate." 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, "I have to see to my eldest child who is in bed with measles." The census taker departs, satisfied.
There’s actually many variation of those Peter and Simon/Sally problems. I’ve seen with two, three and up to four numbers. Often, one of them claim they (finally) know the answer after a certain number of interactions and _then_ the other claiming that they either can, or can’t figure it out. “I knew that” or “Oh, really?” respond the one who knows, and finally: “Then I know what those are.”
One can include certain clues, like “Those are three beautiful numbers” to indicate those are different, or “You would like them” if either of them is presented as a fan of prime numbers, perfect numbers or something like that. With children’s age, they might be in school, boarding school, went to university, or have children, to indicate they are below or above 6, 14, 18, etc.
Hmm. I don't like how "I have an eldest child" is used to imply "therefore my second-oldest child can't have the same age [when rounded down to a year number]". As the article says: "although one could be a few minutes or around 9 to 12 months older". I could imagine parents objecting to the claim that one twin is older than the other (or even saying they didn't keep track of which was born first); but a child having been born 10 months before another is something I'd expect parents to remember, and I don't think it would be weird in that case to call the older one the "eldest".
In case anyone else is confused like I was, the article is wrong about Sandy's first round. The article claims she can eliminate (1, 4) on the basis that it's the only pair that adds up to 5, but the author forgot about (2, 3), which was not eliminated by Peter's first round because it has the same product as (1, 6).
The algorithm itself is correct, and the answer it arrives at is correct.
Oh good catch, I even crossed out the right ones in the above code block. Edited to be (2, 2), which is a better example (since (1, 3) was already cleared out). Thanks!
Two people are told rational numbers of a particular form. They want to know whose number is larger:
> Albert I don’t know.
> Bernard Neither do I.
> Albert Indeed, I still do not know.
> Bernard And still neither do I.
> 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.
> Albert What interesting new information! But alas, I still do not know whose number is larger.
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.
I prefer this less sterile framing of it. It was the most fun that I ever had with a puzzle, so to anyone scrolling around on this page, I would recommend not jumping straight to the solution :)
After the elimination of candidates due to Peter'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.
Readit News
> 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.
> 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.
> 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?)
I wrote up a solution for this (along with a generalized analytical solution) on my blog: https://blog.kdheepak.com/the-egg-tower-puzzle
The egg doesn't break when dropped out of the window (i.e., instantaneously). It potentially breaks when it hits the floor after a time delay t. So, the answer is 100 and 0 trials.
ps: This is a joke. Don't take it too seriously.
Deleted Comment
However, it was short lived since now I know it takes "14 drops" maximum, but not the solution - "which floors should I use the 14 drops on though?"
Maybe I'd be intrigued enough to try and follow the math if that was added in :)
Deleted Comment
Given:
(1) the ordered sequence of whole numbers (1, 2, ... , 99, 100) and
(2) an unknown value N that is a member of this sequence,
(3) the following tests (a candidate is a guess at the value of N), and two separate threads to run tests:
(A) if candidate <= N : true & thread continues (another candidate can be checked with that thread)
(B) candidate > N : false & thread terminates (no more candidates can be checked with that thread)
Determine the best strategy for finding N (minimize the number of tests while leaving at least one thread alive)
Determine the worst case for the number of tests needed to find N using this optimal strategy.
Deleted Comment
Dead Comment
(The puzzle being solvable means that they can't actually get stuck, but that feels like outside information...)
In fact, if you let it run past 15 rounds (for N=100, at least), and check the number of disqualified candidates between rounds, you’ll find that it does get stuck in after 15 rounds as the candidate list doesn’t change. The flip side of this is that there are also solutions before 15 rounds, too, but with the problem’s original statement, we’re looking at exactly 15.
> A census taker approaches a woman leaning on her gate and asks about her children. She says, "I have three children and the product of their ages is seventy–two. The sum of their ages is the number on this gate." 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, "I have to see to my eldest child who is in bed with measles." The census taker departs, satisfied.
https://en.wikipedia.org/wiki/Ages_of_Three_Children_puzzle?...
One can include certain clues, like “Those are three beautiful numbers” to indicate those are different, or “You would like them” if either of them is presented as a fan of prime numbers, perfect numbers or something like that. With children’s age, they might be in school, boarding school, went to university, or have children, to indicate they are below or above 6, 14, 18, etc.
The algorithm itself is correct, and the answer it arrives at is correct.
http://jdh.hamkins.org/cheryls-rational-gifts/
Two people are told rational numbers of a particular form. They want to know whose number is larger:
> Albert I don’t know.
> Bernard Neither do I.
> Albert Indeed, I still do not know.
> Bernard And still neither do I.
> 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.
> Albert What interesting new information! But alas, I still do not know whose number is larger.
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.
https://explainextended.com/2016/12/31/happy-new-year-8/
I prefer this less sterile framing of it. It was the most fun that I ever had with a puzzle, so to anyone scrolling around on this page, I would recommend not jumping straight to the solution :)
https://news.ycombinator.com/item?id=31269698