Tag Archives: Phương pháp chứng minh

Phương pháp chứng minh quy nạp – Các dạng khác

Trong bài này, chúng ta tiếp tục tìm hiểu thêm và phương pháp quy nạp. Ngoài dạng quy nạp như đã biết ta còn một số dạng quy nạp khác như: Quy nạp mạnh, quy nạp bước nhảy, quy nạp lùi.

Quy nạp mạnh được phát biểu như sau: Để chứng minh mệnh đề P(n) đúng với mọi số tự nhiên n, ta thực hiện theo hai bước sau:

  • Chứng minh P(n) đúng với n=1.
  • Giả sử P(n) đúng với 1,2,,n. Chứng minh P(n+1) đúng.

Ví dụ 1. Cho x thỏa x+1x là số nguyên. Chứng minh rằng xn+1xn là số nguyên với mọi n.

Lời giải. 

  • Ta có x+1x là số nguyên  đúng (theo giả thiết).
  • Giả sử xk+1xk là số nguyên với mọi k=1,n. Ta cần chứng minh xn+1+1xn+1.
    • (xn+1+1xn+1=(x+1x)(xn+1n)(xn1+1xn1).
    • Theo giả thiết quy nạp thì xn+1+1xn+1 là số nguyên.
  • Vậy ta có xn+1xn là số nguyên với mọi n.

 

Dạng kế tiếp là Quy nạp bước nhảy  được phát biểu như sau: Chứng minh mệnh đề P(n) đúng với mọi n, ta làm như sau:

  • Chứng minh P(1),P(2),,P(k) đúng.
  • Giả sử P(n) đúng. Ta chứng minh P(n+k) đúng.

Ví dụ 2. Chứng minh rằng với mọi số tự nhiên M tồn tại số tự nhiên n và cách chọn các dấu + hoặc sao cho

M=±12±22±n2.

Lời giải.

  • Khi M=1,2,3,4 ta có 1=12, 2=122232+42, 3=12+224=122232+42.
  • Giả sử đúng với M, tức là tồn tại n thỏa M=±12±22±n2, khi đó M+4=±12±22±n2+(n+1)2(n+2)2(n+3)2+(n+4)2.

Ví dụ 3.  Chứng minh rằng với mọi số tự nhiên n thì phương trình a2+b2=cn luôn có nghiệm trong tập các số nguyên dương.

Lời giải. 

  • Rõ ràng nếu n=1,2 thì phương trình luông có nghiệm nguyên dương.
  • Giả sử phương trình có nghiệm nguyên dương là a,b,c với n nào đó, tức là a2+b2=cn.
    • Khi đó với n+2 thì xét (ac),(bc),c: (ac)2+(bc)2=c2(a2+b2)=cn+2.
    • (ac,bc,c là nghiệm.
  • Vậy phương trình luôn có nghiệm với mọi n.

Dạng kế tiếp là Quy nạp lùi được phát biểu như sau:

  • Chứng minh P(ai) đúng với dãy (ai) là dãy con tăng thực sự của tập các số tự nhiên.
  • Giả sử P(n) đúng, chứng minh P(n1) đúng.

Ví dụ 4. 

a) Hãy chỉ ra cách sắp 8 số nguyên dương đầu tiên 1, 2, …, 8 thành một dãy a1,a2,,a8 sao cho 2 số ai,aj bất kì (i<j) thì mọi số trong dãy nằm giữa aiaj đều khác ai+aj2.
b) Chứng minh rằng với N số nguyên dương đầu tiên 1,2,,N luôn tìm được cách sắp thành dãy a1,a2,,aN sao cho dãy thỏa mãn điều kiện như câu a).
Lời giải.

a) Một cách xếp thỏa đề bài là 26481537.\
b)

Bước 1.Ta chứng minh bằng quy nạp với n=2k thì luôn tồn tại một cách xếp thỏa đề bài.

  • Nếu k=1, hiển nhiên đúng.
    Giả sử luôn tồn tại một cách xếp thỏa đề bài với n=2k, cách xếp đó là a1,a2,,an.
    Ta chứng minh tồn tại một cách xếp với n=2k+1.
    Thật vậy xét hoán vị (2a1,2a2,,2an,2a11,2a21,,2an1) là một hoán vị của 1,2,,2k+1. Ta chứng minh hoán vị trên thỏa đề bài.

    • Ta có nếu ai,aj{2a1,2a2,,2an} theo giả thiết quy nạp không có số nào nằm giữa ai,aj bằng 12(ai+aj).
    • Nếu ai{2a1,,2an},aj{2a11,2a21,,2an1} thì 12(ai+aj) không phải số nguyên.
    • Nếu ai,aj{2a11,2a21,,2an1} theo giả thiết quy nạp thì cũng có số nào nằm giữa ai,aj bằng 12(ai+aj).

