Wolf, goat, cabbage, ... V

Starting with students on both sides

For some start configurations, like the induced subgraph of red box graph # 2 shown to the right, we cannot move (with boat size 3 or less). The vertex-edge covering number of that graph is 4. Still we may work with that game graph, even with boat size 2, but we choose a different start configuration. Now some students are standing on both sides at the very beginning. On the left, some want from left to right, but some want to stay left. The same for the right. Some want to move to the left, and some want to stay right. You can generate them by clicking on "left -----> right", "stays left", "left <----- right", or "stays right". Try the following example:

start configuration both game graph

Difficulty Level 5:

1. Click twice on "next graph" to obtain graph 2.
2. Click "B", "G" "I", "O", "R", and both "F"s.
3. Click on "left <----- right".
4. Click on "A" and "J".
5. Click on "Start" to start.

You see, the background of the T shirt of each student equals the background of the destination of that student. We are done if each student "merges" optically with his/her background. Try to do it in 15 moves for this particular example.

Meaningful start graphs with the both sides variant

Question 6: For which game graphs is it possible to find a start state (remember: for states, at least one move is possible)? Of course, then we must have at least two states.

If k denotes again boat size, the answer is: This is possible if we can partition the vertex set of the start graph into an independent set R and a set L inducing a subgraph having a vertex-edge cover of size at most k. Equivalent, and more interesting is the following condition:

A game graph allows at least one move (for a conveniently chosen start configuration) if deleting at most k vertices results in a bipartite induced subgraph.

previous page
Changing Sides,
Challenges,
Moving with State Graph Map,
A related puzzle: Shunting trains,

Erich Prisner, 2002-2004