Bài 24. Chỉ ra rằng nếu có 5 điểm phân biệt ở trong một hình vuông cạnh bằng 2
thì có ít nhất hai trong năm điểm này có khoảng cách không xa hơn [You must be registered and logged in to see this image.]

Ta chia hình vuông làm 4 phần bằng nhau mỗi phần là một hình vuông 1 x 1.

Nếu có 2 điểm nằm trong 1 phần là hình vuông con, thì 2 điểm đó không thể lớn hơn khoảng cách xa nhất là 2 đỉnh của hình vuông bằng [You must be registered and logged in to see this image.] . Nếu có 2 điểm nằm trong một hình vuông con thì đúng rồi, khỏi phải chứng minh.

Vậy giả sử có 4 điểm nằm trong 4 phần của hình vuông thì theo nguyên lý Dirichlet Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì ít nhất trong một ngăn có nhiều hơn một con chim. Nguyên lý này dĩ nhiên là có thể áp dụng cho các đối tượng không phải là chim bồ câu và chuồng chim.

Nên điểm phần biệt thứ 5 này phải thuộc 1 trong 4 phần là 1 hình vuông con, nên khoảng cách xa nhất của điểm thứ 5 này với 1 điểm nằm trong hình vuông con cũng không thể lớn hơn [You must be registered and logged in to see this image.]

Câu 2, đề 2 trang 164:
Chứng minh rằng 11 số nguyên dương không vượt quá 20, tồn tại ít nhất một cặp số là bội của nhau.

Câu 3, đề 3 trang 165:
Có 11 số nguyên dương khác nhau, mỗi số không vượt quá 20, chứng minh rằng ít nhất có 2 số là nguyên tố cùng nhau.

Câu 3 đề 5 trang 167: Chứng minh rằng, khi chọn 21 số nguyên dương bất kỳ khác nhau, tồn tại ít nhất hai số có hiệu số chia hết cho 20.

Câu 1a đề 6 trang 168:
Có bao nhiêu tập con của tập A {a₁, a₂, a₃.....,a_n} chứa ít nhất một phần tử có chỉ số lẻ.

Câu 4 đề 6 trang 168:
Cho tập {a₁, a₂, a₃.....,a₂₂}trong đó a_i là các số nguyên dương.
a. Chứng minh ba phần tử trong A đồng dư modulo 7.
b. Tồn tại một hay nhiều số hạng liên tiếp của A có tổng chia hết cho 22.

Đề thi năm 2009. Câu số 3.
Chứng minh trong tập bất kỳ (n + 1) số lấy từ tập {1,2,...,2n} luôn tồn tại 2 số nguyên tố cùng nhau!

1. Trước hết cần phải thêm điều kiện tất cả các không thể cùng bằng nhau vì:
Nếu lấy (n + 1) số bằng nhau thì không có cặp 2 số nào nguyên tố cùng nhau.

2. Không mất tính tổng quát giả sử a(1) ≤ a(2) ≤ a(3) .... ≤ a(n + 1)
Xét dãy a(2)-a(1), a(3)-a(2), ...., a(n+1)-a(n) gồm n số, tổng n số này = a(n+1)-a(1) ≤ 2n - 1 < 2n

Vậy tồn tại ít nhất 1 hiệu a(i+1)-a(i) = 1 (Dirichle) → a(i) , a(i+ 1) là 2 số nguyên liên tiếp → a(i) , a(i+1) nguyên tố cùng nhau → đpcm

