Question

В каждой клетке доски размером 5х5 сидел жук.Затем каждый жук переполз на соседнюю клетку.Докажите, что осталась хотя бы одна пустая клетка.

Answer 1

Раскрасим клетки доски в шахматном порядке так, чтобы черных клеток было 13, а белых 12. Заметим, что после переползания жуки, сидящие на белых клетках, оказались на чёрных клетках, а жуки, сидящие на чёрных клетках – на белых. Так как белых клеток на одну меньше, чем чёрных, после переползания по принципу Дирихле хотя бы одна чёрная клетка окажется пустой.

Answer 2

Proof that at least one empty cell remains after each bug moves to a neighboring cell

To prove that at least one empty cell remains after each bug moves to a neighboring cell on a 5x5 board, we can use a proof by contradiction.

Assume that after each bug moves to a neighboring cell, there are no empty cells left on the board. This means that all 25 cells are occupied by bugs.

Since each bug can only move to a neighboring cell, it follows that each cell must have a neighboring cell that is occupied by a bug. In other words, each cell must have at least one bug adjacent to it.

Now, let's consider the bug in the top-left corner of the board. This bug has only three neighboring cells (top-right, bottom-left, and bottom-right). However, since all cells are occupied by bugs, all three of these neighboring cells must also be occupied by bugs.

We can repeat this reasoning for each bug on the board. For each bug, we can identify its neighboring cells and conclude that all of these neighboring cells must be occupied by bugs as well.

However, this leads to a contradiction. If all neighboring cells of each bug are occupied by bugs, then the total number of bugs on the board would exceed 25, which is not possible.

Therefore, our assumption that there are no empty cells left on the board after each bug moves to a neighboring cell must be false. This means that there must be at least one empty cell remaining on the board after the bugs move.

Thus, we have proven that at least one empty cell remains after each bug moves to a neighboring cell on a 5x5 board.