Tô màu mặt phẳng tọa độ

man1995 · 25-09-2011, 11:06 PM

Trong mặt phẳng tọa độ $Oxy $, xét tập hợp $\phi $ gồm những điểm cố định với tọa độ $\left ( x,y \right ) $ ở đây $x,y $ là những số nguyên và $1\leq x \leq 12 $ , $1\leq y \leq10 $.Mỗi điểm được tô bằng một màu trắng , xanh hoặc đỏ. Chứng minh rằng tồn tại hình chữ nhật có các cạnh song song với các trục tọa độ, mà đỉnh của nó là những điểm của $\phi $ được tô cùng màu.

beyondinfinity · 26-09-2011, 08:15 AM

Đếm bằng 2 cách!
Trên bảng $12\times 10 $.
Giả sử phản chứng, cứ 2 cột bất kì thì với mỗi màu có nhiều nhất 1 cặp điểm cùng hàng màu đó trên 2 cột (nếu có 2 thì ta có hcn). Khi đó:
$3\binom{10}{2}\ge \sum_{i=1}^{12}\binom{a_i}{2}+\binom{b_i}{2}+ \binom{c_i}{2} $
$\ge \sum_{i=1}^{12}\frac{S_i^2-3S_i}{6} $
($S_i=a_i+b_i+c_i=10 $, $a_i $, $b_i $, $c_i $ là số điểm mỗi màu trên 1 hàng)
Suy ra mâu thuẫn.

man1995 · 26-09-2011, 11:22 AM

Trích:

Nguyên văn bởi beyondinfinity

Đếm bằng 2 cách!
Giả sử phản chứng. Khi đó:
$3\binom{10}{2}\ge \sum_{i=1}^{12}\binom{a_i}{2}+\binom{b_i}{2}+\bino m{c_i}{2} $
$\ge \sum_{i=1}^{12}\frac{S_i^2-3S_i}{6} $
($S_i=a_i+b_i+c_i=10 $)
Suy ra mâu thuẫn.

Em không hiểu anh có thể viết cụ thể 1 tí được không ?

25-09-2011, 11:06 PM	#1
man1995 +Thành Viên+ Tham gia ngày: Mar 2011 Đến từ: quang ngai Bài gởi: 93 Thanks: 82 Thanked 28 Times in 14 Posts	Tô màu mặt phẳng tọa độ Trong mặt phẳng tọa độ $Oxy $, xét tập hợp $\phi $ gồm những điểm cố định với tọa độ $\left ( x,y \right ) $ ở đây $x,y $ là những số nguyên và $1\leq x \leq 12 $ , $1\leq y \leq10 $.Mỗi điểm được tô bằng một màu trắng , xanh hoặc đỏ. Chứng minh rằng tồn tại hình chữ nhật có các cạnh song song với các trục tọa độ, mà đỉnh của nó là những điểm của $\phi $ được tô cùng màu.

26-09-2011, 08:15 AM	#2
beyondinfinity +Thành Viên+ Tham gia ngày: Dec 2009 Bài gởi: 456 Thanks: 64 Thanked 215 Times in 143 Posts	Đếm bằng 2 cách! Trên bảng $12\times 10 $. Giả sử phản chứng, cứ 2 cột bất kì thì với mỗi màu có nhiều nhất 1 cặp điểm cùng hàng màu đó trên 2 cột (nếu có 2 thì ta có hcn). Khi đó: $3\binom{10}{2}\ge \sum_{i=1}^{12}\binom{a_i}{2}+\binom{b_i}{2}+ \binom{c_i}{2} $ $\ge \sum_{i=1}^{12}\frac{S_i^2-3S_i}{6} $ ($S_i=a_i+b_i+c_i=10 $, $a_i $, $b_i $, $c_i $ là số điểm mỗi màu trên 1 hàng) Suy ra mâu thuẫn. thay đổi nội dung bởi: beyondinfinity, 26-09-2011 lúc 01:33 PM