mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2006-04-18, 23:26   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

5·7·112 Posts
Default 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?
davar55 is offline   Reply With Quote
Old 2006-04-18, 23:54   #2
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32×112 Posts
Default

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
Wacky is offline   Reply With Quote
Old 2006-04-19, 00:01   #3
davar55
 
davar55's Avatar
 
May 2004
New York City

5×7×112 Posts
Default

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
davar55 is offline   Reply With Quote
Old 2006-04-19, 00:47   #4
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default

Given m,n > 0.
Is there a solution for ANY grid of the form 2*m, 2*n ?
Wacky is offline   Reply With Quote
Old 2006-04-19, 05:40   #5
drew
 
drew's Avatar
 
Jun 2005

2×191 Posts
Default

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
drew is offline   Reply With Quote
Old 2006-04-19, 12:21   #6
davar55
 
davar55's Avatar
 
May 2004
New York City

5·7·112 Posts
Default

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.
davar55 is offline   Reply With Quote
Old 2006-04-19, 15:01   #7
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32×112 Posts
Default

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
Wacky is offline   Reply With Quote
Old 2006-04-19, 16:14   #8
davar55
 
davar55's Avatar
 
May 2004
New York City

5·7·112 Posts
Default

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
davar55 is offline   Reply With Quote
Old 2006-04-19, 16:56   #9
drew
 
drew's Avatar
 
Jun 2005

1011111102 Posts
Default

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
drew is offline   Reply With Quote
Old 2006-04-19, 17:50   #10
davar55
 
davar55's Avatar
 
May 2004
New York City

5×7×112 Posts
Default

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 is offline   Reply With Quote
Old 2006-04-19, 18:16   #11
davar55
 
davar55's Avatar
 
May 2004
New York City

5×7×112 Posts
Default

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
davar55 is offline   Reply With Quote
Reply

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 2017-11-04 17:55
SQL puzzle Prime95 Programming 1 2017-05-13 16:01
A combinatorial problem xilman Math 18 2010-03-11 13:49
4 4s puzzle henryzz Puzzles 4 2007-09-23 07:31
Dot puzzle nibble4bits Puzzles 37 2006-02-27 09:35

All times are UTC. The time now is 17:45.


Thu Aug 11 17:45:08 UTC 2022 up 35 days, 12:32, 3 users, load averages: 1.34, 1.30, 1.27

Powered by vBulletin® Version 3.8.11
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.

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