MathLabs

Bài 4

Xét một bảng 32×3232\times32. Đặ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 888888 ô; (b) tồn tại một tập tốt gồm ít nhất 666666 ô.
Bước 4 trên 4: Lặp năm lần đến kích thước 32
Bước trướcBước tiếp
∣L1∣=3, ∣L2∣=11, ∣L3∣=43, ∣L4∣=171, ∣L5∣=683≥666|L_1|=3,\ |L_2|=11,\ |L_3|=43,\ |L_4|=171,\ |L_5|=683\ge666
Phân tích chi tiết

Vì 32=2532=2^5, áp dụng công thức truy hồi bốn lần từ ∣L1∣=3|L_1|=3 cho ∣L2∣=4⋅3−1=11|L_2|=4\cdot3-1=11, ∣L3∣=4⋅11−1=43|L_3|=4\cdot11-1=43, ∣L4∣=4⋅43−1=171|L_4|=4\cdot43-1=171, ∣L5∣=4⋅171−1=683|L_5|=4\cdot171-1=683. Ô L5L_5 là một cách sắp xếp 32×3232\times32 trong đó con chuột vào tại ô dưới-trái hướng lên trên, và các ô phô mai của nó tạo thành một tập tốt gồm 683≥666683\ge666 ô.