Câu hỏi 122
Cho số nguyên $n \geqslant 2$. Một con ếch di chuyển trên một bảng $3n \times 3n$ ô, mỗi lần nhảy từ một ô sang ô nằm ngay phía trên hoặc ngay bên phải nó. Nó muốn đi từ góc dưới bên trái, được đánh dấu $S$, đến góc trên bên phải, được đánh dấu $F$. Không may, một số ô có bẫy, và nếu con ếch nhảy vào một ô như vậy, nó sẽ bị mắc kẹt ở đó.
Một tập các ô có bẫy được gọi là chặn nếu nó ngăn con ếch đi từ ô $S$ đến ô $F$. Một tập chặn được gọi là tối tiểu nếu khi gỡ bẫy khỏi bất kì một ô nào của tập đó, tập còn lại không còn là tập chặn.
Ví dụ, các ô đen của bảng dưới đây tạo thành một tập chặn tối tiểu.
a) Chứng minh rằng tồn tại một tập chặn tối tiểu chứa ít nhất $3n(n-1)$ ô.
b) Chứng minh rằng mọi tập chặn tối tiểu chứa nhiều nhất $3n^{2}$ ô.
Một tập các ô có bẫy được gọi là chặn nếu nó ngăn con ếch đi từ ô $S$ đến ô $F$. Một tập chặn được gọi là tối tiểu nếu khi gỡ bẫy khỏi bất kì một ô nào của tập đó, tập còn lại không còn là tập chặn.
Ví dụ, các ô đen của bảng dưới đây tạo thành một tập chặn tối tiểu.
a) Chứng minh rằng tồn tại một tập chặn tối tiểu chứa ít nhất $3n(n-1)$ ô.
b) Chứng minh rằng mọi tập chặn tối tiểu chứa nhiều nhất $3n^{2}$ ô.