Anh Son áp dụng một bổ đề quan trọng, nhưng các anh chị nên hỏi thầy xem bổ đề này có phải chứng minh không?
Bổ đề phát biểu là:
1. Hai số tự nhiên liên tiếp là 2 số nguyên tố cùng nhau.
Em xin phép chứng minh hộ cái bổ đề bị bỏ quên này nhé!
Gọi d là ước số chung của {n, (n+1)}, theo tính chất của [You must be registered and logged in to see this link.] thì hiệu của hai số chia hết cho d, phải chia hết cho d. Vậy lấy hiệu là n+1 - n chia hết cho d. Mà hiệu bằng 1, nên 1 chia hết cho d. → Vậy d Э 1 hay d = 1--> Hai số {n, (n+1)} là nguyên tố cùng nhau.
2. Lập luận tương tự, anh chị cũng có thể chứng minh 2 số lẻ liên tiếp cũng là 2 số nguyên tố cùng nhau (Nên anh Son cũng có thể áp dụng cái này thì oách hơn).
Gọi d Э Ước chung {(2n+1),(2n-1)} → 2n+1 - 2n -1 chia hết cho d → 2 chia hết cho d. Vậy d Э {1, 2} nhưng d ≠ 2 vì d là ước của số lẻ. Vậy d = 1. → Hai số {(2n+1), (2n-1)} là nguyên tố cùng nhau.
Được chưa nào. Các anh nổi tiếng là tiết kiệm nút cám ơn đó nha!

Chứng minh hai tập con khác nhau gồm 5 phần tử của tập 10 số nguyên dương không vượt quá 30 có cùng tổng

Theo đầu bài ta có : x₁ + x₂ + x₃ + x₄ + x₅ < 5.30 = 150
Tức là số các tổng có thể có của x₁ đến x₅ là < 150 tổng ( từ 1 đến 149)

Số các cách lấy 5 phần tử trong 10 phần tử ít nhất là:

[You must be registered and logged in to see this image.] cách

Theo nguyên lý Dirichle 150 tổng mà có 252 cách lấy 5 phần tử → ít nhất 2 tổng phải có cùng giá trị. → đpcm

Những bài toán tiêu biểu áp dụng nguyên lý Đi dép lê

1. Có 20 thành phố, giữa các thành phố có thể có các đường giao thông nối trực tiếp với nhau hoặc không. Chứng minh rằng có ít nhất 2 thành phố có số thành phố khác nối trực tiếp với chúng là như nhau.
.
Giải:
Gọi ai là số thành phố có có đường giao thông nối trực tiếp với thành phố thứ i
Gọi A = {a₁, a₂, ..., a₂₀} là tập các giá trị lưu đó
Khi đó mỗi giá trị 0 ≤ ai ≤ 19 không thể đồng thời có mặt giá trị 0 và 19. (Vì trong tập A có giá trị 0, tức là thành phố đó bị cô lập, tức là không có thành phố nào được nối với cả 19 thành phố còn lại). Chính vì vậy, theo nguyên lý Đi dép lê thì sẽ tồn tại ít nhất 1 cặp i ≠ j sao cho a_i = a_j.

2. Cho 5 điểm M₁(x₁, y₁), M₂(x₂, y₂), M₃(x₃, y₃), M₄(x₄, y₄), M₅(x₅, y₅),trên mặt phẳng toạ độ Đề các. Chứng minh rằng tồn tại ít nhất 2 điểm mà đoạn thẳng nối 2 điểm đó, có toạ độ trung điểm là số nguyên.

Đặt A = {M₁, M₂, M₃, M₄, M₅}.
Ta xây dựng một ánh xạ f(Mi) = (x_i mod 2, y_i mod 2).
Tức là f: A → B₂. Trong đó B₂ là tập các dãy nhị phân có độ dài 2.
Ta có N(a) = 5, N(B₂) = 4 (Bởi nó chỉ là 1 trong 4 cặp 0,0; 0, 1; 1,0; 1,1).
Nên theo nguyên lý Đi dép lê phải tồn tại Mi ≠ Mj sao cho f(Mi) = f(Mj) tức là toạ độ của 2 điểm theo trục x và y đều cùng chẵn hoặc cùng lẻ.
Do đó toạ độ trung điểm là trung bình cộng của hoành độ hay trung bình cộng của tung độ 2 điểm có dạng [You must be registered and logged in to see this image.] sẽ là một số nguyên do tử số cộng lại (lẻ + lẻ = chẵn, hoặc chẵn + chẵn = chẵn) chia hết mẫu số là 2. Nên toạ độ này phải là số nguyên.

