In this module, we are going to play a game called Involution©. The game includes a tray with a crank handle. The tray has 10 holes that each contain 1 ring (of one colour).

The rings can be moved as shown in the following video:

Challenge 1

Get into pairs and play Involution©: try to solve the problems on the cards.

Challenge 2

Starting with the configuration on the left, can you get to the configuration on the right?

If so, explain your movements. If not, why not?

Challenge 3*

Can all the ring configurations be obtained? If so, how? If not, which of them can’t be obtained? Justify your answer.

For a clearer understanding, let’s now try to play the same game but with 9 white rings and one black one.

The key question is as follows.

Challenge 4*

Is it possible to obtain the configuration below from any other configuration? Justify your answer.

Let’s now play with two black rings.

Challenge 5*

Is it possible to obtain the configuration below from any other configuration? Use your solution from challenge 4 and justify your answer.

Let’s now play with three black rings

Challenge 6*

Use the solution from challenge 5 to see if you can reach the following configuration

starting from any other configuration.

Finally, let’s play with four black rings.

Challenge 7*

Use the solution from challenge 6 to see if you can obtain the following configuration

starting from any other configuration.

Challenge 8*

Review challenge 3*.

Challenge 9**

If we play the same game, but with 12 rings (6 black and 6 white), is it possible to obtain all the configurations? What about with 100 rings (50 black and 50 white)?

Let’s repeat the game with 10 rings.

Challenge 10

Starting with the following configuration

find the following configuration

and count the number of movements.

Compare your solutions with the rest of your group. Which is the best? Define a criterion to evaluate why one solution is better than another.

After discussing it, try to complete the following definition:

A solution is optimal when/if…

Let’s now build a visual representation of our game in order to find an optimal solution. As a reminder, one of the first algorithms we came across in Digital Sciences 1 was an algorithm to find a route on the New York underground. Just as the underground map is a graphic representation of the real network, we will make a graphic representation of the game: the network nodes are the different configurations of the game (in the case of the underground, the nodes were the stations) and two configurations are linked by a line if you can go from one configuration to another in one movement (in the case of the underground, two stations are connected by a line if you can go directly from one station to the other via the underground).

Here’s an example: let’s play Involution©, but with only 5 rings and a smaller tray (take the same tray, but do not use the 5 holes on the right). You are only allowed to make two different movements with the crank handle.

Challenge 11

The class is divided into 3 groups.

• The first group plays with 1 black ring (and 4 white rings).
• The second group plays with 2 black rings (and 3 white rings).
• The third group plays with 3 black rings (and 2 white rings).

In groups of two, draw all the possible configurations of your version of Involution©.

Together, discuss and explain how many configurations of your version of Involution© are possible. Then present your solution and your explanation to the whole class.

Challenge 12*

Decide if, in your case, it is possible to obtain any configuration whatsoever and explain your response.

We will now construct the graphic representation.

Challenge 13

Give a name to each configuration (for example C1, C2, C3, etc). For each configuration found in challenge 11, draw a node and write its name beside it. Then, connect the nodes with a line if it is possible to go from one configuration to the other with just one move of the crank handle. Compare your graphs.

Challenge 14

Go back to challenge 12 (by using the graph you have just drawn).

Now let’s return to the initial game with 10 rings.

Challenge 15*

Can you calculate the number of different configurations or at least give an upper limit?

In total, there are 252 different configurations. This gives a graph with 252 vertices, which looks like this:

The 10-ring Involution© graph is too large to see the shortest path with the naked eye. That’s why we need an algorithm.

Challenge 16

Go back to your game and play with 6 rings now (3 black and 3 white) and a smaller tray (take the same tray, but do not use the 4 holes to the right). Find all the possible configurations and draw the graph.

Challenge 17

Use the graph found in challenge 16 to determine an optimal solution for obtaining the configuration below

starting with the following configuration:

Challenge 18

Based on the previous challenge, look for an algorithm that gives:

1. The minimum number of moves to go from one configuration to another (once the graph for the game is given).
   
   Help
2. An optimal solution for going from one configuration to another (once the graph of the game is given).
   
   Help

Write some informal instructions for your algorithm and draw its flow chart.

Challenge 19

Apply the algorithm to the Involution© game with 10 rings.

Challenge 20

Look at the image below:

What app is this? Look for a link between this app and the search for an optimal solution in the Involution© game.