Vậy bài toán đúng với n=2k.(1)
Bước 2. Nếu bài toán đúng với n, ta chứng minh bài toán đúng với n1.

Xét các số a1,a2,,an là một hoán vị thỏa đề bài của 1,2,,n.

Khi đó nếu xóa bất kì số nào trong các số a1,,an thì dãy còn lại vẫn thỏa điều kiện. (2)
Từ (1) và (2) ta có điều cần chứng minh.

Quy nạp lùi cũng là một trong những cách chứng minh bất đẳng thức Cauchy tổng quát: a1+a2++anna1a2ann.

Các bạn tự làm thử nhé.

Trên đây là một số dạng quy nạp thường gặp trong chứng minh toán. Tùy theo tình huống mà ta sử dụng cho phù hợp, các bạn cần làm thêm nhiều bài tập để rèn luyện.

Bài tập rèn luyện.

Bài 1. Ta gọi tổng các số tự nhiên từ 1 đến n là số tam giác. Chứng minh rằng tồn tại vô hạn các số tam giác đồng thời là số chính phương.

Bài 2. (Chọn đội tuyển PTNK 2014)Tìm số nguyên dương n lớn nhất thỏa mãn các điều kiện sau:

  • n không chia hết cho 3;
  • Bảng vuông n×n ô không thể được phủ kín bằng 1 quân tetramino 1×4 và các quân trimino kích thước 1×3. Trong phép phủ các quân tetramino và trimino được phép quay dọc nhưng không được phép chườm lên nhau hoặc nằm ngoài ra bảng vuông.

Bài 3. n số tự nhiên từ 1 đến n được viết thành một dòng theo một thứ tự nào đó. Mỗi bước thực hiện biến đổi như sau: nếu số đầu tiên là k thì k số đầu tiên sẽ được viết theo thứ tự ngược lại. Chứng minh rằng sau hữu hạn bước thì số đầu tiên của dòng là số 1.

Bài 4. Trong cuộc họp có 2n (n2) người, một số người bắt tay nhau và người ta đếm được có n2+1 cái bắt tay. Chứng minh rằng có n bộ ba, mà mỗi bộ ba đôi một bắt tay nhau.

Bài 5. Chứng minh rằng với mọi số tự nhiên n tồn tại các số nguyên x,y,z phân biệt sao cho x2+y2+z2=14n.

Bài 6. Trong một giải đấu tennis có 10 người tham dự, hai đối thủ gặp nhau đúng một trận. Chứng minh rằng, sau khi kết thúc giải có thể sắp xếp các tay vợt thành một hàng mà người đứng trước thắng người đứng sau.

Phương pháp chứng minh quy nạp – P2

Trong phần trước ta đã làm quen với phương pháp chứng minh quy nạp và áp dụng vào chứng minh một vài đẳng thức, bất đẳng thức hay các bài toán chia hết. Bài này tiếp tục là ứng dụng của quy nạp trong việc chứng minh các bài toán khác, trong cái đề thi học sinh giỏi hay tuyển sinh.

Ví dụ 1. Người ta lát nền nhà hình vuông kích thước n×n ô bằng các viên gạch như hình vẽ dưới sao cho còn chừa lại một ô không lát.
a) Hãy chỉ ra một cách lát như trên với nền nhà kích thước 4×48×8.
b) Hãy chứng minh rằng luôn tồn tại một cách lát nền nhà có kích thước 2k×2k (k nguyên dương) với ô trống còn lại nằm ở vị trí (i,j) bất kì.

Lời giải

