Câu hỏi 79
Xét một bảng ô vuông kích thước $3m\times3m$, trong đó $m$ là số nguyên lớn hơn $1$. Một con ếch đứng ở ô góc dưới bên trái $S$ và muốn đến ô góc trên bên phải $F$. Từ mỗi ô, ếch có thể nhảy sang ô kề bên phải hoặc ô kề phía trên.
Một số ô có thể dính, và ếch bị mắc kẹt ngay khi nhảy vào ô như vậy. Tập ô $X$ được gọi là tập chặn nếu ếch không thể đi từ $S$ tới $F$ khi tất cả các ô của $X$ đều dính. Một tập chặn là tối tiểu nếu nó không chứa một tập chặn nhỏ hơn.
a. Chứng minh rằng tồn tại một tập chặn tối tiểu có ít nhất $3m^2-3m$ ô.
b. Chứng minh rằng mọi tập chặn tối tiểu có nhiều nhất $3m^2$ ô.
Chú ý. Dưới đây là một ví dụ về tập chặn tối tiểu với $m=2$. Các ô của $X$ được đánh dấu bằng chữ $x$.
| | | | | | $F$ |
| :--- | :--- | :--- | :--- | :--- | :--- |
| $x$ | $x$ | | | | |
| | | $x$ | | | |
| | | | $x$ | | |
| | | | | $x$ | |
| $S$ | | $x$ | | | |
Một số ô có thể dính, và ếch bị mắc kẹt ngay khi nhảy vào ô như vậy. Tập ô $X$ được gọi là tập chặn nếu ếch không thể đi từ $S$ tới $F$ khi tất cả các ô của $X$ đều dính. Một tập chặn là tối tiểu nếu nó không chứa một tập chặn nhỏ hơn.
a. Chứng minh rằng tồn tại một tập chặn tối tiểu có ít nhất $3m^2-3m$ ô.
b. Chứng minh rằng mọi tập chặn tối tiểu có nhiều nhất $3m^2$ ô.
Chú ý. Dưới đây là một ví dụ về tập chặn tối tiểu với $m=2$. Các ô của $X$ được đánh dấu bằng chữ $x$.
| | | | | | $F$ |
| :--- | :--- | :--- | :--- | :--- | :--- |
| $x$ | $x$ | | | | |
| | | $x$ | | | |
| | | | $x$ | | |
| | | | | $x$ | |
| $S$ | | $x$ | | | |