3. Khi kiểm kê danh mục 80 chi tiết mỗi chi tiết được đánh giá là tốt hoặc không tốt. Có 50 chi tiết được đánh giá là tốt.
chứng minh rằng có ít nhất 2 chi tiết được đánh giá là không tốt, có số thứ tự cách nhau 3 hoặc 6 đơn vị.
Giải
- Đặt tập A là tập 30 chi tiết đánh giá không tốt.
A = {a₁, a₂, ..., a₃₀} với 1 ≤ a_i ≤ 80

- Đặt tập B là tập các các phần tử b_i cách với các phần tử a_i 3 đơn vị. Hay b_i = a_i + 3

- Đặt tập C là tập các các phần tử c_i cách với các phần tử a_i 6 đơn vị. Hay c_i = a_i + 6

Theo đầu bài ta có 1 ≤ b_i ≤ 83, 1 ≤ c_i ≤ 86

Bây giờ hợp cả 3 tập A, B, C được tập D có 30 + 30 + 30 = 90 phần tử. Mà 90 phần tử này chỉ nhận 86 giá trị khác nhau.

Từ đó theo nguyên lý Đi dép lê phải tồn tại ít nhất một cặp 2 số d_i = d_j. Các cặp số này không đồng thời nằm trong A, không đồng thời nằm trong B, không đồng thời nằm trong C. Vậy chỉ có thể là một trong 3 phương án:
Hoặc: - d_i = a_j Э A và d_j = b_k Э B
Hoặc - d_i = a_j Э A và d_j = c_k Э C
Hoặc - d_i = c_j Э C và d_j = b_k Э B
ĐPCM

Các bài toán ứng dụng Đi dép lê rất giống đề thi (tiếp)
4. Một tháng 30 ngày, một công nhân không làm quá 45 sản phẩm; nhưng làm ít nhất mỗi ngày 1 sản phẩm. chứng minh rằng có những ngày liên tiếp, người công nhân này làm ra đúng 14 sản phẩm.

Gọi a_i là sản phẩm làm trong ngày thứ i, ta có tập A = {a₁, a₂, ..., a₃₀}với a_i ≥ 1
Và a₁+ a_{2 +} ...+a₃₀ ≤ 45
Gọi b_i là tổng số sản phẩm trong tháng tính từ đầu tháng đến ngày thứ i ta có
b₁ = a₁
b₂ = b₁ + a₂
b₃ = b₂ + a₃
...
b₃₀ = b₂₉ + a₃₀

Biết:
1 ≤ b₁

Đề trang 94:
Một trong các câu sau sẽ nằm trong dạng đề thi:
26. Khi kiểm kê danh mục 115 chi tiết mỗi chi tiết được đánh giá là tốt hoặc không tốt. Có 60 chi tiết được đánh giá là tốt.
chứng minh rằng có ít nhất 2 chi tiết được đánh giá là tốt, có số thứ tự cách nhau 4 đơn vị.
27. Khi chọn tuỳ ý n + 1 số nguyên dương khác nhau, chứng minh rằng tồn tại ít nhất 2 số đồng dư theo modulo n.
28. Hãy chỉ ra rằng trong dãy 10 số nguyên dương bất kỳ tồn tại ít nhất một hay nhiều hơn các số hạng liên tiếp có tổng chia hết cho 10.
29. Chỉ ra rằng trong dãy m số nguyên dương bất kỳ tồn tại ít nhất một hay nhiều hơn các số hạng liên tiếp có tổng chia hết cho m.
30. Cho (Xi, Yi, Zi) i = 1, 2, ..., 9 là toạ độ nguyên của 9 điểm trong không gian 3 chiều. chứng minh rằng tồn tại ít nhất một đoạn thẳng nối 2 điểm trong số đó có trung điểm toạ độ nguyên.
31. Có 16 cầu thủ bóng rổ, số áo của mỗi người được đánh từ 1 đến 16, đứng thành vòng tròn theo thứ tự bất kỳ, chứng minh rằng tồn tại ít nhất 3 cầu thủ đứng liền nhau có tổng số áo ít nhất là 26.

