ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
-------------------------------------

Phan Thị Yến

PHƢƠNG PHÁP PHẢN CHỨNG VỚI
CÁC BÀI TOÁN PHỔ THÔNG

LUẬN VĂN THẠC SĨ KHOA HỌC

Hà Nội - 2017


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
-------------------------------------

Phan Thị Yến

PHƢƠNG PHÁP PHẢN CHỨNG VỚI
CÁC BÀI TOÁN PHỔ THÔNG
Chuyên ngành: Phƣơng pháp Toán sơ cấp
Mã số: 60460113

LUẬN VĂN THẠC SĨ KHOA HỌC

NGƢỜI HƢỚNG DẪN KHOA HỌC:
GS.TS ĐẶNG HUY RUẬN

Hà Nội - 2017

1.4.

Bài tập bổ sung. .............................................................................................................. 16

CHƢƠNG 2. PHƢƠNG PHÁP CHỨNG MINH PHẢN CHỨNG ................................................. 18
2.1.

Ví dụ mở đầu. ................................................................................................................. 18

2.2.

Cơ sở lý thuyết của phép chứng minh phản chứng. .................................................... 19

2.3.

Các bƣớc suy luận phản chứng. .................................................................................... 20

2.4.

Phƣơng pháp chứng minh dùng mệnh đề phản đảo. .................................................. 21

2.5.

Một số bài tập vận dụng. ............................................................................................... 23

2.6.

Một số bài toán bổ sung. ................................................................................................ 42

KẾT LUẬN ...................................................................................................................................... 44

Em xin chân thành cảm ơn!

1


CHƢƠNG 1. NGUYÊN LÝ DIRICHLET

1.1.

Giới thiệu.

Nguyên lý Dirichlet còn gọi là nguyên lý chuồng thỏ, hay nguyên lý ngăn kéo.
Nguyên lý Dirichlet đƣa ra nguyên tắc về sự sắp xếp, phân chia các phần tử vào các
lớp.
Nguyên lý Dirichlet đƣợc phát biểu vào năm 1834 bởi nhà Toán học nổi tiếng
ngƣời Đức – Johann Dirichlet (1805 -1859).
Sử dụng nguyên lý Dirichlet có thể chứng minh đƣợc sự tồn tại một cách dễ
dàng và cụ thể, nhƣng không đƣa ra đƣợc phƣơng pháp tìm một vật cụ thể. Đối với
những bài toán chỉ cần sự tồn tại, nguyên lý Dirchlet đƣợc phát biểu một các đơn
giản nhƣ sau: “Nhốt 10 chú thỏ vào 9 cái chuồng, thì ít nhất một chuồng có nhiều
hơn 1 con thỏ”.
Định lý 1.1 (Phát biểu tổng quát của nguyên lý Dirchlet).
Nếu m con thỏ đƣợc đặt vào n chuồng (m > n) thì ít nhất 1 chuồng có ít nhất
m
m
 n  con nếu m chia hết n, và ít nhất  n  +1 con nếu m không chia hết n.

1.2.

Một số dạng phát biểu của nguyên lý Dirichlet.

1.2.3. Dạng số học.
Nếu trung bình cộng của một số số lớn hơn a, thì sẽ có ít nhất một số
trong các số này lớn hơn a.
Dựa trên một số dạng phát biểu của nguyên lý Dirichlet, ta xét một số bài toán sau.
1.3.

Một số ví dụ ứng dụng nguyên lý Dirichlet.

Trƣớc hết ta sẽ giải một số bài toán bằng cách chọn các chú thỏ thích hợp.
Bài toán 1. Trong lớp có 30 học sinh. Khi viết chính tả bạn An phạm 13 lỗi, còn các
bạn khác phạm ít lỗi hơn. Chứng minh rằng trong lớp có ít nhất 3 học sinh đã mắc
một số lỗi nhƣ nhau khi viết chính tả (kể cả những học sinh không mắc lỗi nào).
Lời giải. Ở đây “thỏ” tức là các em học sinh, còn “lồng” là số lỗi đã phạm phải khi
các em viết chính tả.
Ta lập 14 lồng đƣợc đánh số từ 0 đến 13.
Lồng số 0 “nhốt” các em viết chính tả phạm 0 lỗi;
Lồng số 1 “nhốt” các em viết chính tả phạm 1 lỗi;
Lồng số i (0  i  13) “nhốt” các em viết chính tả phạm i lỗi;

3


