Erich Prisner

Wolf, goat, cabbage, ... III

States

Which of the following situations may occur during a game?

To analyze the game, it suffices to consider only situations where the boat is on the left or right bank, and nobody in the boat. We also add the requirement that

  1. there is presently no fight on the non-boat bank, and that
  2. we are able to move the boat by loading some students.
We will specify these two requirements below. Such a situation we call a state. The first picture above violates the first requirement, the second one violates the second requirement, only the third corresponds to some state.

 

Since each state is uniquely determined by the placement (left or right) of the boat and the students, it can be encoded by a 0-1 vector (x0,x1, x2, ..., xn) of length n+1 (if there are n students, #1, ... n). We say x0=0 if the boat is on the left bank, and =1 if it is on the right bank, and we say xi=0 if student #i is on the left bank and =1 if it is on the right bank. (0,0,0,...0) would encode the initial state, and (1,1,1,...1) the state we want to achieve.

Now for each state the students on the left bank induce the left bank graph, those on the right bank the right bank graph.

Here you see a certain state (with encoding (1,0,1,1,0,1,0,0) if the students are ordered as C,F,G,H,I,J,K,N), the corresponding game graph, and also the left bank and right bank graphs.

game graph: left bank graph right bank graph

Let us now formalize our two requirements above in terms of left bank and right bank graphs. Assume the boat is on the left bank. We get:

  1. the right bank graph is edgeless, and
  2. the left bank graph has some vertex-edge cover of size at most k.
Of course, the conditions hold with "right" and "left" interchanged if the boat is on the right bank.
Now we are able answer Only induced subgraphs of the graph to the right work with boat size 1.

Question 3: With a boat of size 2, which start configurations can you move from left to right?

Moving the empty boat

Question 4: Which game graphs allow movement of the empty boat (for some appropriate distribution of students on both sides)?

The answer is clear: Both left bank and right bank graph must be edgeless. So the partition of the students on left and right bank must be a 2-coloring of the game graph, therefore the game graph must be bipartite.

previous page next page

Erich Prisner, 2002-2004