Đề số 2, trang 164, câu 2:
Chứng minh rằng 11 số nguyên dương không vượt quá 20, tồn tại ít nhất một cặp số là bội của nhau.

Đề số 3, trang 165, câu 3:
Chứng minh rằng 11 số nguyên dương không vượt quá 20, ít nhất có 2 số là nguyên tố cùng nhau. (LĐS đã giải)

Đề số 5, trang 167, câu 3:

Chứng minh rằng 21 số nguyên dương khác nhau bất kỳ, tồn tại ít nhất hai số có hiệu chia hết cho 20.

Đề số 6, trang 168, câu 4:
Cho tập A = (a₁, a₂, a₃,..., a₂₂), trong đó a_i là các số nguyên dương. chứng minh rằng:
a. Tồn tại ít nhất 3 phần tử trong A đồng dư modulo 7
b. Tồn tại một hay nhiều số hạng liên tiếp của A có tổng chia hết cho 22.

Em làm thử mấy câu giống nhau mà các anh chị chưa giải nha.

Admin đã viết:Đề trang 94:
28. Hãy chỉ ra rằng trong dãy 10 số nguyên dương bất kỳ tồn tại ít nhất một hay nhiều hơn các số hạng liên tiếp có tổng chia hết cho 10.
29. Chỉ ra rằng trong dãy m số nguyên dương bất kỳ tồn tại ít nhất một hay nhiều hơn các số hạng liên tiếp có tổng chia hết cho m.
Đề số 6, trang 168, câu 4:
Cho tập A = (a₁, a₂, a₃,..., a₂₂), trong đó a_i là các số nguyên dương. chứng minh rằng:
a. Tồn tại ít nhất 3 phần tử trong A đồng dư modulo 7
b. Tồn tại một hay nhiều số hạng liên tiếp của A có tổng chia hết cho 22.

Làm bài số 28 nha anh, chị!
Hãy chỉ ra rằng trong dãy 10 số nguyên dương bất kỳ tồn tại ít nhất một hay nhiều hơn các số hạng liên tiếp có tổng chia hết cho 10.
Giải:
Gọi 10 số nguyên dương bất kỳ, không làm mất tính tổng quát, có thể giả sử:
a₁ ≤ a₂ ≤ a₃ ≤ ... ≤ a₁₀
Như thế này khó cho em quá, làm sao mà em có thể chứng minh được? Thôi em lập dãy số mới thế này nhé:
b₁ = a₁
b₂ = a₁ + a₂
b₃ = a₁ + a₂ + a₃
...
b₁₀ = a₁ + a₂+... + a₁₀
Ta thấy rằng, tồn tại một b_i nào đó mà chia hết cho 10 thì... → điều phải chứng minh.
Nếu không tồn tại một b_i nào chia hết cho 10, tức là b_i chia cho 10 sẽ phải dư. Số dư này chỉ có 9 giá trị thôi, anh chị à (Từ 1 đến 9). Nhưng ta có tới 10 số từ b₁ đến b₁₀, giống như nhốt 10 con "bê" vào 9 cái lồng vậy.
Thế thì theo nguyên lý Đi rích lê (Không phải đi dép lê) sẽ có 2 giá trị b_i ≡ b_j (mod 10)
Lấy số b to trừ đi b nhỏ sẽ phải chia hết cho 10. Mà số b to trừ đi b nhỏ sẽ còn lại các số a_i liên tiếp cộng với nhau. Ôi, thế thì ta có điều phải chứng minh rồi đó anh chị à.

