Trong không gian cho 2007 điểm (Không có 4 điểm nào đp)
Nối cấc cặp điểm lại với nhau .
Ta tô màu các đoạn thẳng đó bẳng 1 trong 2007 màu .
Hỏi có tồn tại cách tô màu t/m:Với 3 màu bất kì trong số 2007 màu đó thì luôn tôn tại 1 tan giác có 3 canh được tô 3 màu đó
Bài được
Bắt đầu bởi tmbtw, 06-05-2006 - 13:54
#1
Đã gửi 06-05-2006 - 13:54
Play the game of life with the attitude of playing to win and not with the attitude of playing not to lose
#2
Đã gửi 18-05-2006 - 21:32
Thực ra thì ra chẳng quan tâm đến 2007 điểm đó nằm trên không gian hay mặt phẳng. Bây giờ ta coi n (n lẻ thay cho 2007) điểm đó là các đỉnh của n giác đều.
Giả sử các đỉnh là http://dientuvietnam...A_1,A_2,...A_n. Bây giờ ta tô màu một cạnh là màu http://dientuvietnam...n/mimetex.cgi?j nếu trung trực của nó đi qua http://dientuvietnam...imetex.cgi?A_j. Thế thì hai cạnh cùng màu khi và chỉ khi nó song song với nhau.
Tiếp theo ta chứng minh không tồn tại hai tam giác nào có các cạnh mà các màu trùng nhau. Thật vậy giả sử ngược lại thì ta có hai tam giác ABC và A'B'C' có Màu của AB trùng với A'B', màu của BC trùng với B'C' màu của CA trùng với C'A'.
Khi đó theo trên ta có AB||A'B", BC||B'C', CA||C'A' nên ta có hai tam giác ABC và A'B'C' đồng dạng. Mà có chung đường trong ngoại tiếp nên ta có hai tam giác đó bằng nhau và do đó nó đối xứng với nhau qua tâm O. Vô lí. Vậy ta có ĐPCM.
Giả sử các đỉnh là http://dientuvietnam...A_1,A_2,...A_n. Bây giờ ta tô màu một cạnh là màu http://dientuvietnam...n/mimetex.cgi?j nếu trung trực của nó đi qua http://dientuvietnam...imetex.cgi?A_j. Thế thì hai cạnh cùng màu khi và chỉ khi nó song song với nhau.
Tiếp theo ta chứng minh không tồn tại hai tam giác nào có các cạnh mà các màu trùng nhau. Thật vậy giả sử ngược lại thì ta có hai tam giác ABC và A'B'C' có Màu của AB trùng với A'B', màu của BC trùng với B'C' màu của CA trùng với C'A'.
Khi đó theo trên ta có AB||A'B", BC||B'C', CA||C'A' nên ta có hai tam giác ABC và A'B'C' đồng dạng. Mà có chung đường trong ngoại tiếp nên ta có hai tam giác đó bằng nhau và do đó nó đối xứng với nhau qua tâm O. Vô lí. Vậy ta có ĐPCM.
#3
Đã gửi 22-05-2006 - 09:30
Ý tưởng lời giải của anh rất hay (Trong đợt thi VNTST vừa rồi ,anh clmt cũng giải bài 3 với ý tưởng tt vậy )
1 điều nói thêm nữa , bài toán có còn được giải quyết trong trường hợp :n chẵn
1 điều nói thêm nữa , bài toán có còn được giải quyết trong trường hợp :n chẵn
Play the game of life with the attitude of playing to win and not with the attitude of playing not to lose
#4
Đã gửi 23-05-2006 - 23:43
Trước hết nhận thấy là không có màu nào được tô cho quá http://dientuvietnam...mimetex.cgi?n/2 cạnh.bài toán có còn được giải quyết trong trường hợp :n chẵn
Giả sử có hai màu đều được tô cho http://dientuvietnam...mimetex.cgi?n/2 cạnh thì ta có số tam giác mà chứa 2 cạnh có 2 màu đó là http://dientuvietnam...n/mimetex.cgi?n tam giác. Nhưng ta chỉ có http://dientuvietnam...mimetex.cgi?n-2 tam giác chứa 2 cạnh có 2 màu đó cho nên trường hợp này không xảy ra.
Lại có số cạnh là http://dientuvietnam...metex.cgi?n(n-1)/2 nên tồn tại một màu được tô cho không ít hơn http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{n-1}{2} cạnh nên nó được tô cho không ít hơn http://dientuvietnam...mimetex.cgi?n/2 cạnh. Theo trên màu đó được tô cho http://dientuvietnam...mimetex.cgi?n/2 cạnh và các màu khác được tô cho không quá http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{n}{2}-1 cạnh nên ta có số cạnh không vượt quá: http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{n}{2}+(n-1)(\dfrac{n}{2}-1)=\dfrac{n}{2}+\dfrac{n^2}{2}-\dfrac{n}{2}-n+1=\dfrac{n(n-1)}{2}-\dfrac{n}{2}+1<\dfrac{n(n-1)}{2} với mọi . Do đó ta có mâu thuẫn.ĐPCM
#5
Đã gửi 24-05-2006 - 14:05
Bài nữa có liên quan đến loạt bài trên :
_Chứng minh nếu ta tô các cạnh của đồ thị đều K[n] bởi n màu và màu nào cũng được tô thì luôn tìm được 1 tam giác có 3 cạnh là cạnh của K[n] và 3 cạnh được tô bởi 3 màu khác nhau.
_Nếu số màu tô chỉ là n-1 và màu nào cũng được tô thì điều trên còn đúng không?
_Chứng minh nếu ta tô các cạnh của đồ thị đều K[n] bởi n màu và màu nào cũng được tô thì luôn tìm được 1 tam giác có 3 cạnh là cạnh của K[n] và 3 cạnh được tô bởi 3 màu khác nhau.
_Nếu số màu tô chỉ là n-1 và màu nào cũng được tô thì điều trên còn đúng không?
My major is CS.
#6
Đã gửi 25-05-2006 - 23:32
Hai bài này có thể giải như sau:
Với bàii 2 thì ta có thể tô như sau: tô màu cạnh http://dientuvietnam...etex.cgi?A_iA_j màu http://dientuvietnam.net/cgi-bin/mimetex.cgi?max\{i;j\}.
Khi đó ta có với mọi tam giác http://dientuvietnam...x.cgi?A_iA_jA_k với http://dientuvietnam...metex.cgi?i<j<k thì có hai cạnh http://dientuvietnam...etex.cgi?A_iA_k và http://dientuvietnam...etex.cgi?A_jA_k đều được tô màu http://dientuvietnam...n/mimetex.cgi?k và ta chỉ cần http://dientuvietnam...mimetex.cgi?n-1 màu.
Đối với bài toán 1:
Quy nạp theo http://dientuvietnam.../mimetex.cgi?n.
http://dientuvietnam.net/cgi-bin/mimetex.cgi?n=3 đúng.
Giả sử đã đúng tới http://dientuvietnam.net/cgi-bin/mimetex.cgi?n
Xét với http://dientuvietnam.net/cgi-bin/mimetex.cgi?n+1.
Giả sử ngược lại:
Ta giả sử các màu xuất phát từ đỉnh http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_{n+1} là màu http://dientuvietnam.net/cgi-bin/mimetex.cgi?1,2,...,t dễ có http://dientuvietnam.net/cgi-bin/mimetex.cgi?S_i là tập hợp các đỉnh http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_j mà cạnh http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_{n+1}A_j được tô màu http://dientuvietnam.net/cgi-bin/mimetex.cgi?i ta có http://dientuvietnam.net/cgi-bin/mimetex.cgi?\sum\limits_{i=1}^t|S_i|=n-1. Bây giờ với http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_iA_j tô bởi một trong hai màu http://dientuvietnam.net/cgi-bin/mimetex.cgi?i hoặc http://dientuvietnam.net/cgi-bin/mimetex.cgi?i'.
Với mỗi tập http://dientuvietnam.net/cgi-bin/mimetex.cgi?S_i thì số màu dùng tối đa là http://dientuvietnam.net/cgi-bin/mimetex.cgi?\sum\limits_{i=1}^{t}(|S_i|-1)+t=n-1.
Mâu thuẫn. Vậy ta có đpcm.
Với bàii 2 thì ta có thể tô như sau: tô màu cạnh http://dientuvietnam...etex.cgi?A_iA_j màu http://dientuvietnam.net/cgi-bin/mimetex.cgi?max\{i;j\}.
Khi đó ta có với mọi tam giác http://dientuvietnam...x.cgi?A_iA_jA_k với http://dientuvietnam...metex.cgi?i<j<k thì có hai cạnh http://dientuvietnam...etex.cgi?A_iA_k và http://dientuvietnam...etex.cgi?A_jA_k đều được tô màu http://dientuvietnam...n/mimetex.cgi?k và ta chỉ cần http://dientuvietnam...mimetex.cgi?n-1 màu.
Đối với bài toán 1:
Quy nạp theo http://dientuvietnam.../mimetex.cgi?n.
http://dientuvietnam.net/cgi-bin/mimetex.cgi?n=3 đúng.
Giả sử đã đúng tới http://dientuvietnam.net/cgi-bin/mimetex.cgi?n
Xét với http://dientuvietnam.net/cgi-bin/mimetex.cgi?n+1.
Giả sử ngược lại:
Ta giả sử các màu xuất phát từ đỉnh http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_{n+1} là màu http://dientuvietnam.net/cgi-bin/mimetex.cgi?1,2,...,t dễ có http://dientuvietnam.net/cgi-bin/mimetex.cgi?S_i là tập hợp các đỉnh http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_j mà cạnh http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_{n+1}A_j được tô màu http://dientuvietnam.net/cgi-bin/mimetex.cgi?i ta có http://dientuvietnam.net/cgi-bin/mimetex.cgi?\sum\limits_{i=1}^t|S_i|=n-1. Bây giờ với http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_iA_j tô bởi một trong hai màu http://dientuvietnam.net/cgi-bin/mimetex.cgi?i hoặc http://dientuvietnam.net/cgi-bin/mimetex.cgi?i'.
Với mỗi tập http://dientuvietnam.net/cgi-bin/mimetex.cgi?S_i thì số màu dùng tối đa là http://dientuvietnam.net/cgi-bin/mimetex.cgi?\sum\limits_{i=1}^{t}(|S_i|-1)+t=n-1.
Mâu thuẫn. Vậy ta có đpcm.
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh