[IMO 2013] Bài 2 - Tổ hợp
 

Cho 2013 điểm màu đỏ và 2014 điểm màu xanh trên mặt phẳng, 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 các điểm trên) thành các miền sao cho không có miền nào chứa các điểm có màu khác nhau. Số nhỏ nhất các đường thẳng luôn thỏa mãn là bao nhiêu?

Ta chứng minh 2013 đường thẳng là đủ.

Nhìn vào dữ kiện của bài toán thì nghĩ ngay đến chứng minh bằng quy nạp với $N $ điểm đỏ và $N+1 $ điểm xanh.

Với $N = 1 $ thì dễ thấy chỉ 1 đường thẳng là đủ.

Ta xét với $N $. Nếu $N $ chẵn thì $N $ đường thẳng là đủ (xét các cặp đường thẳng song song và chứa đúng 2 điểm đỏ).

Với$N $ lẻ, xét bao lồi của $2N+1 $ điểm là một đa giác $\ge 3 $ cạnh.

Nếu bao lồi có chứa một điểm đỏ, thì ta dùng một đường thẳng chia đôi mặt phẳng, một phần chứa duy nhất điểm đỏ đó và phần còn lại chứa $N-1 $ đỏ và $N+1 $ xanh. Ta thấy với $N-1 $ đường thẳng nữa thì đủ cho phần mặt phẳng này. Vậy ta cũng có $N $ đường thẳng là đủ.

Nếu bao lồi không chứa điểm đỏ nào, thì có hai điểm xanh mà với một đường thẳng thì ta chia được thành hai phần, phần chứa 2 điểm xanh và phần chứa $N-1 $ điểm xanh và $N $ điểm đỏ. Đến đây dùng giả thiết quy nạp thì ta $N-1 $ đường thẳng là đủ cho phần mặt phẳng này. Do vậy $N $ đường thẳng là đủ.

Vậy ta kết luận $N $ đường thẳng là đủ.

Bây giờ ta cần chỉ ra một trường hợp mà $N $ đường thẳng là cần. Thật vậy với một bao lồi gồm $N $ điểm xanh và $N $ điểm đỏ xen kẽ nhau. Khi đó mỗi cạnh có hai đỉnh khác màu của bao lồi phải bị cắt bởi một trong các đường thẳng. Vì có $2N $ cạnh và mỗi đường thẳng chỉ cắt không quá 2 cạnh nên phải cần ít nhất là $N $ đường thẳng. ĐPCM.

Hãy giải bài toán với trường hợp có $N $ điểm xanh, $M $ điểm đỏ và $N-M\ge 2 $.:-w

Em có cách này chắc khá giống cách anh Traum nhưng vẫn post lên để mọi người xem có thiếu gì không( vì thấy có vẻ dễ nghĩ hơn và không xét chẵn lẻ).
Xét đường thẳng đi qua 2 trong số $2N+1 $ điểm sao cho tất cả $2N-1 $ điểm còn lại thuộc cùng một nửa mặt phẳng.
Theo giả thiết quy nạp thì $2N-1 $ điểm còn lại đã được chia thỏa mãn bằng $N-1 $ đường thẳng.
Xét các trường hợp:
TH1: 2 điểm thuộc đường thẳng thuộc 2 miền khác nhau khi chia bởi $N-1 $ đường thẳng kia
a) 2 điểm cùng màu, thì điểm mà nằm trong miền khác màu với nó thì ta luôn kẻ được 1 đường thẳng chia mặt phẳng thành 2 nửa mặt phẳng mà một nửa mặt phẳng chứa điểm khác màu kia và một nửa chứa $2N $ điểm còn lại, đây chính là đường thẳng thứ $N $ chia các điểm theo đúng yêu cầu
b) 2 điểm khác màu mà cả hai đều nằm trong miền khác màu với chúng. Ta vẽ thêm đường thẳng song song với đường thẳng đi qua 2 điểm này và chia mặt phẳng thành 2 nửa, một nửa chứa 2 điểm, 1 nửa chưa $2N-1 $ điểm.
TH2: 2 điểm thuộc đường thẳng đều thuộc cùng 1 miền
a) 2 điểm cùng màu, khác màu với miền chứa chúng, ta làm như TH 1b
b) 2 điểm khác màu, ta làm như TH 1a với điểm khác màu với miền trong 2 điểm đó

Các trường hợp còn lại đều thỏa mãn với $N-1 $đường thẳng

Em có ý tưởng này, hi vọng là đúng:
Xét đường gấp khúc không tự cắt đi qua mọi điểm của hệ.
Rõ ràng là số cạnh nằm trên đường gấp khúc sao cho hai điểm mút khác màu là không quá $n+2$.
Xét một dãy đỉnh liên tiếp cùng màu trên đường gấp khúc, ta có nếu số đỉnh liên tiếp này nhiều hơn 1 thì ta chỉ cần 2 đường thẳng để chia dãy đỉnh này với phần còn lại của đường gấp khúc(bằng cách chọn hai điểm nằm trên hai đoạn thẳng nối hai câp đỉnh khác màu liên tiếp ở ngoài cùng, rồi ta quay đường thẳng đó cho đến khi thoả mãn, và rõ ràng là tồn tại vì đường gấp khúc đã cho không tự cắt)

Xét hệ điểm đã cho, vì số điểm xanh và số điểm đỏ không bằng nhau nên ta có một dãy đỉnh cùng màu không ít hơn hai đỉnh. Nếu trong hệ điểm tồn tại một dãy đỉnh có không ít hơn 3 đỉnh liên tiếp cùng màu thì từ thuật toán trên đã có thể dùng hai đường thẳng để tách mặt phẳng đó ra thành 4 phần, trong đó có 1 phần là dãy đỉnh đã cho. Vì ta có $2n+1$ và $n$ đường thẳng nên sau khi chia ta chỉ cần xử lí không quá $2n-2$ với $n-2$ đường thẳng. Theo quy nạp thì mỗi hệ điểm có $k$ điểm chỉ cần không quá $\floor{\frac{n}{2}}$ đường thẳng. Do đó ta chỉ cần chia sao cho có 1 phần chứa số lẻ điểm và điều này có thể thực hiện được bằng cách quay đường thẳng.

Với trường hợp còn lại, chọn ba đỉnh liên tiếp sao cho ba đỉnh đó nằm ngoài bao lồi của hệ điểm còn lại(luôn chọn được), dùng 1 đường thẳng để tách 3 điểm đó ra và 1 đường thẳng để tách các điểm khác màu trong 3 điểm đó(luôn có do không tồn tại dãy 3 đỉnh liên tiếp cùng màu), rồi ta quay đường thẳng thứ 2 sao cho nó chia hệ điểm kia thành 1 phần có lẻ đỉnh, như vậy ta có dpcm.

Đã sửa xong, hi vọng là đúng:(