An Insect Problem
A board is divided into unit squares.
In every square there is an arrow that points up, down, left or right. The board square is surrounded by a wall, except for the right side of the top right corner square.
An insect is placed in one of the squares. Each second, the insect moves one unit in the direction of the arrow in its square. When the insect moves, the arrow of the square it was in moves 90 degrees clockwise.
If the indicated movement cannot be done, the insect does not move that second, but the arrow in its squares does move.
Find the number of ways in which the insect is trapped in the chessboard .
The answer is 0.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Let's prove that no matter of how the arrows are aligned or where the insect is placed, it always leaves the board.
What if this is not true ?, i.e., the insect is trapped. Let's prove this by contradiction .So first let's assume that the insect is trapped .
In this case, the insect makes an infinite number of steps in the board. Since there are only 1 0 0 2 squares, by the infinite pigeonhole principle, there is a square that is visited an infinite number of times. Each time the insect goes through this square, the arrow in there moves.
Thus, the insect was also an infinite number of times in each of the neighboring squares. By repeating this argument, the insect also visited an infinite number of times each of the neighbors of those squares. In this way we conclude that the insect visited an infinite number of times each square in the board, in particular the top right corner. This is impossible, because when that arrow points to the right the insect leaves the board. This contradicts our assumption that the insect is trapped, hence our assumption is wrong .
I think that we might be able to solve this question by using only the finite version of the pigeonhole principle. Can anyone shed any light on it ?
You might want to read this wiki by @Mursalin Habib