2
$\begingroup$

In a problem set about various topics on combinatorics, geometry and algebra, I found this one

There is a $6\times6$ grid, each square filled with a grasshopper. After the bell rings, each grasshopper jumps to an adjacent square (A square that shares a side). What is the maximum number of empty squares possible?

Essentially, we need that each empty square is adjacent to an square with one or more grasshopers. Then, we need that the minimum number of non-empty squares.

Edit: My previous solution was fundamentally wrong, because it did not consider that every grasshopper had to move.

$\endgroup$
1
  • $\begingroup$ I believe that you need each square adjacent to a square with one or more grasshoppers (not each empty square). Hence your above solution is incorrect. One solution that works is: all grasshoppers jump into, or within, the second and fifth columns. $\endgroup$ Commented Sep 13, 2013 at 4:16

2 Answers 2

Reset to default
3
$\begingroup$

The answer is 12. One way to do it with twelve red squares is in the comments. Consider now the following diagram, made in glorious MS paint. The grasshoppers starting in the twelve marked squares must all end up in different squares after they jump. Hence at least twelve squares must have grasshoppers after the jumping.enter image description here

$\endgroup$
2
  • $\begingroup$ Thank you, your solution is short and sweet(especially for the glorious MS paint). So after we have our solution, I think that wandering about the number of ways to configure those razor-blade-like areas of influence is an interesting question, too :) $\endgroup$ Commented Sep 13, 2013 at 4:41
  • $\begingroup$ Could this proof be made more rigorous? $\endgroup$ Commented Dec 22, 2024 at 17:24
2
$\begingroup$

A $6\times 6$ grid contains $36$ squares. The maximum number of grasshoppers that can end up in any square after the jumping is $4$ (each square has $4$ sides). So the minimum number of full squares is $9$. This cannot be achieved because a grasshopper in one of the corners can only jump to an edge square, and that edge square can only end up with at most $3$ grasshoppers, since it has an edge on the side of the large square.

But I may be misinterpreting the question, because in your diagram I can't see where the grasshoppers which started in the red squares on the bottom edge have ended up?

$\endgroup$
1
  • $\begingroup$ My solution was wrong, I somehow overlooked that all the way. Thank you for pointing it. $\endgroup$ Commented Sep 13, 2013 at 4:36

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.