I came up with an idea for a brain game. It's a modification of something called an automaton. Automata theory is a part of theoretical computer science.
The game looks like this:
You can draw those 5 colored edges on a piece of paper and place 2 pawns at the top 2 vertices.
The goal is to end up with only 1 pawn.
To reach the goal, you can make moves of 3 types, one type for each color, call it C:
When you select color C, you locate every edge with color C such that there is a pawn on one end and there is no pawn on the other end. Let's call these edges C-triggered.
Then you move pawns along C-triggered edges:
- If there is a pawn adjacent to k C-triggered edges, it splits into k pawns.
- If more than one pawn arrives at the same destination, they are merged.
In other words, after color C move, every edge that was C-triggered is "swapped"; that is for each end vertex if there was a pawn before, now there isn't and vice versa (note that there is a pawn on exactly one end since edge was C-triggered).
Can you solve the problem instance on the picture? What is the minimum number of moves?
You can post the answer in the form RRYGYGR..., where R=red, Y=yellow, G=green.
Edited by antipope, 08 July 2014 - 02:39 AM.