Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

$P_n\leq 6,75^n$


  • Please log in to reply
Chủ đề này có 1 trả lời

#1 the unknown

the unknown

    Thượng sĩ

  • Thành viên
  • 208 Bài viết
  • Giới tính:Nam
  • Đến từ:Nothingness
  • Sở thích:unknown

Đã gửi 11-09-2017 - 15:24

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$.


$\texttt{If you don't know where you are going, any road will get you there}$


#2 redfox

redfox

    Trung sĩ

  • Thành viên
  • 100 Bài viết
  • Giới tính:Nam
  • Đến từ:PTNK - ĐHQG TPHCM
  • Sở thích:wild animal, furry

Đã gửi 20-09-2017 - 19:08

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





0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh