The safes example assumes independence (see 1 below). That is, the combinations and rewards (hence in $dollars) are part of a whole, not 101 independent parts. Each safe has $1. The firt safe has a 1-but combination the second a 2-bit combo, etc., up to a 100-bit combo for the last safe.
The first small safe with a 1-bit combination is quickly opened by thief, who gains $1 and 1-bit of the combination to the next safe. The second safe has a 2-bit combination, but using his 1-bit knowledge he only needs one more bit! The second safe is also soon opened gaining another $1 and 1 more bit. The thief proceed to open each safe in turn until all the safes are open, and walks out with $100.
Let’s make this harder - The thief does know how the safes are ordered, so it is not clear what order he should proceed.
He starts by entering “0” as the combination for all 100 safes, if one of the does not open, he goes around again and enters “1” as the combination, and one must open. The thief has gained $1 and 1-bit. 99 safes remain.
The thief repeats his task, starting with the bit(s) he knows and and adding 1-bit at a time until all the safes are open.
Additional notes:
-
I am making the error of assuming only a single function, or a single set of safes, when the thief may have many to choose from. A combination that does not open a safe for a particular function might open a safe containing some other new and unexpected function.
-
Another error! There is not just a single thief, but a population of thieves, each working to open the safes and sparing information.
-
If the safe combinations allow extra bits beyond the correct combination, the thief can guess the next two or three bits, possibly opening several safes with each pass, greatly speeding his task.
-
The thief ought to be flipping coins to choose bits instead of sequentially trying “0” and “1” bits. The thief will average 2 attempts per bit, but this does not substantially change the point I am making so I’m not going back to fix it!
