BM 01-Bia SKKN
SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỒNG NAI
Đơn vị THPT chuyên Lương Thế Vinh
Mã số: ................................
(Do HĐKH Sở GD&ĐT ghi)
SÁNG KIẾN KINH NGHIỆM
NGUYÊN LÍ CỰC HẠN
TRONG CÁC BÀI TOÁN TỔ HỢP
Người thực hiện: Phạm Doãn Lê Bình
Lĩnh vực nghiên cứu:
- Quản lý giáo dục
- Phương pháp dạy học bộ môn: Toán
- Lĩnh vực khác: .......................................................
Có đính kèm: Các sản phẩm không thề hiện trong bản in SKKN
Mô hình
Phần mềm
Phim ảnh
Hiện vật khác
Năm học: 2016 - 2017
BM02-LLKHSKKN
SƠ LƯỢC LÝ LỊCH KHOA HỌC
I. THÔNG TIN CHUNG VỀ CÁ NHÂN
1. Họ và tên: Phạm Doãn Lê Bình
2. Ngày tháng năm sinh: 23/04/1986
3. Nam, nữ: Nam
4. Địa chỉ: 1123, KP7, P. Long Bình, TP. Biên Hòa, Đồng Nai
5. Điện thoại: 0613930245 (nhà riêng) ; ĐTDĐ: 01683531100
6. Fax:
E-mail:
[email protected]
7. Chức vụ: Giáo viên
8. Đơn vị công tác: Trường THPT chuyên Lương Thế Vinh.
II. TRÌNH ĐỘ ĐÀO TẠO
- Học vị (hoặc trình độ chuyên môn, nghiệp vụ) cao nhất: Thạc sĩ
- Năm nhận bằng: 2012
- Chuyên ngành đào tạo: Đại số và lý thuyết số
III. KINH NGHIỆM KHOA HỌC
- Lĩnh vực chuyên môn có kinh nghiệm: Sư phạm Toán
Số năm có kinh nghiệm: 9
- Các sáng kiến kinh nghiệm đã có trong 5 năm gần đây:
+ Phương pháp đại lượng bất biến, đơn biến trong các bài toán tổ hợp. (2014)
+ Các bài toán tổ hợp trong các kỳ thi học sinh giỏi (2016)
NGUYÊN LÍ CỰC HẠN
TRONG CÁC BÀI TOÁN TỔ HỢP
Phạm Doãn Lê Bình
Giáo viên trường THPT chuyên Lương Thế Vinh
Tháng 4 năm 2017
Mục lục
1 Lý do chọn đề tài
2
2 Nội
2.1
2.2
2.3
2
2
2
9
dung đề tài
Nêu vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Bài tập tự luyện . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Hiệu quả của đề tài
10
4 Tài liệu tham khảo
11
Trang 1
1
Lý do chọn đề tài
Nguyên lí cực hạn là một nguyên lí đơn giản và dễ hiểu nhưng nếu vận dụng
khéo léo sẽ giúp chúng ta giải quyết được nhiều lớp bài toán, đặc biệt là các
bài toán tổ hợp. Nguyên lí cực hạn thường được sử dụng kết hợp với các
phương pháp khác, đặc biệt là phương pháp phản chứng. Nó giúp chúng ta
giải quyết các bài toán mà trong tập hợp những đối tượng phải xét của nó
tồn tại các đối tượng có giá trị lớn nhất, giá trị nhỏ nhất theo một nghĩa nào
đó. Nguyên lí cực hạn tuy dễ hiểu nhưng để vận dụng nó vào các bài toán
thì lại không phải đơn giản. Với lí do đó, tôi chọn đề tài này để làm tài liệu
giảng dạy cho giáo viên và tài liệu học tập cho học sinh trong quá trình tiếp
cận các bài toán tổ hợp.
2
Nội dung đề tài
2.1
Nêu vấn đề
Nguyên lí 1. Trong một tập hữu hạn và khác rỗng các số thực luôn luôn có
thể chọn được số bé nhất và số lớn nhất.
Nguyên lí 2. Trong một tập hợp khác rỗng các số tự nhiên luôn luôn có thể
chọn được số bé nhất.
Để vận dụng các nguyên lí cực hạn giải các bài toán tổ hợp, người ta
thường dùng một lược đồ chung để giải như sau:
• Đưa bài toán đang xét về dạng có thể sử dụng nguyên lí 1 (hoặc nguyên
lí 2) để chứng tỏ rằng trong tất cả các giá trị cần khảo sát của bài toán
phải có giá trị lớn nhất (hoặc nhỏ nhất).
• Xét bài toán tương ứng khi nó nhận giá trị lớn nhất (hoặc nhỏ nhất)
này.
• Chỉ ra một mâu thuẫn, hoặc đưa ra một giá trị còn lớn hơn (hoặc nhỏ
hơn) giá trị lớn nhất (hoặc nhỏ nhất) mà ta đang khảo sát.
• Theo nguyên lí của phương pháp phản chứng, ta sẽ suy ra điều phải
chứng minh.
Ta xét một số ví dụ sau:
2.2
Một số ví dụ
Ví dụ 1. Chứng minh rằng trong 15 số nguyên dương thuộc {2.3. . . . , 1992}
và đôi một nguyên tố cùng nhau, có ít nhất một số nguyên tố.
Trang 2
Lời giải. Giả sử tìm được 15 số lấy từ {2; 3; . . . ; 1992} sao cho chúng đều là
hợp số và đôi một nguyên tố cùng nhau. Khi đó mỗi một số này đều phải có
√
ước số nguyên tố nhỏ hơn 45 ( 1992 < 45). Vì chỉ có 14 số nguyên tố nhỏ
hơn 45 nên phải tồn tại ít nhất 2 trong 15 số trên có cùng ước số nguyên tố.
Nhưng khi đó chúng không nguyên tố cùng nhau, mâu thuẫn. Vậy điều giả
sử là sai, tức là tồn tại một trong 15 số đã cho là số nguyên tố.
Ví dụ 2. Chứng minh rằng bốn hình tròn có đường kính là bốn cạnh của
một tứ giác lồi thì phủ kín tứ giác đã cho.
Lời giải. Lấy M là một điểm tùy ý của tứ giác lồi ABCD. Có hai khả năng
xảy ra:
1. Nếu M nằm trên một cạnh của tứ giác ABCD. Khi đó M nằm trong hình
tròn có đường kính là cạnh ấy.
2. Nếu M nằm bên trong tứ giác lồi ABCD. Khi đó ta có
AM B + BM C + CM D + DM A = 360◦ .
Theo nguyên lý cực hạn, tồn tại α = max{AM B, BM C, CM D, DM A}. Khi
ấy, α ≥ 90◦ . Không mất tính tổng quát, giả sử α = AM B. Suy ra M nằm
trong hình tròn đường kính AB. Vậy M bị phủ bởi hình tròn này.
Như thế, do M là điểm bất kỳ của tứ giác ABCD và M luôn thuộc một hình
tròn nào đó có đường kính là một cạnh của tứ giác ABCD nên tứ giác ABCD
sẽ bị phủ kín bởi 4 hình tròn có đường kính là bốn cạnh.
Ví dụ 3. Trên mặt phẳng vô hạn được kẻ ô vuông, người ta điền các số
tự nhiên vào các ô vuông sao cho mỗi số tùy ý luôn bằng trung bình cộng
của bốn số tự nhiên trong bốn ô vuông có cạnh chung với ô vuông chứa nó.
Chứng minh rằng khi đó tất cả các số được điền đều bằng nhau.
Lời giải. Xét tập hợp các số được điền. Đây là tập hợp các số tự nhiên khác
rỗng, nên theo nguyên lí cực hạn phải tồn tại phần tử nhỏ nhất mà ta kí hiệu
là a.
Trang 3
Giả sử kết luận của bài toán không đúng, tức là các số được điền không phải
tất cả đều bằng nhau. Như vậy sẽ có một ô chứa số a mà trong bốn ô cạnh
chung với nó sẽ có ít nhất một số b = a. Giả sử ba ô còn lại có cạnh chung
với ô chứa số a này là c, d, e. Theo cách xác định số a, ta có: b > a, c ≥ a,
d ≥ a, e ≥ a. Từ đó suy ra
a<
b+c+d+e
.
4
Điều này mâu thuẫn với giả thiết a là trung bình cộng của b, c, d, e. Vậy
giả thiết phản chứng là sai, tức là tất cả các số viết trong bảng đều bằng
nhau.
Ví dụ 4. Cho n điểm xanh và n điểm đỏ trên mặt phẳng, trong đó không có
3 điểm nào thẳng hàng. Chứng minh rằng ta có thể nối 2n điểm này bằng n
đoạn thẳng có đầu mút khác màu sao cho chúng đôi một không giao nhau.
Lời giải. Với mỗi cách nối 2n điểm bằng n đoạn thẳng xanh-đỏ, ta tính tổng
độ dài các đoạn thẳng được nối. Do số cách nối là hữu hạn nên tồn tại cách
nối có tổng độ dài nói trên là nhỏ nhất. Ta chứng minh rằng cách nối này
thỏa mãn yêu cầu bài toán.
Giả sử ngược lại, tồn tại hai đoạn thẳng cắt nhau, giả sử đó là AB và CD
cắt nhau tại O (A, C được tô màu đỏ, còn B, D được tô màu xanh).
Áp dụng bất đẳng thức tam giác, ta có
AD < OA + OD và BC < OB + OC.
Suy ra AD + BC < AB + CD. Như vậy, nếu ta giữ nguyên n − 2 đoạn nối
còn lại và thay AB, CD bằng AD, BC thì tổng các đoạn nối của cách nối
mới nhỏ hơn cách nối cũ. Mâu thuẫn với tính nhỏ nhất. Vậy tồn tại cách nối
2n điểm bằng n đoạn thẳng xanh-đỏ sao cho chúng không cắt nhau.
Ví dụ 5. Tập hợp S các sinh viên của một trường đại học có tính chất: bất
kì hai sinh viên có cùng số người quen trong S thì không có người quen chung
trong S. Chứng minh rằng tồn tại sinh viên chỉ có đúng một người quen trong
S.
Trang 4
Lời giải. Do tập hợp S có hữu hạn sinh viên nên tồn tại một sinh viên quen
với nhiều người nhất. Gọi sinh viên đó là A và Ai (i = 1, . . . , n) là những
sinh viên người đó quen. Do các sinh viên Ai cùng quen A nên số người quen
của họ không bằng nhau và không lớn hơn n. Do đó số người quen của các
sinh viên này lần lượt là 1, 2, . . . , n. Vậy tồn tại một sinh viên chỉ quen với
đúng 1 người.
Ví dụ 6. Có 3 trường học, mỗi trường học có n học sinh. Mỗi học sinh quen
với ít nhất n + 1 học sinh từ hai trường khác. Chứng minh rằng người ta có
thể chọn ra từ mỗi trường một bạn sao cho ba học sinh được chọn đôi một
quen nhau.
Lời giải. Gọi A là học sinh có nhiều bạn nhất ở một trường khác. Gọi số
bạn là k. Giả sử A ở trường 1 và những bạn quen A là B1 , B2 , . . . , Bk ở
n+1
. Cũng theo giả thiết, có ít nhất 1 học sinh C ở
trường 2. Ta có k ≥
2
trường 3 quen với A. Giả sử C không quen với Bi với mọi i = 1, 2, . . . , k thì
C quen với nhiều nhất n − k học sinh của trường 2. Suy ra C quen với ít
nhất n + 1 − (n − k) = k + 1 học sinh ở trường 1, điều này mâu thuẫn với
cách chọn A. Vậy C phải quen với một bạn Bi nào đó. Khi đó A, Bi và C
chính là 3 học sinh cần tìm.
Ví dụ 7. Một nước có 100 sân bay, mà khoảng cách giữa hai sân bay nào
cũng khác nhau. Mỗi máy bay cất cánh từ một sân bay và bay đến sân bay
nào gần nhất. Chứng minh rằng không có sân bay nào có quá 5 chuyến bay
đến.
Lời giải. Giả sử tồn tại một sân bay có hơn 5 chuyến bay đến. Gọi O là sân
bay đó và Ai (i ∈ {1, . . . , 6}) là một trong các sân bay bay đến O. Không
mất tính tổng quát, ta có thể giả sử thứ tự các sân bay này duyệt theo chiều
kim đồng hồ từ A1 là A1 A2 A3 A4 A5 A6 .
6
Ai OAi+1 = 360◦ nên tồn tại i để Ai OAi+1 ≤ 60◦ (xem A7 ≡ A1 ).
Khi đó
i=1
Do đó, một trong hai góc còn lại của tam giác Ai OAi+1 lớn hơn 60◦ (do các
khoảng cách không bằng nhau) ⇒ Ai Ai+1 < max{OAi , OAi+1 }, mâu thuẫn
với giả thiết (vì nếu Ai Ai+1 < OAi thì sân bay Ai có chuyến bay đến Ai+1
chứ không phải đến O).
• Chú ý: Con số 100 trong đề bài thực ra không có tác dụng gì ngoài
việc cho thấy là có thể có khả năng một sân bay có hơn 5 chuyến bay đến
(cần ít nhất là 7 sân bay để có thể có điều đó). Ta có thể thay nó bằng 1 con
số khác lớn hơn hoặc bằng 7 và cách giải quyết bài toán này cũng như vậy.
Ví dụ 8. (Định lí Sylvester) Cho tập hợp S gồm hữu hạn các điểm trên
mặt phẳng thỏa mãn tính chất sau: Một đường thẳng đi qua hai điểm thuộc
S đều đi qua ít nhất một điểm khác thuộc S. Khi đó tất cả các điểm của S
nằm trên một đường thẳng.
Trang 5
Lời giải. Giả sử phản chứng là tồn tại một tập hợp S gồm hữu hạn điểm
không thẳng hàng nhưng mọi đường thẳng qua hai điểm trong S đều chứa
ít nhất ba điểm thuộc S. Xét tập hợp A = {h|h > 0 và h là khoảng cách từ
một điểm thuộc S đến một đường thẳng đi qua hai điểm thuộc S}.
Do giả thiết phản chứng nên A = ∅ và A là
tập hợp có hữu hạn phần tử. Theo nguyên lí cực
hạn thì A có phần tử nhỏ nhất h◦ . Giả sử h◦
M
là khoảng cách từ M đến đường thẳng đi qua
E
B, C (M, B, C ∈ S). Theo giả thiết phản chứng
thì tồn tại D ∈ S và D nằm trên đường thẳng
F
BC. Kẻ M H⊥BC thì M H = h◦ . Rõ ràng trong
3 điểm B, C, D thì theo nguyên lí Dirichlet phải
có ít nhất 2 điểm nằm cùng phía so với H trên
B
H
C
D
đường thẳng BC. Giả sử C nằm giữa H và D.
Kẻ HE và CF vuông góc với MD. Rõ ràng ta có
CF < HE < M H.
Mà CF ∈ A và CF < h◦ nên giả thiết phản chứng bị sai, tức là tất cả các
điểm thuộc S thẳng hàng với nhau.
Ví dụ 9. Trong một cuộc thi Toán có 65 học sinh tham gia đến từ hai trường.
Mỗi học sinh thi một trong 4 môn Toán, Lí, Hoá, Anh Văn. Biết rằng trong
5 học sinh thi cùng một môn thì có hai học sinh cùng tuổi. Chứng minh rằng
trong 65 học sinh có ít nhất 3 học sinh đến từ một trường, thi cùng một môn
và bằng tuổi nhau.
Lời giải. Giả sử không có 3 học sinh nào thoả yêu cầu bài toán.
Vì có 65 học sinh đến từ hai trường nên có ít nhất 33 học sinh đến từ một
trường. Xét 33 học này thì có ít nhất 9 học sinh thi cùng một môn.
Ta xét 9 học sinh này:
Lấy 5 học sinh bất kì trong 9 học sinh trên. Khi đó sẽ có hai học sinh cùng
tuổi, ta giả sử đó là hai học sinh A1 , B1 . Ta loại hai học sinh này còn lại 7
trong học sinh và trong 7 học sinh nay ta tìm được hai học sinh cùng tuổi
A2 , B2 . Sau khi loại hai học sinh này ta còn lại 5 học sinh và tiếp tục chọn
được 2 học sinh A3 , B3 .
Xét 3 học sinh A1 , A2 , A3 ta có tuổi của ba học sinh này đôi một khác nhau.
Xét 5 học sinh gồm ba học sinh A1 , A2 , A3 với 2 trong ba học sinh còn lại,
khi đó hai học sinh còn lại ta kí hiệu A4 , B4 cùng tuổi nhau.
Xét 5 học sinh gồm 4 học sinh A1 , A2 , A3 , A4 và học sinh còn lại (ta kí hiệu
là A5 ). Khi đó A5 sẽ cùng tuổi với 1 trong 4 học sinh A1 , A2 , A3 , A4 . Chẳng
hạn A5 , A1 cùng tuổi. Khi đó A1 , B1 , A5 thoả yêu cầu bài toán . Điều này
mâu thuẫn với điều giả sử ở trên. Vậy bài toán được chứng minh.
Ví dụ 10. (Trận đấu toán học Nga 2010) Một quốc gia có 210 thành
phố. Ban đầu giữa các thành phố chưa có đường. Người ta muốn xây dựng
một số con đường một chiều nối giữa các thành phố sao cho: Nếu có đường
Trang 6
đi từ A đến B và từ B đến C thì không có con đường đi từ A đến C. Hỏi có
thể xây dựng được nhiều nhất bao nhiêu đường?
Lời giải. Gọi A là thành phố có nhiều đường đi nhất (gồm cả đường đi xuất
phát từ A và đường đi đến A). Ta chia các thành phố còn lại thành 3 loại.
• Loại I - có đường đi xuất phát từ A.
• Loại II - có đường đi đến A.
• Loại III - không có đường đi đến A hoặc xuất phát từ A.
Đặt m = |I|, n = |II|, p = |III|. Ta có m + n + p = 209.
Dễ thấy giữa các thành phố loại I không có đường đi. Tương tự, giữa các
thành phố loại II không có đường đi. Số các đường đi liên quan đến các thành
phố loại III không vượt quá p(m+n) (Do bậc của A = m + n là lớn nhất).
Tổng số đường đi bao gồm:
• Các đường đi liên quan đến A: m + n.
• Các đường đi liên quan đến III: ≤ p(m + n).
• Các đường đi giữa I và II: ≤ mn.
Suy ra tổng số đường đi nhỏ hơn
2102
(m + n + p + 1)2
=
.
mn + (p + 1)m + (p + 1)n ≤
3
3
Dấu bằng xảy ra với đồ thị 3 phe, mỗi phe có 70 thành phố, thành phố phe
1 có đường đi đến thành phố phe 2, thành phố phe 2 có đường đi đến thành
phố phe 3, thành phố phe 3 có đường đi đến thành phố phe 1.
Ví dụ 11. Trong quốc hội Mỹ, mỗi một nghị sĩ có không quá 3 kẻ thù. Chứng
minh rằng có thể chia quốc hội thành 2 viện sao cho trong mỗi viện, mỗi một
nghị sĩ có không quá một kẻ thù.
Lời giải. Ta chia quốc hội ra thành 2 viện A, B một cách bất kỳ. Với mỗi
viện A, B, ta gọi s(A), s(B) là tổng của tổng số các kẻ thù của mỗi thành
viên tính trong viện đó. Vì số cách chia là hữu hạn nên phải tồn tại cách chia
(A0 , B0 ) sao cho s(Ao ) + s(B0 ) nhỏ nhất. Ta chứng minh cách chia này thỏa
mãn yêu cầu bài toán.
Giả sử rằng cách chia này vẫn chưa thoả mãn yêu cầu, tức là vẫn có một
nghị sĩ nào đó có nhiều hơn 1 kẻ thù trong viện của mình. Không mất tính
tổng quát, giả sử nghị sĩ x thuộc A0 có ít nhất 2 kẻ thù trong A0 . Khi đó ta
thực hiện phép biến đổi sau: chuyển x từ A0 sang B0 để được cách chia mới
là A = A0 \ {x} và B = B0 \ {x}. Vì x có ít nhất 2 kẻ thù trong A0 và A
không cón chứa x nên ta có s(A ) ≤ s(A0 ) − 4 (trong tổng mất đi ít nhất 2
Trang 7
của s(x) và 2 của các kẻ thù của x trong A0 ).
Vì x có không có quá 3 kẻ thù và có ít nhất 2 kẻ thù trong A0 nên x có
nhiều nhất 1 kẻ thù trong B0 (hay B ) cho nên s(B ) ≤ s(B0 ) + 2. Từ
đó s(A ) + s(B ) ≤ s(A0 ) + s(B0 ) − 2. Mâu thuẫn với tính nhỏ nhất của
s(A0 ) + s(B0 ). Vậy điều giả sử là sai, tức là cách chia (A0 , B0 ) thỏa mãn yêu
cầu bài toán.
Ví dụ 12. Chứng minh rằng trên mặt phẳng tọa độ, không thể tìm được
năm điểm nguyên là đỉnh của một ngũ giác đều. (Một điểm M (x; y) trên mặt
phẳng tọa độ được gọi là “điểm nguyên” nếu cả hai tọa độ x, y của nó đều là
những số nguyên)
Lời giải. Giả thiết trái lại, tồn tại một ngũ giác đều sao cho 5 đỉnh của nó
đều là các “điểm nguyên”. Ta xét tập hợp sau:
Ω = {a2 |a là cạnh của ngũ giác đều có năm đỉnh là các “điểm nguyên”}.
Dễ thấy, do a là cạnh của ngũ giác đều với các đỉnh nguyên, nên a2 là số
nguyên dương.
Thật vậy, giả sử Aa A2 A3 A4 A5 là đa giác giác đều thuộc Ω. Giả sử Ai (xi ; yi ),
i = 1, n, thì nếu gọi a là cạnh của ngũ giác đều này, ta có:
a2 = A1 A2 = (x1 − x2 )2 + (y1 − y2 )2 .
2
Do xi , yi ∈ Z, ∀i = 1, 5 nên a2 là số nguyên dương. Tập Ω = ∅, điều này suy
ra từ giả thiết phản chứng.
Tập Ω các số tự nhiên, khác rỗng nên theo nguyên lí cực hạn suy ra tồn
tại phần tử nhỏ nhất, tức là tồn tại ngũ giác đều ABCDE sao cho a2 là số
0
nhỏ nhất, ở đây a0 là cạnh của ngũ giác đều này. Dễ thấy ABCB , BCDC ,
CDED , DEAE và EABA đều là các hình bình hành với BD ∩ CE =
A , AD ∩ CE = B , AD ∩ BE = C , AC ∩ BE = D , AC ∩ BD = E . Từ hình
bình hành EABA suy ra
xA = xB + xE − xA
yA = yB + yE − yA .
Do A, B, C, D, E là các “điểm nguyên” nên suy ra A cũng là “điểm nguyên”.
Tương tự ta có B , C , D , E cũng là các “điểm nguyên”. Rõ ràng A B C D E
Trang 8
là ngũ giác đều có các đỉnh là các “điểm nguyên” mà nếu gọi cạnh của ngũ
giác đều này là a0 thì rõ ràng a02 < a2 (mâu thuẫn với việc a2 là giá trị nhỏ
0
0
nhất). Vậy giả thiết phản chứng là sai nên không tồn tại ngũ giác đều có các
đỉnh đều là “điểm nguyên”.
2.3
Bài tập tự luyện
Bài tập 1 Trên đường thẳng cho 50 đoạn thẳng. Chứng minh rằng hoặc có
8 đoạn thẳng trong chúng đôi một giao nhau, hoặc có 8 đoạn
thẳng trong chúng đôi một rời nhau.
Bài tập 2 Chứng minh rằng mọi đa giác lồi có diện tích bằng 1 đều có thể
phủ bằng một hình chữ nhật có diện tích không lớn hơn 2.
Bài tập 3 Có một bộ quả cân có tính chất sau:
i) Trong bộ có ít nhất 5 quả cân có trọng lượng khác nhau.
ii) Với hai quả cân bất kì, tìm được hai quả cân khác có tổng
trọng lượng bằng với tổng trọng lượng của hai quả cân đó.
Hỏi bộ quả cân này có ít nhất là bao nhiêu quả cân?
Bài tập 4 Chứng minh rằng nếu a, b là các số nguyên dương sao cho k =
a2 + b2
là số nguyên thì k = 5.
ab − 1
Bài tập 5 Một số thực dương được viết lên bảng. Tổng của các tích đôi một
của chúng bằng 1. Chứng minh rằng ta có thể xóa đi một số để
√
tổng các số còn lại nhỏ hơn 2.
Bài tập 6 Trong mặt phẳng cho n điểm (n > 1). Hai người chơi lần lượt
nối một cặp điểm chưa được nối bằng một vector với một trong
hai chiều. Nếu sau nước đi của người nào đó, tổng các vector đã
vẽ bằng 0 thì người thứ hai thắng; nếu cho đến khi không còn
vẽ được vector nào nữa mà tổng vẫn chưa có lúc nào bằng 0 thì
người thứ nhất thắng. Hỏi ai là người thắng cuộc nếu chơi đúng?
Bài tập 7 Trên mặt phẳng kẻ những đường thẳng song song cách đều.
Chứng minh rằng không thể dựng được một ngũ giác đều có
đỉnh chỉ nằm trên các đường thẳng này.
Bài tập 8 Cho đa giác lồi A1 A2 A3 . . . An . Chứng minh rằng tồn tại ba đỉnh
liên tiếp sao cho hình tròn qua ba đỉnh này chứa toàn bộ đa giác
đã cho.
Trang 9
Bài tập 9 Trên một đường thẳng đánh dấu n điểm khác nhau A−1, A2 , . . . , An
theo thứ tự từ trái qua phải (n ≥ 4). Mỗi điểm được tô bằng một
trong bốn màu khác nhau và cả bốn màu đều được dùng. Chứng
minh rằng tồn tại một đoạn thẳng chứa đúng hai điểm của hai
màu và ít nhất của hai màu còn lại.
Bài tập 10 Từ một điểm M cho trước ở trong một đa giác lồi hạ các đường
vuông góc xuống các cạnh của đa giác. Chứng minh rằng tồn tại
một cạnh của đa giác mà chân đường vuông góc hạ từ M xuống
cạnh này thì nằm ở phía trong của nó.
Bài tập 11 Cho 997 điểm khác nhau trên mặt phẳng. Chứng minh rằng tồn
tại ít nhất 1991 trung điểm khác nhau từ các cặp điểm này. Khi
nào thì có đúng 1991 trung điểm khác nhau.
Bài tập 12 Trên mặt phẳng cho một số hữu hạn điểm không cùng nằm trên
một đường thẳng. Chứng minh rằng tồn tại ba điểm sao cho
đường tròn đi qua ba điểm đó không chứa điểm nào ở bên trong.
Bài tập 13 Bên trong một hình vuông cạnh 1 cho n điểm sao cho không có
ba điểm nào thẳng hàng. Chứng minh rằng tồn tại một tam giác
có đỉnh tại các điểm đã cho và diện tích S của nó thỏa mãn bất
1
.
đẳng thức: S <
n−2
3
Hiệu quả của đề tài
Học sinh có thêm kinh nghiệm trong việc xử lý các bài toán tổ hợp bằng
phương pháp sử dụng nguyên lí cực hạn.
Trang 10
4
Tài liệu tham khảo
1. Đoàn Quỳnh - Doãn Minh Cường - Trần Nam Dũng - Đặng Hùng Thắng
(2010), “Tài liệu chuyên toán đại số 10”, Nhà xuất bản giáo dục Việt
Nam, 2012.
2. Phan Huy Khải, “Chuyên đề bồi dưỡng học sinh giỏi toán Trung
học phổ thông: Các bài toán hình học Tổ hợp”, Nhà xuất bản Giáo
dục, 2007.
3. Trần Nam Dũng, “Nguyên lí cực hạn)”, 2012.
Người thực hiện
Phạm Doãn Lê Bình
Trang 11
BM04-NXĐGSKKN
SỞ GD&ĐT ĐỒNG NAI
Đơn vị THPT chuyên Lương Thế Vinh
CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập - Tự do - Hạnh phúc
................................, ngày
tháng
năm
PHIẾU NHẬN XÉT, ĐÁNH GIÁ SÁNG KIẾN KINH NGHIỆM
Năm học:2016 - 2017
–––––––––––––––––
Tên sáng kiến kinh nghiệm: NGUYÊN LÍ CỰC HẠN TRONG CÁC BÀI TOÁN TỔ HỢP
...............................................................................................................................................
Họ và tên tác giả: Phạm Doãn Lê Bình
Chức vụ: Giáo viên
Đơn vị: THPT chuyên Lương Thế Vinh.
Lĩnh vực: (Đánh dấu X vào các ô tương ứng, ghi rõ tên bộ môn hoặc lĩnh vực khác)
- Quản lý giáo dục
- Phương pháp dạy học bộ môn: ...............................
- Phương pháp giáo dục
- Lĩnh vực khác: ........................................................
Sáng kiến kinh nghiệm đã được triển khai áp dụng: Tại đơn vị
Trong Ngành
1. Tính mới (Đánh dấu X vào 1 trong 2 ô dưới đây)
- Có giải pháp hoàn toàn mới
- Có giải pháp cải tiến, đổi mới từ giải pháp đã có
2. Hiệu quả (Đánh dấu X vào 1 trong 4 ô dưới đây)
- Hoàn toàn mới và đã triển khai áp dụng trong toàn ngành có hiệu quả cao
- Có tính cải tiến hoặc đổi mới từ những giải pháp đã có và đã triển khai áp dụng trong
toàn ngành có hiệu quả cao
- Hoàn toàn mới và đã triển khai áp dụng tại đơn vị có hiệu quả cao
- Có tính cải tiến hoặc đổi mới từ những giải pháp đã có và đã triển khai áp dụng tại đơn vị
có hiệu quả
3. Khả năng áp dụng (Đánh dấu X vào 1 trong 3 ô mỗi dòng dưới đây)
- Cung cấp được các luận cứ khoa học cho việc hoạch định đường lối, chính sách:
Tốt
Khá
Đạt
- Đưa ra các giải pháp khuyến nghị có khả năng ứng dụng thực tiễn, dễ thực hiện và dễ đi
vào cuộc sống:
Tốt
Khá
Đạt
- Đã được áp dụng trong thực tế đạt hiệu quả hoặc có khả năng áp dụng đạt hiệu quả trong
phạm vi rộng:
Tốt
Khá
Đạt
Phiếu này được đánh dấu X đầy đủ các ô tương ứng, có ký tên xác nhận của người có
thẩm quyền, đóng dấu của đơn vị và đóng kèm vào cuối mỗi bản sáng kiến kinh nghiệm.
XÁC NHẬN CỦA TỔ CHUYÊN MÔN
(Ký tên và ghi rõ họ tên)
THỦ TRƯỞNG ĐƠN VỊ
(Ký tên, ghi rõ họ tên và đóng dấu)