Postcard from Switzerland: Dilbert’s hotel

This week, I’ve been at a conference in the beautiful village of Les Diablerets in Switzerland.

A photo of the mountains near Les Diablerets – this job is great!

On the first evening, one of the professors shared a problem that I thought was very nice.

Hilbert’s distant cousin Dilbert is opening a hotel, in the hopes of cashing in on the roaring success of Hilbert’s Hotel.

However, unlike Hilbert, Dilbert only has a finite number of rooms in his hotel. He decides to make up for this by starting an offer for bookings with 10 people or more.

Each of the people on the booking must play a game. If all of them win, then the party gets to stay at the hotel for free! Sounds pretty good, right?

Here’s the game:

Suppose there are n people in the party. Each person is assigned a number from 1 to n with no repeats.

Dilbert sets up n boxes in a separate room and then randomly puts one number in each box.

The people are then able to go into the room one by one and open at most n/2 boxes. If they find their number, they win the game.

There’s an additional catch though – the members of the party can strategise beforehand, but once the game starts, they can no longer communicate, and the room is reset after every person.

Dilbert calculates that the probability that a party of at least 10 people gets a free booking is at most (1/2)¹⁰=1/1024, so he’ll definitely make more money than he loses.

However, Dilbert goes broke after only 2 years after introducing the scheme.

What went wrong?

Here’s a little hint: The conference I’m at is for young group theorists.