a) Các bạn tự làm.
b) Ta chứng minh bằng quy nạp.

  • Với k=2 hiển nhiên đúng.
  • Giả sử với k thì nền 2k×2k bỏ ô (i;j) bất kì thì luôn phủ được. Ta chứng minh đúng với k+1.
    Với nền nhà 2k+1×2k+1 ta chia thành 4 hình vuông 2k×2k. Khi đó ô bỏ đi thuộc một trong 4 hình vuông đó, ta phủ được hình vuông này theo giả thiết quy nạp. Tiếp tục,theo giả thiết quy nạp, với 3 hình vuông còn lại, bỏ đi ô ở góc (hình vẽ) thì ta có thể phủ được. Khi đó 3 ô ở góc ta phủ tiếp bằng một viên gạch.
  • Với cách thực hiện đó thì ta có thể phủ được nền nhà 2k+1×2k+1 khi bỏ ô bất kì.

Ví dụ 2. Trong cuộc họp có 2n (n2) người, một số người bắt tay nhau và người ta đếm được có n2+1 cái bắt tay. Chứng minh rằng có 3 người đôi một bắt tay nhau.

Lời giải
  • Rõ ràng bài toán đúng khi n=2.
  • Giả sử bài toán đúng với n, ta chứng minh bài toán đúng với n+1. Xét hai người A,B bắt tay.
    Nếu số bắt tay của AB với 2n người còn lại không vượt quá 2n thì n người kia có n2+1 cái bắt tay, ta có điều cần chứng minh.
    Nếu số người bắt tay với A,B là hơn 2n cái.
  • Do đó trong 2n người kia thì sẽ có ít nhất một người bắt tay với cả AB, ta có điều cần chứng minh.

Ví dụ 3.  a) Cho bốn số nguyên dương a1,a2,a3,a4 sao cho 1akk với mọi k=1,2,3,4 và tổng S=a1+a2+a3+a4 là một số chẵn. Chứng minh rằng có ít nhất một trong các số dạng ±a1±a2±a3±a4 có giá trị bằng 0.
b) Cho 1000 số nguyên dương a1,a2,,a1000 sao cho 1akk với k=1,2,,1000 và tổng S=a1+a2++a1000 là một số chẵn.\
Hỏi trong các số có dạng ±a1±a2±a1000 có số nào bằng 0 hay không? Giải thích vì sao?

Lời giải

a) Ta có 4S10S chẵn, suy ra S=4,6,8,10. Xét các trường hợp sau:

  • S=4, suy ra a1=a2=a3=a4=1. Suy ra 11+1+1=0.
  • S=6 ta có 6=1+1+1+3=1+1+2+2, suy ra có một cách thỏa đề bài.
  • S=8 ta có 8=1+1+2+4=1+1+3+3=1+2+2+3=2+2+2+2. Suy ra mỗi cách đều tồn tại một cách chọn dấu +, thỏa đề bài.
  • S=10=1+2+3+4. Suy ra có một cách thỏa đề bài.

a) Ta chứng minh bằng quy nạp mệnh đề sau: Cho n các số nguyên dương thỏa 1akk thỏa Sn=a1++an chẵn. Khi đó tồn tại số có dạng ±a1±a2±an bằng 0.

  • Khi n=2 ta có a1+a2 chẵn, suy ra a1=a2=1. Suy ra a1a2=0.
  • Giả sử bài toán đúng với kn. Ta chứng minh bài toán đúng với n+1. Ta có Sn+1=a1++an+an+1 chẵn. Ta có 0|anan+1|n.
    • Nếu anan+1=0 ta áp dụng giả thiết quy nạp với n1 số a1,,an1 ta có điều cần chứng minh.
    • Nếu anan+10. Áp dụng giả thiết quy nạp với n số a1,a2,,an1,|anan+1| ta thấy a1++an+1 chẵn nên a1++an1+|anan+1| chẵn.
    • Suy ra tồn tại số có dạng ±a1±a2±|anan+1|=±a1±a2±an+1 bằng 0.

 

Ví dụ 4. (USAMO 2002) Cho tập S có 2002 phần tử, số tự nhiên k thỏa 0k22002 chứng minh rằng tồn tại cách tô màu các tập con của S bằng hai màu xanh và đỏ thỏa:
a)  Có đúng k tập được tô màu đỏ.
b) Hợp của hai tập đỏ là một tập đỏ.
c) Hợp của hai tập xanh là một tập xanh.

