Geometric Combinatorial Puzzle

[davar55]

There is a rectangular m x n grid, and a snail in one corner.
Every other square contains a pea. (This snail eats peas.)
The snail can only travel to an adjacent square if
(a) it is horizontally or vertically connected to the snail's
current square, and (b) it still has a pea, which the snail then eats.
If the snail must end in the diagonally opposite corner,
and must eat evey pea,
how many different paths is it possible for it to follow?

[Wacky]

Your conditions may not be adequate.

Consider the simple 2x2 grid.
It has 3 peas. Let's label the nodes (0,0), (0,1), (1,0), and (1,1).

The Snail starts at (0,0) and must end at (1,1).
It has two possible first moves, namely (0,1) or (1,0).
From there, the only allowed move is to (1,1), the exit point.

However, that consumes only two of the three peas.
If it moves to the remaining pea, it cannot return.

Thus, there is no solution in this most simple case.

[davar55]

Yes, in certain cases, such as 2 x n where n is even,
the answer is zero possible paths.
This is the degenerate case.

[Wacky]

Given m,n > 0.
Is there a solution for ANY grid of the form 2*m, 2*n ?

[drew]

Originally Posted by Wacky

Given m,n > 0.
Is there a solution for ANY grid of the form 2*m, 2*n ?

I'm certain there's not, but I'm at a loss to provide a proof.

I thought I proved it to myself a couple of times, but then realized I overlooked something.

[davar55]

Actually, yes, if m and n are both even, then f(m,n) == 0.
This can be shown by a tiling argument.
Consider two (consective) moves as removing a 1x2 tile.
Then since, when m and n are both even (or both odd)
the last (diagonally opposite the first) square is of the same
parity (say, color of a checkerboard) as the original corner,
when it is reached there must be at least one square of the
opposite parity still unreached if m*n is even.
Also note: f(1,n) == f(m,1) == 1, and f(2,n) == 1 if n is odd.

[Wacky]

davar,

I don't think that your method is quite correct.

Your colouring argument seems to give a different result for {even by odd} and {odd by odd}.

However, any grid that has an odd number of rows in, at least, one direction can be "solved".

Consider the grid to be of size (2*m+1, n).

The solution for m=0 is obvious.
By induction, it is easy to show a solution for all larger m.


I think that you are on the "right track", but that the argument needs a bit more refining.

I'm approaching the proof by the inductive argument:
(I) If there is a solution for (m>2, n), there must be a solution for (m-2,n).
Similarly, (II) a solution for (m, n>2) implies a solution for (m, n-2).
In the case of (even, even) this would lead to a contradiction since there is no solution for (2,2).

I think that all of the steps are rather obvious if I can prove lemma (I).

[davar55]

No, the tiling-parity-coloring argument was only intended
to apply to even by even grids to show these have no solution.
It fails on odd by odd or odd by even grids.
I only mentioned the "opposite corner color" property for
odd by odd grids to be complete. Re-reading my explanation,
I realise this was unclear.
(If odd by odd, m*n is odd so the argument doesn't apply.)
(If odd by even, diagonal is opposite parity, so again the
argument doesn't apply.)

[drew]

Originally Posted by davar55

No, the tiling-parity-coloring argument was only intended
to apply to even by even grids to show these have no solution.
It fails on odd by odd or odd by even grids.
I only mentioned the "opposite corner color" property for
odd by odd grids to be complete. Re-reading my explanation,
I realise this was unclear.
(If odd by odd, m*n is odd so the argument doesn't apply.)
(If odd by even, diagonal is opposite parity, so again the
argument doesn't apply.)

I think it is your description that is unclear, but you are correct.

To try to elaborate, if on a checkerboard you start on a black square...every odd move would land on a red square, and an even move lands on a black square. Since traversing all the squares on an even-squared checkerboard requires an odd number of steps, it must finish at the opposite parity from the starting position. Any board with the same-colored square in the opposite corner cannot be solved if it has an even number of squares. This is the case iff m and n are both even.

The converse should be true as well if there was an odd-numbered board with the opposite corner having the opposite parity. But this never happens because the only odd-numbered boards are constructed with odd x odd dimensions, which always have like parity on opposite corners.

Very elegant solution!

[davar55]

In my original explanation, in my attempt to be concise,
I lost some clarity. Your expansion is all correct.

Now back to the original question: what is f(m,n) for m,n > 0?

We know f(1,n) for all n, f(2,n) for n odd, and f(m,n) for m,n both even.

What about f(3,n)?

[davar55]

What about f(3,n)? Let f(3,n) = g(n).

Orient the grid so that the n dimension is horizontal.
Start in the top left corner.

A path is determined by j >= 0 steps to the right, down one,
j+1 steps to the left, down one, j+1 steps to the right (in the third row),
k >= 1 more steps to the right, up one, left as far as possible, up one,
k steps to the right, followed by completion of a 3 x (n-j-k-1) grid.

So g(n) = sum(j=0 to n-2) { sum(k=1 to n-j-2) { g(n-j-k-1) } }

Solve, using g(1) = g(2) = f(3,1) = f(3,2) = 1.