Câu hỏi 93
Cho $m \gt 1$ là một số nguyên dương. Một con chuột muốn đi từ ô dưới cùng bên trái $a$ đến ô trên cùng bên phải $b$ của một bàn cờ $3m \times 3m$. Mỗi bước con chuột có thể chạy sang ô ngay bên phải hoặc ô ngay phía trên ô nó đang đứng. Tuy nhiên, trên bàn cờ có một số ô đặt bẫy keo dính chuột; nếu con chuột chạy vào ô có bẫy keo thì nó bị dính lại và không thể di chuyển nữa.
Với một tập $X$ gồm các ô của bàn cờ, ta nói $X$ chặn được con chuột khi và chỉ khi, nếu đặt bẫy keo vào mọi ô của $X$ thì con chuột không thể đi từ $a$ đến $b$. Ta nói $X$ là tối tiểu khi và chỉ khi $X$ chặn được con chuột, nhưng bỏ đi bất kỳ một ô nào của $X$ thì không còn chặn được nữa. Chứng minh rằng:
(i) mọi tập tối tiểu chặn được con chuột có không quá $3m^2$ ô;
(ii) tồn tại một tập tối tiểu chặn được con chuột có ít nhất $3m^2 - 3m$ ô.
Với một tập $X$ gồm các ô của bàn cờ, ta nói $X$ chặn được con chuột khi và chỉ khi, nếu đặt bẫy keo vào mọi ô của $X$ thì con chuột không thể đi từ $a$ đến $b$. Ta nói $X$ là tối tiểu khi và chỉ khi $X$ chặn được con chuột, nhưng bỏ đi bất kỳ một ô nào của $X$ thì không còn chặn được nữa. Chứng minh rằng:
(i) mọi tập tối tiểu chặn được con chuột có không quá $3m^2$ ô;
(ii) tồn tại một tập tối tiểu chặn được con chuột có ít nhất $3m^2 - 3m$ ô.