Chương 1. Nguyên lý Đirichlê và ví dụ cho tương ứng với một số bằng số lượng các quan ngồi đúng vị trí tên mình, thì tổng của tất cả những số nhận được (mọi trạng thái bàn) sẽ không nhỏ hơn n. Nhưng một trạng thái đầu tiên của sắp xếp bàn cho tương ứng với 0 (không ai ngồi đúng chỗ ). Nếu giả sử trong n − 1 trạng thái mặt bàn còn lại tương ứng với số nhỏ hơn 2 (tức là chỉ có số 1 hoặc 0), thì tổng của n số nhận được sẽ nhỏ hơn n, điều đó không thể được.
Suy ra từ n − 1 trạng thái mặt bàn còn lại có ít nhất một trạng thái mà hai người sẽ đối diện với chính tên của mình. Trong sân cung điện nhà vua hội họp 2n(n ≥ 2) ông quan, mỗi ông quan đã quen biết không ít hơn n ông có mặt tại đó. Chứng minh rằng người xếp bàn tròn có thể xếp được mỗi bàn 4 người sao cho mỗi người đứng giữa hai người quen của mình. Một khu rừng thông có dạng hình vuông mỗi chiều 1km.
Trong rừng có 4500 cây thông, cây to nhất có đường kính 0,5m. Chứng minh rằng trong khu rừng có ít nhất 60 mảnh đất, diện tích mỗi mảnh 200m2 , không có một cây thông nào. Trong một giá sách có 25 ngăn. Ta thấy có một ngăn chứa 10 cuốn, còn các ngăn khác chứa số sách ít hơn.
Chứng minh rằng có ít nhất ba ngăn sách chứa cùng số sách như nhau (kể cả những ngăn không có sách). Tại một thành phố biển xe ôtô được đánh số bằng tổ hợp chữ cái rồi đến dãy số. Chứng minh rằng trên một đoạn đường cứ có 11 chiếc ôtô đi qua thì bao giờ cũng có hai chiếc ôtô có cùng chữ số tận cùng. Một chiếc hồ lớn được bọc bởi 4 trạm chuyển tiếp sóng thông tin.
Giữa hai trạm người ta xây dựng các trung tâm phát sóng và nhận sóng, đường sóng bao phủ lớn nhất là đường tròn có tâm ở trung tâm và đi qua hai trạm. Chứng minh rằng với bốn trung tâm ở các đoạn giữa của từng cặp trạm thì toàn bộ mặt hồ sẽ được phủ sóng thông tin. CHƯƠNG 2 SỐ HỌC 2. Phép chia số tự nhiên.
PHÉP CHIA SỐ TỰ NHIÊN Trong các phép tính trên số nguyên: cộng, trừ, nhân, chia, thì phép chia là rất đặc biệt. Phép chia có hàng loạt tính chất mà tất cả các phép tính còn lại không có. Ví dụ các phép toán đều thực hiện với số 0 được, nhưng riêng phép chia cho số 0 thì không được. Phép chia không chỉ đặc biệt với phép chia cho 0.
Với các phép tính cộng, trừ, nhân trên số nguyên cho ta số nguyên, nhưng với phép chia thì tính chất đó không còn đúng vì không phải lúc nào ta cũng nhận được số nguyên sau phép chia. Nhờ những dị biệt của phép chia mà trong toán học xây dựng hẳn một lý thuyết về phép chia những số nguyên. Những ví dụ và bài tập chương này có liên quan mật thiết giữa phép chia và nguyên lý Đirichlê, nên chúng ta nhắc lại định nghĩa phép chia: Cho a và b là những số nguyên, với b > 0. Chúng ta nói rằng a chia hết cho b, ký hiệu là b| a, khi tồn tại một số nguyên q sao cho đẳng thức sau đúng a = bq.
Vídụ 13 Chúng ta thường gọi số a là bội của b, hoặc b là ước của a. Số q gọi là thương số của phép chia a cho b. Trong phát biểu định nghĩa trên, nếu không tồn tại một số q nào cả, thì chúng ta nói rằng a không chia hết cho b và ký hiệu là b 6 | a. Từ định nghĩa chúng ta dễ dàng chứng minh được các tính chất sau 1) Với mọi số nguyên a > 0 chúng ta có a| a, Phép chia hết có tính phản xạ.
2) Nếu b| a và a|c thì b|c- phép chia hết có tí nh bắc cầu. 3) Nếu b| a và b|c, thì b|( ac). 4) Nếu a, b, m, n là những số nguyên và nếu c| a và c|b, thì c|(ma + nb). Định lý sau đây giữ vai trò quan trọng cho phép chia một số nguyên cho một số nguyên.
Với hai số nguyên bất kỳ a và b sao cho b > 0, tồn tại duy nhất những số nguyên q và r thỏa mãn a = bq + r và 0 ≤ r < b. Còn rất nhiều tính chất khác của số nguyên cũng như số thực nhưng chúng ta không đi theo hướng này, mà chỉ dùng các tính chất của số học và Nguyên lý Đirichlê để giải các bài toán. Cho k là một số tự nhiên, A là tập hợp gồm k + 1 số tự nhiên. Chứng minh rằng có ít nhất một hiệu hai phần tử trong A chia hết cho k.
, ak+1 là các phần tử của A, còn b1 , b2 ,. , bk+1 là những số dư của phép chia các số trên cho k. Khi đó a1 = 14 Chương 2. Số học kc1 + b1 , a2 = kc2 + b2 ,.
, ak+1 = kck+1 + bk+1 ,với các số nguyên c1 , c2 ,. , ck+1 sao cho 0 ≤ b1 ≤ k − 1, 0 ≤ b2 ≤ k − 1,. Một phần tử bất kỳ as thuộc A cho tương ứng với số dư bs của nó.Gọi tập hợp các số dư là B. Như vậy, mỗi phần tử của A được đặt tương ứng với một phần tử của tập hợp B, gồm tất cả các số nguyên từ 0 đến k − 1.
Nhưng số lượng phần tử của A theo giả thiết là k + 1, còn B có số lượng k. Theo nguyên lý Đirichlê suy ra tồn tại hai phần tử khác nhau của A có cùng số dư. Điều đó nghĩa là, tồn tại hai chỉ số khác nhau s và t với as = kcs + bs và at = kct + bs sau khi trừ đi cho nhau ta được at − as = k (ct − cs ). Cho A một tập hợp bất kỳ gồm 101 số tự nhiên, mỗi số không lớn hơn 200.
Chứng minh rằng trong A có ít nhất hai số mà một số này chia hết cho số kia. Mỗi số a của A có thể biểu diễn dưới dạng a = 2k b với k là số nguyên không âm, còn b là một số lẻ. Với mỗi số a thuộc A cho tương ứng với số b trong sự biểu diễn ở trên. Bằng cách này, mỗi phần tử a của A được đặt tương ứng với một phần tử của tập hợp B gồm các số lẻ giữa 1 và 200.
Nhưng tập hợp B chỉ có 100 phần tử vì vậy số phần tử của A lớn hơn số phần tử của B. Ta có thể áp dụng nguyên lý Đirichlê, suy ra tồn tại hai phần tử khác nhau a1 và a2 thuộc A mà chúng tương ứng với cùng một số của tập hợp B. Nghĩa là, a1 = 2k1 b, a2 = 2k2 b và nếu k1 < k2 , thì số a2 chia hết cho a1. Cho M là tập hợp bất kỳ gồm 75 số tự nhiện mà mỗi số không lớn hơn 100.
Chứng minh rằng với mỗi số tự nhiên l nhỏ hơn hoặc bằng 49 tồn tại hai phần tử của M có hiệu là l. Gọi các phần tử của M là x1 , x2 ,. Ký hiệu A là tập hợp các số tự nhiên từ 1 đến 150. Với mỗi số 1, 2, 3.
Vídụ 15 ứng với các số x1 , x2 ,. 150 lần lượt ứng với x1 + l, x2 + l,. , 75) và l ≤ 49 thì xm + l < 150. Suy ra mỗi phần tử của A tương ứng với một phần tử của B gồm những số tự nhiên từ 1 đến 149.
Vì số phần tử của A lớn hơn số phần tử của B, theo nguyên lý Đirichlê tồn tại hai phần tử khác nhau của A, mà chúng tương ứng với cùng một phần tử của B. Nhưng với các giá trị khác nhau của m từ 1 đến 75 được cho tương ứng với các giá trị khác nhau của x1 đến x75 trong B. Tương tự các giá trị của m ở khoảng 76 đến 150 tương ứng với các giá trị khác nhau trong khoảng còn lại. Từ đó suy ra tồn tại xm và xn mà xm = xn + l, nghĩa là xm − xn = l.
Cho k ≥ 1 và n ≥ 1 là những số tự nhiên và A là tập hợp gồm (k − 1)n + 1 số nguyên dương, mỗi số này đều nhỏ hơn hoặc bằng kn. Chứng minh rằng ít nhất có một phần tử của A có thể biểu diễn như tổng của k phần tử trong A. Với k = 1 bài toán hiển nhiên là đúng, chúng ta giả thiết k ≥ 2. Ký hiệu m là số nhỏ nhất thuộc A.
Dễ thấy rằng m ≤ n và tồn tại đúng n − m số thuộc A mà chúng lớn hơn m nhưng không vượt quá kn. Để chứng minh bài toán chúng ta tìm hai số x và y thuộc A sao cho x = y + (k − 1)m; nghĩa là biểu diễn một số nào đó thuộc A thành tổng k số hạng thuộc A trong đó có k − 1 số hạng bằng m. Chỉ cần tìm số x thuộc A mà x > (k − 1)m và x − (k − 1)m thuộc A. Thật vậy, trong khoảng ∆ = ((k − 1)m, kn] có kn − (k − 1)m = k (n − m) + m số nguyên.
Vì k ≥ 2, nên (k − 1)m ≥ m, theo nhận xét ban đầu suy ra có nhiều nhất n − m số trong ∆ không thuộc A. Điều này nghĩa là A chứa ít nhất s = k (n − m) + m − (n − m) = 16 Chương 2. Số học (k − 1)(n − m) + m số. , as thuộc A, với (k − 1)m < ai ≤ kn, i = 1, 2,.
Khi đó những hiệu a1 − (k − 1)m, a2 − (k − 1)m,. Nếu một số nào đó trong chúng không thuộc A, thì theo nguyên lý Đirichlê chúng ta nhận được s ≤ n − 1, vì ngoài A có đúng n − 1 số trong khoảng này. Như vậy trái với bất đẳng thức đã chứng minh s ≥ n. Suy ra tồn tại một hiệu ai − (k − 1)m thuộc A.
Chứng minh rằng từ n + 1 số dương khác nhau nhỏ hơn 2n, có thể chọn được ba số sao cho tổng hai số trong chúng bằng số thứ ba. < an+1 là những số đã cho. Chúng ta xét các hiệu số a2 − a1 , a3 − a1 ,. , an+1 − a1 và các số a2 , a3 .