20060418, 23:26  #1 
May 2004
New York City
108B_{16} Posts 
Geometric Combinatorial Puzzle
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? 
20060418, 23:54  #2 
Jun 2003
The Texas Hill Country
3^{2}·11^{2} Posts 
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. Last fiddled with by Wacky on 20060418 at 23:56 
20060419, 00:01  #3 
May 2004
New York City
5×7×11^{2} Posts 
Yes, in certain cases, such as 2 x n where n is even,
the answer is zero possible paths. This is the degenerate case. Last fiddled with by davar55 on 20060419 at 00:02 
20060419, 00:47  #4 
Jun 2003
The Texas Hill Country
2101_{8} Posts 
Given m,n > 0.
Is there a solution for ANY grid of the form 2*m, 2*n ? 
20060419, 05:40  #5  
Jun 2005
2·191 Posts 
Quote:
I thought I proved it to myself a couple of times, but then realized I overlooked something. Last fiddled with by drew on 20060419 at 05:41 

20060419, 12:21  #6 
May 2004
New York City
108B_{16} Posts 
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. 
20060419, 15:01  #7 
Jun 2003
The Texas Hill Country
10001000001_{2} Posts 
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 (m2,n). Similarly, (II) a solution for (m, n>2) implies a solution for (m, n2). 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). Last fiddled with by Wacky on 20060419 at 15:05 
20060419, 16:14  #8 
May 2004
New York City
10213_{8} Posts 
No, the tilingparitycoloring 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. Rereading 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.) Last fiddled with by davar55 on 20060419 at 16:17 
20060419, 16:56  #9  
Jun 2005
101111110_{2} Posts 
Quote:
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 evensquared checkerboard requires an odd number of steps, it must finish at the opposite parity from the starting position. Any board with the samecolored 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 oddnumbered board with the opposite corner having the opposite parity. But this never happens because the only oddnumbered boards are constructed with odd x odd dimensions, which always have like parity on opposite corners. Very elegant solution! Last fiddled with by drew on 20060419 at 16:58 

20060419, 17:50  #10 
May 2004
New York City
1000010001011_{2} Posts 
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)? 
20060419, 18:16  #11 
May 2004
New York City
5·7·11^{2} Posts 
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 (njk1) grid. So g(n) = sum(j=0 to n2) { sum(k=1 to nj2) { g(njk1) } } Solve, using g(1) = g(2) = f(3,1) = f(3,2) = 1. Last fiddled with by davar55 on 20060419 at 18:25 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prime Numbers as a Function of a Geometric Progression  danupp  And now for something completely different  2  20171104 17:55 
SQL puzzle  Prime95  Programming  1  20170513 16:01 
A combinatorial problem  xilman  Math  18  20100311 13:49 
4 4s puzzle  henryzz  Puzzles  4  20070923 07:31 
Dot puzzle  nibble4bits  Puzzles  37  20060227 09:35 