Đề bài:
Trên một bảng vuông 8x8 lúc đầu có 64 con bọ mỗi con đậu trong một ô 1x1. Sau một tiếng chuông reo, tất cả con bọ cùng nhảy sang một ô 1x1 liền kề có cạnh chung với ô mà nó đang đứng. Sau khi nhảy, mỗi ô 1x1 có thể không có con bọ nào hoặc có một con bọ hoặc có một vài con bọ.
Hỏi sau tiếng chuông đầu tiên có tối đa bao nhiêu ô 1x1 không chứa con bọ nào?
Hướng dẫn giải:
Tô 20 ô màu đỏ trong bảng vuông 8x8 như hình vẽ dưới đây:
Để ý rằng không có một ô vuông 1x1 nào có cạnh chung với cả hai ô vuông 1x1 màu đỏ. Như thế khi hai con bọ đậu ở hai ô màu đỏ khác nhau thì sau một bước sẽ không thể nhảy đến cùng một ô vuông 1x1 được. Do đó sau một tiếng chuông, 20 con bọ đang đậu ở 20 ô màu đỏ sẽ nhảy tới 20 ô vuông 1x1 khác nhau và trên bảng 8x8 luôn có ít nhất 20 ô chứa các con bọ.
Dễ thấy nếu tất cả con bọ ở 44 ô màu trắng đều nhảy vào 20 ô màu đỏ có chung cạnh và bất kỳ 2 con bọ ở hai ô màu đỏ kề nhau đều nhảy đổi chỗ cho nhau thì sau một bước nhảy trên bảng 8x8 có đúng 20 ô chứa các con bọ.
Vậy sau tiếng chuông đầu tiên trên bảng 8x8 có tối đa 64 - 20 = 44 ô không chứa con bọ nào.
Trần Phương