Bài 4
Xét một bảng . Đặt một con chuột (hướng lên trên) trong ô góc dưới bên trái và đặt các miếng phô mai vào một số ô khác. Chuột bắt đầu di chuyển: nó đi thẳng, trừ khi gặp một miếng phô mai thì ăn một phần miếng đó, rẽ phải rồi tiếp tục đi thẳng. Gọi một tập các ô có phô mai là tốt nếu trong quá trình này chuột nếm mỗi miếng phô mai đúng một lần rồi rơi khỏi bảng. Chứng minh rằng (a) không có tập tốt nào gồm ô; (b) tồn tại một tập tốt gồm ít nhất ô.
Bước 1 trên 4: Bốn lần rẽ liên tiếp sẽ khép thành một vòng
Phân tích chi tiết
Gọi một ô được thăm là ô mà con chuột bước lên (ô phô mai hoặc ô trống). Nếu con chuột thăm bốn ô phô mai tại bốn bước liên tiếp, nó sẽ rẽ phải bốn lần liên tiếp sau các bước đơn vị, vẽ nên một hình vuông đơn vị khép kín và quay lại đúng ô mà chuỗi này bắt đầu — nhưng mỗi ô phô mai chỉ được thăm một lần, mâu thuẫn. Vậy dãy các ô được thăm không bao giờ chứa bốn lần thăm phô mai liên tiếp.