Diễn Đàn MathScopeDiễn Đàn MathScope
  Diễn Đàn MathScope
Ghi Danh Hỏi/Ðáp Thành Viên Social Groups Lịch Ðánh Dấu Ðã Ðọc

Go Back   Diễn Đàn MathScope > Sơ Cấp > Tổ Hợp > Chuyên Đề

News & Announcements

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é !

* Nội quy MathScope.Org

* Một số quy định chung !

* 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

* Những câu hỏi thường gặp

* Về việc viết bài trong Box Đại học và Sau đại học


Trả lời Gởi Ðề Tài Mới
 
Ðiều Chỉnh Xếp Bài
Old 16-02-2012, 01:31 PM   #1
huynhcongbang
Administrator

 
huynhcongbang's Avatar
 
Tham gia ngày: Feb 2009
Đến từ: Ho Chi Minh City
Bài gởi: 2,413
Thanks: 2,165
Thanked 4,188 Times in 1,381 Posts
Gửi tin nhắn qua Yahoo chát tới huynhcongbang
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.


[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Sự im lặng của bầy mèo
huynhcongbang is offline   Trả Lời Với Trích Dẫn
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)
Old 16-02-2012, 02:17 PM   #2
Highschoolmath
Moderator
 
Highschoolmath's Avatar
 
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.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
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 :))
Highschoolmath is offline   Trả Lời Với Trích Dẫn
Old 16-02-2012, 02:37 PM   #3
huynhcongbang
Administrator

 
huynhcongbang's Avatar
 
Tham gia ngày: Feb 2009
Đến từ: Ho Chi Minh City
Bài gởi: 2,413
Thanks: 2,165
Thanked 4,188 Times in 1,381 Posts
Gửi tin nhắn qua Yahoo chát tới huynhcongbang
Trích:
Nguyên văn bởi Highschoolmath View Post
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.
Hihi, mình thấy cái ý đó cũng đến nổi đâu.
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ế...
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Sự im lặng của bầy mèo
huynhcongbang is offline   Trả Lời Với Trích Dẫn
The Following 3 Users Say Thank You to huynhcongbang For This Useful Post:
Highschoolmath (16-02-2012), nhat7d (16-02-2012), Thmcuongvn (03-05-2014)
Old 16-02-2012, 05:37 PM   #4
n.v.thanh
Moderator
 
n.v.thanh's Avatar
 
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 đề.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
n.v.thanh is offline   Trả Lời Với Trích Dẫn
Old 29-02-2012, 10:49 PM   #5
huynhcongbang
Administrator

 
huynhcongbang's Avatar
 
Tham gia ngày: Feb 2009
Đến từ: Ho Chi Minh City
Bài gởi: 2,413
Thanks: 2,165
Thanked 4,188 Times in 1,381 Posts
Gửi tin nhắn qua Yahoo chát tới huynhcongbang
Trích:
Nguyên văn bởi n.v.thanh View Post
Em move sang chuyên đề.
Giờ mới phát hiện Latex của diễn đàn mà xem trên Google Chrome đẹp thật!
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Sự im lặng của bầy mèo
huynhcongbang is offline   Trả Lời Với Trích Dẫn
Old 08-04-2012, 09:27 PM   #6
quanctt2
+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
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

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
quanctt2 is offline   Trả Lời Với Trích Dẫn
Trả lời Gởi Ðề Tài Mới

Bookmarks

Ðiều Chỉnh
Xếp Bài

Quuyền Hạn Của Bạn
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt

Chuyển đến


Múi giờ GMT. Hiện tại là 12:46 PM.


Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.
Inactive Reminders By mathscope.org
[page compression: 70.82 k/78.48 k (9.77%)]