My girlfriend has been playing a game on her smartphone for a while. The rules are:
- there are $n+2$ tubes (with $n\ge 1$) and $n$ colored liquids.
- Two tubes are left empty and the others are filled with four doses of liquid.
- A tube cannot contain more than $4$ doses of liquid.
- There are exactly $4$ doses of each liquid.
- Liquids of different colors are non-miscible.
- The goal is to move liquids so that the $4$ doses of each liquid are in a single tube.
- Only the doses of liquid on the top of a tube can be moved. They have to be moved on top of a liquid of the same color.
- All doses of the same color at the top have to be moved at the same time. The only exception is when there is not enough space available when moving into a new tube. Only the doses of the same color that can be moved are then moved. For example, imagine that tube 1 contains three red doses and tube 2 contains a red dose above a blue one. In that case, two red doses from tube 1 can be moved to tube 2.
Here is a picture that illustrates the problem (with $n=9$):
For example, the pink liquid at the top of the fifth tube can be moved to an empty tube. After that, the two doses of red liquid from the same tube can be moved on the remaining empty tube. It is not possible to move only one dose of red liquid.
Is there a general strategy to solve this problem?
My intuition tells me that I could use induction (like the Hanoi towers problem), or graphs, or invariants (defining the degree of disorder of a configuration, the solution of the problem corresponding to a degree of disorder of $0$), but I don't really know how to get started in any of these directions.
Note: I am not sure that it is possible to win from any starting configuration.
This one is impossible to solve:
It is easy to see that the best thing you can do here is to take two pairs of the same color from the top row and put those in the two extra tubes. This either exposes four new and all different colors, so you are stuck immediately, or you expose two pairs of tiles of the same color on the second row. For example, we can take the two red top tiles and the two grey top tiles and put them in the extra tubes, thereby exposing two brown tiles as well as two blue tiles. So, we can put a brown one of top of another, and also for blue, but after that we expose one orange and one purple one, of which no counterparts have been exposed yet, and hence we are stuck. By symmetry of the configuration, this is true for whatever pairs of colors you choose to start with.
Note that the placement of the tiles on the bottom row doesn't matter, since you'll never get to the bottom row.