13 ms·
“I don't know the numbers”: a math puzzle
- vintermann 4y agoIs there an OEIS sequence for the N's for which this game terminates?
- kej 4y agoI like puzzles like this, where it's not just "what does each person know?" but also "when did they know it?" Another similar puzzle, with more logic and fewer numbers, is this one which was nicely written up on xkcd: https://xkcd.com/blue_eyes.html https://xkcd.com/blue_eyes.html
- xdfgh1112 4y agoBilled as "the hardest logic puzzle in the world". Now I feel less dumb for not solving it myself when it appeared in Cracking the Code Interview.
- lmm 4y agoI guess that's the root for https://slatestarcodex.com/2015/10/15/it-was-you-who-made-my-blue-eyes-blue/ https://slatestarcodex.com/2015/10/15/it-was-you-who-made-my... .
- thaumasiotes 4y ago> this one which was nicely written up on xkcd But there's not a writeup there. That's just a statement of the problem. This is not the hardest logic puzzle in the world, though stating the answer can be tricky. If it takes one day for a solitary blue-eyed person to realize he's the one with blue eyes and leave, then it takes 100 days for a group of 100 blue-eyed people to realize they have blue eyes and leave. The blue eyes puzzle relies on everyone receiving input from the same synchronized digital clock ("Every night at midnight, a ferry stops at the island"), which is unusual for a logic puzzle. The puzzle here is similarly discretized, but it's more a pure question of sequence - each line of dialog happens after the previous line, and that's all that matters.
- xdfgh1112 4y agohttps://xkcd.com/solution.html https://xkcd.com/solution.html
- deleted 4y ago[deleted]
- conradludgate 4y agoThat was a good puzzle. I won't put the answer here for spoilers, but there is a neat solution. If you get stuck, try imagine a different number of blue/brown eyes on the island and what that might change
- lisper 4y agoBonus 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?
- onionisafruit 4y agoIs it that the other person was told either the sum or the product? Or that the number they were told is the sum or product? edit: After rereading the problem they weren’t told the parameters of the problem or even that they are participating in a puzzle.
- AveburySutton 4y agoprocess of elimination. as soon as peter starts, all primes are off the table. Given that, some number pairs which sum to the same number as just one other number pair where the second number pair has at least one prime are off the table. And so on and so forth. My instinct was to program the solution. Bet there are people who could do it in their heads.
- caf 4y agoIt's only the primes above 50 that are immediately eliminated by the fact that Peter does not know the answer right away. The primes below that can be present in products that have multiple possible answers: eg. we can't eliminate 47 right off the bat because Peter could have been told a product like 3290.
- corndoge 4y ago>as soon as peter starts, all primes are off the table How do you figure? If Peter is given 97 (a prime), how is he supposed to know that a) he's been given a product (puzzle doesn't say he was told it's a product) and b) if he knows he's been given a product how is he supposed to know 97 is prime? He wasn't told that in the puzzle either.
- nicoburns 4y agoThat the other person is following the same system as them to decide whether they "know the numbers". It would be super easy for one of them to say they don't know for some other reason, in which the others' reasoning would be false.
- pvg 4y agoYesterday: https://news.ycombinator.com/item?id=31269698 https://news.ycombinator.com/item?id=31269698
- hackernewds 4y agoThe explanation here is much more clearer. but it doesn't seem humanly possible to play this game without a computer? what am I missing
- kdheepak 4y agoThat 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?) I wrote up a solution for this (along with a generalized analytical solution) on my blog: https://blog.kdheepak.com/the-egg-tower-puzzle https://blog.kdheepak.com/the-egg-tower-puzzle
- moron4hire 4y ago
- danachow 4y agoLol. Someone needs some fresh air.
- jammaloo 4y agoOn August 22, 1994, David Donoghue threw an egg out of a helicopter onto a golf course in the UK, from a height of 213 meters (700 feet). He now has the record for the longest egg drop without breaking in the world (all without an outside structure for added protection!). https://www.scienceworld.ca/resource/egg-drop/ https://www.scienceworld.ca/resource/egg-drop/ Eggs are evolutionarily designed to survive falling out of nests and perches. You assume that the egg is dropping onto a hard surface, but there is no mention of that in the puzzle. That's even assuming it's a chicken egg, but other eggs may be more resilient. It may not even be a biological egg, but an artifically designed egg, that is resilient to drops onto harder surfaces.
- the_af 4y ago
- blagie 4y agoTheir code was horrific. My algorithm: import itertools import collections candidates = [s for s in itertools.product(range(100), range(100)) if s[0]<=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)) (Usually, next step is variable names, comments, etc.)
- jcheng 4y agoMy logic was similar, in R: library(dplyr) combos <- expand.grid(x = 1:99, y = 1:99) |> filter(x <= y) |> # Remove dupes mutate(sum = x + y, prod = x * y) find_singletons <- function(col = c("sum", "prod")) { singletons <- combos %>% group_by(!!sym(col)) %>% tally() %>% filter(n == 1) which(combos[[col]] %in% singletons[[col]]) } for (i in 1:7) { # Peter: I don't know the numbers. combos <- combos[-find_singletons("prod"),] # Sandy: I don't know the numbers. combos <- combos[-find_singletons("sum"),] } # Peter: I know the numbers. combos[find_singletons("prod"),]
- blagie 4y agoTo people who either know: - both R and Python; or - neither R nor Python: Which of the solutions do you find more readable? (I have my own opinion, but I'm biased)
- otras 4y agoHorrific is a new one! Thanks for posting your solution :)
- blagie 4y agoIt's worth looking at the other solutions in-thread. Key points: - Use of higher-order operations, like filters and aggregations, to avoid loops. - Passing around functions (the * and + side are the same, except for one operation) to avoid repeated code This results in: - Less code. Defects per KLOC tends to be pretty constant, so shorter / higher-level programs are typically less buggy. - In particular, less repeated code. Cut-and-paste introduces a whole slew of potential defects. - Less dependence on order-of-operations, which eliminates whole classes of errors, from off-by-ones to data structures in intermediate inconsistent states. The relevant book here is still SICP.
- Arainach 4y agoThis isn't quite right. This does find the solution when the problem is well-formed, but it doesn't prove that the solution is valid: if round == 15: for product in products: if len(products[product]) == 1: print('Peter: I do know the numbers') print(products[product][0]) return This should not return - it should continue iterating. If the problem (and the code) is correct, then it should only find one answer - but unless you exhaustively search and find exactly one answer you don't know that it's correct. Incidentally, I was also a bit surprised by 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)) That first (i, j) check can never return false and should be omitted, right?
- Jtsummers 4y agoRegarding the second snippet, yeah, that (i,j) test will always be true. And if the inner loop is changed from `range(1, N)` to `range(i, N`) then it will be totally unnecessary anyways to have the conditional. With that change every pair would be generated exactly once.
- otras 4y agoThat's a good point! The `15` check relies on 1) knowing it will stop after 15 rounds as written in the problem (though I explore that later) and 2) assuming that there must be a single answer after 15 rounds (which I also explore later). And that's true, the `(i, j)` check is spurious - I blame it on it being throwaway blog post code :)
- Someone 4y agoThe ‘normal’ way to write something like that (I hope I got the range ends right) is for i in range(1, N): for j in range(1, j + 1): candidate_pairs.add((i, j)) Also, conceptually, you don’t have tuples, but multisets. If you were to use those, you wouldn’t need that if at all. Multiset isn’t built-in to python, so you’d need to use an external package. Alternatively, write a class for storing pairs of ints i, j that enforces i ≤ j.
- icambron 4y agoThis problem is a variation of this one: https://en.m.wikipedia.org/wiki/Sum_and_Product_Puzzle https://en.m.wikipedia.org/wiki/Sum_and_Product_Puzzle, sometimes called “The Impossible Puzzle”
- gurkendoktor 4y agoOoohh, I didn't know this name for it, thanks. I somehow came across it as The Sultan's Riddle on the internet: https://explainextended.com/2016/12/31/happy-new-year-8/ 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 :)
- Arnavion 4y agoIn 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.
- otras 4y agoOh 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!
- alasdair_ 4y agoAn alternate solution guaranteed to work in every case and bounded to a maximum of 14 steps (for each side): 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.
- jasamer 4y agoWhy not just go for: Peter: "My number is [X]." Sandy: I know the answer!
- seoaeu 4y agoDid 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...)
- otras 4y agoYou’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.
- refurb 4y agoYup, 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"
- rcxdude 4y agoThe 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)
- isaacg 4y agoAfter 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.
- otras 4y agoOh yes of course, I must have missed copying that over. Thanks!
- kthejoker2 4y agoA similar (simpler) well known puzzle > 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?wprov=sfla1 https://en.wikipedia.org/wiki/Ages_of_Three_Children_puzzle?...
- waterhouse 4y agoHmm. 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".
- bertil 4y agoThere’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.
- rexpan 4y agoMy SQL Solution (SQL Server) -- 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 > 99 ; -- Create Candidate #c(x, y, s, p) with pair (x,y) (x <= 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 <= 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 < 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 < 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 < 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 < 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 < 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 < 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 < 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 < 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 < 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 < 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 < 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 < 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 < 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 < 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 < 2) /* x y s p 77 84 161 6468 */
- 4y ago
- tobr 4y agoI understand it’s a puzzle and it requires some suspension of disbelief, but I think Peter is wrong. He doesn’t know 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.
- hvdijk 4y agoWe are given that he says he does know and have no reason to doubt it. It is possible that Peter and Sandy know one another and already know that they are perfect at figuring out maths/logic puzzles.
- tobr 4y agoI would phrase the puzzle differently. They both need to say they know, otherwise we have no reason to believe Sandy has figured it out. And they both need to be right, which we also have no reason to believe at the moment.
- hvdijk 4y agoThe puzzle doesn't state whether Sandy has figured it out because that information is not necessary to figure out the solution. We can infer that she has (under that implicit assumption that she is a perfect logician) by the fact that we know less than she does and still have enough information, though. As for that last part: we also don't truly know that Peter isn't lying just to mess with the puzzle, I guess. That is another implicit assumption.
- bertil 4y agoIt’s generally presented as both of them being experienced mathematicians who have been doing it for a while, that they have access to a notebook and a calculator and recently (I’ve seen those since the 1980s) to a computer.
- 6gvONxR4sf7o 4y agoMy favorite version of this is a real mind fuck. http://jdh.hamkins.org/cheryls-rational-gifts/ 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.
- IngoBlechschmid 4y agoThis puzzle also exists in a transfinite version, where the two players converge on the correct solution but require longer than infinity for the process: http://jdh.hamkins.org/cheryls-rational-gifts/ http://jdh.hamkins.org/cheryls-rational-gifts/