Giải được bài này Mon bái làm thánh (Chỉ tính học sinh). Đề hsg quốc tế năm nay

Question

Trên mặt phẳng cho 2013 điểm màu đỏ và 2014 điểm màu xanh, trong đó không có ba điểm nào thẳng hàng. Ta chia mặt phẳng bởi các đường thẳng (không đi qua bất kì điểm nào trong các điểm đã cho) thành các vùng, sao cho không có bất kì vùng nào chứa các điểm có hai màu khác nhau. Hỏi cần ít nhất là bao nhiêu đường thẳng để luôn thực hiện được cách chia đó ?

khangnguyenthanh · Answer 1 · 7/29/2013 9:06:19 PM

Đề thi chính thức được phát biểu như sau:

"Một tập hợp gồm đúng 4027 điểm trên mặt phẳng được gọi là tập Colombia nếu không có ba điểm nào trong các điểm đó thẳng hàng, đồng thời có 2013 điểm được tô màu đỏ và 2014 điểm còn lại được tô màu xanh. Mặt phẳng được phân chia thành các miền khi ta kẻ một số đường thẳng. Một cách kẻ một số đường thẳng được gọi là cách kẻ tốt đối với tập Colombia cho trước nếu hai điều kiện sau được thỏa mãn:

1. Không đường thẳng nào đi qua dù chỉ một điểm thuộc tập hợp đó;

2. Không miền nào chứa cả điểm màu đỏ và điểm màu xanh.

Tìm số k nhỏ nhất sao cho với tập Colombia tùy ý gồm đúng 4027 điểm, tồn tại một cách kẻ k đường thẳng là cách kẻ tốt."

Xét đa giác đều 4027 cạnh

$A_1A_2\ldots A_{4027}$ nội tiếp đường tròn

$(O)$ nào đó.

Giả sử rằng các đỉnh

$A_{2k},k=\overline{1;2013}$ màu đỏ và các đỉnh

$A_{2k+1},k=\overline{0;2013}$ màu xanh.

NX: Vì các điểm

$A_i;A_{i+1},i=\overline{1;4026}$ khác màu nhau nên

$A_i;A_{i+1}$ nằm về 2 phía của 1 đường thẳng nào đó trong số

$N$ đường thẳng đã cho, hay tồn tại 1 đường thẳng cắt cung nhỏ

$A_iA_{i+1}$ .

Có tất cả 4026 cung mà mỗi đường thẳng chỉ cắt tối đa 2 cung nên cần ít nhất 2013 đường thẳng để thực hiện cách phân chia thỏa mãn.

Ta chứng minh: với 4027 điểm bất kỳ thì chỉ cần 2013 đường thẳng để có 1 cách phân chia thỏa mãn.

Gọi

$X_1X_2\ldots X_k$ là bao lồi của 4027 điểm trên.

TH1: Giả sử tồn tại

$i$ sao cho

$X_i$ màu đỏ, KMMTQ, giả sử

$X_1$ .

Khi đó, tồn tại đường thẳng

$\Delta$ chia mặt phẳng ra làm 2 miền trong đó 1 miền chỉ chứa duy nhất điểm

$X_1$ .

Xét 2012 điểm màu đỏ còn lại

$A_1;A_2;\ldots;A_{2012}$ .

Với mỗi

$i=\overline{1;1006}$ , tồn tại 2 đường thẳng

$x_i;y_i$ song song với nhau và song song với

$A_{2i-1}A_{2i}$ sao cho miền mặt phẳng nằm giữa

$x_i,y_i$ chỉ chứa 2 điểm

$A_{2i-1},A_{2i}$ .

Khi đó, 2013 đường thẳng

$\Delta, x_1, y_1, x_2, y_2, \ldots, x_{1006}, y_{1006}$ thỏa mãn bài toán.

TH2: Tất cả các điểm

$X_1, X_2, \ldots ,X_k$ đều màu xanh.

Khi đó, tồn tại đường thẳng

$\Delta$ song song với

$X_1X_2$ chia mặt phẳng ra làm 2 miền trong đó 1 miền chỉ chứa 2 điểm

$X_1, X_2$ .

Xét 2012 điểm màu xanh còn lại

$B_1;B_2;\ldots;B_{2012}$ .

Với mỗi

$i=\overline{1;1006}$ , tồn tại 2 đường thẳng

$x_i;y_i$ song song với nhau và song song với

$B_{2i-1}B_{2i}$ sao cho miền mặt phẳng nằm giữa

$x_i,y_i$ chỉ chứa 2 điểm

$B_{2i-1},B_{2i}$ .

Khi đó, 2013 đường thẳng

$\Delta, x_1, y_1, x_2, y_2, \ldots, x_{1006}, y_{1006}$ thỏa mãn bài toán.

Vậy cần ít nhất 2013 đường thẳng để thực hiện cách phân chia thỏa mãn.

k hỉu lắm. ngồi ngâm cứu đã =)). may mắn thì sẽ hiểu được =))
người lớn nói chuyện chẳng hiểu trẻ con nói gì à...... Thế ngu gì post lên đây làm gì.???
theo kết quả thống kê thì bài này có 118 hs tham dự kì thi đạt điểm tối đa (trong đó có 3 hs VN), 50 hs đạt từ 4-6 điểm, 130 hs đạt từ 1-3 điểm. bạn sẽ gọi các học sinh này là thánh chứ?