One Hundred Prisoners and a Rubik's Cube

They simply decide on 98 different valid Rubik's cube states at the beginning of the game and denote them 1 to 98. On the first day, the prisoner leaves the cube in any state apart from the pre-defined 98. We can call this state 0.

After this, everyone (including the 1st prisoner) follows the same strategy. Whenever a prisoner sees the cube for the first time, he takes it from the current state to the next one. So suppose it is currently in 23rd state, he just takes it to the 24th state. If a prisoner has already seen the cube he does nothing.

If a prisoner finds the cube in the 98th state the first time he sees it, then he knows that everyone else has already seen it. Hence he can declare it.

Before leaving their cell for the first time, the prisoner breaks the permanent marker and wets their finger with the ink. If they have ever left their cell before, they take no action while in the cell.

If there are no cube faces marked, they smear the ink on one and leave the cube unsolved. If there are any marked faces:

• if the cube is solved, mark a face and scramble the cube
• if the cube is scrambled, solve it

After this, if 50 faces are marked and the cube is solved, declare victory.

The first prisoner to enter the room disassembles the Rubik's cube. That gives them 26 pieces, which they put in one corner of the room. Then they treat the spot 30cm to the left as the tens pile, and 30cm to the right as the units pile. So the first person puts a single piece in the units pile and leaves.

Each prisoner who enters the room for the first time increases the count (adding one to the units pile, and carrying to the tens pile as needed). The prisoner who increases it to 100 reassembles the cube with one corner inverted (these are criminals after all), hands it to the robot to solve, and summons the warden.

Meanwhile, each prisoner who returns to their cell knows what number they were in the queue, and uses their marker pen to draw the appropriate frame from an agreed flip-book style animation of a prisoner removing their chains and walking out a door.

I think I used everything.

Here is my solution:

Take any permutation with order (the amount of times you need to apply it to arrive where you started) above 100, for example this permutation I just constructed:

(R U)29

Which is the same as

(R U)15 (R U)14

This has order 105:

The first prisoner lets the cube be solved by the robot, in case they didn't get it solved, and he then has to apply the above moves 6 times (5 times to get rid of the extra 5 in 105, then once).

all the other prisoners apply the sequence once. If they get called in the room more than once they just do nothing after the first time, or maybe have a chat with the robot.

Now when a prisoner sees that his application of the sequence solves the cube he knows that the sequence has been applied 105 times to a solved cube, of which 6 by the first one, so he is number 100 and tells it to the warden.

I like this solution because the last prisoner will have a great experience. He will see the cube getting solved magically, but trough logic he knows that he's number 100. I also used everything except the marker, but it might be useful for the prisoners to write (R U)29 on their wall so they don't forget.

This solution is also as efficient as possible, the prisoners get out on the first occasion!

I want to build on ghosts_in_the_code and Jens Renders' ideas and provide a practical solution easy to perform and to memorize.

It seems that this problem needs an additional assumption for the initial configuration of the cube at the start of the game.

If the initial cube configuration is not predefined (i.e. random initialization), then there doesn't seem to be a way to know if you are "The first prisoner to enter the room" (Callidus' solution). Similarly, for any other solutions using cube states for counting (i.e. Jens Renders') the initial configuration of the cube could match any counting state, thus making the problem unsolvable in general.

So the initial state of the cube must be predefined for the problem to be solved. There are only two possible initializations for the cube:

• scrambled: then you can only use the unscrambled state to signal having entered the room, meaning you can only count up to 1. Any other configuration a prisoner applies to the cube still counts as scrambled and is therefore indistinguishable from the initial state. This version of the problem thus has no solution.

• unscrambled: then you can use cube states for counting as in Jens Renders' solution. Callidus' solution doesn't seem to work here either because again you can only count up to 1.

[This puzzle just got bumped to the front page due to another answer being added, so I just saw it for the first time]

This mainly expands on ghosts_in_the_code's answer.

The prisoner who is invited into the room the first day first puts the cube to a solved state (if it is not already in such a state), which has a "cube number" of zero.

That prisoner, and each subsequent visitor on their first visit to the room, increments the "cube number" by 1.

On a repeat visit, if the plans are secret from the warden, and they don't want to give the game away, they can play with the cube and leave it in a different representation of the same number it showed when they arrived.

The "cube number" is determined by

The solving machine will be particularly useful on

The prisoner who, on entering the room for the first time after at least 100 days have elapsed, sees the cube scoring of 99 - e.g.

can either make the declaration immediately, or leave the cube showing a score of 100.

The next prisoner to visit would immediately know on looking at the cube that all 100 prisoners have been in the room at least once (and left and gone back to their cells).

This leaves 1 extra day beyond the absolute minimum, in case the warden starts being tricksy - "no, you're still in the middle of your visit, so not all 100 have visited yet.".

This scheme also allows for a check mechanism as follows - if at any time:

They may assume that someone has been tampering with the cube - either the warden, or another prisoner who failed to follow the plan correctly (if they're not ABSOLUTELY sure they detected tampering, and the state of the cube otherwise seems valid, they should continue as normal). They can then attempt to signal this to other prisoners by leaving the cube showing a score higher than 100, or by leaving the cube solved. They can do this on any future visits too, to maximise the chance of other prisoners discovering the tampering.

Whilst the puzzle will not be able to be solved once tampering is detected, they at least avoid risking everyone being executed because one of the other prisoners made a mistake or a sabotage occurred...

The marker will be used