Đề toán sô học về Nguyên lí Dỉichlet

Đề toán Số học ứng dụng Nguyên lý Dirichlet


I.- Giới thiêu:
Nguyên lý Dirichlet (Di-ric- lê) có nhiều ứng dụng trong việc giải các bài toán chứng minh sự tồn tại một “Mệnh đề” hoặc một giả thiết nào đó ( lĩnh vực toán sơ cấp cũng như cao cấp, logic học, tin học, triết học…) . Đặc biệt với số học có những định lý, bài toán chứng minh bằng các phương pháp khác rất khó thì Nguyên lý này giải được.
Trên Violet phần “Công cụ toán học”, NST đã có bài chi tiết. Tài liệu này giới thiệu một số bài ứng dung Nguyên lý Dirichlet trong số học sơ cấp.

II.- Bài mẫu
Đề 1 : Cho 10 số tự nhiên bất kỳ : a1, a2, ....., a10. Chứng minh rằng ít nhất cũng có một số hoặc tổng một số các số liên tiếp nhau trong dãy trên chia hết cho 10.
Giải : Lập dãy số Bi ( i= 1,2,3...10)..
Với B1 = a1.
B2 = a1 + a2 .
B3 = a1 + a2 + a3
...................................
B10 = a1 + a2 + ... + a10 .
Nếu tồn tại Bi ( i= 1,2,3...10). nào đó chia hết cho 10 thì bài toán được chứng minh.
Nếu không tồn tại Bi nào chia hết cho 10 ta làm như sau:
Đem các số Bi lần lượt chia cho 10 sẽ được 10 số dư :
Nếu có số dư = 0 thì khỏi phải chứng minh.
Trường hơp chỉ có 9 số dư ( { 1,2.3...9}) thì Theo nguyên tắc Di-ric- lê, phải có ít nhất 2 số dư bằng/trùng nhau. Số dư trùng này (là m chẳng hạn) ít nhât cũng tìm được một số ( n chẳng hạn ) trong dãy 1,2,3, ….9 để m + n = 10 . Nghĩa là có tổng số Bm + Bn chia hết cho 10 ( ĐPCM.

Đề 2 : Chứng minh trong 52 số Tự nhiên bất kì luôn tìm được 2 số có tổng hoặc hiệu là bội số của 100.

Giải
Cách 1: Gọi những cặp số có tổng hoặc hiệu là bội của 100 là (a0,a0) , (a1,a99) , (a2,a98),....(a50,a50) Trong đó a là một số tự nhiên bất kì. Dễ thấy có 51 cặp nhưng có 52 số dư. Vậy theo nguyên lí Dirichlet thì tồn tại ít nhất 1 cặp số có tổng hoặc hiệu là bội số của 100. --> Đpcm!

Cách 2:
Giả sử thứ nhất: trong 52 số có 2 số chia cho 100 đều dư 1 số bằng nhau thì hiệu của chúng chắc chắn là bội của 100. - Giả sử thứ hai: trong 52 số không có cặp số vào có số dư cho 100 như nhau, Điều đó không làm mất tính tổng quát của mệnh đề cần chứng minh; bởi vì, dù có 51 số có số dư cho 100 liên tiếp từ 1 đến 51 thì chắn chắn số còn còn lại thứ 52 có số dư mà tổng với 1 trong 51 số đã kể trước đó phải là bội của 100. ( Điều này cũng chính là “Nguyên lý Dirichle” )

III.- Bài thực hành

Đề : Cho các số tự nhiên từ 1 đến 11 được viết theo thứ tự tuỳ ý, Nghĩa là có dãy số
Ai { a0, a1, a2,…..a10} ; 1 ≤ Ai ≤ 11 theo thứ tự bất kỳ (xem bảng dưới ).

Thứ tự
1
2
3
4
5
6
7
8
9
10
11

 Ai
a 0
a 1
a 2
a 3
a 4
a 5
……

…
….
a 10

TT+Ai
1+a0
2+a1
3+a2
……
…….
……
……
…….
…..
….
11+a10


Sau đó đem cộng mỗi số với số chỉ thứ tự của nó ta được một tổng.
Chứng minh rằng trong các tổng nhận được, bao giờ cũng tìm ra hai tổng mà hiệu của chúng là một số chia hết cho 10.

HD giải
Vì có 11 tổng mà chỉ có thể có 10 chữ số tận cùng đều là các số từ 0 , 1 ,2, …., 9 nên theo Nguyên lý Dirichle luôn tìm được hai tổng có chữ số tận cùng giống nhau .
Hãy đăt các tình huống để chứng minh .