Doff your hat to a new trick: The Weekly Puzzle by Dilip D’Souza

One hat, 11 boxes and a hotel owner in Cherrapunjee who likes to shake things up. Can you work it out and win yourself the prize of a free stay?

At a certain hotel in Cherrapunjee, there are 11 large boxes arranged in a line in the lobby. The hotel owner, a definite eccentric, offers every new guest the chance to play a peculiar game that goes like this.

One of the boxes contains a distinctive hat. The guest doesn’t know which box has the hat. Every hour, on the hour, the owner first blindfolds the guest and then moves the hat from whichever box it’s in to an adjacent one. Thus if it is in box #8 at noon, he moves it to either #7 or #9. Let’s say he chooses #7. At 1 pm, he will move it either to #6 or back to #8.

As soon as he moves the hat, he removes the blindfold and asks the guest to open any one box. If there’s no hat there, it’s on to the next move, an hour later. But if the guest finds the hat in the box she opened, she wears it and turns with a smile to the owner, who announces that her entire stay will be free.

So naturally, every guest wants to play. But note: the offer is only valid for the guest’s first 24 hours at the hotel.

You arrive at the hotel one very rainy day (it’s Cherrapunjee after all). The owner explains his game and invites you to play.

Can you be sure of getting a free stay? If so, how, and what’s the maximum time it will take to find the hat? Or will the owner always be able to keep the hat hidden?

Scroll down for the answers.

.

.

.

.

.

Answers:

Yes! You will certainly find the hat — if you follow the right strategy. Try this: start by opening box #1, then box #2, #3, and so on. If you reach #11 and have still not found the hat, open #11 again, and then go backwards: #10, #9, #8 and so on. With this strategy, you will find the hat in at most 20 hours.

How does that work?

First, let’s say that when you open #1, the hat is actually in #11, or in any odd-numbered box. The difference between your choice and the box containing the hat is an even number (10, if it was in #11, or 4, if it was in #5, etc). A moment’s thought will persuade you that whatever the owner does, following the strategy above will keep that difference even. This means that at some point as you go from #1 to #11, you will necessarily find the hat. , For example, let’s say that when you open #9 the hat is in #11. The next hour, it will necessarily move to #10, and that’s the box you will open. It will take at most 9 hours to find the hat this way.

But second, suppose that when you open #1, the hat is in an even-numbered box. Now the difference between your box number and the hat’s is odd, will stay that way, and you will certainly miss the hat as you go from #1 to #11. For example, if it was in #2 when you opened #1, the owner could then move it to #1, so you won’t see it when you open #2. Now he could, for example, keep moving it to the box you last opened, and you won’t find it before reaching #11, 10 hours on. At that point, the hat will be in #10. One hour later, the owner will move it either to #9 or #11 and you open #11 again. Now you’ve either found the hat or the difference is now even — which means you’ll necessarily find the hat in a maximum of 9 more hours.

Total 20 hours at most. I just saved you a pile of money. Send me a rain-drenched Cherrapunjee postcard, please.