Chỉ có em An phạm 13 lỗi khi viết chính tả, nên lồng số 13 chỉ có một mình em An,
29 em còn lại đƣợc “nhốt” vào các lồng từ 0 đến 12, tức là 29 em đƣợc “nhốt” vào
13 lồng. Theo nguyên lý Dirichlet, phải có ít nhất một lồng “nhốt” từ 3 em trở lên.
Chẳng hạn lồng i (0  i  12) có ít nhất ba em. Khi đó, ba em ở lồng i cùng phạm i
lỗi khi viết chính tả.
Bài toán đƣợc chứng minh.
Bài toán 2. Chứng minh rằng với mọi số nguyên dƣơng n trong n + 2 số tự nhiên đã
chọn luôn luôn tìm đƣợc hai số, mà hoặc tổng hoặc hiệu của chúng chia hết 2n.

thời có ngƣời, nên n ngƣời đã chọn ra chỉ đƣợc đƣa vào n – 1 “phòng”. Do đó, theo
nguyên lý Dirichlet, phải có ít nhất một “phòng”, chẳng hạn, “phòng” thứ t
(0  t  n  1) có ít nhất 2 ngƣời. Nhƣ vậy, có ít nhất hai ngƣời cùng có t ngƣời quen

trong n ngƣời đã chọn ra. Bài toán đƣợc chứng minh.
Bài toán 4. Một học sinh suốt một năm giải toán. Mỗi ngày em giải ít nhất một bài.
Để dành đều thời gian học tập các môn học khác, mỗi tuần em giải không quá 12
bài toán. Chứng minh rằng nhất định tìm đƣợc một số ngày liên tiếp, mà tổng số bài
toán em giải trong tất cả các ngày này là đúng 20 bài.
Lời giải. Xét trong n (n  1) tuần liên tiếp. Ký hiệu số bài tập em học sinh giải đƣợc
trong ngày thứ i là ai (1  i  7n) . Khi đó, có một dãy các số lƣợng bài tập em đã giải:
a1 , a2 ,....., ak , ak 1 ,....., a7 n .

Và số bài tập em giải đƣợc trong k ngày đầu là Sk  a1  a2  .....  ak (k  1, 2,.....,7n) .
Xét hai dãy S1 , S2 ,....., S7 n (1)
S1  20, S2  20,....., S7 n  20 (2)

Vì hàng ngày em giải ít nhất 1 bài toán, nên i, j (1  i, j  7n) , i  j  Si  S j .
Từ đó suy ra các số trong dãy (1) đều khác nhau, nên các số trong dãy (2) cũng
khác nhau.
Mặt khác, do mỗi tuần em giải không quá 12 bài toán và không ít hơn 1 bài toán.
Bởi vậy  i (1  i  7 n) đều có 1  Si  12n , nên mỗi số trong dãy (2) đều không vƣợt
quá 12n + 20.
Do đó tất cả các số thuộc dãy (1) và dãy (2) đều không nhỏ hơn 1 và không lớn hơn
12n + 20.

5


Cả dãy (1) và dãy (2) có đúng 2.7n = 14n số, mà mỗi số đều không nhỏ hơn 1 và

Nếu trong số các điểm còn lại, tồn tại điểm Bkhông trùng điểm A, sao cho
B   C1  .

Vì B   C1  nên AB > 1.

6


Xét hình tròn C2  tâm B, bán kính 1. Lấy điểm C bất kỳ trong số 25
điểm đã cho. Theo giả thiết, trong ba điểm A,B,C luôn tồn tại hai điểm có
khoảng cách nhỏ hơn 1, nên min CA, CB  1 . Vì thế C   C1  hoặc

C   C2  .
Điều này chứng tỏ rằng các hình tròn  C1  và C2  chứa tất cả 25 điểm
đã cho.
Theo nguyên lý Dirichlet, có ít nhất một trong hai hình tròn trên chứa
không ít hơn 13 điểm đã cho.
Bài toán 6. Cho hình chóp đáy là đa giác 9 cạnh. Tất cả các cạnh bên và 27 đƣờng
chéo của đa giác đáy đƣợc tô bằng một trong hai màu đỏ hoặc xanh. Chứng tỏ rằng:
Tồn tại ba đỉnh của hình chóp, sao cho chúng là những đỉnh của hình tam giác với
các cạnh đƣợc tô cùng màu.
Lời giải. Xét 9 cạnh bên. Vì 9 cạnh này đƣợc tô bằng hai màu đỏ hoặc xanh, nên
theo nguyên lý Dirichlet, tồn tại 5 cạnh bên đƣợc tô cùng màu.
Không giảm tổng quát, giả sử 5 cạnh bên SA1 , SA2 , SA3 , SA4 , SA5 đƣợc tô cùng màu đỏ.
Các điểm A1 , A2 , A3 , A4 , A5 xếp theo chiều ngƣợc chiều kim đồng hồ.
Xét đa giác A1 A2 A3 A4 A5 . Có hai khả năng sau xảy ra:
i.

