Diễn Đàn MathScopeDiễn Đàn MathScope
  Diễn Đàn MathScope
Ghi Danh Hỏi/Ðáp Thành Viên Social Groups Lịch Ðánh Dấu Ðã Ðọc

Go Back   Diễn Đàn MathScope > Sơ Cấp > Việt Nam và IMO > 2013

News & Announcements

Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé !

* Nội quy MathScope.Org

* Một số quy định chung !

* Quy định về việc viết bài trong diễn đàn MathScope

* Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây

* Những câu hỏi thường gặp

* Về việc viết bài trong Box Đại học và Sau đại học


Trả lời Gởi Ðề Tài Mới
 
Ðiều Chỉnh Xếp Bài
Old 24-07-2013, 12:56 AM   #1
novae
+Thành Viên Danh Dự+
 
novae's Avatar
 
Tham gia ngày: Jul 2010
Đến từ: Event horizon
Bài gởi: 2,453
Thanks: 53
Thanked 3,057 Times in 1,288 Posts
[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?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
M.

thay đổi nội dung bởi: novae, 24-07-2013 lúc 12:58 AM
novae is offline   Trả Lời Với Trích Dẫn
The Following 4 Users Say Thank You to novae For This Useful Post:
ACGIN (24-07-2013), dvtruc (24-07-2013), n.v.thanh (24-07-2013), quocbaoct10 (24-07-2013)
Old 24-07-2013, 05:23 AM   #2
Traum
Moderator
 
Traum's Avatar
 
Tham gia ngày: Nov 2007
Đến từ: cyber world
Bài gởi: 413
Thanks: 14
Thanked 465 Times in 170 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 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.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Traum is giấc mơ.
Traum is offline   Trả Lời Với Trích Dẫn
The Following 8 Users Say Thank You to Traum For This Useful Post:
ACGIN (24-07-2013), batigoal (24-07-2013), caoxuanhuy (24-07-2013), dungtoank22 (24-07-2013), hoangqnvip (21-08-2013), huynhcongbang (24-07-2013), quocbaoct10 (24-07-2013), RAIZA (24-07-2013)
Old 24-07-2013, 06:17 AM   #3
Traum
Moderator
 
Traum's Avatar
 
Tham gia ngày: Nov 2007
Đến từ: cyber world
Bài gởi: 413
Thanks: 14
Thanked 465 Times in 170 Posts
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 $.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Traum is giấc mơ.
Traum is offline   Trả Lời Với Trích Dẫn
Old 24-07-2013, 10:01 AM   #4
Fool's theorem
+Thành Viên Danh Dự+
 
Fool's theorem's Avatar
 
Tham gia ngày: Oct 2012
Đến từ: T1 K46 Chuyên ĐHSP Hà Nội
Bài gởi: 187
Thanks: 42
Thanked 191 Times in 101 Posts
Gửi tin nhắn qua Yahoo chát tới Fool's theorem
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
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

thay đổi nội dung bởi: Fool's theorem, 24-07-2013 lúc 10:04 AM Lý do: Latex
Fool's theorem is offline   Trả Lời Với Trích Dẫn
Old 24-07-2013, 04:13 PM   #5
TNP
+Thành Viên+
 
TNP's Avatar
 
Tham gia ngày: Feb 2012
Đến từ: PTNK TPHCM
Bài gởi: 180
Thanks: 487
Thanked 106 Times in 67 Posts
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
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Believe in yourself $\Leftrightarrow$ Believe in miracles

thay đổi nội dung bởi: TNP, 24-07-2013 lúc 06:19 PM
TNP is offline   Trả Lời Với Trích Dẫn
Trả lời Gởi Ðề Tài Mới

Bookmarks

Ðiều Chỉnh
Xếp Bài

Quuyền Hạn Của Bạn
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt

Chuyển đến


Múi giờ GMT. Hiện tại là 12:56 AM.


Powered by: vBulletin Copyright ©2000-2018, Jelsoft Enterprises Ltd.
Inactive Reminders By mathscope.org
[page compression: 59.35 k/66.58 k (10.86%)]