Lời giải
  • Ta chứng minh bài toán đúng với tập S có số phần tử n bất kì bằng quy nạp.

    Rõ ràng bài toán đúng với n=1, S={1}. Nếu k=0 tô màu xanh cả hai tập con. Nếu k=1 tô màu đỏ tập S, xanh tập rỗng. Nếu k=2 thì tô S và rỗng đều màu đỏ.

  • Giả sử Sn phần tử thì với mọi k đều tồn tại cách tô thỏa đề bài.
    Ta chứng minh bài toán đúng với Sn+1 phần tử.
    Giả sử S={1,2,,n,n+1}, 0k2n+1.

    • Nếu k2n.Theo giả thiết quy nạp các tập con của {1,2,,n} được tô thỏa đề bài và các tập con chứa n+1 ta tô màu xanh. Rõ ràng cách tô này thỏa đề bài.
    • Nếu 2n<k2n+1. Thì ta chỉ cần đổi màu các tập tô như trường hợp trên, tập nào tô màu xanh thì đổi thì màu đỏ và ngược lại. Rõ ràng thỏa đề bài.

Trên đây là một vài ví dụ khá hay về áp dụng của Quy nạp, tất nhiên còn nhiều bài tập khác cũng hấp dẫn không kém, các bạn tự tìm hiểu nhé. Chúng ta sẽ trở lại trong bài viết sau về một số dạng quy nạp thường gặp.

Bài tập rèn luyện. 

Bài 1. Lúc đầu có n lít nước để vào một số lu, mỗi lu chứa đúng một số nguyên dương lít nước, ta thực hiện cách đong nước như sau: nếu số nước ở lu A nhỏ hơn hoặc bằng lu B thì ta có thể cho hết nước của B vào A một lượng bằng lượng nước lu A đang có.
a) Nếu có 3 lu nước chứa lần lượt 2,3,8 thì có thể đưa về hai lu không? Tại sao?
b) Nếu n=1024. Chứng minh rằng ta có thể đưa số nước hết về một lu. Giả sử lu này là lu lớn, chứa đủ số nước đã có.
Bài 2. Cho n đội bóng, n là số chẵn lớn hơn 2.  Mỗi một lượt, các đội chia cặp để đấu với nhau một trận. Chứng minh rằng sau hai lượt thì có thể tìm được n2 đội mà không có hai đội nào đấu với nhau.

Bài 3. Cho n=2k, chứng minh rằng người ta có thể chọn n số nguyên từ 2n1 số nguyên để tổng của chúng chia hết cho n.

Bài 4. Gọi x1,x2 là nghiệm của phương trình x2+2017x1=0. Đặt Sn=x12+x2n. Chứng minh rằng SnSn+1 là nguyên tố cùng nhau với mọi n.

Phương pháp chứng minh quy nạp – P1

Phương pháp chứng minh quy nạp là một trong những phương pháp chứng minh quan trọng trong toán học. Trong bài viết nhỏ này dành cho các bạn THCS chúng tôi xin trình bày một số dạng của phương pháp này trong việc chứng minh các bài toán ở các lĩnh vực như: Đại số, số học, tổ hợp. Hy vọng các em có thể nắm bắt vận dụng phù hợp trong các tình huống cụ thể.

Để chứng minh một mệnh đề P(n) là đúng với mọi số nguyên dương n, ta thực hiện các bước sau:

  • Bước cơ sở:      Chứng minh P(1) đúng.
  • Bước quy nạp: Giả sử P(n) đúng với n nào đó (giả thiết quy nạp), chứng minh P(n+1) đúng.

Ví dụ 1. Chứng minh rằng với mọi số nguyên dương n thì 1+2++n=n(n+1)2.

Lời giải. 

  • Khi n=1 rõ ràng : 1=1(1+1)2.
  • Giả sử đẳng thức đúng với n, ta chứng minh đẳng thức đúng với n+1.
    • Thật vậy áp dụng giả thiết quy nạp ta có: 1+2++n+n+1=n(n+1)2+n+1=(n+1)(n+2)2.
  • Vậy đẳng thức đúng với mọi n.

Ví dụ 2. Chứng minh n3+11n chia hết cho 6 với mọi số tự nhiên n.