Nếu A1 A2 là đƣờng chéo của đáy. Khi đó hiển nhiên A2 A4 và A1 A4 cũng
là các đƣờng chéo của đáy.

Tóm lại, bài toán đƣợc giải quyết hoàn toàn.
Bài toán 7. Trong mặt phẳng có 19 điểm, không có ba điểm nào thẳng hàng. Từ
mỗi điểm nối với từng điểm khác bằng một đoạn thẳng màu xanh hoặc đỏ, sao cho
tại mỗi điểm xuất phát ít nhất 13 đoạn thẳng màu đỏ.
Chứng tỏ rằng có ít nhất một tứ giác có đỉnh nằm trong số các điểm đã cho, mà các
cạnh và đƣờng chéo đều màu đỏ.
Lời giải. Giả sử P là một trong số các điểm đã cho và 13 đoạn thẳng xuất phát từ P
là PA1 , PA2 ,....., PA13 . Nối A1 với A2 , A3 ,....., A13 bằng 12 đoạn thẳng.

8


P

A13

A1

A4
A2
A3

Hình 3
Theo giả thiết, từ mỗi điểm nối đƣợc 18 đoạn thẳng với các điểm còn lại, trong đó
có ít nhất 13 đoạn màu đỏ. Do đó xuất phát từ mỗi điểm có tối đa 5 đoạn màu xanh.
Khi đó, trong các đoạn A1 A2 , A1 A3 ,....., A1 A12 , A1 A13 có ít nhất 7 đoạn màu đỏ. Giả sử
các đoạn màu đỏ đó là A1 A2 , A1 A3 ,....., A1 A8 .
Trong 6 đoạn A2 A3 , A2 A4 ,....., A2 A8 có ít nhất 1 đoạn màu đỏ, giả sử là A2 A3 . Khi đó,
tứ giác PA1 A2 A3 là tứ giác cần tìm.
Bài toán 8. Trong hình vuông đơn vị (cạnh bằng 1) có 101 điểm. Chứng tỏ rằng có

Giả sử M có k cạnh. Khi đó, có k mặt khác của khối đa diện có cạnh chung với M.
Do đó khối đa diện có ít nhất k + 1 mặt.
Vì mặt có số cạnh lớn nhất là k cạnh, nên mọi mặt của khối đa diện có số cạnh nhận
một trong các giá trị 3, 4,....., k .
Khối đa diện có ít nhất k + 1 mặt mà số cạnh của mỗi mặt nhận một trong k – 2 giá
trị, nên theo nguyên lý Dirichlet, có ít nhất hai mặt của khối đa diện có cùng số cạnh.
Bài toán 10. Một hình lập phƣơng có cạnh bằng 15 chứa 11000 điểm. Chứng minh
rằng có một hình cầu bán kính 1 chứa ít nhất 6 điểm trong số 11000 đã cho.
Lời giải. Chia mỗi cạnh của hình lập phƣơng thành 13 phần bằng nhau. Nhƣ thế
hình lập phƣơng đã cho đƣợc chia thành 133  2197 hình lập phƣơng nhỏ.
Do 11000 > 5.2197 = 10985, nên tồn tại ít nhất một hình lập phƣơng nhỏ, mà hình
lập phƣơng này chứa ít nhất 6 điểm.

10


Nhƣ đã biết, nếu gọi cạnh của hình lập phƣơng này là a, thì hình cầu ngoại tiếp có
1
2

bán kính là R, với R  .a 3 . Vì thế bán kính hình cầu ngoại tiếp hình lập phƣơng
nhỏ (cạnh của nó là

15
) là:
13
1 15
1
225 1 675 1
R  . . 3  . 3.

A

B

D

C

