BrainDen.com - Brain Teasers

# Brain game from computer science

## Recommended Posts

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?

The only place to reduce the number of pawns is in the center, with green color.

You can post the answer in the form RRYGYGR..., where R=red, Y=yellow, G=green.

Edited by antipope

YRGYGGYRYRYGG

##### Share on other sites

Nice! I wasn't sure if someone would be patient enough to solve this on paper

For those of you who liked this, there's a game for Android and this is exactly one level from this game. It's called J-Fizo and you can find it on Google Play if you have Android phone or tablet.

Let me know how far you got since I don't think anybody can pass this entire game without brute-force computer approach

PS Here's k-man's solution in animated GIF form (in fact it is the minimum possible number of moves):

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×