Diễn Đàn MathScope - Xem bài viết đơn - [IMO 2013] Bài 2

**Traum** · 24-07-2013, 05:23 AM

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 nà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.

24-07-2013, 05:23 AM	#2
Traum Moderator Tham gia ngày: Nov 2007 Đến từ: cyber world Bài gởi: 413 Thanks: 14 Thanked 466 Times in 171 Posts	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 nà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. __________________ Traum is giấc mơ.