Hình 5
Lời giải. Vì đa giác đều 100 cạnh nội tiếp trong (C), nên có đúng 50 đƣờng kính
khác nhau mà các đầu mút của các đƣờng kính này đều là các đỉnh của đa giác đều
100 cạnh cho trƣớc.
Giả sử AB là một trong các đƣờng kính ấy và giả sử A tƣơng ứng với số a, B tƣơng
ứng với số b.Bây giờ ta gán cho đƣờng kính AB số a  b .
Do a, b1, 2,3,....., 49 nên dễ thấy: 0  a  b  48 .
Nhƣ vậy mỗi một trong 50 đƣờng kính vừa xét tƣơng ứng với một trong các số
1, 2,3,....., 48 . Theo nguyên lý Dirichlet, có ít nhất hai đƣờng kính (trong số 50

đƣờng kính) đƣợc đặt tƣơng ứng với cùng một số.
Không giảm tổng quát, giả sử hai đƣờng kính AC, BD đƣợc đặt tƣơng ứng cùng một
số và các đỉnh A, B, C, D tƣơng ứng với các số a, b, c, d trong đó c  a ; b  d (Nếu
không phải nhƣ thế thì chỉ việc đổi tên các đầu mút của đƣờng kính).
Theo giả thiết thì đƣờng kính AC ứng với số a – c, còn đƣờng kính BD ứng với số
d b.

Từ a  c  d  b  a  b  c  d .
Rõ ràngABCD là hình chữ nhật, do đó AB // CD.
Bài toán đã đƣợc chứng minh.

12

 Nếu 2b  a thuộc nhóm I thì b;2b  a; a là bộ ba số cần tìm.
b) 2a  b và 2b  a đều thuộc nhóm II.
Vì

(2a  b)  (2b  a ) a  b

nên
2
2

ab


; 2b  a  là bộ ba số
2a  b;
2



cần tìm.
Vậy bài toán đƣợc chứng minh.
Bài toán 14. Cho ba số nguyên tố lớn hơn 3. Chứng tỏ rằng tồn tại hai sốc có tổng
hoặc hiệu chia hết 12.
Lời giải. Ký hiệu p là số nguyên tố lớn hơn 3. Khi đó, p là số lẻ và p không chia hết
3.

13


Do đó, phép chia p :12 có số dƣ có thể là 1;5;7;11 .

m lần

14

n lần


 123123.....123000000.....000
m-n lần

n lần

 122(tm  r )  122(tn  r )
 122(tm  tn ) 122

Vậy A chia hết 122.
Bài toán 16. Chứng minh rằng với mọi số nguyên dƣơng n đều tìm đƣợc số tự
nhiên là lũy thừa của 3, mà nó tận cùng bằng 00.....01 .
n1

Lời giải. Xét dãy số gồm 10n lũy thừa khác nhau của 3:
3,32 ,33 ,.....,3s3s1,.....,3t 3t 1,.....,310 1,310 (*) .
1

n

Các số của dãy này chia 3 sẽ đƣợc 10n số dƣ.
Vì tất cả các số của dãy (*) đều là số lẻ, nên chúng không chia hết cho 10n . Bởi vậy
10n số dƣ chỉ thuộc tối đa 10n - 1 loại nên phải có ít nhất hai số dƣ trùng nhau.



 10(s  t ) 10

ai  a j  (10.s  r )  (10.t  r )
 10(s  t )  2r 2

Bởi vậy (ai  a j )(ai  a j ) 20 hay ai2  a2j 20 .
Bài toán đƣợc chứng minh.
Bài toán 18. Cho 92 số tự nhiên bất kỳ có ba chữ số. Lấy hai số bất kỳ trong 92 số
này viết kề nhau ta thu đƣợc số có sáu chữ số. Chứng tỏ rằng bằng cách làm này ta
luôn có số có sáu chữ số chia hết 91.
Lời giải. 92 số tự nhiên khi chia cho 91 thu đƣợc không quá 91 loại số dƣ. Theo
nguyên lý Dirichlet, tồn tại hai số có cùng số dƣ khi chia cho 91.
Không giảm tổng quát, giả sử hai số đó là abc và mnp .
Ta có abcmnp = abc .1000 + mnp
 (91.s  r ).1000 + (91.t  r )
 91(1000s  t ) + 1001r
 91(1000s  t )  91.11r 91

Vậy bài toán đƣợc chứng minh.
1.4.

Bài tập bổ sung.

1.4.1. Viết 7 số tự nhiên bất kỳ, mỗi số vào một tấm bìa. Chứng tỏ rằng có
thể chọn ra một hay nhiều tấm bìa để tổng các số trên đó chia hết 7.
1.4.2. (Dạng tổng quát của bài 1.4.1) Chứng tỏ rằng từ tập hợp tùy ý gồm n
số tự nhiên luôn tách ra đƣợc một tập con (khác rỗng) chứa các số mà
tổng của chúng chia hết n.
1.4.3. Cho p là số nguyên tố lớn hơn 5. Chứng tỏ rằng tồn tại số có dạng

đƣợc một giai đoạn gồm một số ngày liên tục nào đó trong tháng sao
cho trong giai đoạn đó đội chơi đúng 14 trận.

