Câu hỏi 15
Hãy xem xét một hình vuông $3 m \times 3 m$ ca rô, trong đó $m$ là một số nguyên lớn hơn 1. Một con ếch ngồi ở ô góc dưới bên trái $S$ và muốn đến ô $F$ ở góc trên bên phải. Con ếch có thể nhảy từ ô bất kỳ sang ô tiếp theo ở bên phải hoặc ô tiếp theo trở lên.
Một số ô có thể dính và ếch sẽ bị mắc kẹt khi nhảy vào ô đó. Một tập hợp $X$ gồm các ô được gọi là chặn nếu con ếch không thể tiếp cận $F$ từ $S$ khi tất cả các ô của $X$ đều bị dính. Tập chặn là cực tiểu nếu nó không chứa tập chặn nhỏ hơn.
(a) Chứng minh rằng tồn tại tập chặn cực tiểu chứa ít nhất $3 m^{2}-3 m$ ô.
(b) Chứng minh rằng mọi tập chặn cực tiểu đều chứa nhiều nhất $3 m^{2}$ ô.
Lưu ý. Một ví dụ về tập chặn cực tiểu cho $m=2$ được hiển thị bên dưới. Các ô của tập hợp $X$ được đánh dấu bằng các chữ cái $x$.
| | | | | | $F$ |
| :--- | :--- | :--- | :--- | :--- | :--- |
| $x$ | $x$ | | | | |
| | | $x$ | | | |
| | | | $x$ | | |
| | | | | $x$ | |
| $S$ | | $x$ | | | |
Hình minh họa gốc cho ví dụ:
Một số ô có thể dính và ếch sẽ bị mắc kẹt khi nhảy vào ô đó. Một tập hợp $X$ gồm các ô được gọi là chặn nếu con ếch không thể tiếp cận $F$ từ $S$ khi tất cả các ô của $X$ đều bị dính. Tập chặn là cực tiểu nếu nó không chứa tập chặn nhỏ hơn.
(a) Chứng minh rằng tồn tại tập chặn cực tiểu chứa ít nhất $3 m^{2}-3 m$ ô.
(b) Chứng minh rằng mọi tập chặn cực tiểu đều chứa nhiều nhất $3 m^{2}$ ô.
Lưu ý. Một ví dụ về tập chặn cực tiểu cho $m=2$ được hiển thị bên dưới. Các ô của tập hợp $X$ được đánh dấu bằng các chữ cái $x$.
| | | | | | $F$ |
| :--- | :--- | :--- | :--- | :--- | :--- |
| $x$ | $x$ | | | | |
| | | $x$ | | | |
| | | | $x$ | | |
| | | | | $x$ | |
| $S$ | | $x$ | | | |
Hình minh họa gốc cho ví dụ: