Câu hỏi 75
Cho một bảng $2n \times 2n$; một tập con $S$ các ô của bảng được gọi là kiểu mê cung nếu nó có các tính chất sau:
- từ mỗi ô của $S$ có thể đi tới mọi ô khác của $S$ chỉ bằng cách di chuyển từ ô của $S$ sang ô kề của $S$ (theo chiều ngang hoặc dọc, tức là có chung một cạnh với ô xuất phát);
- không thể, xuất phát từ một ô của $S$, quay lại chính ô đó chỉ bằng cách di chuyển sang các ô kề thuộc $S$ mà không bao giờ đi qua cùng một cạnh hai lần.
a. Chứng minh rằng nếu $S$ là kiểu mê cung thì $S$ không thể có nhiều hơn $3n^{2}$ ô;
b. Chỉ ra một tập kiểu mê cung gồm 12 ô khi $n=2$.
c. Ta gọi chu vi của $S$ là số cạnh kề với ít nhất một ô của $S$ nhưng không kề với hai ô của $S$. Nếu $S$ là kiểu mê cung và gồm $k$ ô thì chu vi của nó bằng bao nhiêu?
d. Chứng minh rằng không tồn tại tập kiểu mê cung gồm 300 ô khi $n=10$.
- từ mỗi ô của $S$ có thể đi tới mọi ô khác của $S$ chỉ bằng cách di chuyển từ ô của $S$ sang ô kề của $S$ (theo chiều ngang hoặc dọc, tức là có chung một cạnh với ô xuất phát);
- không thể, xuất phát từ một ô của $S$, quay lại chính ô đó chỉ bằng cách di chuyển sang các ô kề thuộc $S$ mà không bao giờ đi qua cùng một cạnh hai lần.
a. Chứng minh rằng nếu $S$ là kiểu mê cung thì $S$ không thể có nhiều hơn $3n^{2}$ ô;
b. Chỉ ra một tập kiểu mê cung gồm 12 ô khi $n=2$.
c. Ta gọi chu vi của $S$ là số cạnh kề với ít nhất một ô của $S$ nhưng không kề với hai ô của $S$. Nếu $S$ là kiểu mê cung và gồm $k$ ô thì chu vi của nó bằng bao nhiêu?
d. Chứng minh rằng không tồn tại tập kiểu mê cung gồm 300 ô khi $n=10$.