You’ve probably watched The Price is Right TV game show. On it they run the Clock Game.
The game is played for two prizes. The actual price of the first prize is shown to the studio and home audiences. After the contestant gives their first bid, a 30 second clock is started and the host tells the contestant whether the actual price is higher or lower than the bid. The contestant continues to bid, responding to the host’s clues, until either the contestant wins by correctly guessing the price of the prize or the time expires. If time remains after the first prize is won, the process is repeated for the second prize.…With few exceptions, only prizes valued below $1,000 have traditionally been offered in the Clock Game.
The algorithm to use is simple:
- Pick a ceiling ($1000) and a floor ($0)
- Bid the average ($500)
- If the bid is too low, the bid becomes the floor
- If the bid is too high, the bid becomes the ceiling
- Repeat
Being computer types, we’ll put the ceiling at $1024. For a $407-priced prize, your guesses would look like this:
| C | D | E | F | |
|---|---|---|---|---|
| 1 | 407 | <-- Price | ||
| 2 | Floor | BID | Ceiling | |
| 3 | 0 | 512 | Too High | 1024 |
| 4 | 0 | 256 | Too Low | 512 |
| 5 | 256 | 384 | Too Low | 512 |
| 6 | 384 | 448 | Too High | 512 |
| 7 | 384 | 416 | Too High | 448 |
| 8 | 384 | 400 | Too Low | 416 |
| 9 | 400 | 408 | Too High | 416 |
| 10 | 400 | 404 | Too Low | 408 |
| 11 | 404 | 406 | Too Low | 408 |
| 12 | 406 | 407 | Stop | 408 |
Ten guesses, and you’ve won a washing machine. Here are the formulas that make this work.
- D1: = 407 (the unknown price)
- C3: = 0 (the initial floor)
- F3: = 1024 (the initial ceiling)
- D3: = (C3+F3)/2 (512—the initial bid)
- E3: = IF(D3=$D$1,”Stop”,IF(D3>$D$1,”Too High”,”Too Low”)) (the host’s clues)
- C4: = IF(E3=”Stop”,””,IF(E3=”Too Low”,D3,C3))
- D4: = IF(E3=”Stop”,””,(C4+F4)/2)
- E4: = IF(D4=$D$1,”Stop”,IF(D4>$D$1,”Too High”,”Too Low”))
- F4: = IF(E3=”Stop”,””,IF(E3=”Too High”,D3,F3))
Watch out for “curly quotes” if you copy and paste in. Filldown C4:F13. So what’s the point? We knew the “unknown price” going in. Here’s a recent prospective employee question the BBC got from Qualcomm:
Given 20 ‘destructible’ light bulbs (which break at a certain height), and a building with 100 floors, how do you determine the height the light bulbs break?
You watch The Price is Right or you read DDoE, and you think “Clock Game!” In 20 bulbs, if they break from a 407.407 foot drop, and a floor = 10 feet:
| 407.407 | <-- Break | |||
| Floor | BID | Ceiling | ||
| 1 | 0 | 512 | Too High | 1024 |
| 2 | 0 | 256 | Too Low | 512 |
| 3 | 256 | 384 | Too Low | 512 |
| 4 | 384 | 448 | Too High | 512 |
| 5 | 384 | 416 | Too High | 448 |
| 6 | 384 | 400 | Too Low | 416 |
| 7 | 400 | 408 | Too High | 416 |
| 8 | 400 | 404 | Too Low | 408 |
| 9 | 404 | 406 | Too Low | 408 |
| 10 | 406 | 407 | Too Low | 408 |
| 11 | 407 | 407.5 | Too High | 408 |
| 12 | 407 | 407.25 | Too Low | 407.5 |
| 13 | 407.25 | 407.375 | Too Low | 407.5 |
| 14 | 407.375 | 407.4375 | Too High | 407.5 |
| 15 | 407.375 | 407.4063 | Too Low | 407.4375 |
| 16 | 407.4063 | 407.4219 | Too High | 407.4375 |
| 17 | 407.4063 | 407.4141 | Too High | 407.4219 |
| 18 | 407.4063 | 407.4102 | Too High | 407.4141 |
| 19 | 407.4063 | 407.4082 | Too High | 407.4102 |
| 20 | 407.4063 | 407.4072 | Too High | 407.4082 |
You’re 2-ten-thousandths of a foot off. You get the job, a great way to start the new year.
…mrt
©¿©¬
Binary search. Why not juice it up with exponential extrapolation to bracket the target value?
With the target value in a cell named target, start off with 500 as the initial guess in cell A4, and hi/lo/done in B4, so
A4: 500
B4: =LOOKUP(SIGN(target-A4),{-1;0;1},{“hi”;”done”;”lo”})
Either A4 is the target value, or it still needs to be bracketed.
A5: =ROUND(IF(B4=”done”,A4,IF(B4=”hi”,A4/2,A4*2)),0)
B5 is just B4 filled down.
The rest could be accomplished with formulas only in column A.
A6:
=ROUND(IF(B5=”done”,A5,IF(SIGN(COUNTIF(B$4:B5,”<>”&B5))=0,IF(B5=”hi”,A5/2,A5*2),
AVERAGE(A5,LOOKUP(2,1/(B$4:B5<>B5),A$4:A5)))),0)
with B5 filled down as far as needed.
I haven’t quite watched this show to comment, but to comment on your procedure, I believe this is called the Bisection method of root-finding approximation.
There are many methods that can be employed, like Regula Falsi method which uses the secants to derive the next interval [a,b] or the Newton Raphson method which uses a tangent to derive the [a,b]. These might be faster converging, hence lesser steps, but what could be a problem is deriving a functional form for the root in question!
Just curious – within a 30 sec time limit, how many ppl crack this? Are you given additional computing help or just mental math? And is there a limit to the number of trials other than time?
Hi Arun –
Thanks. I only watch when I’m sick, so I don’t see it very often. I’ve never seen anyone win the two prizes, but most everyone gets one. They all do it differently/sub-optimally. They go in half-steps until they’re close and below, and then they just count up by ones not waiting for clues. Which maybe is why they don’t win twice.
They get no other help than the host. This is one game that the audience is quiet for.
…mrt
@Arun, secant and Newton-Raphson require you know the function, actually the latter requires that you also know the derivative of the function. You don’t derive it/them. If you don’t know the function, you use nonparametric methods.
Secant and Newton-Raphson also require that the function be continuously differentiable. That’s not the case with the Price Is Right function. It’s discontinuous, trivalent: LOW if the current guess is below the actual price, HIGH if the current guess is above the actual price, or YOU WIN. That’s amenable to binary search, but not to these other approaches.
@fzz – That’s exactly what I stated in my comment “finding the functional form for the root is a problem!”. It’s probably suited better for a different type of game, you’re right about this is suitable for this game.