Brainteasers · Weighing and search · Hard
Two dollars for a yes
I pick a whole number from 1 to 30. You ask questions of the form "Is your number in this set?" for a set of your choosing, each chosen after hearing the earlier answers, and I answer truthfully. Every answer of "yes" costs you $2 and every answer of "no" costs you $1. You stop when the answers leave only one possible number. What is the smallest budget, in whole dollars, that is certain to cover the cost of identifying my number, whatever I picked?
Answer and solution
Answer
8
Solution
A budget of c dollars handles F(c) = F(c − 1) + F(c − 2) numbers: the "yes" group is made smaller because it costs more.
With $0 or $1 no question is safe, so only one number can be handled: F(0) = F(1) = 1. Then F(2) = 2, F(3) = 3, F(4) = 5, F(5) = 8, F(6) = 13, F(7) = 21 and F(8) = 34. Seven dollars handle only 21 numbers; eight handle 34, which covers 30. The answer is 8.