Waste less time on Facebook — follow Brilliant.

The Prisoner's Dilemma

Imagine a prison consisting of \(64\) cells arranged like the squares of an \(8\times8\) chessboard. There are doors between all adjoining cells. A prisoner in one of the corner cells is told that he will be released, provided he can get into the diagonally opposite corner cell after passing through every other cell exactly once. Can the prisoner obtain his freedom?

This is not an original problem.

Note by Marc Vince Casimiro
2 years, 10 months ago

No vote yet
1 vote


Sort by:

Top Newest

Imagine the cell floors painted like on a chess board, and suppose the starting cell floor is black. Then the cell floor of the opposite corner cell will be black as well.

Now every move by the prisoner results in a change in floor color. Further, each odd-numbered move leaves the prisoner in a white-floored cell. So after any path of \(63\) moves he will always be in a white-floored cell, which means he can never end up in the (black-floored) opposite corner cell after \(63\) moves, and hence there is no way he can complete the freedom-giving task. :(

Brian Charlesworth - 2 years, 10 months ago

Log in to reply

Poor prisoner :(

Jake Lai - 2 years, 10 months ago

Log in to reply

Haha. Yes, so sad. :(

Brian Charlesworth - 2 years, 10 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...