17


CHƢƠNG 2. PHƢƠNG PHÁP CHỨNG MINH PHẢN CHỨNG

2.1.

Ví dụ mở đầu.

Các nhà Toán học Hy Lạp đầu tiên đã sử dụng chứng minh phản chứng trong các
chứng minh của họ với những quy luật và các quy tắc hợp lý mà không cần giải
thích. Ví dụ kinh điển nhất về phép chứng minh phản chứng thuộc về Euclid, đƣợc
trình bày trong định lý sau:
Định lý 2.1. Tồn tại vô số số nguyên tố.
Ở đây, Euclid đã giả sử ngƣợc lại rằng tồn tại hữu hạn số nguyên tố p1 , p2 ,....., pn
Ông xét tích N  p1 p2 ..... pn  1 . Trong đó, N phải có ít nhất một ƣớc số nguyên tố p.
Do p1 , p2 ,....., pn là tất cả các số nguyên tố, nên tồn tại i để p  pi .
Khi đó, p là ƣớc của 1. Điều này mâu thuẫn.
Vậy nên kết luận tập hợp số nguyên tố là vô hạn.
Một chứng minh nổi tiếng khác bằng phƣơng pháp phản chứng chính là chứng minh
của Euler cho định lý nhỏ Fermat với trƣờng hợp n = 4.
Định lý 2.2. Phƣơng trình x 4  y 4  z 2 (1) không có nghiệm nguyên dƣơng.
Để chứng minh định lý này, Euler có dùng đến cấu trúc nghiệm của phƣơng trình
Pythagore đƣợc phát biểu thành định lý sau:
Định lý 2.3. Mọi nghiệm nguyên dƣơng của phƣơng trình x 2  y 2  z 2 đều có thể
 x  (m 2  n 2 )k
 x  2mnk

2
 Theo định lý về phƣơng trình Pythagore, tồn tại p,q sao cho  y  p  q
 z  p2  q2


 Vì y 2  p 2  q 2 nên ( y, p, q) là một bộ số Pythagore.


 q  2ab

Nhƣ vậy tồn tại a, b với (a, b)  1, sao cho  y  a 2  b 2
 p  a 2  b2


 Kết hợp các phƣơng trình ta có x 2  2 pq  2(a 2  b2 )2ab  4ab(a 2  b2 ) .
 Vì a, b và a2  b2 đôi một nguyên tố cùng nhau, nên a, b, a2  b2 đều là các
số chính phƣơng.
 Nhƣ vậy tồn tại p sao cho p  a 2  b 2  a14  b14 .
Bộ nghiệm (a1 , b1 , p)  (a, b, p) , p  z .
Nhƣ vậy, sự tồn tại một số chính phƣơng là tổng của hai số lũy thừa bậc 4 sẽ dẫn
đến sẽ tồn tại của một số chính phƣơng khác nhỏ hơn có cùng tính chất. Điều này
không thể xảy ra!
Nhƣ vậy để thấy rằng, phép chứng minh phản chứng đã xuất hiện từ rất lâu và tính
hữu hiệu của nó khi chứng minh bài toán.
Phần tiếp theo của luận văn sẽ tìm hiểu kỹ hơn về phép chứng minh phản chứng.
2.2.

Cơ sở lý thuyết của phép chứng minh phản chứng.

Cơ sở lý thuyết của phép chứng minh phản chứng là hai định luật cơ bản của logic

 P  Q  P  Q
 Luật giao hoán: P  Q  Q  P ; P  Q  Q  P
 Luật kết hợp: P  Q  R    P  Q   R
P  Q  R    P  Q  R

 Luật phân bố: P  Q  R    P  Q   P  R 
P  Q  R    P  Q   P  R 

 Luật lũy đẳng:  P  P   P;  P  P  P





 Luật về phần tử bù: P  P  0;  P  0  P
 Luật thống trị:  P  0  0;  P  1  1
20


 Luật hấp thụ: P   P  Q   P; P   P  Q  P
 Luật chứng minh phản chứng: P  Q  Q  P
P  Q  P Q

 Nếu P(x) là hàm mệnh đề xác định trên tập A thì:
i.

x  A, P( x) = x  A, P ( x)

ii.




Giả sử phản chứng rằng AB  AC . Không giảm tổng quát, giả sử AB  AC .
Khi đó, lấy trên cạnh AB điểm D, sao cho BD = AC và D không trùng A.
A
D

B

C

Hình 6

Xét

và

ta có AC  BD
̂

(theo cách vẽ)

̂

(giả thiết)

Cạnh BC chung.
Nên

=