Các bài kia anh chị chỉ việc thay số và lập luận tương tự mà. Nếu em làm đúng thì nhớ nháy nút thanks cho em nha!

Em làm thêm một vài câu mà nó không giống lắm cách làm ở trên nha.

Admin đã viết:
27. Khi chọn tuỳ ý n + 1 số nguyên dương khác nhau, chứng minh rằng tồn tại ít nhất 2 số đồng dư theo modulo n.
Đề số 5, trang 167, câu 3:
Chứng minh rằng 21 số nguyên dương khác nhau bất kỳ, tồn tại ít nhất hai số có hiệu chia hết cho 20.
Đề số 6, trang 168, câu 4:
Cho tập A = (a₁, a₂, a₃,..., a₂₂), trong đó a_i là các số nguyên dương. chứng minh rằng:
a. Tồn tại ít nhất 3 phần tử trong A đồng dư modulo 7
b. Tồn tại một hay nhiều số hạng liên tiếp của A có tổng chia hết cho 22.

Cách giải những bài trên giống nhau, nên em giải Đề số 5, trang 167, câu 3:
Chứng minh rằng 21 số nguyên dương khác nhau bất kỳ, tồn tại ít nhất hai số có hiệu chia hết cho 20.

Giải:
21 số nguyên dương khác nhau, nhưng mỗi số em phân tích như thế này nhé, anh chị xem có phù hợp không:
a_i = 20* k_i + b_i
Có nghĩa là 20* k_i là phần chia hết, hay phần nguyên của phép chia. Còn b_i là phần dư của phép chia. Vậy ta chỉ quan tâm đến phần dư. Không mất tính tổng quát, giả sử phần dư này:
0 ≤ b₁ ≤ b₂ ≤ ... b₂₁ ≤ 19
Ta thấy có 21 số b_i, mà giá trị của số dư từ 0 đến 19 có 20 số → Chắc chắn có 2 số b_i = b_j.
Vậy số a_i và a_j được thành lập sẽ lấy số lớn trừ số bé thì phần nguyên luôn chia hết cho 20, phần dư bằng nhau, khi trừ sẽ bị triệt tiêu và bằng 0. Vậy hiệu này luôn chia hết cho 20 → đpcm.

Câu 30. Cho (Xi, Yi, Zi) i = 1, 2, ..., 9 là toạ độ nguyên của 9 điểm trong
không gian 3 chiều. chứng minh rằng tồn tại ít nhất một đoạn thẳng nối 2
điểm trong số đó có trung điểm toạ độ nguyên.
Ta có trung điểm của 2 điểm (Xi, Yi, Zi) và (Xj, Yj, Zj) là điểm M có toạ độ:
[You must be registered and logged in to see this image.]
Với mọi Xi, Yi, Zi và i từ 1 đến 9.
Muốn M có toạ độ nguyên thì hoành độ, tung độ và cao độ của nó phải nguyên.
Hoành độ, tung độ và cao độ của nó nguyên khi các cặp hoành độ của 2 điểm phải cùng chẵn, hoặc cùng lẻ. Để (chẵn + chẵn)/2 = là số nguyên; hoặc (lẻ + lẻ)/2 = là số nguyên.
Ta thấy nếu giá trị của các hoành độ, tung độ và cao độ có tính chẵn, lẻ của M thì
- Mỗi Xi có thể có giá trị: Hoặc chẵn, hoặc lẻ
- Mỗi Yi có thể có giá trị: Hoặc chẵn, hoặc lẻ
- Mỗi Zi có thể có giá trị: Hoặc chẵn, hoặc lẻ
Số trường hợp chẵn lẻ của M có thể có là 2³ = 8 trường hợp
Nhưng ta có tới 9 điểm mà có 8 trường hợp, nên theo nguyên lý Đi dép lê chắc chắn có 1 trường hợp mà tính chẵn lẻ của toạ độ 2 điểm là như nhau. Như vậy, toạ độ của M sẽ luôn có hoành độ, tung độ và cao độ là các cặp giá trị có trung bình cộng là các số nguyên. Hay M có toạ độ nguyên. đpcm.