Lời giải. 

  • Khi n=0 ta có 03+110=0 chia hết cho 6.
  • Giả sử n3+11n chia hết cho 6, ta chứng minh (n+1)3+11(n+1 chia hết cho 6.
    • Thật vậy (n+1)3+11(n+1)=n3+11n+3n(n+1)+12.
    • Theo giả thiết quy nạp thì n3+11n chia hết cho 6, và 3n(n+1),12 cũng chia hết cho 6 nên (n+1)3+11n chia hết cho 6.
  • Vậy n3+11n chia hết cho 6 với mọi n.

Trong một số trường hợp ta cần chứng minh P(n) đúng với mọi số tự nhiên nno nào đó, ta cũng làm tương tự, chỉ thay bước cơ sở thành: Chứng minh P(no) đúng.

Ví dụ 3. Chứng minh rằng 2n>n2 với mọi n5.

Lời giải. 

  • Khi n=5 ta có 25>52( đúng)
  • Giả sử 2n>n2 với n>5. Ta cần chứng minh 2n+1>(n+1)2.
    • Thật vậy áp dụng giả thiết quy nạp ta có 2n+1=22n>2n2.
    • 2n2>(n+1)2n22n+1>0 (đúng với n>5).
    • Do đó 2n+1>(n+1)2.
  • Vậy 2n>n2 với mọi n5.

Bài tập rèn luyện.

Bài 1. Chứng minh các đẳng thức sau:

a) 12+22++n2=n(n+1)(2n+1)6.

b) 13+23++n3=n2(n+1)24.

c) 11.2.3+12.3.4++1n(n+1)(n+2)=n(n+3)4(n+1)(n+2).

Bài 2.

a) Chứng minh rằng n!>3n với mọi n>7.

b) Chứng minh rằng với số thực a>1, thì với mọi số tự nhiên n ta có (1+a)n1+na.

Bài 3. Chứng minh rằng với mọi số tự nhiên n thì:

a) 52n+1+2n+4+2n+1 chia hết cho 23.

b) Với n là số tự nhiên chẵn, chứng minh rằng: (20n+16n3n1)  323.

Phương pháp chứng minh phản chứng – P1

Ta dùng tương đương logic sau ABBA để thiết lập phương pháp chứng minh Phản chứng.

Để chứng minh mệnh đề AB đúng, ta có thể thực hiện các bước sau (Phương pháp phản chứng)

  • Giả sử mệnh đề B sai.
  • Chứng minh A sai, hoặc một điều vô lý.

Ví dụ 1. (Nguyên lý Dirichlet) Có nk+1 viên bi, bỏ vào trong k cái hộp. Chứng minh rằng có ít nhất một hộp có ít nhất là là n+1 viên bi.

Lời giải

Giả sử tất cả các hộp chỉ chứa số lượng bị không vượt quá n viên, khi đó tổng số viên bi không vượt quá kn, mâu thuẫn với số bi là kn+1.
Vậy phải có một hộp chứa nhiều hơn n viên bi.

Ví dụ 2. Cho n là số tự nhiên n>3. Chứng minh rằng 2n+1 không chia hết cho 2m1 với mọi số tự nhiên m sao cho 2<mn.

Lời giải

Giả sử tồn tại m,n sao cho 2n+1 chia hết cho 2m1 với 2<m<n.
Ta có 2nm(2m1)2m1, suy ra 2n2nm2m1, mà 2n+12m1 suy ra 2nm+1 chia hết cho 2m1.
Lý luận tương tự ta có 2nkm+1 chia hết cho 2m1.\ Giả sử n=km+q,0q<m. Chọn k như trên ta có 2q+1 chia hết cho 2m1. Mà q<m nên 2q+1=2m1,giải ra q=1,m=2 (vô lý).

Ví dụ 3. Cho tập B=1,2,3,,16. Người ta ghi các số của tập B thành một vòng tròn (mỗi số ghi một lần). Hỏi có cách ghi để tổng thỏa:
a) Tổng của hai số kế nhau bất kì lớn hơn hoặc bằng 17 được không? Tại sao?
b) Tổng của ba số kế nhau bất kì lớn hơn 24 được không? Tại sao?

Lời giải

a) Giả sử có cách ghi thỏa đề bài xét hai số đứng kề số 1, gọi là a,b như sau a1b, khi đó a+117,b+117, suy ra a=b=16 vô lí. Do đó không có cách ghi thỏa đề bài.
b) Giả sử có cách ghi thỏa đề bài: 3 số liên tiếp bất kì có tổng lớn hơn 24. Khi đó bỏ số 16 ra, còn lại 15 số chia làm 5 nhóm rời nhau thì tổng lớn hơn 24×5=120, trong khi đó 1+2++15=120 vô lí.

