Chủ đề này có 1 trả lời

[the unknown]

Với mỗi số nguyên dương $n$,trong lưới ô vuông, ta định nghĩa một $n-$mino là một tập hợp $n$ hình vuông $1\times 1$ liên thông với nhau ( có nghĩa là từ hình vuông này có thể đi đến các hình vuông khác chỉ qua các cạnh ). Hai $n-$mino là giống nhau khi và chỉ khi có một phép tịnh tiến biến mino này thành mino kia. Gọi $P_n$ là số tất cả các $n-$mino khác nhau. Chứng minh rằng $P_n\leq 6,75^n$.

[redfox]

Welcome back, unknown!

Bổ đề: $C_n=\binom{3n}{n}<6,75^n, \forall n\in \mathbb{N}$. $n=1$ đúng và $\frac{C_n}{C_{n-1}}=\frac{3(3n-1)(3n-2)}{2n(2n-1)}<\frac{27}{4}$

Xét tập hợp $D_n$ gồm $3(n-1)$ phần tử $l_2,l_3,...,l_n,u_2,u_3,...,u_n,r_2,r_3,...,r_n$

Xét thuật toán: Với mỗi $n$-mino, xét ô dưới cùng bên trái, đặt số $1$ và một vector hướng lên, đánh dấu ô $1$ chuyển sang bước $1$. Ở bước $i$, từ ô được đặt số $k$ và vector nào đó được đánh dấu ($k$ nhỏ nhất trong các ô được đánh dấu), xét các ô vuông kề với nó và chưa được đặt số, nếu có một ô vuông bên trái (hoặc bên trên, bên phải) ta chọn phần tử $l_k$ (hoặc $u_k, r_k$), đặt các số nguyên tiếp theo vào các ô kề với ô $k$ và chưa được đặt số theo thứ tự trái, trên, phải theo chiều vector của ô $k$, và đặt các vector vào các ô kề với ô $k$ theo hướng từ ô $k$ đến ô đó, sau đó bỏ đánh dấu ô $k$. Sau khi hết ô được đánh dấu, đánh dấu các ô đã được đặt số ở bước $i$ và chuyển sang bước $i+1$ nếu còn ô chưa được điền số. Sau hữu hạn bước (vì $n$-mino liên thông và hữu hạn ô vuông) thì ta chọn được $n-1$ phần tử của $D_n$ (chọn thêm được một phần tử thì thêm một ô được đặt số.

Ta sẽ chứng minh với hai $n$-mino khác nhau ta thu được hai bộ $n-1$ phần tử khác nhau.

Với $n=2$ đúng

Giả sử $n$ đúng. Xét hai $n+1$-mino có cùng một bộ $n$ phần tử của $D_{n+1}$. Xét ô thứ $n+1$ tương ứng với một phần tử $l_n$ hoặc $u_n, r_n$ nào đó, loại ô và phần tử đó đi trong bộ $n$ phần tử ta thu được hai $n$-mino có cùng một bộ $n-1$ phần tử của $D_n$, theo giả thiết quy nạp, hai $n$-mino đó giống nhau, gọi là $n$-mino chung. Chú ý phần tử được loại tương ứng với vị trí của ô thứ $n+1$ so với $n$-mino chung nên vị trí của ô $n+1$ với $n$-mino chung của hai $n+1$-mino chung giống nhau nên hai $n+1$-mino giống nhau.

Vậy ta thu được đơn ánh từ các $n$-mino đến cách chọn $n-1$ phần tử từ $D_n$. Vậy $D_n \leq C_{n-1} <6,75^n$.

Q.E.D

(seem too hard!)

Bài viết đã được chỉnh sửa nội dung bởi redfox: 20-09-2017 - 20:13