Làm câu này vì nó khác hoàn toàn cách giải so với các bài khác:

Bài 31 trang 94 sách ôn Cao học đã viết:
31. Có 16 cầu thủ bóng rổ, số áo của mỗi người được đánh từ 1 đến 16, đứng thành vòng tròn theo thứ tự bất kỳ, chứng minh rằng tồn tại ít nhất 3 cầu thủ đứng liền nhau có tổng số áo ít nhất là 26.

Gọi mỗi số áo của cầu thủ khi xếp thành vòng tròn là a_i với điều kiện 1 ≤ a_i ≤ 16, với i là số thứ tự xếp trong vòng tròn, nên 1 ≤ i ≤ 16
Gọi tiếp S_i là tổng của 3 cầu thủ đứng liền nhau. Hay ta có:
S₁ = a₁ + a₂ + a₃
S₂ = a₂ + a₃ + a₄
S₃ = a₃ + a₄ + a₅
...
S₁₆ = a₁₆ + a₁ + a₂

Theo đầu bài thì phải có ít nhất 1 trong các S_i phải lớn hơn hoặc bằng 26. Ta chứng minh bằng phản chứng:
Giả sử không có S_inào lớn hơn 26. Tức là ta có:
S₁ = a₁ + a₂ + a₃ ≤ 25
S₂ = a₂ + a₃ + a₄ ≤ 25
S₃ = a₃ + a₄ + a₅ ≤ 25
...
S₁₆ = a₁₆ + a₁ + a₂ ≤ 25
Vì là bất đẳng thức nên ta cộng tất cả các vế bên trái lại và tất cả vế bên phải lại, để được một bất đẳng thức mới:
[You must be registered and logged in to see this image.]

Vế trái = S_t = S₁+ S₃+ S₃+ ... + S₁₆
S_t = (a₁ + a₂ + a₃) + (a₂ + a₃ + a₄) +...+ (a₁₆ + a₁ + a₂)
[You must be registered and logged in to see this image.]
Vế phải = 25 * 16 = 400
Ta thấy vô lý khi nói 408 ≤ 400 nên giả thiết phản chứng sai. ĐPCM.

Bài toán tồn tại: Khi chọn tuỳ ý n + 1 số nguyên dương khác nhau, chứng minh rằng tồn tại ít nhất 2 số đồng dư theo modulo n.
************************************************************************************************
Trong tập hợp A có (n + 1) số nguyên dương khác nhau có 2 phần tử bất kỳ là x_i # x_j thì ta có thể suy ra rằng
x_i chia cho n dư a và x_j chia cho n dư b
như vậy [ x_i - x_j ] chia cho n thì sẽ dư là (a-b). trong đó a và b sẽ nhận giá trị trong (0,n-1) hay a và b có thể lựa chọn trong n giá trị khác nhau tương ứng với giá trị x khác nhau trong A. Tuy nhiện với tập hợp A có (n+1) giá trị x khác nhau => theo nguyên lý Drichlet tồn tại 2 giá trị x khác nhau mà a và b cùng nhận một giá trị. tức (a-b) = 0
=> [ x_i - x_j ] chia cho n dư 0 hay còn gọi là x_i và x_j đồng dư theo modulo n
==> dpcm

Hic Hic.... Đi dép lê thật đau đầu... em năm nay thi đầu vào mà ngại nhất phần lập luận đi dép lê, tổ hợp chỉnh hợp... đau đầu quá .. huhu

Bác Cường đi chơi mà vẫn còn quan tâm đến anh em k24!hihi
Bác xem lớp mình có thông báo gì thì báo cho anh em biết với nhá!