Bài tập về nguyên lý đi-rích lê

Trong một lớp chuyên toán có 40 học sinh. Trong một kỳ kiểm tra chất lượng môn toán chỉ có một em đạt

điểm tối đa là 10, và một em đạt điểm 4, các em khác đạt từ điểm 5 trở lên. Chứng minh rằng trong lớp ít

nhất cũng có 8 em có điểm số như nhau, biết rằng điểm số các em đều là các số nguyên.

Lời giải:

Theo giả thiết của bài toán thì chỉ có một em đạt điểm 10 và một em đạt điểm 4, do đó sẽ

có 40−2=3840−2=38 em đạt điểm 5 đến điểm 9. Coi mỗi học sinh là một "thỏ", mỗi loại điểm là 1 "lồng",

như vậy ta sẽ có các lồng sau:

"Lồng 5": nhốt những ai đạt điểm 5

"Lồng 6": nhốt những ai đạt điểm 6

"Lồng 7": nhốt những ai đạt điểm 7

"Lồng 8": nhốt những ai đạt điểm 8

"Lồng 9": nhốt những ai đạt điểm 9

Với 5 lồng nhốt 38 thỏ, vậy có ít nhất một lồng nhốt không ít hơn 8 thỏ, bài toán được chứng minh.

Ví dụ 2: Cho 10 số tự nhiên bất kỳ: a1,a2,a3...,a9,a10a1,a2,a3...,a9,a

Chứng minh rằng thế nào cũng có một số hoặc tổng một số số liên tiếp nhau trong dãy 10 số đã cho chia hết

cho 10.

Lời giải:

Để làm xuất hiện khái niệm "thỏ", "lồng", ta thành lập dãy số mới sau đây:

Đặt B1=a1B1=a

B2=a1+a2B2=a1+a

B3=a1+a2+a3B3=a1+a2+a

B4=a1+a2+a3+a4B4=a1+a2+a3+a

...

B10=a1+...+a10B10=a1+...+a

Ta thấy rằng:

• Nếu tồn tài một BiBi nào đó [i=1,2,3,...,10] chia hết cho 10 thì bài toán đã được chứng minh.
• Nếu không tồn tại một B1B1 nào đó chia hết cho 10 thì ta chỉ việc đem tất cả BiBi chia cho 10, lúc đó được

10 số dư từ 1-9, trong khi đó các số tự nhiên từ 1-9 chỉ có 9 số [như vậy tương đương với việc nhốt 10 chủ

thỏ vào 9 lồng], theo nguyên tắc Đi-rích-lê, tồn tại 1 lồng nhốt không ít hơn 2 chú thỏ, tương đương với việc

tồn tại hai số có cùng số dư, như vậy có hiệu chia hết cho 10, bài toán được chứng minh.

1. Toán suy luận:

Ví dụ 1: Có 10 đội bóng thi đấu với nhau mỗi đội phải đấu một trận với các đội khác. CMR vào bất cứ lúc

nào cũng có hai đội đã đấu số trận như nhau.

GIẢI: Rõ ràng nếu trong 10 đội bóng có 1 đội chưa đấu một trận nào thì trong các đội còn lại không có đội

nào đã thi đấu 9 trận như vậy 10 đội chỉ có số trận đấu hoặc từ 0 đến 8 hoặc từ 1 đến 9. Vậy theo nguyên lý

Đirichlê phải có ít nhất 2 đội có số trận đấu như nhau.

Ví dụ 2: Có 6 đội bóng thi đấu với nhau [mỗi đội phải đấu 1 trận với 5 đội khác]. CMR vào bất cứ lúc nào

cũng có 3 đội trong đó từng cặp đã đấu với nhau hoặc chưa đấu với nhau trận nào.

GIẢI: Giả sử 6 đội bóng đó là A,B,C,D,E,F. Xét đội A.

Theo nguyên lý Đirichlê ta suy ra: A phải đấu hoặc không đấu với ít nhất 3 đội khác. Không mất tính tổng

quát, giả sử A đã đấu với B,C,D.

Nếu B,C,D từng cặp chưa đấu với nhau thì bài toán được chứng minh.

Nếu B,C,D có 2 đội đã đấu với nhau, ví dụ B và C thì 3 đội A,B,C từng cặp đã đấu với nhau.

