## Items

- Pick 5 colours to represent teams
- 5 long tiles represent the bases, one for each team colour
- 2 meeples for each team colour represent the players

## Setup

- Arrange the base tiles in a circle with the player tiles being on their matching bases
- Remove one meeple to create a team that has only one player (the solo team)
- Shift the players around with the audience so that the players end up in random bases (max 2 players can stand on a base). This just represents the players playing the match, and is done to engage the audience.

## Rules

- Each base can host at most 2 players
- A player may move to a neighbour base ("left" or "right") if there is space for them
- The problem is solved once each player is on their home base of the correct colour

## The Trick & Background

- A player X that is alone can move to the platform left of it in three steps (moving to the right is symmetrical):
- Move one of the players from the left platform to the current platform The left platform now has space to go to but the original platform is full.
- Move X to the free spot on the left platform The left platform is full and the original platform has a free space.
- Move the second player from the left platform to the original one Now player X is again alone on their platform and we can repeat the process

- When a player moves to the free spot, the free spot "moves" into the other direction. This means we can move the free spot to any position by shifting players to the left / right. The player assignment of the bases in between is destroyed in this process so we need to make sure that we never cross a solved base.
- Imagine the circle is cut apart at the solo team's base Start solving the base that is furthest away from the solo base, then continue with the second furthest away, etc. - the solo team base is last.

## Computer Scientific Lessons

- We develop a simple algorithm from the basic block of moving a player to the adjacent base
- Cutting the circle makes the ordering visible that is necessary to solve the problem
- The algorithm is based on inductive reasoning: we reduce problem of solving N bases to the problem solving N-1 bases. This can be made intuitive by removing the solved base from the line.
- We can also estimate the worst-case run time of the algorithm: it takes at most N steps to move the hole to a player and 3N steps to move the player back. Solving base N then needs at most 8N moves because it is home to two players. The upper limit for five bases is then 8*(1+2+3+4+5)=120 steps.

## Variants / Comments

- Sometimes it is easier to talk about the open spot moving instead of the players
- Solved bases can not be crossed anymore
- When cutting the circle it is helpful to arrange the bases in a line
- Younger children can start already with the circle cut to make it easier
- The mixing step can be omitted when we start with a random assignment from the beginning (or earlier runs) Setting up the game with the players on their home base has the advantage of showing the final situation
- Grown-ups might find it interesting that the worst-case complexity of the game is O(n²) but this requires knowledge of the Gaussian summation formula 1+...+N = (N*N+1)/2.
- Duplo blocks are well suited for the game: you can use 4x2 blocks for bases and 2x2 blocks for players

## References

- Marie Duflot-Kremer's webpage on Scientific Outreach (in French)
- Comprendre l'informatique en jouant … avec Marie Duflot (in French with English subtitles)