|
|
|
Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé ! * Quy định về việc viết bài trong diễn đàn MathScope * Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây |
| Ðiều Chỉnh | Xếp Bài |
16-02-2012, 01:31 PM | #1 |
Administrator | Về bài toán tổ hợp khó nhất thi VN TST 2001 Trong kì thi VN TST 2001, có hai bài Tổ hợp khá thú vị. Bài đầu tiên là bài 3 của ngày 1 về các cặp nam-nữ trong CLB. Bài này trong sách của thầy Vũ Đình Hoà có một cách giải rất "khiếp" theo lý thuyết graph - đồ thị lưỡng phân; tuy nhiên, trên mathlinks.ro có một cách tiếp cận nhẹ nhàng hơn theo nguyên lí Dirichlet. Bài toán mà mình muốn đề cập trong bài viết này là về bài 5 trong ngày 2. Bài toán về tô màu điểm trong không gian Oxyz. Có thể phát biểu ban đầu của bài toán rất đơn giản, dễ hiểu nhưng trên thực tế, nó đã dựa trên 2 định lí khó của số học- tổ hợp và đây cũng chính là dạng tổng quát cho 1 bài trong IMO Shortlist 1988. Dưới đây là đề bài và lời giải đầy đủ cho bài toán đó. Mời mọi người tham khảo thử và đóng góp ý kiến. Đề bài. Cho số nguyên dương $n$ lớn hơn 1. Trong không gian vuông góc $Oxyz$, gọi T là tập hợp tất cả các điểm có tọa độ là $(x,y,z)$ với $x,y,z$ là các số nguyên dương thỏa mãn $1\le x,y,z\le n$. Tô màu tất cả các điểm thuộc tập hợp T sao cho: nếu điểm $A({{x}_{0}},{{y}_{0}},{{z}_{0}})$ được tô màu thì những điểm có dạng $B({{x}_{1}},{{y}_{1}},{{z}_{1}})$ với ${{x}_{1}}\le {{x}_{0}},{{y}_{1}}\le {{y}_{0}},{{z}_{1}}\le {{z}_{0}}$ sẽ không được tô màu. Tìm giá trị lớn nhất các điểm được tô màu thỏa mãn điều kiện trên. Lời giải. Nếu hai bộ $(x,y,z)$ và $({x}',{y}',{z}')$ thỏa mãn $x\le {x}',y\le {y}',z\le {z}'$ thì ta nói bộ $({x}',{y}',{z}')$ trội hơn bộ $(x,y,z)$, ta quy ước gọi hai bộ đó là hai bộ trội. Ta có thể phát biểu bài toán dưới dạng tương đương là: Tìm số lớn nhất $S(n)$ tất cả các bộ $(x,y,z)$ thỏa mãn $0\le x,y,z\le n-1$ sao cho trong đó, không tồn tại hai bộ trội. (thay $1\to 0,n\to n-1$). Rõ ràng với hai bộ trội bất kì thì tổng của chúng là phân biệt vì nếu có hai bộ trội như trên và tổng bằng nhau thì $x+y+z\le {x}'+{y}'+{z}'$ và đẳng thức xảy ra khi $x={x}',y={y}',z={z}'$, vô lí. Tổng lớn nhất có thể có của các bộ này là $3(n-1)$ và tổng nhỏ nhất là 0. Ta sẽ chứng minh các mệnh đề sau với hai trường hợp $n$ chẵn và lẻ. (1) Số các bộ $(x,y,z)$ thỏa mãn $ x+y+z=\left\lceil \frac{3(n-1)}{2} \right\rceil $ và $0\le x,y,z\le n-1$ là $\left\lfloor \frac{3{{n}^{2}}+1}{4} \right\rfloor $. (2) Với mọi cách chọn $\left\lfloor \frac{3{{n}^{2}}+1}{4} \right\rfloor +1$ đều tồn tại hai bộ mà bộ này là bộ trội của bộ kia. Ta xét hai trường hợp: *Nếu $n=2k,k\in \mathbb{N}$ thì ta sẽ đếm số bộ thỏa $x+y+z=\left\lceil \frac{3(2k-1)}{2} \right\rceil =3k-1$ và $1\le x,y,z\le 2k-1$. + Nếu $x=0$ thì $y+z=3k-1$ và $k\le y\le 2k-1$: có $k$ nghiệm thỏa. + Nếu $x=k$ thì $y+z=2k-1$ và $0\le y\le 2k-1$: có $2k$ nghiệm thỏa. + Nếu $x=i,1\le i\le k-1$ thì $y+z=3k-i$ và $k-i\le y\le 2k-1$: có $k+i$ nghiệm thỏa. Do đó, số nghiệm tổng cộng là $k+2k+2\left( \sum\limits_{i=k+1}^{2k-1}{i} \right)=3k+\frac{2k(2k-1)-k(k+1)}{2}=3{{k}^{2}}$. Rõ ràng $\left\lfloor \frac{3{{(2k)}^{2}}+1}{4} \right\rfloor =3{{k}^{2}}$. Mệnh đề (1) được chứng minh. Gọi $A$ là tập hợp tất cả các bộ ba $(x,y,z)$ với $0\le x,y,z\le n-1$ hay $A=\left\{ (x,y,z)|0\le x,y,z\le n-1 \right\}$ Giả sử $B\subset A$ là một tập con có đúng $3{{k}^{2}}$ phần tử. Ta cần chứng minh rằng trong $B$, tồn tại ít nhất hai bộ mà bộ này là bộ trội của bộ kia. Ta sẽ chứng minh mệnh đề (2) bằng cách xây dựng các tập con sau đây của tập tất cả các bộ ba: $\begin{align} & {{C}_{1}}=\left\{ (x,y,z)\in A|x=0\vee y=2k-1 \right\} \\ & {{C}_{2}}=\left\{ (x,y,z)\in A|\left( x=1\wedge y\le 2k-2 \right)\vee \left( x\ge 1\wedge y=2k-2 \right) \right\} \\ & {{C}_{2}}=\left\{ (x,y,z)\in A|\left( x=2\wedge y\le 2k-3 \right)\vee \left( x\ge 2\wedge y=2k-3 \right) \right\} \\ & ... \\ & {{C}_{k}}=\left\{ (x,y,z)\in A|\left( x=k-1\wedge y\le k \right)\vee \left( x\ge k-1\wedge y=k \right) \right\} \\ \end{align}$ Đặt $C=\bigcup\limits_{i=1}^{k}{{{C}_{i}}}$ và $D=A\backslash C=\left\{ (x,y,z)\in A|x\ge k\wedge y\le k-1 \right\}$. Xét các tập hợp ${{C}_{i,j}}=\left\{ (x,y,z)\in {{C}_{i}}|z=j \right\}$ trong đó $1\le i\le k,0\le j\le 2k-1$. Rõ ràng có tất cả $2{{k}^{2}}$ tập hợp như thế và chúng là các phân hoạch của $C$. Xét các tập hợp ${{D}_{p,q}}=\left\{ (x,y,z)\in D|x=p\wedge y=q \right\}$ trong đó $k\le p\le 2k-1,0\le q\le k-1$. Rõ ràng có tất cả ${{k}^{2}}$ tập hợp như thế là chúng là các phân hoạch của $D.$ Ta có hai trường hợp sau: - Nếu $\left| B\cap C \right|\ge 2{{k}^{2}}$ phần tử thì theo nguyên lí Dirichlet, tồn tại hai bộ thuộc cùng một tập ${{C}_{i,j}}$. Giả sử hai phần tử $({{x}_{1}},{{y}_{1}},{{z}_{1}}),({{x}_{2}},{{y}_{ 2}},{{z}_{2}})$ cùng thuộc tập ${{C}_{i,j}}=\left\{ (x,y,z)\in {{C}_{i}}|z=j \right\}$. Rõ ràng, ta thấy rằng ${{z}_{1}}={{z}_{2}}=j$ và có ba trường hợp như sau: + Nếu ${{x}_{1}}={{x}_{2}}=i-1$ thì ${{y}_{1}},{{y}_{2}}\le i$ nên trong hai bộ trên, phải tồn tại một bộ là bộ trội của bộ kia. + Nếu ${{x}_{1}}={{x}_{2}}=i$ thì ${{y}_{1}},{{y}_{2}}\le i-1$ nên trong hai bộ trên, phải tồn tại một bộ là bộ trội của bộ kia. + Nếu ${{x}_{1}}=i,{{x}_{2}}\le i-1$ thì ${{y}_{1}}\le i-1,{{y}_{2}}=i$ nên dễ thấy rằng bộ $({{x}_{1}},{{y}_{1}},{{z}_{1}})$ trội hơn bộ $({{x}_{2}},{{y}_{2}},{{z}_{2}}).$ - Nếu $\left| B\cap C \right|<2{{k}^{2}}$ thì $\left| B\cap D \right|>{{k}^{2}}$ thì do $D$ chỉ có ${{k}^{2}}$ phần tử nên tồn tại hai bộ thuộc $D,$ lập luận tương tự trên, ta thấy rằng $B$ chứa hai bộ mà bộ này là bộ trội của bộ kia. Như thế, hai mệnh đề đã được chứng minh trong trường hợp $n$ chẵn. * Nếu $n=2k+1,k\in \mathbb{N}$, cách chứng minh hoàn toàn tương tự. Tóm lại, trong mọi trường hợp, hai mệnh đề ban đầu là đúng. Từ đó suy ra ta chỉ cần tô màu tất cả các điểm nằm trên mặt phẳng \[x+y+z=\left\lceil \frac{3(n-1)}{2} \right\rceil \] thì số điểm tô được sẽ lớn nhất và là $\left\lfloor \frac{3{{n}^{2}}+1}{4} \right\rfloor $. Nhận xét. Để hiểu rõ hơn bản chất của lời giải trên, ta cần phải xem xét hai định lí nổi tiếng sau: *Định lí de Bruijn-Tengbergen-Kruyswijk: Với mỗi số nguyên dương $n=p_{1}^{{{a}_{1}}}\cdot p_{2}^{{{a}_{2}}}\cdot p_{3}^{{{a}_{3}}}\cdot ...\cdot p_{k}^{{{a}_{k}}}$, tổng $t(n)={{a}_{1}}+{{a}_{2}}+{{a}_{3}}+...+{{a}_{k}}$ được gọi là bậc của n. Chứng minh rằng tập hợp $S$gồm các ước dương của $n$, có bậc là $\left\lfloor \frac{t(n)}{2} \right\rfloor $ sẽ không chứa hai phần tử nào mà phần tử này chia hết cho phần tử kia. *Định lí Dilworth: Một thứ tự bộ phận yếu trên tập P là quan hệ hai ngôi giữa các phần tử trong P. Ta nói hai phần tử $x,y$ so sánh được nếu $x<y$ hoặc $x>y$. Một xích (chain) là một tập hợp Y là con của P sao cho bất kì phần tử nào trong Y đều so sánh được. Nếu không có hai phần tử khác nhau nào của Y so sánh được thì ta có đối xích (antichain). Khi đó, nếu xét $\left| P \right|\ge rs+1$ thì tồn tại xích có kích thước là r hoặc đối xích có kích thước là s. Các tài liệu phát biểu-chứng minh của chúng có thể tìm được khá nhiều trên mạng. Có lẽ 2 kết quả này chính là cơ sở để xây dựng nên bài toán trên. Rõ ràng, bài toán này có nhiều hướng phát triển và có thể liên hệ được với nhiều vấn đề số học-tổ hợp khác. Các bạn thử tìm hiểu thử xem! ******************* Thông qua bài toán này, mình cảm nhận được một điều thế này và mình muốn chia sẻ với mọi người! Trong cuộc sống này, mỗi chúng ta cần tạo ra một điều đặc biệt gì đó riêng cho bản thân mình. Nếu để thua kém một người khác về mọi mặt, như các điểm không được tô màu trong không gian Oxyz kia, thì ta cần phải suy nghĩ lại và cố gắng phấn đấu để thay đổi. __________________ Sự im lặng của bầy mèo |
The Following 15 Users Say Thank You to huynhcongbang For This Useful Post: | 251295 (01-03-2012), conami (17-02-2012), Highschoolmath (16-02-2012), iklike (16-02-2012), n.v.thanh (16-02-2012), ngocson_dhsp (21-02-2012), nhat7d (16-02-2012), quocbaoct10 (01-12-2013), sang89 (16-02-2012), sine (16-02-2012), thanhorg (24-10-2012), thinhptnk (08-04-2012), Thmcuongvn (03-05-2014), tranghieu95 (01-03-2012), Trànvănđức (05-11-2012) |
16-02-2012, 02:17 PM | #2 |
Moderator Tham gia ngày: Apr 2008 Đến từ: Hàm Dương-Đại Tần Bài gởi: 698 Thanks: 247 Thanked 350 Times in 224 Posts | Bài viết rất hay và độc đáo, đọc cách giải này xong tự dưng lại đâm ra thích Tổ hợp. Tuy nhiên câu nhận xét cuối cùng của Lữ thì đáng bị ném gạch thật. __________________ As long as I live, I shall think only of the Victory...................... thay đổi nội dung bởi: sang89, 16-02-2012 lúc 02:21 PM Lý do: Bỏ bớt cái Quote :)) |
16-02-2012, 02:37 PM | #3 | |
Administrator | Trích:
Chẳng hạn thế này: Trong lớp có một đứa học Toán, Lý, Hoá, Văn, Sử, Địa đều giỏi hơn mình hết thì mình cố luyện tập chơi thể thao giỏi hơn, chơi đàn giỏi hơn nó. Nói chung là phải có ít nhất một cái gì đó nổi bật giữa tập thể thì mới được. Đại loại là thế... __________________ Sự im lặng của bầy mèo | |
The Following 3 Users Say Thank You to huynhcongbang For This Useful Post: |
16-02-2012, 05:37 PM | #4 |
Moderator Tham gia ngày: Nov 2009 Bài gởi: 2,849 Thanks: 2,980 Thanked 2,537 Times in 1,008 Posts | Em move sang chuyên đề. |
29-02-2012, 10:49 PM | #5 |
Administrator | Giờ mới phát hiện Latex của diễn đàn mà xem trên Google Chrome đẹp thật! __________________ Sự im lặng của bầy mèo |
08-04-2012, 09:27 PM | #6 |
+Thành Viên+ Tham gia ngày: Dec 2010 Bài gởi: 22 Thanks: 0 Thanked 1 Time in 1 Post | Chào các bạn,bạn nào có thể tạo cái file pdf để mọi người cùng tải được không,mình xin cảm ơn,bài viết quá hay thay đổi nội dung bởi: 99, 08-04-2012 lúc 09:29 PM Lý do: bỏ trích dẫn quá dài |
Bookmarks |
|
|