Usually we choose a starting state, perform the moves and discover what happens. Here the question changes: what starting state must we prepare to obtain exactly the result we want? In these two problems, inverse operations become a concrete way to reason.
Open the laboratory: cards and Josephus, forward and backward
Two applications to try with friends:
Starting at the end
A reverse algorithm is not a series of random attempts. We start from a desired final state and undo the operations in reverse order. The result of the last normal action becomes the starting point for the first inverse action. We must know which information to retain: here we keep the cards on the table and distinguish those who must remain from those who must leave.
Problem 1: the deck of cards
You have 10 cards numbered from 1 to 10. How must you arrange them so that repeating the following moves makes them appear on the table in the order 1, 2, 3, 4, 5, 6, 7, 8, 9, 10?
- Take the card from the bottom of the deck.
- Place it on top of the deck.
- Take the card from the bottom of the deck.
- Place it face up on the table, on top of the earlier cards.
The removal order is chronological: first 1, then 2, through to 10. In the final pile on the table, however, 10 is on top and 1 is at the bottom. These readings must not be confused.
The card video in reverse
Imagine rewinding the video. The hand is empty and the final pile is on the table. Take back 10 first, then 9, and so on. Reverse both the direction of each transfer and the order of the four actions:
- Take the card from the top of the pile on the table.
- Place it underneath the deck in hand.
- Take the card from the top of the deck in hand.
- Place it underneath the deck in hand.
The first two actions undo removal onto the table; the last two undo the bottom-to-top transfer. The principle remains the same even when the hand contains only one card.
After each group of four inverse actions, the deck in hand grows by one card. Always read from top to bottom:
| Card taken back from the table | Deck after the inverse round, top to bottom |
|---|---|
| 10 | 10 |
| 9 | 9, 10 |
| 8 | 10, 8, 9 |
| 7 | 8, 9, 7, 10 |
| 6 | 9, 7, 10, 6, 8 |
| 5 | 7, 10, 6, 8, 5, 9 |
| 4 | 10, 6, 8, 5, 9, 4, 7 |
| 3 | 6, 8, 5, 9, 4, 7, 3, 10 |
| 2 | 8, 5, 9, 4, 7, 3, 10, 2, 6 |
| 1 | 5, 9, 4, 7, 3, 10, 2, 6, 1, 8 |
Starting arrangement, top to bottom:
5, 9, 4, 7, 3, 10, 2, 6, 1, 8
The same arrangement read from bottom to top:
8, 1, 6, 2, 10, 3, 7, 4, 9, 5
Playing the normal game with this deck gives exactly the numbers from 1 to 10. In the laboratory, check this one card at a time; you can also change N or choose a different removal order.
A comparison: simulation and permutation
We can obtain the same deck without directly undoing the moves. Label the starting positions from 1 to 10, counting from the bottom. Simulate the normal game and record the chronological order in which those labels are removed:
2, 4, 6, 8, 10, 3, 7, 1, 9, 5
Assign value 1 to the first removed position, value 2 to the second, and so on. The table keeps the same reading direction throughout:
| Removed position label (from bottom) | Assigned value |
|---|---|
| 2 | 1 |
| 4 | 2 |
| 6 | 3 |
| 8 | 4 |
| 10 | 5 |
| 3 | 6 |
| 7 | 7 |
| 1 | 8 |
| 9 | 9 |
| 5 | 10 |
Sorting by label from 1 to 10 recovers the bottom-to-top arrangement. The two methods agree: simulation observes the permutation of positions; reverse reconstruction undoes the transfers.
Problem 2: the Josephus circle
Arrange N people in a circle. Count to K, eliminate the K-th person and restart with the next one. We want V people from the winners’ group to remain after P eliminations. How can we construct the starting arrangement? We do not choose the winners’ seats beforehand: reconstruction must reveal them.
In the elimination game, seat 1 is the counting origin: the person there counts 1, the next counts 2, and so on up to K. After each elimination, restart at 1 with the next person. Seats in the completed arrangement are numbered clockwise; the game follows the chosen direction. The main examples count clockwise.
Seat 1 is where counting starts for elimination. It is not necessarily occupied by the person labelled 1, and it is not necessarily a winning seat.
The game shows forward simulation. The new laboratory instead reconstructs the arrangement backward and then lets you check it in the same game.
Open the existing Josephus game
Reconstructing Josephus one move at a time
The algorithm knows only how many winners and losers there are and how often to eliminate. At the start it gathers all winners together, one after another. It does not use any earlier positions or assign their final seats yet. To follow the procedure, label the people: 1 to V are winners; V + 1 to N are losers.
- Put only the V winners in a queue, labelled 1, 2, …, V. They are together: these are not yet numbered seats in the game.
- Take the first loser, labelled V + 1, and put that person at the head of the queue.
- Repeat the same pair of operations K − 1 times: take the last number from the tail and put it at the head.
- Take the next loser and repeat insertion and moves. Continue one loser at a time until all P losers have been inserted.
- Only at the end read the completed arrangement from the head, assign seats 1, 2, …, N and identify those occupied by winners. The elimination count will start at seat 1.
The procedure uses exactly K − 1 moves per insertion, as in the program’s loop. For example, with K = 3: insert a loser at the head, then perform “take from the tail and put at the head” twice. With K = 1, only insert the loser, without any moves.
During reconstruction, numbers identify people. They do not indicate where those people will win. In the laboratory circle, the green winners start together; the blue losers wait separately and are reinserted one at a time. The winning seats are an outcome of the procedure, not an input.
A small example: N = 4, K = 3
Use V = 1 winner, P = 3 losers and K = 3. The winner is person 1; the losers are people 2, 3 and 4. Start with 1 alone. Insert 2 and make two tail-to-head moves; then do the same with 3 and 4. The table shows every insertion and every completed move:
| Operation | Queue: people’s labels, head to tail |
|---|---|
| Gather the winners alone | 1 |
| Insert loser 2 at the head | 2, 1 |
| Move 1 from tail to head (1 of 2) | 1, 2 |
| Move 2 from tail to head (2 of 2) | 2, 1 |
| Insert loser 3 at the head | 3, 2, 1 |
| Move 1 from tail to head (1 of 2) | 1, 3, 2 |
| Move 2 from tail to head (2 of 2) | 2, 1, 3 |
| Insert loser 4 at the head | 4, 2, 1, 3 |
| Move 3 from tail to head (1 of 2) | 3, 4, 2, 1 |
| Move 1 from tail to head (2 of 2) | 1, 3, 4, 2 |
The completed queue is 1, 3, 4, 2. Now, and only now, assign seats: seat 1 holds person 1, seat 2 holds person 3, seat 3 holds person 4 and seat 4 holds person 2. Thus the winning seat is 1. Starting the count there and eliminating every third person removes seats 3, 2 and 4: seat 1 remains.
The birthday: I always win!
We are at a party: 9 guests plus the birthday person, so N = 10. The birthday age is 12: choose K = 12 and a single winner, V = 1. The guests to eliminate number P = 9.
Reconstruct the circle and give the winning seat to the birthday person. Starting at seat 1, the clockwise winner is seat 10; anticlockwise it is seat 2.
This is not luck: we chose the result and prepared the appropriate seat. For a different party, set P to the number of guests, V = 1 and K to the birthday age. Add the birthday person to the guests to obtain total N.
Clockwise eliminations:
2, 5, 9, 6, 4, 8, 7, 3, 1
The pair: two chosen winners
There are 20 friends and we want two people chosen beforehand to remain. Set N = 20, V = 2, P = 18 and K = 11.
Backward reconstruction finds the seats to give the pair: clockwise, 9 and 15; anticlockwise, 7 and 13. Counting always starts at seat 1.
The two people can exchange the two winning seats with each other. This does not mean that two arbitrary seats can win: the specific calculated positions guarantee the outcome.
Clockwise eliminations:
11, 2, 14, 6, 19, 13, 8, 4, 1, 20, 3, 7, 12, 18, 16, 17, 10, 5
Two groups of 15 people
Another example uses two groups of 15 people: V = 15, P = 15, N = 30 and K = 9. The method is unchanged: start with 15 winners and reinsert 15 eliminated people. The winning seats are:
Clockwise
1, 2, 3, 4, 10, 11, 13, 14, 15, 17, 20, 21, 25, 28, 29
Anticlockwise
1, 3, 4, 7, 11, 12, 15, 17, 18, 19, 21, 22, 28, 29, 30
Reconstruct the circle of 30 people
Another example: 2 winners and 28 losers
With V = 2, P = 28 and K = 11, start by gathering winners 1 and 2 alone. Reinsert losers 3 to 30 one at a time. No winning seat is fixed beforehand. At the end number the 30 seats and, counting clockwise from seat 1, find these winning seats:
18, 28
Try 2 winners, 28 losers and eliminate every 11
How to use the laboratory
- In Cards choose N and the desired order. In Josephus set the numbers of winners and losers, K and direction, or load an example.
- Use Next and Previous for individual moves, Play/Pause for animation and the slider to return to an exact step. The initial pace is one second per action; you can change it.
- During Josephus reconstruction, watch the first group arranged in a circle: it starts with the green winners alone. Blue losers stay in the second list during the animated count, then join one at a time without turning green. The circular shape shows the group under construction, not seats already assigned.
- At the end see the row of seats, with winning ones in green. Seat 1 is the counting origin for the elimination game. Check forward runs that game so you can verify the arrangement.
Open the laboratory: cards and Josephus, forward and backward
What we have learned
With cards we reconstruct the deck that produces the required removal order. With Josephus we instead start with the winners gathered together and reinsert losers one at a time. We do not impose winning positions: we discover them at the end. Once the completed arrangement is numbered, seat 1 determines where to begin counting for elimination. The forward check confirms the result.