mersenneforum.org Geometric Combinatorial Puzzle
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2006-04-18, 23:26 #1 davar55     May 2004 New York City 423510 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?
 2006-04-18, 23:54 #2 Wacky     Jun 2003 The Texas Hill Country 32×112 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 2006-04-18 at 23:56
 2006-04-19, 00:01 #3 davar55     May 2004 New York City 5×7×112 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 2006-04-19 at 00:02
 2006-04-19, 00:47 #4 Wacky     Jun 2003 The Texas Hill Country 44116 Posts Given m,n > 0. Is there a solution for ANY grid of the form 2*m, 2*n ?
2006-04-19, 05:40   #5
drew

Jun 2005

2·191 Posts

Quote:
 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.

Last fiddled with by drew on 2006-04-19 at 05:41

 2006-04-19, 12:21 #6 davar55     May 2004 New York City 5·7·112 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.
 2006-04-19, 15:01 #7 Wacky     Jun 2003 The Texas Hill Country 32×112 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 (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). Last fiddled with by Wacky on 2006-04-19 at 15:05
 2006-04-19, 16:14 #8 davar55     May 2004 New York City 5·7·112 Posts 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.) Last fiddled with by davar55 on 2006-04-19 at 16:17
2006-04-19, 16:56   #9
drew

Jun 2005

2·191 Posts

Quote:
 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!

Last fiddled with by drew on 2006-04-19 at 16:58

 2006-04-19, 17:50 #10 davar55     May 2004 New York City 5·7·112 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)?
 2006-04-19, 18:16 #11 davar55     May 2004 New York City 5×7×112 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 (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. Last fiddled with by davar55 on 2006-04-19 at 18:25

 Similar Threads Thread Thread Starter Forum Replies Last Post danupp And now for something completely different 2 2017-11-04 17:55 Prime95 Programming 1 2017-05-13 16:01 xilman Math 18 2010-03-11 13:49 henryzz Puzzles 4 2007-09-23 07:31 nibble4bits Puzzles 37 2006-02-27 09:35

All times are UTC. The time now is 01:42.

Sat Jun 25 01:42:27 UTC 2022 up 71 days, 23:43, 0 users, load averages: 1.39, 1.08, 1.01

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