“I don't know the numbers”: a math puzzle | Hacker News Reader

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

alexanderell.is

176 pointsotras111 comments

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?)

I wrote up a solution for this (along with a generalized analytical solution) on my blog: https://blog.kdheepak.com/the-egg-tower-puzzle

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.

Maybe that's why I don't work at google :)

Wouldn't one normally just try to convert this to an unambiguous discrete problem, something like:

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.

I'm not too math-y, but this did capture my sense of wonder.

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 :)

First the 14th floor, then the (14 + 13 =) 27th floor, and so on.

> 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.

ps: This is a joke. Don't take it too seriously.

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").

I would assume it hinges on the fact that when one party says "I don't know the answer" then they are eliminating a possibility (which isn't intuitive at all with that answer).

I believe (I could be wrong here, I haven't rigorously checked this) that when the numbers are less than 100 and both parties know this, there will always be a possibility eliminated by a "I don't know" statement.

After the round in the posed problem, it reaches a stalemate.

If Peter had said "I don't know the numbers" at the end there, Sandy can exclude the possibility that the numbers were 77 and 84. However, at this point Peter already knows that Sandy still doesn't know the numbers: Even if the sum Sandy was told was 161, there are still five remaining live possibilities for that sum (62 + 99, 65 + 96, 70 + 91, 76 + 85 and 80 + 81), so Peter gains no new information from Sandy's next statement that Sandy does not know the numbers.

They did mention that you get stuck on certain N. That sounds like nice material for an OEIS sequence.

A 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?...

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".

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.

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!

My favorite version of this is a real mind fuck.

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.

This problem is a variation of this one: https://en.m.wikipedia.org/wiki/Sum_and_Product_Puzzle, sometimes called “The Impossible Puzzle”

Ooohh, 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/

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.

Oh yes of course, I must have missed copying that over. Thanks!

Yesterday:

https://news.ycombinator.com/item?id=31269698

The explanation here is much more clearer. but it doesn't seem humanly possible to play this game without a computer? what am I missing

This 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?

Regarding 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.

That'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 :)

The ‘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.

Python actually has built in support for multisets, you use a set of frozensets

>>> a = set( (frozenset((1,2)), frozenset((3,4)) ) )

>>> frozenset((2,1)) in a

True

That’s not a multiset, it’s a set containing tuples. A multiset (https://en.wikipedia.org/wiki/Multiset) allows you to add identical items multiple times.

You would use that to, for example, store the knowledge that 6 can be written as 3+3, by using a multiset {3,3} instead of a tuple (3,3)

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:

http://jdh.hamkins.org/cheryls-rational-gifts/

I 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.

We 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.

I 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.

The 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.

It’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.

An 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.

Why not just go for:

Peter: "My number is [X]." Sandy: I know the answer!

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?

Is 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.

process 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.

>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.

It'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.

That 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.

This is what I thought. Two unstated (but implied) parts of the puzzle are that they can’t tell each other the numbers outright, and that they can only share information in yes/no format. But since they have clearly already agreed on a system beforehand, they could have also encoded the digits in binary or something.

So each person could have been sharing one binary digit of their number with each round. Or they might have used a completely different encoding. We simply cannot know.

That the order of the numbers is unimportant? Otherwise every non-duplicate solution has a correlate solution, inverted. E.g. (3,2) implies (2,3) is also a solution.

I don’t think that’s necessary. The problem only says there are two numbers, not that the numbers have any order.

The number of steps it would take to solve the puzzle.

No, they discover that as they talk. It's not something they need to know; it's something you need to know.

That both are perfect logicians with an understanding of the system sans the information about the two numbers themselves?

since this is a fair assumption (that they will humanly miss a combination when true) the next inference is they have access to a perfect calculator

They both have to know what the other person knows (e.g the product or sum), and that the other person is a perfect logician.

The fact that it's unsolvable as stated is precisely why I hate this puzzle.

Each one of them:

1. is a person that solves logical puzzles if possible

2. knows that the other one + (insert point 1 here).

3. knows that the other one + (2)

4. knows that the other one + (3)

...

This is called Common Knowledge in game theory:

Common knowledge is a special kind of knowledge for a group of agents. There is common knowledge of p in a group of agents G when all the agents in G know p, they all know that they know p, they all know that they all know that they know p, and so on ad infinitum. It can be denoted as {\displaystyle C_{G}p}.

My 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
    */

It's not pretty, but it works!

I 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

Billed 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.

> 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.

https://xkcd.com/solution.html

That 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

I guess that's the root for https://slatestarcodex.com/2015/10/15/it-was-you-who-made-my... .

Is there an OEIS sequence for the N's for which this game terminates?

Their 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.)

My 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"),]

To 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)

Horrific is a new one! Thanks for posting your solution :)

It'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.

I am still trying to wrap my head around the problem. Here's my attempt at your implementation in Raku:

    sub solutions-filter(@sols, &agg, Bool:D :$flip = False) {
        my @aggregates = @sols.map({ agg($_) });
    
        my %d;
        %d{$_} += %d{$_} ?? %d{$_} !! 1 for @aggregates;
    
        return @sols.grep({ %d{ agg($_) } == 1 }) if $flip;
        return @sols.grep({ %d{ agg($_) } != 1 });
    }
    
    my @candidates = ((1..99) X (1..99)).grep({ $_[0] ≤ $_[1] });
    my @ns = @candidates;
    
    for 1..7 {
        @ns = solutions-filter @ns, { $_[0] * $_[1] };
        @ns = solutions-filter @ns, { $_[0] + $_[1] };
    }
    
    say solutions-filter(@ns, { $_[0] * $_[1] }, :flip);

Never thought I'd see anything more concise than Python, but here's the Kotlin version:

    data class Candidate(val x: Int, val y: Int)

    fun List<Candidate>.filterCandidates(knows: Boolean, aggBy: (Candidate) -> Int) =
        groupBy(aggBy)
            .values
            .filter {value -> if (knows) {value.count() == 1} else {value.count() > 1} }
            .flatten()
    
    fun main() {
        var cs = (1..99).flatMap { x -> (x..99).map { y -> Candidate(x, y) } }
        repeat(7) {
            cs = cs.filterCandidates(knows = false) { (x, y) -> x * y }
            cs = cs.filterCandidates(knows = false) { (x, y) -> x + y }
        }
        cs = cs.filterCandidates(knows = true) { (x, y) -> x * y }
        println(cs)
    }

Reply on news.ycombinator.com