Ví dụ 4.  Có tồn tại hay không một cách điền các số 0,1,2,3,,9 vào các đỉnh của một đa giác 10 đỉnh sao cho hiệu hai số ở hai đỉnh kề nhau chỉ có thể nhận một trong các giá trị sau:5,4,3,3,4,5.

Lời giải

Giả sử có một cách ghi thỏa đề bài. Khi đó
ta thấy rằng các số 0,1,2,8,9 không thể đứng cạnh nhau đôi một. Hơn nữa có đúng 10 số, vậy các số còn lại sẽ đứng xen kẽ giữa các số này.
Khi đó xét số 7, ta thấy số 7 chỉ có thể đứng bên cạnh số 2 trong các số {0,1,2,8,9}, mâu thuẫn.
Vậy không tồn tại cách ghi thỏa đề bài.

Ví dụ 5.  Điền các số 1,2,3,…,121 vào một bảng ô vuông kích thước 11×11 sao cho mỗi ô chứa một số. Tồn tại hay không một cách điền sao cho hai số tự nhiên liên tiếp sẽ được điền vào hai ô có chung một cạnh và các tất cả các số chính phương thì nằm trong cùng một cột?

Lời giải
  • Giả sử tồn tại một cách điền số vào các ô thỏa yêu cầu đặt ra. Khi đó bảng ô vuông được chia thành hai phần ngăn cách nhau bởi cột điền các số chính phương. Một phần chứa 11n ô vuông 1×1, và phần còn lại chứa 11011n ô vuông 1×1 , với 0n5.
  • Để ý rằng các số tự nhiên nằm giữa hai số chính phương liên tiếp a2(a+1)2 sẽ cùng nằm về một phần và dó đó các số tự nhiên nằm giữa (a+1)2(a+2)2 sẽ nằm ở phần còn lại.
  • Số lượng các số tự nhiên nằm giữa 1 và 4, 4 và 9, 9 và 16,…,100 và 121 lần lượt là 2,4,6,8,…,20. Do đó một phần sẽ chứa 2+6+10+14+18=50 số, phần còn lại chứa 4+8+12+16+20=60 số. Cả 50 và 60 đều không chia hết cho 11, mâu thuẫn. Vậy không tồn tại cách điền số thỏa yêu cầu đề bài.

Ví dụ 6.  Cho F=E1,E2,,Ek là một họ các tập con có r phần tử của tập X. Nếu giao của r+1 tập bất kì của F là khác rỗng, chứng minh rằng giao của tất cả các tập thuộc F là khác rỗng.

Lời giải
  • Giả sử ngược lại, giao tất cả các tập thuộc F bằng rỗng.
    Xét tập E1={x1,,xr}.
  • Do giao tất cả các tập thuộc F là rỗng, nên với xk tồn tại một tập EikxEik,k=1,r.
  • Khi đó xét giao của họ gồm r+1 tập E1,Ei1,,Eir thì bằng rỗng, mâu thuẫn.
    Vậy giao của tất cả các tập thuộc F là khác rỗng.

Ví dụ 7.  Cho AB là các tập phân biệt và hợp của AB là tập các số tự nhiên. Chứng minh rằng với mọi số tự nhiên n tồn tại các số phân biệt a,b>n sao cho a,b,a+bA hoặc a,b,a+bB.

Lời giải
  • Nếu A hoặc B là tập hợp hữu hạn phần tử thì chỉ cần chọn a,b lớn hơn phần tử lớn nhất của A hoặc B ta có điều cần chứng minh.
  • Nếu A,B là tập vô hạn, giả sử tồn tại n sao cho với mọi a,b thì a,b,a+b không cùng thuộc A hoặc B. (1)
  • Ta chọn các số x,y,zA sao cho x<y<zzy,yx>n.
  • Do (1) nên các số yx,zy,zxB, suy ra zy+yx=zxA (mâu thuẫn).
    Vậy điều giả sử là sai, tức là ta có điều cần chứng minh.

Ví dụ 8.  Trong mặt phẳng tọa độ thì một điểm mà hoành độ và tung độ đều là các số nguyên được gọi là điểm nguyên. Chứng minh rằng không tồn tại tam giác đều nào mà các đỉnh đều là điểm nguyên.