Như vậy bất cứ lúc nào cũng có 3 đội trong đó từng cặp đã đấu với nhau hoặc chưa đấu với nhau trận nào.

Ví dụ 3: CMR trong n người bất kì, tồn tại hai người có số người quen như nhau [kể cả trường hợp quen 0

người]

GIẢI: Tương tự ví dụ 1, ta xét n nhóm...

Ví dụ 4: Trong 45 học sinh làm bài kiểm tra không có ai bị điểm dưới 2, chỉ có 2 học sinh được điểm 10.

CMR ít nhất cũng tìm được 6 học sinh có điểm kiểm tra bằng nhau [điểm kiểm tra là một số tự nhiên từ 0

đến 10]

GIẢI: Có 43 học sinh phân chia vào 8 loại điểm [từ 2 đến 9]. Giả sử mỗi loại trong 8 loại điểm đều là điểm

của không quá 5 học sinh thì lớp học có không quá 5=40 học sinh, ít hơn 43 học sinh. Vậy tồn tại 6 học

sinh có điểm kiểm tra bằng nhau.

2ự chia hết:

Trong các phép tính trên số nguyên thì phép chia là rất đặc biệtép chia có hàng loạt các tính chất mà các

phép còn lại không có. Ví dụ các phép toán cộng , trừ , nhân đều thực hiện với số 0 còn phép chia thì không

thể.Vì những lí do đặc biệt đó mà trong toán học xây dựng hẳn 1 lý thuyết về phép chia. Những ví dụ sau có

liên quan mật thiết giữa phép chia và nguyên lý Dirchlet

Ví dụ 1: CMR tồn tại một số tự nhiên gồm toàn chữ số 1 chia hết cho 2007.

a1=2k1,a2=2k2,a3=2k3,a4=2k4+1,a5=2k5+1a1=2k1,a2=2k2,a3=2k3,a4=2k4+1,a5=2k5+

Tacó P=16[k1−k2][k1−k3][k2−k3].MP=16[k1−k2][k1−k3][k2−k3].M

Trong 3 số k1,k2,k3k1,k2,k3 có 2 số cùng tính chẵn lẻ. Giả sử k1k1 đồng dư k1k1 [mod 2]

thì k1−k2k1−k2 chia hết cho 2 nên P chia hết cho 32.

-Nếu có 3 số lẻ là a1,a2,a3a1,a2,a3 còn a4,a5a4,a5 chẵn thì

đặt a1=2k1+1,a2=2k2+1,a3=2k3+1,a4=2k4,a5=2k5a1=2k1+1,a2=2k2+1,a3=2k3+1,a4=2k4,a5=2k

Xét tương tự cũng có P chia hết cho 32.

Vậy ta có P chia hết cho 288.

3. Toán về tổng, hiệu, chữ số tận cùng..ác loại:

Ví dụ 1: Cho 51 số nguyên dương khác nhau có 1 chữ số và có 2 chữ số. CMR ta có thể chọn ra 6 số nào đó

mà bất cứ 2 số nào trong số đã lấy ra ấy không có chữ số hàng đơn vị giống nhau cũng không có chữ số hàng

chục giống nhau.

GIẢI:Vì có 51 số nên tìm được 6 chục sao cho một nhóm có không ít hơn 6 số rơi vào một trong các số chục

đó, một nhóm có không ít hơn 5 số rơi vào chục khác... Cuối cùng có ít nhất một trong các số đã cho rơi vào

một chục nào đó [như vậy số các chục khác nhau không ít hơn 6] về các số đã cho là khác nhau [chú ý các số

dạng xét nhiều nhất có 2 chữ số ] do đó ở nhóm cuối cùng ta lấy một số , sau đó nhóm trước đó [vì có ít nhất

2 chữ số hàng đơn vị của hai số trong nhóm ấy khác nhau] ta lấy một số khác với chữ số hàng đơn vị khác số

chọn trước, rồi nhóm trước đó lại lấy 1 số có chữ số hàng đơn vị khác 2 số chọn trước... Cuối cùng sẽ được 6

số phải tìm với các chữ số khác nhau.

Ví dụ 2: Chọn bất kì n+1 số trong 2n số tự nhiên từ 1 đến 2n [n>=2]. CMR trong các số được chọn có ít nhất

1 số bằng tổng của 2 số được chọn [kể cả các trường hợp 2 số hạng của tổng bằng nhau ].

GIẢI:Giả sử a1