Tạp chí Toán Sputnik - Số 1, Tháng 1 năm 2017

Số 1, tháng 1 năm 2017
SPUTNIK NEWSLETTER
Tạp chí điện tử miễn phí về toán học,
giáo dục, các khoa học, và các tin tức Sputnik
Trong số này:
Các bài toán hình học tổ hợp tại IMO . . . . . . . . . . . . . 2
Romeo đi tìm công chúa (21 câu đố lô-gic và chiến lược) . . 29
Các tiêu chí cho sách giáo khoa về toán . . . . . . . . . . . . 48
Học tiếng Anh cùng “Hoàng tử bé” . . . . . . . . . . . . . . 52
Một vài hình ảnh về các hoạt động của Sputnik . . . . . . . 65
Kể từ Số 2, Sputnik Newsletter nhận đăng chọn lọn các bài viết
về các chủ đề: toán học, STEM, quan điểm giáo dục, giới thiệu sách,
v.v. Tác giả của các bài được đăng sẽ được tặng các bộ sách Sputnik.
Liên hệ bài vở: lbphuong@sputnik.vn, shop@sputnikedu.com
1
Hình học tổ hợp tại IMO
Quyển sách “Hình học tổ hợp” (Tủ sách Sputnik, số 032), tác giả
là Nhà giáo Nhân dân Vũ Hữu Bình, mà các bạn đọc mong đợi bao
lâu, đã được in ra đúng vào những ngày cuối năm 2016. Đây thực sự
là một quyển sách rất bổ ích cho các học sinh THCS và THPT muốn
phát triển thêm năng khiếu về môn toán, và được rất nhiều bạn đọc
quan tâm. Sputnik kỳ vọng sẽ bán hết 3000 cuốn sách này trong vòng
4 tháng đầu năm 2017.
Các bài hình học tổ hợp thường hay xuất hiện trong các kỳ thi
olympic, đặc biệt là IMO (International Mathematical Olympiad). Và
phần lớn các bài này là “sát thủ” đối với đoàn học sinh Việt Nam:
nhiều bài cả đoàn không ai làm được. Nhiều khi không phải vì chúng
quá khó, mà chẳng qua vì chúng “lạ” và học sinh Việt Nam chưa được
dạy cách tiếp cận các bài toán lạ để mà “trăm trận trăm thắng”.
GS Nguyễn Tiến Dũng gần đây có viết một bài hướng dẫn các bạn
học sinh về việc tiếp cận các bài toán lạ như thế nào, qua ví dụ 5 bài
hình học tổ hợp IMO từ 2013 đến 2016. Trong đó 4 bài đầu tiên được
đưa vào thành phần phụ lục của sách “Hình học tổ hợp” của thầy Vũ
Hữu Bình. Bài thứ 5 vì quá phức tạp, hướng dẫn cách giải quá dài
nên không cho vào sách.
2
Một chồng sách Hình Học Tổ Hợp (Tủ sách Sputnik, số 032).
Ở đây, Sputnik xin giới thiệu đầy đủ cả 5 bài, bao gồm đề bài và
hướng dẫn giải. Bạn đọc nên giành nhiều thời gian cố gắng tự giải
những bài toán này trước khi xem lời giải ở phía sau.
Đề bài
Bài tập 1 (IMO 2015). Gọi V là một tập hữu hạn các điểm trên mặt
phẳng. Ta nói rằng V là cân bằng nếu với hai điểm phân biệt bất kỳ
A,B ∈ V tồn tại một điểm thứ ba C ∈ V sao cho CA = CB. Ta nói
rằng V là không có tâm nếu như không tồn tại một bộ bốn điểm phân
biệt A,B,C, P ∈ V sao cho PA = PB = PC.
i) Chứng minh rằng với n ≥ 3 tồn tại một tập hợp điểm V cân
3
bằng có đúng n điểm.
ii) Với những n ≥ 3 nào thì tồn tại tập hợp V cân bằng và không
có tâm với đúng n điểm?
Bài tập 2 (IMO 2013). Tìm số N nhỏ nhất thỏa mãn tính chất sau:
Lấy 2013 điểm tô trắng và 2014 điểm tô đen bất kỳ trên mặt phẳng
sao cho không có ba điểm nào thẳng hàng. Khi đó tồn tại N đường
thẳng trên mặt phẳng không đi qua điểm nào trong số các điểm trên
và chia mặt phẳng thành các miền sao cho các điểm trong cùng một
miền thì phải cùng màu.
Bài tập 3 (IMO 2014). Giả sử có n đường thẳng trên mặt phẳng sao
cho không có 2 đường nào song song và không có 3 đường nào đồng
quy. Chứng minh rằng có thể tô ít nhất
√
n đường màu xanh sao cho
không có miền bị chặn nào có biên toàn là màu xanh.
Bài tập 4 (Bài toán con ếch IMO 2016). Có N đoạn thẳng đôi một
giao nhau sao cho không có ba đoạn nào đồng quy. Như vậy, trên
mỗi đoạn có N − 1 điểm nút cắt và 2 nút đầu đuôi. Thầy Minh
(Nguyễn Khắc Minh) chơi trò như sau: Đặt N con ếch vào N điểm
nút ngoài cùng (nút đầu đuôi) của N đoạn thẳng đó, mỗi đoạn đặt
một con rồi thầy vỗ tay N lần. Mỗi lần vỗ tay thì tất cả con ếch đồng
thời nhảy, con nào cũng nhảy trên đoạn thẳng của con đó theo hướng
cố định từ điểm xuất phát đến đầu bên kia từ nút đang đứng sang
nút tiếp theo. Chứng minh rằng
i) Nếu N lẻ thì có thể đặt ếch sao cho khi nhảy như vậy không có
lần nào mà có 2 con ếch cùng nhảy vào 1 nút.
ii) Nếu N chẵn thì dù đặt ếch kiểu gì cũng có lúc có 2 con ếch
cùng nhảy vào 1 nút ở một lần vỗ tay nào đó.
4
Bài tập 5 (IMO 2013). Xét n + 1 điểm xếp đều nhau (n > 1) trên
vòng tròn được đánh số 0, 1, 2, ..., N theo một thứ tự vòng tròn nào
đó. Hai cách đánh số được coi là như nhau nếu có thể xoay vòng tròn
để di chuyển cách đánh số này sang thành cách đánh số khác. Một
cách đánh số như vậy gọi là đánh số đẹp (hay xếp đẹp) nếu với mọi
0 ≤ a < b < c < d ≤ n sao cho a+d = b+ c thì đoạn thẳng nối (điểm
đánh số) a với d không cắt đoạn thẳng nối b với c. GọiM(n) là số tất
cả các cách đánh số đẹp, N(n) là số tất cả các cặp số nguyên dương
có xếp thứ tự (k, l) nguyên tố cùng nhau sao cho k + l ≤ n. Chứng
minh rằngM(n) = N(n) + 1.
Hướng dẫn tìm lời giải
Bài tập 1. Trước khi xét n tùy ý, ta xét n từ nhỏ đến lớn rồi từ đó
tổng quát lên và phán đoán quy luật.
n = 3. Gọi A,B,C là ba điểm phân biệt của V . Giả sử V cân
bằng. Khi đó C phải là điểm cân bằng giữa A và B, tức là CA = CB
vì không còn điểm nào khác trong V . Tương tự như vậy, A phải là
điểm cân bằng của cặp điểm (B, C), tức là AB = AC. Suy ra AB =
BC = CA, tức4ABC là tam giác đều. Ngược lại nếu tam giác ABC
là tam giác đều thì V = {A,B,C} cân bằng và không có tâm (Hình
1).
n = 4. Tương tự như trường hợp n = 3, trong trường hợp n = 4
ta có thể sử dụng hai tam giác đều ghép thành hình quả trám để xây
dựng một tập hợp cân bằng (Hình 2).
Chú ý rằng trong ví dụ này thì V có tâm: BA = BC = BD và
DA = DB = DC. Câu hỏi là có thể xây dựng ví dụ khác mà không
5
Hình 1 Hình 2
có tâm được không?
Sau khi thử vài lần không được, ta đặt giả thuyết rằng điều đó
không thể được. Tức là, nếu tập hợp gồm 4 điểm là cân bằng thì nó
có tâm.
4 điểm lập thành 6 cặp điểm (không tính thứ tự trong các cặp).
Mỗi cặp điểm có (ít nhất) một điểm cân bằng của chúng.
Vì số cặp điểm là 6 mà số điểm là 4 nên theo nguyên lý Dirichlet
tồn tại một điểm là điểm cân bằng của ít nhất hai cặp điểm khác
nhau. Gọi hai cặp điểm đó là (A1, A2), (B1, B2) và điểm cân bằng
chung là C. Nếu tất cả các điểm A1, A2, B1, B2 là khác nhau thì V
có ít nhất 5 điểm phân biệt C,A1, A2, B1, B2, vô lý. Bởi vậy hai cặp
(A1, A2) và (B1, B2) phải có chung 1 điểm, không chung cả 2 vì nếu
vậy thì 2 cặp trùng nhau. Giả sử chẳng hạn A2 = B1 (Hình 3).
Khi đó, CA1 = CA2(= CB1) = CB2. Do đó, C là tâm điểm của
bộ 3 điểm (A1, A2, B2), tức là V có tâm.
n = 5. Ta có thể mở rộng ý tưởng từ các trường hợp n = 3, n = 4
lên trường hợp n = 5.
Nếu ta chấp nhận có tâm điểm như khi n = 4 thì ta có thể tạo hai
tam giác đều có cùng một đỉnh, không dính vào nhau và tách nhau
6
Hình 3 Hình 4
ra (Hình 4). Khi đó ta sẽ được một tập hợp cân bằng (và có tâm) với
5 điểm.
Nếu ta không muốn tập có tâm thì có thể thử mở rộng trường hợp
tam giác đều khi n = 3 lên thành đa giác đều khi n > 3.
Hình 5
Chẳng hạn, trong ngũ giác đều
ABCDE (Hình 5) thì hai đỉnh A và B
của cạnh AB cách đều điểm D còn hai
đỉnh A và C của đường chéo AC cách đều
điểm B. Tương tự như vậy cho các cạnh
và đường chéo khác, và do đó bộ đỉnh
V = {A,B,C,D,E} của một ngũ giác
đều là một tập hợp cân bằng và không có
tâm.
n > 5. Dựa trên các suy luận có trước, ta đưa ra giả thuyết sau:
a) Nếu n lẻ thì tồn tại cặp n điểm cân bằng và không có tâm điểm.
7
b) Nếu n chẵn thì cũng tồn tại tập n điểm cân bằng nhưng các
tập như vậy đều có tâm điểm.
Chứng minh. a) Thật vậy, chỉ cần sử dụng n−giác đều khi n lẻ.
Chú ý rằng khi n chẵn thì tập các đỉnh của n giác đều không phải là
tập cân bằng. Ví dụ như khi n = 4 thì đường trung trực của cạnh AB
của hình vuông ABCD không chứa đỉnh nào cả (Hình 6).
Hình 6 Hình 7
b) Khi n chẵn và n ≥ 4, ta có thể mở rộng ví dụ từ trường hợp
n = 4 và thêm vào đó các tam giác đều có chung một đỉnh. Trên Hình
7 minh họa ví dụ với n = 8.
Bây giờ ta sẽ chứng minh rằng:
Khi n = 2m ≥ 4 là số chẵn thì mọi tập V cân bằng với n điểm đều
chứa tâm điểm, bằng cách tương tự như khi n = 4.
Thật vậy, khi V có n = 2m điểm thì chúng lập thành:
C2n =
2m(2m− 1)
2
= 2m2 −m cặp điểm (không xếp thứ tự).
Mỗi cặp điểm có ít nhất một điểm cân bằng (cách đều) trong số
các điểm của V và vì V có 2m điểm nên sẽ có điểm P ∈ V là điểm
8
cân bằng của ít nhất
2m2 −m
2m
= m− 1
2
cặp điểm khác nhau, vì
1
2
< 1
nên thực ra P phải là điểm cân bằng của (ít nhất) m cặp điểm khác
nhau.
Nếu tất cả các điểm trong tất cả m cặp đó đều khác nhau thì
tổng cộng có 2m = n điểm phân biệt, thêm điểm P thành n + 1
điểm phân biệt trong V , vô lý. Như vậy có 2 cặp điểm trong số đó có
chung một điểm, ví dụ như cặp (A,B) và cặp (B,C). Khi đó, ta có
PA = PB = PC, tức là P là tâm điểm của bộ điểm (A,B,C).
Bài tập 2
Vẽ vài ví dụ (với ít điểm) để hiểu yêu cầu của bài toán trước khi
bắt tay vào giải (Hình 8).
Yêu cầu của bài toán là tìm số N nhỏ nhất sao cho trong mọi
trường hợp thì có thể chia tách các màu mà chỉ dùng không quá N
đường.
Hình 8
Gọi số điểm trắng là n thì số điểm đen là n+ 1.
9
Bài toán yêu cầu giải với n = 2013.
Vì n là số lớn nên ta thử tìm cách quy nạp theo n, đầu tiên giải
bài toán cho n nhỏ và tổng quát dần lên.
Với n = 1, ta có 1 điểm trắng và 2 điểm đen.
Hình 9
Dễ dàng dựng đường thẳng tách điểm trắng khỏi 2 điểm đen. Ví
dụ như là đường đi qua trung điểm các đoạn thẳng nối điểm trắng
với điểm đen (Hình 9).
Như vậy N(1) = 1 chỉ cần 1 đường thẳng.
Với n = 2, ta có 2 điểm trắng và 3 điểm đen.
Hình 10 Hình 11
Có những khi chỉ cần một đường thẳng là đủ để tách các điểm
trắng khỏi các điểm đen. Chú ý rằng các đường như thế sẽ phải cắt
mọi đoạn thẳng nối điểm trắng với điểm đen (Hình 10).
10
Nếu có 2 điểm trắng và 2 điểm đen tạo thành 4 đỉnh xen kẽ của
một tứ giác lồi (Hình 11) thì không thể có đường thẳng nào cắt cả 4
cạnh của tứ giác (các cạnh đó nối điểm trắng với điểm đen). Như vậy,
trong những ví dụ như thế thì một đường là không đủ, cần ít nhất
hai đường?
Hai đường có luôn đủ không?
Sau khi tiếp tục quan sát, ta đưa ra một chiến lược sau: Nếu lấy 2
đường thẳng tạo thành một dải rất hẹp chứa 2 điểm trắng thì dải đó
không chứa thêm điểm nào vì các điểm không thẳng hàng với nhau
và như vậy 2 đường thẳng này là đủ để tách 2 điểm trắng khỏi các
điểm đen (bất kể là có bao nhiêu điểm đen) (Hình 12).
Như vậy với n = 2 ta có N(2) = 2.
Hình 12
Từ N(1) = 1, N(2) = 2 ta tạm thiết lập một giả thuyết quy nạp:
N(n) = n,∀n. Nếu giả thuyết này là đúng thì đáp số của bài toán là
N(2013) = 2013.
Với n ≥ 3, ta có n điểm trắng và n+ 1 điểm đen.
Ta muốn chứng minh N(n) ≥ n (tức là tồn tại cấu hình cần đến
ít nhất n đường) và N(n) ≤ n (tức là luôn có cách làm với n đường).
Để xây dựng cấu hình cần ít nhất n đường ta có thể xây dựng
tương tự như khi n = 2. Lấy các điểm sao cho chúng là đỉnh của một
đa giác lồi với n đỉnh trắng và n đỉnh đen xen kẽ nhau (và thừa thêm
một điểm đen ở đâu đó) (Hình 13). Nếu các đường muốn tách các
11
điểm trắng khỏi các điểm đen thì chúng phải cắt tất cả các cạnh của
đa giác này. Vì có 2n cạnh và mỗi đường chỉ cắt được (nhiều nhất là)
hai cạnh nên cần ít nhất là
2n
n
= n đường.
Hình 13
Bây giờ ta muốn chỉ ra cách làm
với n đường. Trong trường hợp n =
2m là số chẵn, ta có thể làm tương tự
như khi n = 2. Tức là ta chia các điểm
trắng thành m =
n
2
cặp điểm (một
cách tùy ý) rồi với mỗi cặp điểm trắng
này ta kẻ hai đường tạo thành một dải
hẹp chứa hai điểm trắng này và không
chứa thêm điểm nào khác.
Hình 14
Bằng cách đó ta có m × 2 = 2m = n đường thẳng tách toàn bộ
các điểm trắng ra khỏi các điểm đen (Hình 14).
Khi n = 2m+1 là số lẻ, ta cũng thử làm như trên và chia các điểm
trắng thành từng cặp được 2m cặp và một điểm lẻ. Nếu có điểm lẻ
nào mà có thể tách được chỉ bằng một đường thì tốt, vì 2m điểm còn
lại có thể làm như trên.
12
Để xét xem có điểm trắng nào mà tách được ra khỏi các điểm
khác bởi một đường hay không, ta có thể xét bao lồi của toàn bộ các
điểm. Bao lồi đó sẽ là một đa giác.
a) Đa giác đó có đỉnh màu trắng (Hình 15). Khi đó có thể lấy đỉnh
đó làm điểm trắng lẻ và kẻ một đường thẳng tách nó ra khỏi tất cả
các điểm còn lại.
b) Tất cả các đỉnh của bao lồi đều màu đen (Hình 16).
Khi đó ta tách được 2 đỉnh đen sát nhau bằng 1 đường nằm sát
cạnh tương ứng rồi chia (n + 1) − 2 = 2m đỉnh đen còn lại thành m
cặp và dựng m dải nhỏ để tách chúng ra (như là lúc trước làm với
các điểm trắng). Ta dùng tổng cộng 2m+ 1 = n đường và tách được
toàn bộ các điểm đen khỏi điểm trắng.
Hình 15 Hình 16
Bài tập 3.
Đoàn học sinh thi IMO của Việt Nam năm 2014 không có bạn nào
giải được bài này nên có thể coi đây là bài toán khó. Tuy nhiên, nếu
ta biết suy luận đúng hướng thì sẽ tìm được lời giải khá ngắn gọn,
chẳng hề phức tạp.
13
Con số
√
n trong bài có thể gây hoang mang vì khi có n đoạn
thẳng cắt nhau thì số điểm cắt, số đoạn cắt, số miền sẽ là những
đa thức theo n chứ không có dạng căn thức. Sự hoang mang có ảnh
hưởng xấu đến tâm lý khiến việc tìm lời giải trở nên khó khăn hơn.
Bỏ qua sự hoang mang đó, ta thử làm một thuật toán “ngây thơ”
để giải quyết vấn đề tô màu này xem nó có thể gặp bế tắc ở đâu.
Thuật toán ngây thơ đó là: Đầu tiên ta tô một đường bất kỳ màu
xanh. Sau đó nếu còn tô thêm đường nào đó màu xanh sao cho không
có miền nào có biên toàn màu xanh thì ta còn tô tiếp đường đó, còn
đến lúc không còn tô được thêm nữa thì dừng lại. Gọi số đường đã
tô xanh vào thời điểm dừng lại là k. Nếu ta chứng minh được k2 ≥ n
thì thuật toán của ta là tốt và ta giải quyết xong bài toán.
Như vậy sử dụng phương pháp phản chứng, ta muốn đưa bài
toán ban đầu về bài toán sau: Giả sử đã tô được k đường xanh và
k2 < n. Khi đó còn tô thêm được ít nhất một đường nữa. Để chứng
minh điều đó chỉ cần chứng minh rằng số đường cấm không vượt quá
k2 − k = k(k − 1). Đường cấm là đường chưa được tô xanh và nếu tô
nó màu xanh thì sẽ có miền bị chặn có biên toàn màu xanh.
Ta lại quan sát điều sau: Số điểm nút xanh =
k(k − 1)
2
(điểm nút
xanh = điểm giao nhau của hai đường xanh). Con số này bằng
1
2
chặn trên của số đường cấm mà ta muốn chứng minh. Từ đây nảy
ra ý tưởng: Nếu chẳng hạn mỗi đường cấm phải được gắn với một
điểm nút xanh và trong cách gắn đó mỗi điểm nút xanh được gắn với
không quá 2 đường cấm thì số đường cấm không vượt quá hai lần số
điểm nút xanh, tức là không quá 2× k(k − 1)
2
= k(k−1) đường cấm.
Làm sao để liên hệ đường cấm với điểm nút xanh? Một đường
14
cấm tạo ra miền bị chặn có biên toàn xanh và có một khúc biên chính
là đường cấm đó. Trên miền đó có hai đỉnh nút xanh gần kề nhất với
đường cấm. Ta sẽ gọi hai tia cạnh xanh xuất phát từ hai đỉnh đó về
phía hai đỉnh trên đường cấm là hai tia liên đới (Hình 17).
Hình 17
Chú ý rằng hai đỉnh xanh
gần liền kề có thể trùng nhau
thành một đỉnh nhưng hai tia
liên đới không trùng nhau.
Như vậy mỗi đường cấm
ứng với ít nhất hai tia liên đới
(có thể nhiều hơn hai nếu tạo
ra nhiều miền bị chặn có biên
xanh).
Ngược lại từ mỗi đỉnh nút
xanh chỉ có bốn tia xanh xuất
phát tức là tạo ra nhiều nhất bốn tia liên đới cho tất cả các đường
cấm. (Dễ thấy một tia không thể là tia liên đới của hai đường cấm
cùng lúc).
Như vậy:
Số tia liên đới≤ số nút xanh×4 và số tia liên đới≥ số đường cấm× 2.
Suy ra, số đường cấm ≤ số nút xanh × 4
2
= 2× số nút xanh
= k(k + 1) = k2 − k.
Vậy nếu n > k2 thì trong số n − k > k2 − k đường chưa tô có ít
nhất 1 đường không bị cấm và ta có thể tô xanh đường đó.
Ghi chú. Quan hệ giữa đường cấm và nút xanh không phải là kiểu
15
“2 − 1” như ý tưởng ban đầu mà là quan hệ kiểu “4 − 2” nhưng vẫn
cho cùng bất đẳng thức về số đường cấm).
Bài tập 4.
Bài này có thể coi thuộc loại khó, đoàn học sinh đi thi IMO của
Việt Nam năm đó không ai giải được. Cái khó chủ yếu nằm ở chỗ nó
lạ, không theo khuôn mẫu đã được học để giải rập khuôn chứ thực
ra nó không phức tạp lắm. Ta có thể suy luận như sau:
Bước 1. Tìm cách đánh số các đoạn thẳng để tạo cái gì đó mà
bấu víu vào. Phương pháp “thông tin phụ” này cũng tương tự phương
pháp vẽ thêm hình phụ để giải quyết bài toán hình học thông thường.
Để đánh số ta có thể hình dung một vòng tròn thật to chứa tất
cả các đoạn thẳng bên trong rồi kéo dài các đoạn thẳng sao cho các
đỉnh của chúng nằm trên vòng tròn (Hình 18). Điều này tất nhiên
không làm thay đổi trò chơi. Sau khi làm như vậy ta có 2N điểm nút
trên vòng tròn, đánh số thứ tự xoay vòng (ngược chiều kim đồng hồ)
1 đến 2N . Chú ý rằng với mọi k thì điểm k và N + k là hai điểm của
cùng một đoạn thẳng. Điều này suy ra từ tính chất tất cả các đoạn
đều cắt nhau.
Bước 2. Nhận xét tiếp theo và là một quan sát quan trọng cho bài
toán: Nếu có 2 con ếch đặt liền nhau ở các vị trí k và k+1 (mod 2N)
lúc ban đầu thì thể nào chúng cũng cùng nhảy vào 1 điểm nút (chính
là điểm cắt nhau của đoạn Ik và đoạn Ik+1, với Ik là kí hiệu đoạn
thẳng có một đầu là điểm k) sau một số lần vỗ tay nào đó.
Thật vậy, tất cả các đoạn khác nếu cắt đoạn con kP (P là giao
của Ik và Ik+1) thì cũng cắt đoạn con (k + 1)P và ngược lại và do
đó số bước nhảy từ k đến P cũng bằng số bước nhảy từ k + 1 đến P
16
Hình 18 Hình 19
(Hình 19).
Bước 3. Thầy Minh muốn đặt ếch sao cho chúng không nhảy vào
nhau thì phải làm thế nào? Theo Bước 2 nếu đặt ếch, chẳng hạn, ở
điểm 1 (không mất tính tổng quát ta có thể giả sử như vậy) thì không
được đặt ở điểm 2 và do đó phải đặt ở điểm 2 + N cho đoạn thẳng
I2 = I2+N . Khi có ếch đặt ở điểm 2 + N thì không được đặt ở điểm
3+N kế bên mà phải đặt ếch ở điểm 3 cho đoạn thẳng đó và cứ thế.
Suy ra phải đặt theo kiểu “đặt 1 cách 1”:
1− 3− 5− 7.
Nếu N = 2m là số chẵn thì cứ tiếp tục như vậy ta có ếch được đặt
tại các điểm
1− 3− 5− ...− (2m− 1)− (2m+ 1) = N + 1− ...
Thế nhưng điều đó có nghĩa là ếch được đặt ở cả hai đầu 1 và
N + 1 của đoạn thẳng I1, mâu thuẫn với đề bài.
Như vậy ,ta đã chứng minh được rằng khi N chẵn thì dù đặt ếch
theo kiểu gì cũng có 2 con nhảy vào nhau (vào cùng nút) tại thời
điểm nào đó.
17
Hình 20
Bước 4. N = 2m + 1 là số lẻ
thì sao. Khi đó thì có thể xếp ếch
theo kiểu “đặt 1 cách 1” (Hình
20) sao cho trên mỗi đoạn thẳng
Ik có đúng một con ếch.
Để chứng minh rằng không có
hai con nào nhảy vào cùng một
nút cùng lúc ta có thể sử dụng
tính chẵn lẻ.
Chẳng hạn có hai con ếch được đặt tại i và j (mod 2N) và điểm
nút P là giao của Ii với Ij (Hình 21).
Hình 21
Chú ý rằng trên cung tròn ở giữa i và j có một số lẻ các điểm nút.
Vì một đoạn thẳng cắt “hình mẩu bánh ijP ” tại đúng 2 điểm (nếu
cắt) hoặc 0 điểm (nếu không cắt) nên tổng số các nút trên biên, trừ
ra i, j, P là số chẵn.
Số các nút trên cung ij là lẻ nên tổng số các nút trên iP và jP
cũng lẻ.
18
Suy ra tính chẵn lẻ của số bước từ i đến P và số bước từ j đến P
là khác nhau, nếu một số là chẵn thì số kia là lẻ và ngược lại.
Như vậy con ếch từ i sẽ không thể gặp con ếch từ j tại điểm P
vì số bước nhảy để chúng đến P là khác nhau về tính chẵn lẻ, không
thể bằng nhau.
Vậy ta đã chứng minh xong là khi N lẻ thì thầy Minh có cách xếp
ếch sao cho không có hai con nào nhảy vào cùng một chỗ tại một
bước nào đó.
Bài tập 5. Tương tự như với các bài toán khác có chứa n bất kỳ ta
sẽ thử tìm cách quy nạp theo n. Đàu tiên ta xét các trường hợp n nhỏ
rồi quan sát để mà phán đoán các quy luật (đưa ra các giả thuyết)
rồi tìm cách chứng minh các quy luật đó rồi áp dụng vào bài toán.
n = 1. Chỉ có 1 cách duy nhất "2 người ngồi đối diện nhau"
M(1) = 1, N(1) = 0 vì tất nhiên không có 2 số nguyên dương nào
có tổng nhỏ hơn hoặc bằng 1. Đẳng thứcM(1) = N(1) + 1 đúng cho
trường hợp này.
Hình 22 Hình 23
n = 2. Có 2 cách, M(2) = 2, còn N(2) = 1 vì chỉ có một cặp số
(1, 1) thỏa mãn yêu cầu. Như vậyM(2) = N(2) + 1.
19
n = 3. Có 3 cặp số thỏa mãn yêu cầu: (1, 1), (1, 2) và (2, 1). Như
vậy N(3) = 3. CònM(3) = 4 vì có 4 cách như trên Hình 24.
Hình 24
Dễ quan sát thấy rằng, nếu ta có một cách xếp đẹp cho các số từ
0 đến n trên vòng tròn thì khi bỏ số n đi ta sẽ được một cách xếp đẹp
cho các số từ 0 đến n− 1, vì các điều kiện vẫn như cũ. Như vậy, ta có
cách sau để xây dựng các cách xếp đẹp bằng quy nạp: Đầu tiên đánh
các