Lời giải
  • Giả sử tồn tại tam giác đều có các đỉnh là các điểm nguyên.
    Xét hình chữ nhật có các đỉnh là các điểm nguyên, sao cho đỉnh của tam giác đều thuộc cạnh của hình chữ nhật. Khi đó dễ dàng suy ra diện tích tam giác đều là số hữu tỷ.
  • Mặt khác diện tích tam giác đều S=a234 là số vô tỷ, vì a là số nguyên, 3 là số vô tỷ.

Ví dụ 9.  Cho A là tập con có 19 phần tử của tập 1,2,,106 sao cho không có hai phần tử nào có hiệu bằng 6,9,12,15,18. Chứng minh rằng có 2 phần tử thuộc A có hiệu bằng 3.

Lời giải
  • Xét các phần tử thuộc A theo mod 3 thì có ít nhất 7 phần tử có cùng 0, 1, 2 mod 3. Xét tập B có 7 hoặc nhiều hơn phần tử có cùng số dư khi chia cho 3. Khi đó hiệu 2 số bất kì là số chia hết cho 3.
  • Giả sử không có hai số có hiệu bằng 3, khi đó hiệu hai số sẽ từ 21 trở đi. Giả sử a1<a2<a3<a4<a5<a6<a7B. Ta có a2a121,,a7a621, suy ra a71+21×6=127 mâu thuẫn.
  • Vậy có 2 số có hiệu bằng 3.

Ví dụ 10. Một hình vuông n×n ô được tô bởi hai màu đen trắng, sao cho trong 4 ô góc thì 3 ô được tô màu đen, 1 ô được tô màu trắng. Chứng minh rằng trong hình vuông có ô vuông 2×2 mà có số ô màu đen là số lẻ.

Lời giải
  • Giả sử ngược lại, không có hình vuông 2×2 nào mà số ô đen là lẻ mà đều là số chẵn.
  • Lấy tổng các ô đen của các hình vuông 2×2, khi đó ta được một số chẵn các ô đen.
  • Mặt khác, mỗi ô vuông trên cạnh (khác ô góc) được tính 2 lần (vì có 2 hình vuông 2×2 chứa nó, các ô vuông bên trong được tính 4 lần, các ô góc được tính 1 lần, do đó số ô đen là một số lẻ. Mâu thuẫn.
  • Vậy có ít nhất một hình vuông 2×2 ô đen là một số lẻ.

 

Bài tập rèn luyện

Bài 1. Giải các bài toán sau bằng phương pháp phản chứng
a) Chứng minh rằng 2 là một số vô tỷ.
b) Chứng minh rằng tổng của một số hữu tỷ và một số vô tỷ là số vô tỷ.
c) Chứng minh tích của một số hữu tỷ và một số vô tỷ là số vô tỷ.
d) Tổng, tích hai số vô tỷ có luôn là số vô tỷ không? Tại sao?
e) Cho 15 số thỏa mãn tổng của 8 số bất kì lớn nhơn tổng của 7 số còn lại. Chứng minh tất cả các số đã cho đều dương.
f) Từ 8 số nguyên dương không lớn hơn 20, chứng minh rằng có thể chọn ra 3 số x,y,z là độ dài 3 cạnh của một tam giác.

Bài 2. Có thể chia tập X=1,2,,17 thành hai tập rời nhau sao cho tích các phần tử thuộc tập này bằng tổng các phần tử thuộc tập kia?
Bài 3. Có tồn tại hay không cách chia tập hợp X=1,2,,2017 thành các tập hợp sao cho trong mỗi tập đó thì phần tử lớn nhất bằng tổng các phần tử còn lại.

Bài 4. Một tập hợp có ít nhất 3 số nguyên dương phân biệt được gọi là \textbf{tập đều} nếu có ít nhất một số lẻ và khi bỏ đi một phần tử bất kì thì các số còn lại có thể chia thành hai tập hợp mà tổng các số trong hai tập hợp đó bằng nhau.
a) Chứng minh không có tập đều nào có 3 phần tử.
b) Chứng minh số phần tử của tập đều luôn là một số lẻ.
c) Có tồn tại hay không một tập đều có 5 phần tử? Tại sao?