Hướng tới kỳ thi Vietnam TST 2014

**Fool's theorem** · 28-01-2014, 02:09 PM

Bài 5
Chuyển bài toán về thành đếm số dãy nhị phân gồm $m$ số $1$ và $n$ số $0$ là $a_1,...a_{m+n}$ thỏa mãn với mọi $i \in {1,2,...,m+n}$ thì dãy con $a_1,a_2,...,a_i$ chứa nhiều số $1$ hơn hoặc bằng số $0$. Gọi dãy như vậy là dãy có tính chất “đẹp”
Đầu tiên ta có dãy nhị phân gồm $m$ số $1$ và $n$ số $0$ là $a_1,...a_{m+n}$ là số cách chọn $m$ vị trí cho số 1 trong $m+n$ vị trí và bằng $ \binom{m+n}{m} $
Tiếp theo ta có nhận xét là
Xét một nhị phân gồm $m$ số $1$ và $n$ số $0$ là $a_1,...a_{m+n}$, dãy này có $m+n$ hoán vị vòng quanh trên đường tròn ($a_1,...a_{m+n}$, $a_2,a_3...a_{m+n},a_1$, $a_3,a_4...a_{m+n},a_1,a_2$,...)
Số hoán vị vòng quanh có tính chất “đẹp” là $m-n$
Thật vậy xếp dãy $a_1,...a_{m+n}$ lên vòng tròn, các hoán vị vòng quanh được lấy theo chiều kim đồng hồ. Ta sẽ bỏ các cặp $1,0$ (Số $1$ đứng trước số $0$ theo chiều kim đồng hồ). Việc này không ảnh hưởng đến tính “đẹp” của các hoán vị vòng quanh và do không có hoán vị “đẹp” nào bắt đầu bằng số $0$ nên việc bỏ các cặp này không ảnh hưởng đến số hoán vị “đẹp”. Do $m \geq n $ nên luôn có ít nhất 1 cặp như vậy và ta cứ bỏ đến khi nào còn $m-n$ số $1$ và không còn số $0$, tức là ta có $m-n$ hoán vị đẹp.
Áp dụng NX này vào thì số dãy thỏa mãn là $\frac{m-n}{m+n} \binom{m+n}{m}$ (Nếu xét gộp tất cả các dãy trùng nhau qua hoán vị vòng quanh thành 1 dãy thì có $\frac{1}{m+n} \binom{m+n}{m}$ dãy, mỗi dãy như vậy khi xét các hoán vị vòng quanh thì sinh ra $m-n$ dãy “đẹp”)

28-01-2014, 02:09 PM	#11
Fool's theorem +Thành Viên Danh Dự+ Tham gia ngày: Oct 2012 Đến từ: T1 K46 Chuyên ĐHSP Hà Nội Bài gởi: 187 Thanks: 42 Thanked 192 Times in 101 Posts	Bài 5 Chuyển bài toán về thành đếm số dãy nhị phân gồm $m$ số $1$ và $n$ số $0$ là $a_1,...a_{m+n}$ thỏa mãn với mọi $i \in {1,2,...,m+n}$ thì dãy con $a_1,a_2,...,a_i$ chứa nhiều số $1$ hơn hoặc bằng số $0$. Gọi dãy như vậy là dãy có tính chất “đẹp” Đầu tiên ta có dãy nhị phân gồm $m$ số $1$ và $n$ số $0$ là $a_1,...a_{m+n}$ là số cách chọn $m$ vị trí cho số 1 trong $m+n$ vị trí và bằng $ \binom{m+n}{m} $ Tiếp theo ta có nhận xét là Xét một nhị phân gồm $m$ số $1$ và $n$ số $0$ là $a_1,...a_{m+n}$, dãy này có $m+n$ hoán vị vòng quanh trên đường tròn ($a_1,...a_{m+n}$, $a_2,a_3...a_{m+n},a_1$, $a_3,a_4...a_{m+n},a_1,a_2$,...) Số hoán vị vòng quanh có tính chất “đẹp” là $m-n$ Thật vậy xếp dãy $a_1,...a_{m+n}$ lên vòng tròn, các hoán vị vòng quanh được lấy theo chiều kim đồng hồ. Ta sẽ bỏ các cặp $1,0$ (Số $1$ đứng trước số $0$ theo chiều kim đồng hồ). Việc này không ảnh hưởng đến tính “đẹp” của các hoán vị vòng quanh và do không có hoán vị “đẹp” nào bắt đầu bằng số $0$ nên việc bỏ các cặp này không ảnh hưởng đến số hoán vị “đẹp”. Do $m \geq n $ nên luôn có ít nhất 1 cặp như vậy và ta cứ bỏ đến khi nào còn $m-n$ số $1$ và không còn số $0$, tức là ta có $m-n$ hoán vị đẹp. Áp dụng NX này vào thì số dãy thỏa mãn là $\frac{m-n}{m+n} \binom{m+n}{m}$ (Nếu xét gộp tất cả các dãy trùng nhau qua hoán vị vòng quanh thành 1 dãy thì có $\frac{1}{m+n} \binom{m+n}{m}$ dãy, mỗi dãy như vậy khi xét các hoán vị vòng quanh thì sinh ra $m-n$ dãy “đẹp”) __________________ Hope against hope. thay đổi nội dung bởi: Fool's theorem, 28-01-2014 lúc 02:16 PM