The basic setup for each problem is given below. For more details,
hints, and a solution to each, click on the problem's title.
Opening / Closing 100 Locker Doors
Over at your local high school, the main hallway has a bank of 100 lockers.
All of these lockers, labeled 1 through 100, start with their doors closed.
The resident class clown decides to open every locker door.
He then returns to the front of the row and
toggles (opens/closes) every 2nd locker door (2,4,6,8...) in the hallway.
That is, he goes to every 2nd locker, if it's open, he closes it,
if it's closed, he opens it.
The class clown repeats this for every 3rd locker (3,6,9...),
then every 4th locker (4,8,12...), then every 5th (5,10,15...), etc.
until he finally repeats for every 100th locker.
After the class clown is done, which locker numbers will end up closed,
which will end up open?
10 Boxes of Pills, 1 Box's Pills Were Misweighed
Working at the local pharmacy, you get a new shipment of Viagra pills
in 10 boxes. Each box contains 10,000 pills.
You open up the boxes, preparing to package the pills in separate bottles
when the Viagra supplier calls. "WAIT! Don't unpack the pills yet. We just
found out we had a packaging problem, and we know that in ONE of the boxes we sent
you, all of the pills were misweighed. We don't know which box it is,
but we do know that all normal pills will weigh exactly 100 mg while all
of the pills in the bad box weigh exactly 101 mg."
The shop is about to open, and ravenous customers are eager to get
their Viagra. It would be dangerous to give people overdosed pills
though. Who knows what kind of damage that could cause!
Luckily, next door is a hardware store which has a very precise
electronic scale, which can measure down to a single milligram. This is
the type of scale where you simply put something on top of it, activate it,
and it gives you a number, which is the precise weight of what's on it.
The scale is coin-operated and requires one quarter every time
you activate it.
You were hoping to save some arcade money for after work so,
what is the fewest times you need to use the electronic scale
to determine which is the box of defective pills (and how would you do it)?
Was that too easy for you? Okay then smarty-pants. The next shipment
of 10 boxes of pills you get, the supplier calls and says they REALLY
messed up. ANY number of the boxes might have been stuffed with the
101 mg pills instead of 100 mg. Not only do they not know which
ones are faulty, they don't even know how many are faulty. It could
be ALL of them, it could be NONE of them.
What is the fewest times you'll need to use that electronic scale
this time to determine which boxes, if any, have the defectively
weighted pills (and how would you do it)?
10 Prisoners in a Line and 1 Psycho Cop with Blue and Red Hats
You are in a group of 10 prisoners who are captured and rounded up by a crooked, psycho cop.
He decides to execute the lot of you, but to play a game to give some of you a chance to live.
He tells you his plan to incite a little sadistic fear. His plan is to put either a blue or red
hat on each of your heads, and then he will ask each person what color his hat is. If they guess
correctly, they may leave freely. Otherwise, BANG! he shoots them dead.
Furthermore, the psycho cop will first line all of you up, single file, all facing in one direction,
such that each person is facing the next prisoner's back. Thus, every prisoner will be
able to see the hats of every one in front of them, but not their own hat or anyone
behind them. He will ask each of you in order, starting from the back of the line
and moving forward.
After telling you his sadistic plan, he leaves the room to get the hats, which could be in
any combination of red and blue, and in any order. They could all be red, or they could all be blue,
or any combination in between. During this time, you, the prisoners, have the chance to discuss
and try to come up with some sort of communication system, to help each other out in guessing
your hat colors. You happen to be very generous and humanitarian prisoners, or perhaps you have a
hive mind, such that you are not interested in your individual survival, only in ensuring
that as many of you survive as possible.
What communication/code system can you come up with for the prisoners to use, to save the
most prisoners? How many prisoners would be saved, on average, using your system?
Note that "Red" and "Blue" are the ONLY two words that you can each say, and only once.
You can't say them in any funny voices or stamp your feet, etc.
Thus, you may ONLY give these two distinct outputs.
If you attempt anything funny otherwise, the cop will just kill all of you.