Hacker News new | ask | show | jobs
by Cogito 2968 days ago
They can communicate, before they start. That's how they share the strategy with each other.

> Before the first prisoner enters the room, the prisoners may discuss strategy—but may not communicate once the first prisoner enters to look in the drawers

So they just write down a random permutation and give a copy to each prisoner while discussing strategy.

1 comments

They need to communicate before seeing the boxes. You assume the can decide on a strict ordering before looking at the boxes. If they say box one is the highest box closest to the door their might be two boxes that satisfy that criteria. As a math problem it's assumed that such problems don't occur, as a riddle things are not so clear.

On the other hand, if they could communicate after getting a reasonable definition of the room and know they would not be moved then sure strict ordering is easy. But, nothing says they are given that.

Further, they need to pick random numbers without the warden deducing the scheme, but let's assume the can use a public key crypto to get around the need for privacy.

There are many strict orderings that can be used, but we just need one.

Since each number is in a physical draw in a physical room, and no two draws can occupy the exact same space, there is a strict ordering of the drawers given by each drawers distance from a fixed point in the room (say a specific corner agreed on beforehand) in each of the three orthogonal dimensions sideways (x), backwards (y), and up (z).

We say a drawer A is before a drawer B if A.x < B.x; or, if A.x = B.x then if A.y < B.y; or, if A.x = B.x and A.y = B.y then if A.z < B.z

If A.x = B.x and A.y = B.y and A.z = B.z then A = B.

This is a strict ordering that will number the drawers from 1-100, and can be determined beforehand.

Now the prisoners take that order, and shuffle it randomly, without telling the warden what they are doing.

As math that works fine, in practice it's a world of problems. A.x = B.x is a question of finite precision close enough and all prisoners will not agree if A.x = B.X or A > B or A < B. Adding precision tools does not help as you get into things like thermal expansion and the weight of prisoners deforming the floor etc.

So, while that works as a math problem, it may fail as an actual solution.