Every story and comment from the Hacker News API, in a layout borrowed from 2001.
A comment on “I don't know the numbers”: a math puzzle. Parent 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.
There are no comments on this comment yet.
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.