Ứng dụng phương pháp Đirichlê: Phần 1

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:88

Thêm vào BST

Báo xấu

13
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phần 1 cuốn sách "Phương pháp Đirichlê và ứng dụng" trình bày các nội dung: Nguyên lý Đirichlê và ví dụ, số học, dãy số, hình học, mở rộng nguyên lý Đirichlê, bài tập số học nâng cao, bài tập dãy số nâng cao, số thực với tập trù mật. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Ứng dụng phương pháp Đirichlê: Phần 1

, ˜ ˜, NGUYÊN HUU ÐIÊN , , ´ PHUONG PHAP ÐIRICHLÊ ´, ` UNG DUNG VA . , ` ´ ` ˜ NHA XUÂT BAN KHOA HOC VA KY THUÂT . . ` . HA NÔI - 1999
, ` ` ´ LOI NOI ÐÂU , , ,, , y u a ` Nguyên l´ nh˜ ng c´i lông v` c´c ch´ tho da duoc biêt dên t` rât a a u ¯˜ ¯ . ´ ¯´ u ´ ,, , , ,, lâu. Ngay trong chuong tr` phô thông co so ch´ ng ta c˜ ng da l`m ınh u u ¯˜ a , ,, , , ´ quen voi phuong ph´p giai to´n n`y. Thuc ra nguyên l´ n`y mang a a a . y a ,`, ´ , tên nh` b´c hoc nguoi Ðuc Pête Gutxtap Legien Dirichlet (1805- a a . , , , ´ ¯, 1859). Nguyên l´ ph´t biêu rât don gian: Nêu ch´ng ta nhôt tho v`o y a ´ u ´ a , ´ , , a ` a ´ ` ıt c´c lông m` sô lông ´ hon sô tho, th` thê n`o c˜ng c´ môt lông nhôt ´ ı a u o . ` ´ ıt , ´ nhât hai con tho. , , , , ` ˘ Chı bang nguyên l´ don gian nhu vây h`ng loat c´c b`i to´n da y¯ . a . a a a ¯˜ ,, , duoc giai. ¯ . , ´ a ¯ , ., , Cuôn s´ch duoc biên soan lai theo t` ng chu dê c´ liên quan dên . . u ¯` o ¯´ ˜ a , , , ,, nguyên l´, môi c´ch giai trong v´ du cua t` ng chuong l` ap dung y ı . u a´ . , , ,´ , diên h` nguyên l´ Ðirichlê. B`i tâp giai truoc c´ liên quan dê a ¯ ınh y a . o ¯ ´n b`i , , , giai sau nên câ `n luu ´ khia doc s´ch. Voi mong muôn c` ng ban doc y ¯. a ´ ´ u . ¯. , ,, , thao luân môt phuong ph´p chu . . a ´ ng minh to´n hoc v` hy vong cung a . a . , câ´p môt t`i liêu bô ´ cho c´c thây cô gi´o v` c´c em hoc sinh ham . a . ıch a ` a a a . , mê t` t`i trong to´n hoc, t´c gia manh dan biên soan cuôn s´ch ım o a . a . . . ´ a , , n`y. Do kha n˘ng v` th` i gian c`n han chê, cuôn s´ch chac chan a a a o o . ´ ´ a ´ ˘ ´ ˘ , ,, , không tr´nh khoi thiê o a ´u s´t. Ch´ ng tôi mong duoc su dong g´p ´ u ¯ . . ¯´ o y , , , ,, , kiê´n cua doc gia. Thu g´p ´ xin gui vê Nh` xuât ban Khoa hoc v` K˜ ¯. o y ` a ´ . a y , `n Hung Ðao, H` Nôi. thuât - 70 Trâ . . a . 3
, 4 o o ¯` L`i n´i dâu , , , ˜ ` a a ¯˜ ¯ . T´c gia xin chân th`nh cam on PGS-TSKH Ðô Hông Tân da doc , , a ¯´ v` dong g´p nhiê y o `u ´ kiên qu´ b´u trong qu´ tr` ho`n chınh ban ´ ı a a ınh a , thao. , T´c gia a
, , CHUONG 1 NGUYÊN LY ÐIRICHLÊ VA V´ DU ´ ` I . 1.1. Nguyên l´ Ðirichlê y ` ,, , Nguyên l´ Ðirichlê nhiêu khi ngu` i ta goi l` ¨Nguyên l´ nh˜ ng y o . ,a y u , a e a . y ´ ¯ ¯˘ ng˘n k´o¨. Ðây l` môt nguyên l´ rât don gian, dac biêt c´ nhiêu . . o ` , , , ´ ung dung trong c´c l˜ vuc kh´c nhau cua to´n hoc. D` ng nguyên . a ınh . a a . u ,`, , ,, ˜ d`ng chung minh tôn tai môt dôi tuong voi t´ ` . , l´ n`y nguoi ta dê a y a ´ , , . ¯´ . , ´ ınh ´ a ¯. , ´ o , chât x´c dinh. Dang don gian nhât c´ thê ph´t biêu nhu sau: . ¯ a ´ o Nêu c´ m vât dat v`o n c´i ng˘n k´o v` m > n th` c´ ´ nhât môt . ¯˘ a. a a e a ı o ıt ´ . , ´ ıt ´ ng˘n k´o chua ´ nhât hai vât. a e . , ,, , , ,, , ` Tuy rang voi nguyên l´ n`y ngu` i ta chı chung minh duoc su tôn ˘ ´ y a o ´ ¯ . . ` , ,, ,, ,, , , tai m` không dua ra duoc phuong ph´p t` duoc vât cu thê, nhung . a ¯ ¯ . a ım ¯ . . . , , , , , . ´ ` a a ` trong thuc tê nhiêu b`i to´n ta chı cân chı ra su tôn tai l` du rôi. . ` . a¯ ` , , , y a . ¯. y ` . Nguyên l´ Ðirichlê l` môt dinh l´ vê tâp hop h˜ u han. Ph´t biêu . u . a , ch´ x´c nguyên l´ n`y nhu sau: ınh a y a , ,, , Cho A v` B l` hai tâp hop không rông c´ sô phân tu h˜ u a a ˜ o ´ ` u . , ,. ,, , ,, , , , ,, a ´ . ` ´ han, m` sô luong phân tu cua A lon hon sô luong phân tu cua . ´ . ` , ,, , ,, B. Nêu voi môt qui ta a ¯ ´ ´ ´ ˘ ˜ ´c n`o dây, môi phân tu cua A cho tuong ` . ,, ,, , ´, ´, ` ı ` . ung voi môt phân tu B, th` tôn tai hai phân tu kh´c nhau cua A . ` a , , ´, , ,, , ´ u m` ch´ ng tuong ung voi c` ng môt phân tu cua B. a u . ` , ˜ , , ,, , , ` a ` Ðê dê hiêu ta cu cho rang c´c phân tu cua tâp B l` ¨Nh˜ ng ng˘n ´ ˘ . a u a
,, 6 Chuong 1. Nguyên l´ Ðirichlê v` v´ du y a ı . , , , e a a ` , ,, ¯ . ¯˘ a a k´o¨ v` c´c phân tu cua A duoc dat v`o c´c ng˘n k´o cua n´. Trong . a e o , , ,, ph´t biêu cua nguyên l´ trên c´c phâ a y a `n tu h˜,u han duoc t´ bang u ,, . ¯ . ınh ` ˘ , , ´ tu nhiên, v` vây Nguyên l´ Ðirichlê c´ liên quan mât thiêt toi tâp ´ ´ . sô . ı . y o . , ´ , , , ´ hop sô tu nhiên v` c´c t´ châ . . a a ınh ´t cua tâp hop sô n`y. . . a 1.2. V´ du ı . , , , . a a o ` 1.1. Ðê ky niêm 20 n˘m ng`y giai ph´ng Miên Nam, tai môt th`nh . , . a ,`, , , , ´ ´ ˜ gap mat nhu,ng ngu,`,i 20 tuôi. Ng`y 30 phô nguoi ta tô chuc buôi lê ˘ ˘ ˜ o a , . . , a ¯´ th´ng 4 n˘m do trong buôi gap mat c´ 400 thanh niên. Chung minh a ˘ . ˘ o . ´ `ng c´ ´ nhât hai ngu,`,i trong sô ngu,`,i t´,i du, c`ng chung môt ng`y ra ˘ o ıt ´ o ´ o o . u . a sinh. , , `, o a u ˜ Loi giai. N˘m 1995 c´ 365 ng`y. Ch´ ng ta coi môi ng`y nhu môt a a . , ´ u ¯´ ´ u ng˘n k´o v` danh sô t` 1 dên 365 (ng˘n k´o cuôi c` ng l` ng`y 31 a e a ¯´ a e a a , th´ng 12 n˘m 1995). Ch´ ng ta dat nh˜ ng thanh niên c´ ng`y sinh a a u ¯˘ . u o a ,, ´ , , , , tuong ung v`o c´c ng˘n k´o do. Nhung sô thanh niên dên du l˜ lon a a a e ¯´ ´ ¯´ . ê ´ , ´ ´ ,, ,, hon sô ng˘n k´o, theo nguyên l´ Ðirichlê c´ ´ nhât hai ngu` i duoc a e y o ıt o ¯ . ¯˘ a u . . ` ¯´ o dat v`o c` ng môt ng˘n k´o. Ðiêu do c´ ngh˜ l` ho sinh c` ng môt a e ıa a . u . ng`y. a J ,, , ,, . o ´ ˘` ´o ¯` ˜ 1.2. Trong sinh hoc ngu`i ta biêt rang sô t´c trên dâu cua môi ngu`i o , , a a ´ không qu´ 200.000 c´i. Chung minh ra `ng trong sô ngu,`,i cua th`nh ˘ ´ o a ´ a . o , ´ , ´ ,`, ´ phô H` nôi, v´i sô dân hon 2.000.000, c´ ´ nhât 11 nguoi c´ c`ng sô o ıt o u t´c. o , ,, , `, u e a e ¯ . ¯´ ´ u ¯´ Loi giai. Ch´ ng ta x´t 200.000 ng˘n k´o duoc danh sô t` 0 dên ˜ ,, 199.999. Ch´ ng ta ¨dat¨ môi ngu` i dân H` nôi v`o môt ng˘n k´o u ¯˘ . o a . a . a e , , , , ,, ,, a ´ o ` ˘ ´ ´ . m` sô t´c bang sô thu tu cua ng˘n k´o. Gia su không c´ 11 ngu` i a e o o ´ o , ˜ ` ´ a ,`, c´ c` ng sô t´c, nhu vây môi ng˘n c´ nhiêu nhât l` 10 nguoi c´ c` ng o u . a o o u ´ o ¯´ ´ ` ´ a sô t´c, do do sô dân H` nôi nhiêu nhât l` 200.000×10=2.000.000, a .
1.2. V´ du ı . 7 , , , , ¯ ` a ¯´ ´ ´ a ´ a . ´ diêu n`y không dung voi gia thiêt l` sô dân H` nôi lon hon 2 triêu. . J ,, , . a a ´ ınh . ´ . 1.3. Ba muoi hoc sinh l`m b`i viêt ch´ ta. Môt trong sô hoc sinh ˜ o a . , , ˘ ˜ ıt ´ ´ ` do bi 14 lôi, c`n c´c hoc sinh kh´c mac lôi ´ hon. Chung minh rang ¯´ . a ˘ ´ ,`, ´ ´ ˜ ` c´ ´ nhât ba nguoi mac sô lôi bang nhau. o ıt ˘ ˘ , ,, , `, u e a e ¯ . ¯´ ´ u ¯´ Loi giai. Ch´ ng ta x´t 15 ng˘n k´o duoc danh sô t` 0 dên 14. Ch´ ng u ¯˘ ta ¨dat¨ môi . ˜ hoc sinh v`o môt ng˘n k´o mang sô dung bang sô lôi a a e ´ ¯´ ` ˘ ´ ˜ , . . cua hoc sinh n`y. Nê . a o . a o ´˜ ` ´u không c´ ba hoc sinh n`o c´ sô lôi bang nhau, ˘ th` trong môi a ı ˜ ng˘n mang sô t`, 0,1,2,. . . ,13 s˜ c´ nhiêu nhât hai hoc ´ u e o ` ´ . ,, , , ¯´ sinh. Khi do sô . ´ luong cua nh˜ ng hoc sinh n`y nhiêu nhât l` 28. Nêu u . a ` ´ a ´ a ¯´ . thêm v`o do hoc sinh ma ˘ ˜ ´c 14 lôi (trong ng˘n k´o sô 14) ch´ ng ta s˜ a e ´ u e ,, , nhân duoc nhiê . ¯ . ´ . ´ ınh ¯ ` a ˜ ¯´ `u nhât 29 hoc sinh viêt ch´ ta, diêu n`y dân dên , , ` y ´ ¯ . ¯˜ su vô l´ voi diêu kiên da cho. . J ´, ` ˜ ,, ´ 1.4. Chung minh rang trong môi nh´m ban 5 ngu`i c´ ´ nhât hai ˘ o . o o ıt ,`, ´ .,, ,`, ˜, ˜, ,`, nguoi c´ c`ng sô luong nguoi quen giua nhung nguoi trong nh´m dos. o u o ¯ , `ng c`ng kêt luân nhu, vây v´,i nh´m ban c´ sô lu,o,ng ´ . ´ Chung minh ra ˘ u . o o . o ´ . ´ y th`nh viên bât k`. a , , ,, `, u e a a e ¯´ ´ u ¯´ Loi giai. Ch´ ng ta x´t n˘m ng˘n k´o, danh sô t` 0 dên 4. Môi ngu` i ˜ o , ,, , ´ tr` ng voi sô ngu`,i trong ´, ´ . ¯ . ¯˘ a tham du duoc dat v`o ng˘n k´o mang sô u . a e o ,`, o a ¯´ nh´m m` nguoi do quen. ,, , , ,, ´ o . ´ u a) Nêu c´ môt ngu` i không quen ai ca trong sô nh˜ ng ngu` i o o ,, , o . ı a ´ a ´ c`n lai, th` ng˘n sô 4 l` trông (v` nguoc lai th` ca hai ng˘n 0 v` 4 ı . . ı a a ˜ ¯´ , ˜ ,`, ¯` ´ dêu không trông, dân dên vô l´). Nhu vây, môi nguoi trong sô 5 y . ´ ,`, , , ´ ´, ´ ,, ¯ . ¯˘ a a nguoi duoc dat v`o c´c ng˘n mang sô 0,1,2,3 voi sô luong 4 ng˘n. . a . a , ´ o ,`, ,, T` nguyên l´ Ðirichlê suy ra ´ nhât c´ hai nguoi o trong môt ng˘n, u y ıt . a ,, ´ . ,`, hay l`, ho c´ chung sô luong nguoi quen. a . o
,, 8 Chuong 1. Nguyên l´ Ðirichlê v` v´ du y a ı . ´ ,, ´ . ,, ˜ ,, ,, b) Nêu moi ngu` i c´ ´ nhât môt ngu` i quen, môi ngu` i s˜ duoc . o o ıt o o e¯ . ¯˘ a a ´ ´ ´ , ., , ` o . dat v`o c´c ng˘n mang sô 1,2,3,4, voi sô luong 4 ng˘n. Phân c`n lai . a a ´ ap dung nguyên l´ Ðirichlê. . y J , , , . . ¯. ˜ ˘ 1.5. Trong môt giai b´ng da tham du 16 dôi. Môi cap hai dôi phai o ¯´ . , ¯. , , ¯´ o , ´, ` ˘ . ˜ o, ¯ o ıt ´ dâu v´i nhau. Chung minh rang tai môi th`i diêm cua giai c´ ´ nhât , ¯ . o ´ . ¯˜ ¯ ´ 2 dôi c´ sô trân da dâu nhu nhau. , , `, u e a e ¯´ ´ u ¯´ Loi giai. Ch´ ng ta x´t 16 ng˘n k´o danh sô t` 0 dên 15. Ch´ ´ rang uy ` ˘ ,, , 15 l` sô . a ´ luong lon nhât c´c trân b´ng m` môi dôi c´ thê dâu tai th`,i ´, ´ a . o a ˜ ¯. o ¯ ´ . o , ˜ dôi b´ng v`o ng˘n k´o mang sô bang ¯ ¯ a ¯˘ diêm dang x´t. H˜y dat môi ¯ . o e . a a e ´ ` ˘ , ´ c´c trân m` dôi da dâu dên th`,i diêm do. Ch´ ng ta nhân ra rang sô a . a ¯ . ¯˜ ¯ ´ ¯´ o ¯ ¯´ u . ` ˘ , c´c ng˘n 0 v` 15 không thê dô a a a ¯ o ´ ¯ , ., a `ng th`,i không trông duoc v` nhu vây, . , ´ c´ thê ap dung nguyên l´ Ðirichlê. o . y J , , ,, a ¯´ ´ o ´ ˘ ` a ´ 1.6. Trên tr´i dât sông hon 5 ty ngu`i, biêt rang không qu´ 1% sông , , ,`, ´ ` ´ o trên môt tr˘m tuôi. Chung minh rang ´ nhât c´ hai nguoi sinh c`ng . a ˘ ıt u ¯` môt giây dông hô. . ` , ,, `, . . a o ıt , Loi giai. Theo duong lich hiên h`nh 100 n˘m c´ ´ hon 37000 ng`y. a a ˜ ng`y c´ 24 gi`,, môi gi`, c´ 3600 giây. Khi do 100 n˘m c´ ´ hon Môi a o o ˜ o o ¯´ a o ıt , , , ,, , ,, u¯ ` 3,33 ty giây. T` diêu kiên ch´ ng ta t` duoc nh˜ ng ngu` i trên tr´i . u ım ¯ . u o a , , dâ ¯ ´t không qu´ 100 tuôi ´ nhât l` 99% t`, 5 ty ngu`,i ngh˜ l` ´ nhât a ıt ´ a u , o ıa a ıt ´ , , ,`, o . ´ ¯˘ c´ 4,9 ty. Viêc c`n lai ap dung nguyên l´ Ðirichlê: dat 4,9 ty nguoi o y , . . . v`o 3,33 ty ng˘n k´o. a a e J , , e a . a . . . ıt ´ 1.7. Trong th`i gian k´o d`i môt n˘m hoc môt hoc sinh giai ´ nhât o , , , ˜ môt b`i tâp môi ng`y. Ðê tr´nh c˘ng thang hoc sinh giai h`ng tuân . a . a a a ˘ . a ` ´, ` , không qu´ 12 b`i tâp. Chung minh rang trong th`i gian k´o d`i liên a a . ˘ o e a , , . . ´ a . a ¯´ a . ˜ tuc môt sô ng`y hoc sinh n`y phai giai dung 20 b`i tâp môi ng`y. a
1.2. V´ du ı . 9 , ,, , `, u y . a ´ . Loi giai. Ch´ ng ta k´ hiêu a1 l` sô luong b`i tâp hoc sinh da giaia . . ¯˜ ,, , a ¯` a ´ . a . ¯˜ trong ng`y dâu tiên, a2 l` sô luong b`i tâp da giai trong hai ng`y a , dâ ¯ a ´ , ., `u, a3 l` sô luong b`i tâp da giai trong ba ng`y dâu, v` v.v. a77 a . ¯˜ a ¯ ` a ,, , , l` sô . a ´ luong b`i tâp da giai trong 77 ng`y dâu (11 tuân). Theo gia a . ¯˜ a ¯ ` ` ´ thiêt a77 ≤ 11.12 = 132. Ch´ ng ta x´t tâp hop c´c sô tu nhiên u e . . , a ´ ., M = { a1 , a2 , a3 , . . . , a77 , a1 + 20, a2 + 20, a3 + 20, . . . , a77 + 20}. N´ o , , chu ` , a ´ ´ , ´ ´ a 154 phân tu v` sô lon nhât trong ch´ ng l` a77 + 20 ≤ 152. u a ´ ` ´t hai sô bang nhau. Nhung , Theo nguyên l´ Ðirichlê trong M c´ ´ nhâ y o ıt ˘ a ´ c´c sô a1 , a2 , a3 , . . . , a77 l` ho`n to`n kh´c nhau. suy ra tôn tai ak v` a a a a ` . a , `u n`y al m` ak = al + 20, l < k ≤ 77. Nhu vây ak − al = 20, diê a . ¯ a , , c´ ngh˜ l` tu a o ıa a `, ng`y thu l + 1 dên ng`y thu k hoc sinh n`y phai giai ´, ¯ ´ a ´, . a ¯´ dung 20 b`i. a J , ,, , , , . . ´ 1.8. Trong môt khu tâp thê sông 123 ngu`i. Tông sô tuôi cua ho o ´ ., , , l` 3813. Chu a ´,ng minh rang c´ thê chon 100 ngu,`,i sông o, khu tâp thê ` ˘ o ., o ´ . , , , n`y, m` tông sô a a ´ tuôi cua ho không nho ho,n 3100. . , ,, , , ,, `, u a . o ` Loi giai. Ch´ ng ta h˜y chon 100 ngu` i nhiêu tuôi nhât v` gia su ´ a , , , , , ,, , ´ tông sô tuôi cua ho nho hon 3100. Khi do ngu` i tre nhât trong sô . ¯´ o ´ ´ ,`, , , , ,`, ¯ ˘ nguoi duoc chon l` 3100:100=31 tuôi. Mat kh´c nguoi n`y không . a a a , , . ,`, . , , , o . a . ¯´ tre hon 23 nguoi c`n lai theo c´ch chon. Khi do tông sô tuôi cua 23 ´ ,, , , , , , , ngu` i n`y không lon hon 23.31=713. Suy ra tông sô tuôi cua tât ca o a ´ ´ ´ ,, ´ , , , ˜ ¯´ moi ngu` i sông trong tâp thê nho hon 3100+713=3813 dân dên . o . vô l´. y J , , , , a ˘ . ` . ´ 1.9. N˘m cap vo chông tô chuc môt buôi gap mat. Khi gap nhau ho . ˘. ˘ . ˘ . . ´ , , ´ ,`, bat tay nhau, nhung không ai tu bat tay nguoi trong gia d` m` ˘ . ˘ ¯ınh ınh ,, , ´ a o a ` v` ngu`i m` chông m` (hoac vo m` ınh ˜ ˘ ˘ . ınh) da bat tay rôi. C˜ng không . ¯ ` u ´ ,, ` `, ai bat tay c`ng môt ngu`i hai lân. Sau cuôc gap ch´c mung ban dâu, ˘ u . o ˘ u ¯` ,`, , ,. . , ,`, , , . ¯` a u ´ ˜ môt nguoi dan ông tên l` H`ng hoi tât ca nhung nguoi c´ mat, kê ca o ˘ .
,, 10 Chuong 1. Nguyên l´ Ðirichlê v` v´ du y a ı . , ´ ,, ` ´ ˘ ` vo m` a . ¯˜ ˘ tay ¯ . . ınh, l` ho da bat , duoc bao nhiêu lân. Ho nhân thây rang ch´ . . ın ,`, , , , ` , , , , ´ kh´c nhau. Nhu vây vo cua H`ng nguoi duoc hoi dêu tra l`i c´c con sô a ¯ . ¯ o a . . u ¯˜ ˘ d a ba ´t tay bao nhiêu lân? ` , ,, , , `, ˜ . o a ´ Loi giai. Môi môt ngu` i kh´ch bat tay không qu´ 8 lân. V` câu tra l` i ˘ a ` ı o , ,`, , a a ´ a a ´ ¯´ cua 9 nguoi l` c´c sô kh´c nhau nên c´c sô do phai l` 0,1,2,3,4,5,6,7 a ,`, ´ , , , ,, a ` v` 8. Nguoi bat tay 8 lân phai l` vo (hoac chông) cua ngu` i không ˘ a . ˘. ` o ´ ` a ´ ,, ,`, ´ ` ˘ bat tay lân n`o (nêu nguoc lai th` nguoi do không bat tay 8 lân m` . . ı ¯´ ˘ a , ,, , , ,`, ´ ` ´ ` nhiêu nhât chı l` 7 lân thôi). Tuong tu nhu vây nguoi bat tay 7 lân a . . ˘ ` ,`, , ` ´ ,`, ´ ˘ ˘ . ` c´ nguoi vo (hoac chông) bat tay môt lân, nguoi bat tay 6 lân c´ o . . ˘ ` o ,`, , ` ´ ` ,`, ´ ` o ,`, , ˘ ˘ nguoi vo (hoac chông) bat tay 2 lân, nguoi bat tay 5 lân c´ nguoi vo . . ˘ . , ,`, ˘ . ` ´ ˘ ` (hoac chông) bat tay 3 lân. Chı c`n lai môt nguoi duy nhât bat tay o . . ´ ´ ˘ ` ¯´ ınh a ,, , , 4 lân, do ch´ l` ngu` i vo cua H` ng. o . u J , , ,, . . . ˘ ` 1.10. Môt câu chuyên cô t´ kê lai rang: Môt lân vua H`ng vuong ıch . ` u , ` . ` 18 c´ m`i c´c quan trong triêu hop ngôi quanh môt c´i b`n tr`n. Theo o o a . a a o , , . . , ` ¯˜ ´ lênh cua vua, môt cân thân da viêt tên cua môi . ˜ quan trên b`n tru,o,c a ´ ´ ´ a ` a ` ,, chiêc ghê m` ông ta phai ngôi. C´c quan trong triêu không duoc b´o ¯ . a ,´, ´p xêp da dinh m` chiêm chô môt ˜ . truoc nên ho da ngôi không theo sa ´ ¯˜ ¯. . ¯˜ ` ˘ a ´ , , a ´ y ´ ` ` o c´ch bât k`. Chung minh rang ông cân thân c´ thê quay chiêc b`n sao ˘ . ´ a , ıt ´ o ` ¯´ cho ´ nhât c´ hai ông quan ngôi dung vi tr´ tên cua m` ? . ı ınh , ,, `, ˘ ´ . . a ¯´ ˘ a o Loi giai. Ðat sô luong c´c quan l` n. Khi do mat b`n c´ n trang th´i, a . . a , , , ´ a a a ¯´ . ´ a ¯` voi c´c trang th´i n`y dôi diên voi c´c quan l` biên dê tên n`o do. . a a ¯´ , ˜ , ´ Ngo`i ra voi môi môt ông quan chı c´ môt trang th´i, m` khi ngôi a . o . . a a ` , , , ¯´ ´ ¯´ . ´ dung th` ông ây dôi diên voi ch´ tên cua m` trên biên dê san. ı ınh ınh ¯` ˜ ˘ ˜ . , , ,, ıa a ´ Ngh˜ l`, nêu môi trang th´i cua b`n (v` b`n c´ thê xoay duoc) ta a a ı a o ¯ . ,, ´ , ´, ´ ` ´ .,, ` ¯´ ˘ cho tuong ung voi môt sô bang sô luong c´c quan ngôi dung vi tr´ a . ı , ,. , , ,, tên m` ı ´ u ´ . ¯ . ınh, th` tông cua tât ca nh˜ ng sô nhân duoc (moi trang th´i . . , a , , , a e . . a ¯` b`n) s˜ không nho hon n. Nhung môt trang th´i dâu tiên cua sap ´ ˘
1.3. B`i tâp a . 11 ,, ´ , , ˜ , ,, ´ a ´ ` ¯´ ´ xêp b`n cho tuong ung voi 0 (không ai ngôi dung chô ). Nêu gia su ,, ´ , , , , . a ˘ a o . . ´ ´ trong n − 1 trang th´i mat b`n c`n lai tuong ung voi sô nho hon 2 , , , , , , ´ a o ´ ˘ ´ . ¯ , ., e (tuc l` chı c´ sô 1 hoac 0), th` tông cua n sô nhân duoc s˜ nho hon . ı , ,, , ¯ ` ¯´ n, diêu do không thê duoc. Suy ra t` n − 1 trang th´i mat b`n c`n ¯ . u . a ˘ a o . , ´t môt trang th´i m` hai ngu`,i s˜ dôi diên voi ch´ tên ´ . ´ , lai c´ ´ nhâ ., o ıt . . a a o e¯ ınh cua m` ınh. J ` . 1.3. Bai tâp 1.11. Trong sân cung diên nh` vua hôi hop 2n(n ≥ 2) ông quan, ¯. a . . , ˜ ông quan da quen biêt không ´ hon n ông c´ mat tai do. Chung ´ ´, môi ¯˜ ıt o ˘ . ¯´ . ,, ´ , ` ˘ o a o o ´ ¯ , ., ˜ a ,, minh rang ngu` i xêp b`n tr`n c´ thê xêp duoc môi b`n 4 ngu` i sao o , , , , ˜ ngu`,i dung gi˜,a hai ngu`,i quen cua m` cho môi o ¯´ u o ınh. , ˜ ` 1.12. Môt khu r` ng thông c´ dang h` vuông môi chiêu 1km. . u o . ınh , ´ o ¯ ,`, Trong r` ng c´ 4500 cây thông, cây to nhât c´ duong k´ 0,5m. u o ınh , , , Chu ` u o ıt ´ ¯ ´ ´ ng minh rang trong khu r` ng c´ ´ nhât 60 manh dât, diên t´ ˘ . ıch , ˜ manh 200m2 , không c´ môt cây thông n`o. môi o . a ´ o . ´, 1.13. Trong môt gi´ s´ch c´ 25 ng˘n. Ta thây c´ môt ng˘n chua . a a o a a ´ o a , ´ ´ a ıt , ´, ` 10 cuôn, c`n c´c ng˘n kh´c chua sô s´ch ´ hon. Chung minh rang a a ˘ , , , , , o ıt ´ a a ´ u ´ a c´ ´ nhât ba ng˘n s´ch chua c` ng sô s´ch nhu nhau (kê ca nh˜ ng u ng˘n không c´ s´ch). a o a , ,, , , ´ ¯ . ¯´ 1.14. Tai môt th`nh phô biên xe ôtô duoc danh sô bang tô hop . . a ´ `˘ . , , `i dên d˜y sô. Chung minh rang trên môt doan du`,ng cu ´ a ´ ` , , ch˜ c´i rô ¯ u a ´ ˘ . ¯ . ¯ o ´ ´ , ´ , c´ 11 chiêc ôtô di qua th` bao gi` c˜ ng c´ hai chiêc ôtô c´ c` ng ch˜ o ¯ ı o u o o u u ´ . u sô tân c` ng. ,, , ´ ` ´ ¯ , ., . , 1.15. Môt chiêc hô lon duoc boc boi 4 tram chuyên tiêp s´ng . . ´ o , ,`, , thông tin. Gi˜ a hai tram nguoi ta xây dung c´c trung tâm ph´t s´ng u . a a o ,`, , , . ,`, ,, . o ¯ o ´ ´ a¯ v` nhân s´ng, duong s´ng bao phu lon nhât l` duong tr`n c´ tâm o a o o
,, 12 Chuong 1. Nguyên l´ Ðirichlê v` v´ du y a ı . ´, ` , ´ ´ a¯ . ˘ trung tâm v` di qua hai tram. Chung minh rang voi bôn trung tâm ,, , , , ,, , a ¯ . u u ˘. . ı a . ˘ ` e¯ . o c´c doan gi˜ a cua t` ng cap tram th` to`n bô mat hô s˜ duoc phu . s´ng thông tin. o
, , CHUONG 2 ´ SÔ HOC . ´ ´ ., 2.1. Phep chia sô tu nhiên ´ , Trong c´c ph´p t´ trên sô nguyên: công, tr` , nhân, chia, th` a e ınh . u ı , ph´p chia l` râ ¯˘ e a ´t dac biêt. Ph´p chia c´ h`ng loat t´ chât m` tât ca . . e o a . ınh ´ a ´ , c´c ph´p t´ c`n lai không c´. V´ du c´c ph´p to´n dêu thuc hiên a e ınh o . o ı . a e a ¯` . . ´, ´ ,, , ´ 0 th` không duoc. Ph´p ,, voi sô 0 duoc, nhung riêng ph´p chia cho sô ¯ . e ı ¯ . e , , , ¯˘ . ´ ´ a chia không chı dac biêt voi ph´p chia cho 0. Voi c´c ph´p t´ công, . e e ınh . , , ´ nguyên cho ta sô nguyên, nhung voi ph´p chia th` ´ , tr` , nhân trên sô u ´ e ı , t´ châ ¯´ ınh ´t do không c`n dung v` không phai l´ c n`o ta c˜ ng nhân o ¯´ ı u a u . ,, ´ , ˜, , duoc sô nguyên sau ph´p chia. Nh` nhung di biêt cua ph´p chia m` ¯ . e o . . e a , , trong to´n hoc xây dung han môt l´ thuyê a . . ˘ . y ´t vê ph´p chia nh˜,ng sô ` e u ´ , ,, ´ nguyên. Nh˜ ng v´ du v` b`i tâp chuong n`y c´ liên quan mât thiêt u ı . a a . a o . , ´ . ¯. gi˜ a ph´p chia v` nguyên l´ Ðirichlê, nên ch´ ng ta nhac lai dinh u e a y u ˘ ngh˜ ph´p chia: ıa e , ´ ´, ` a a ˜ Cho a v` b l` nhung sô nguyên, voi b > 0. Ch´ ng ta n´i rang a u o ˘ ´ ` . . ´ chia hêt cho b, k´ hiêu l` b| a, khi tôn tai môt sô nguyên q sao cho y . a , , ¯˘ ´ ¯´ dang thuc sau dung a = bq. ,, , ,, , u o , . ´ a . Ch´ ng ta thu` ng goi sô a l` bôi cua b, hoac b l` uoc cua a. Sô q ˘. a ´ , ´ ,, ´ goi l` thuong sô cua ph´p chia a cho b. Trong ph´t biêu dinh ngh˜ . a e a ¯. ıa , ´ ` . . ´ trên, nêu không tôn tai môt sô q n`o ca, th` ch´ ng ta n´i ra a ı u o ˘ `ng a
,, ´ . 14 Chuong 2. Sô hoc ´ không chia hêt cho b v` k´ hiêu l` b | a. a y . a , , ,, T` dinh ngh˜ ch´ ng ta d˜ d`ng chung minh duoc c´c t´ chât u ¯. ıa u ê a ´ ¯ . a ınh ´ sau , , ´ . ´ 1) Voi moi sô nguyên a > 0 ch´ ng ta c´ a| a, Ph´p chia hêt c´ u o e ´ o t´ phan xa. ınh . 2) Nê a ı e ´ o ı ´ ` ´u b| a v` a|c th` b|c- ph´p chia hêt c´ t´ nh bac câu. ˘ ´ 3) Nêu b| a v` b|c, th` b|( ac). a ı ´ , ´ u a ´ 4) Nêu a, b, m, n l` nh˜ ng sô nguyên v` nêu c| a v` c|b, th` a a ı c|(ma + nb). , Ðinh l´ sau dây gi˜ vai tr` quan trong cho ph´p chia môt sô . y ¯ u o . e . ´ . ´ nguyên cho môt sô nguyên. ´ , ´ ´ y ` . Voi hai sô nguyên bât k` a v` b sao cho b > 0, tôn tai duy a , , ´ ˜ ´ nhât nhung sô nguyên q v` r thoa m˜n a = bq + r v` 0 ≤ r < b. a a a , , ´ , ´ ` ınh ´ ´ C`n rât nhiêu t´ chât kh´c cua sô nguyên c˜ ng nhu sô thuc o a u . , ,´, , ¯ a a u a ınh ´ nhung ch´ ng ta không di theo huong n`y, m` chı d` ng c´c t´ chât u , , , ´ . a cua sô hoc v` Nguyên l´ Ðirichlê dê giai c´c b`i to´n. y ¯ a a a 2.2. V´du ı . , , ` ´ ., a . ´ . 2.1. Cho k l` môt sô tu nhiên, A l` tâp hop gôm k + 1 sô tu nhiên. a . . , ´, ` ´ . ` , Chung minh rang c´ ´ nhât môt hiêu hai phân tu trong A chia hêt ˘ o ıt . ´ cho k. , , , `, . a a ` , Loi giai. Goi a1 , a2 , . . . , ak+1 l` c´c phân tu cua A, c`n b1 , b2 , . . . , bk+1 o , ´ , , ´ l` nh˜ ng sô du cua ph´p chia c´c sô trên cho k. Khi do a1 = a u e a ¯´ , ´ a ´ kc1 + b1 , a2 = kc2 + b2 , . . . , ak+1 = kck+1 + bk+1 ,voi c´c sô nguyên c1 , c2 , . . . , ck+1 sao cho 0 ≤ b1 ≤ k − 1, 0 ≤ b2 ≤ k − 1, . . . , 0 ≤ , ` , ´ y bk+1 ≤ k − 1. Môt phân tu bât k` as thuôc A cho tuong ung voi sô . . ,, ´ , , ´ ´
2.2. V´ u ıd . 15 , , , , , , , . a ´ ˜ ` , du bs cua n´.Goi tâp hop c´c sô du l` B. Nhu vây, môi phân tu cua A o . . a . ,, ,, ´ , , , , ¯ . ¯˘ ´, ` , , ` duoc dat tuong ung voi môt phân tu cua tâp hop B, gôm tât ca c´c . . . . ´ a , , , sô´ nguyên t`, 0 dên k − 1. Nhung sô luong phân tu cua A theo gia u ¯ ´ , ´ , ., ` , ´ a ,, o o ´ . thiêt l` k + 1, c`n B c´ sô luong k. Theo nguyên l´ Ðirichlê suy ra y , , tô . ` , a o u ´ , `n tai hai phân tu kh´c nhau cua A c´ c` ng sô du. Ðiêu do ngh˜ l`, ` ¯´ ıa a , , `n tai hai chı sô kh´c nhau s v` t voi as = kcs + bs v` at = kct + bs tô . ´ a a ´ a `, di cho nhau ta duoc at − as = k (ct − cs ). sau khi tru ¯ ,, ¯ . J . . . , ´ y ` ´ ., ˜ ´ 2.2. Cho A môt tâp hop bât k` gôm 101 sô tu nhiên, môi sô không o , , ´, ` ˘ o ıt ´ ´ a . ´ l´n hon 200. Chung minh rang trong A c´ ´ nhât hai sô m` môt sô ´ ´ n`y chia hêt cho sô kia. a , `, ˜ ´ , , , ,, Loi giai. Môi sô a cua A c´ thê biêu di˜ duoi dang a = 2k b voi k l` o ên ´ . ´, a , , ˜ ´ ´ a . ´ sô nguyên không âm, c`n b l` môt sô le. Voi môi sô a thuôc A cho o ´ . ,, ´ , , ´ , , ,, ˜ o trên. Bang c´ch n`y, môi ˜ ´ tuong ung voi sô b trong su biêu diên . ` ˘ a a ,, , ,, ,, ´ , , ,, , , ` ¯ . ¯˘ ´ phân tu a cua A duoc dat tuong ung voi môt phân tu cua tâp hop B . . ` . . , , , , , ` a ´ u a . , gôm c´c sô le gi˜ a 1 v` 200. Nhung tâp hop B chı c´ 100 phân tu v` . , o ` , ı , , , ´ ` ,, , ´ ` , ´, vây sô phân tu cua A lon hon sô phân tu cua B. Ta c´ thê ap dung . o ´ . ,, y ` . ` nguyên l´ Ðirichlê, suy ra tôn tai hai phân tu kh´c nhau a1 v` a2 a a ,, ´ , , , , . ´ u . ´ thuôc A m` ch´ ng tuong ung voi c` ng môt sô cua tâp hop B. Ngh˜ a u . . ıa l`, a1 = 2 a 2 a ´ 1 2 ı ´ 2 k1 b, a = 2k2 b v` nêu k < k , th` sô a chia hêt cho a . ´ 1 J , ´ y ` ´ ., a ˜ ´ 2.3. Cho M l` tâp hop bât k` gôm 75 sô tu nhiên m` môi sô không a . . . , , , , ˜ ´ , , , ´ ` l´n hon 100. Chung minh rang v´i môi sô tu nhiên l nho hon hoac o ˘ o . ˘ . ,, , ` ` . ` bang 49 tôn tai hai phân tu cua M c´ hiêu l` l. ˘ o . a , , , `, . a ` , Loi giai. Goi c´c phân tu cua M l` x1 , x2 , . . . , x75 . K´ hiêu A l` tâp a y . a . , , , , ˜ ´ ,, . a ´ . u ¯´ hop c´c sô tu nhiên t` 1 dên 150. Voi môi sô 1, 2, 3 . . . , 75 cho tuong ´ , , ´ a ´ ` , ., ´ o a ´ ung voi c´c sô x1 , x2 , . . . , x75 , c`n c´c sô 76, 77, 78, . . . 150 lân luot ´, ´, ung voi x1 + l, x2 + l, . . . , x75 + l. V` xm ≤ 100(m = 1, 2, . . . , 75) v` ı a
,, ´ . 16 Chuong 2. Sô hoc , , ˜ ` , l ≤ 49 th` xm + l < 150. Suy ra môi phân tu cua A tuong ung voi ı ,, ´ , ´, ,, , , . , ` ` ´ ., , u ¯´ môt phân tu cua B gôm nh˜ ng sô tu nhiên t` 1 dên 149. V` sô phân u ı ´ ` ,, ´, , ´ ` ,, , ` . tu cua A lon hon sô phân tu cua B, theo nguyên l´ Ðirichlê tôn tai y ,, , ,, ´ , , ` hai phân tu kh´c nhau cua A, m` ch´ ng tuong ung voi c` ng môt a a u ´ u . ,, , , phâ , `n tu cua B. Nhung voi c´c gi´ tri kh´c nhau cua m t`, 1 dên 75 , ´ a a . a u ¯ ´ ,, ,, ´ , , , duoc cho tuong ung vo a ¯ . a . a ¯ ´ ´i c´c gi´ tri kh´c nhau cua x1 dên x75 trong ,, , , ,, , ,, ´ , , B. Tuong tu c´c gi´ tri cua m o khoang 76 dê . a a . ¯ ´n 150 tuong ung voi ´ , , c´c gi´ tri kh´c nhau trong khoang c`n lai. T` do suy ra tôn tai xm a a . a o . u ¯´ ` . v` xn m` xm = xn + l, ngh˜ l` xm − xn = l. a a ıa a J , ´ ., , ` 2.4. Cho k ≥ 1 v` n ≥ 1 l` nhung sô tu nhiên v` A l` tâp hop gôm a a ˜ a a . . , , , (k − 1)n + 1 sô nguyên duo,ng, môi sô n`y dêu nho hon hoac bang kn. ´ ˜ ´ a ¯` ˘ ˘ ` ,, , , . , ´, ` ´ o . ` ˜ Chung minh rang ´ nhât c´ môt phân tu cua A c´ thê biêu diên nhu ˘ ıt o , , , ,, ` tông cua k phân tu trong A. , , , `, ´, a a a ¯´ Loi giai. Voi k = 1 b`i to´n hiên nhiên l` dung, ch´ ng ta gia thiêt u ´ , ˜ thây rang m ≤ n v` k ≥ 2. K´ hiêu m l` sô nho nhât thuôc A. Dê ´ ˘ y . a ´ ´ . ` a ` . ¯´ ´ ´, , , tôn tai dung n − m sô thuôc A m` ch´ ng lon hon m nhung không . a u ,, vuot qu´ kn. . a , , ´ a a u ım ´ a Ðê chung minh b`i to´n ch´ ng ta t` hai sô x v` y thuôc A sao . , ˜ môt sô n`o do thuôc A cho x = y + (k − 1)m; ngh˜ l` biêu diên .ıa a ´ a ¯´ . , , th`nh tông k sô . a . ¯´ o ´ . ` ´ hang thuôc A trong do c´ k − 1 sô hang bang m. Chı ˘ `n t` sô x thuôc A m` x > (k − 1)m v` x − (k − 1)m thuôc A. câ ım ´ . a a . , Thât vây, trong khoang ∆ = ((k − 1)m, kn] c´ kn − (k − 1)m = . . o ´ k (n − m) + m sô nguyên. V` k ≥ 2, nên (k − 1)m ≥ m, theo nhân ı . x´t ban dâu suy ra c´ nhiêu nhât n − m sô trong ∆ không thuôc A. e ¯ ` o ` ´ ´ . ` a , ´ ıt ´ Ðiêu n`y ngh˜ l` A chua ´ nhât s = k(n − m) + m − (n − m) = ıa a ´ , (k − 1)(n − m) + m sô. Nhung s ≥ n, v` (k − 2)(n − m) ≥ 0. Goi ı . ´ , a1 , a2 , . . . , as thuôc A, voi (k − 1)m < ai ≤ kn, i = 1, 2, . . . , s. Khi do . ¯´
2.2. V´ u ıd . 17 , , nh˜ ng hiêu a1 − (k − 1)m, a2 − (k − 1)m, . . . , as − (k − 1)m l` nh˜ ng u . a u , ´ ´ . ´ a ¯´ sô nguyên kh´c nhau trong khoang [1, kn]. Nêu môt sô n`o do trong a ch´ ng không thuôc A, th` theo nguyên l´ Ðirichlê ch´ ng ta nhân u . ı y u . ,, , , duoc s ≤ n − 1, v` ngo`i A c´ dung n − 1 sô ¯ . ı a o ¯´ ´ trong khoang n`y. Nhu a , , , , a ´ ´ ¯˘ ´ ¯˜ ´ ` . vây tr´i voi bât dang thuc da chung minh s ≥ n. Suy ra tôn tai môt . . hiêu ai − (k − 1)m thuôc A. . . J , , ´, ` `, ´ ,, 2.5. Chung minh rang tu n + 1 sô duong kh´c nhau nho hon 2n, c´ ˘ a o , ,, , , ´ ´ ` ´ ´ thê chon duoc ba sô sao cho tông hai sô trong ch´ng bang sô thu ba. . ¯ . u ˘ , , `, Loi giai. K´ hiêu 0 < a1 < a2 < . . . < an+1 l` nh˜ ng sô da cho. y . a u ´ ¯˜ u e a . , ´ , , a a ´ Ch´ ng ta x´t c´c hiêu sô a2 − a1 , a3 − a1 , . . . , an+1 − a1 v` c´c sô ı ´ a ´ a ¯` a ´ a2 , a3 . . . , an+1 . V` tât ca c´c sô n`y dêu nho hon 2n nên c´c sô trên , , , ,, ` chı nam trong khoang 1, 2, . . . , 2n − 1. Nhu vây ch´ ng ta s˜ t` duoc ˘ . u e ım ¯ . ,, , ,, , . ´ o ´ ´ ` ˘ . ´ o ´ môt sô o nh´m thu nhât bang môt sô o nh´m thu hai: ak − a1 = al , suy ra ak = a1 + al . J ´, ` , . ´ ´ y ` . . ´ o . 2.6. Chung minh rang v´i môt sô bât k` n tôn tai môt sô c´ dang ˘ o ´ 111 . . . 000 m` chia hêt cho n. a ˜, ´ n chu sô , , , `, u e u ´ Loi giai. Ch´ ng ta x´t nh˜ ng sô 1, 11, 111, . . . , 111 . . . 111 v` nh˜ ng a u ˜, ´ n chu sô ´ , ´ ´ ¯˜ ` ` sô du khi chia d˜y sô trên cho n. V` d˜y sô da cho gôm n phân a ı a ,, , , ,, u ´ tu, nên nh˜ ng sô du duong kh´c nhau khi chia ch´ ng cho n c´ sô a u o ´ ,, , , . o ´ o . ´ a luong n − 1. C´ thê gia thiêt không c´ môt sô n`o trong d˜y trên a ,, ,, , chia hê ´t cho n v` nêu nguoc lai th` b`i to´n da duoc giai. Khi do ı ´ . . ı a a ¯˜ ¯ . ¯´ s˜ c´ hai sô e o ´ trong ch´ ng, v´ du 111 . . . 111 v` 111 . . . 111, l > k, u ı . a ˜ , ´ ˜, ´ k chu sô l chu sô , a u e u . ´ m` khi chia ch´ ng cho n s˜ cho c` ng môt sô du. Do do l − k = ¯´
,, ´ . 18 Chuong 2. Sô hoc 111 . . . 000 ´ s˜ chia hêt cho n. e J ˜, ´ ˜, ´ (l-k chu sô 1, k chu sô 0) a ´ ´ o, , ´, ` ` . 2.7. Cho p l` sô nguyên tô l´n hon 5. Chung minh rang tôn tai môt ˘ . ´ c´ dang 111 . . . 111 m` chia hêt cho p. sô o . a ´ , `, e a ´ ´ Loi giai. Ta x´t d˜y sô 1, 11, 111, . . . , 111 . . . 1 . Nêu trong d˜y trên a ˜, ´ (p chu sô ) ,, ´ , , ˜ ´ ´ ´ o ´ a ´ không c´ sô n`o chia hêt cho p, th` ta cho tuong ung môi sô voi sô ı , , , , , . ,. a ´ ` du cua ph´p chia. Tâp hop c´c sô du chı c´ 1, 2, . . . , p − 1 gôm p − 1 e o ,, , ` phân tu (v` 0 không thê c´ trong tâp n`y). Nhung v` ch´ ng ta c´ p ı o . a ı u o ,, ´ o dang trên, nên theo nguyên l´ Ðirichlê tôn tai hai sô c´ c` ng sô . , y ` . ´ o u , ,, , ´ du. Gia su c´c sô do l` 111 . . . 1 v` 111 . . . 1 voi m > n. Khi sô a ´ ¯´ a a ´ ˜, ´ (m chu sô ) ˜, ´ ( n chu sô ) do 1 ≤ n < m ≤ p. Vây ¯´ . 111 . . . 1 − 111 . . . 1 = 111 . . . 000 ˜ , ´ ˜ , ´ ˜, ´ ˜, ´ (m chu sô ) (n chu sô ) (m-n chu sô 1, n chu sô 0) = 111 . . . 1 .10n ˜, ´ (m-n chu sô ) ıch a ´ T´ n`y chia hêt cho p v` ( p, 10) = 1, suy ra ı 111 . . . 1 ˜, ´ (m-n chu sô 1) ` ,, ´ chia hêt cho p v` n´ c˜ ng nam trong d˜y o trên. M` 1 ≤ m − n ≤ p a o u ˘ a a ´, , ˜ voi gia thiêt không c´ sô n`o trong d˜y chia hêt cho p. ´ ´ a ´ mâu thuân o a J ` ´ o, ` ´, , ´ 2.8. (Ðê thi Olympic to´n thê gi´i lân thu 14) Cho M l` tâp hop bât a a . . y ` ´ ., ˜ ´ , , ´, k` gôm 10 sô tu nhiên, môi sô không l´n hon 100. Chung minh rang o ` ˘ , , , , ,, ` . . . a ` tôn tai hai tâp hop con cua M m` tông cua c´c phân tu trong ch´ng a u ` bang nhau. ˘
2.2. V´ u ıd . 19 , , , , `, ´ ´ ` . Loi giai. C´ thê chung minh nêu tôn tai hai tâp thoa m˜n kêt luân o . a ´ . , , ,, cua b`i to´n, th` ta c´ thê chon duoc hai tâp con c´ c` ng t´ chât a a ı o . ¯ . . o u ınh ´ , , ´ ây nhung không giao nhau. Thât vây, Cho X, Y l` hai tâp con cua M . . a . , ,, c´ tông c´c phâ o a ` `n tu bang nhau. Ch´ ng ta k´ hiêu X1 gôm c´c phân ˘ u y . ` a ` ,, , ,, , , tu cua X m` không thuôc Y. Tuong tu nhu vây Y1 gôm c´c phân a . . . ` a ` ,, , , tu cua Y m` không thuôc X. R˜ r`ng X1 v` Y1 c´ tông c´c phân a . o a a o a ` ,, , , ` ˘ tu bang nhau m` không giao nhau. Goi A l` tâp hop moi tâp hop a . a . . . . . , , , ˜ ´ , ., con không rông cua M. Sô luong phân tu cua A l` 210 − 1 = 1023. ` , a , ,, , , , Ch´ ng ta x´t tông S c´c phâ u e a `n tu cua môt tâp hop con nhu vây, r˜ . . . . o , `n tai r`ng S ≤ 91 + 92 + · · · + 100 < 10.100 = 1000. Nhu vây tô . a . , , ´ , không qu´ 1000 tông kh´c nhau. K´ hiêu B l` tâp hop tât ca c´c a a y . a . . a , , ,, , , ,, , , tông nhu vây. Do do sô . . ¯´ ` , ´ luong phân tu cua B nho hon 1000 v` nho a , ´ ,, , , , , ` , ˘ ,, ´ hon sô luong phân tu cua A. Ðat tuong ung môi phân tu cua tâp hop . . , ˜ ` , . . , , , , , ´, ` , A voi tông c´c phân tu cua n´. Ta thây rang c´ thê ap dung nguyên a o ´ ` ˘ o ´ . ,, , l´ Ðirichlê o dây. Suy ra tô . ıt y ¯ `n tai ´ nhât hai tâp hop con kh´c nhau c´ ´ . . a o , c` ng môt tông c´c phân tu. u . a ` , , J , ` ´ 2.9. (Ðê thi hoc sinh gioi to´n Câp II to`n quôc 1983) Chung minh . a a ´ ´, ` , rang trong c´c sô tu nhiên thê n`o c˜ng c´ sô k sao cho 1983k − 1 chia ˘ a ´ . ´ a u o ´ hêt cho 105 . ´ , , , , `, ´ a . u ¯´ Loi giai. Cho k lây gi´ tri t` 1 dên 105 + 1 rôi thay v`o biêu thuc ` a ´ ,, ´ 1983k − 1 s˜ nhân duoc 105 + 1 gi´ tri kh´c nhau. Chia 105 + 1 sô e . ¯ . a . a , ,, ,, , v` a nhân o trên cho 10 e ¯ . u . ` ´ a 5 , s˜ duoc nhiêu nhât l` 105 sô du. Do do ´ ¯´ , , theo nguyên l´ Ðirichlê phai c´ ´ nhât hai sô cho c` ng môt sô du. y o ıt ´ ´ u . ´ , ,, ¯´ a ´ Gia su do l` sô 1983m − 1 v` 1983n − 1(m > n). Thê th` (1983m − a ´ ı 1) − (1983 ´ n − 1) chia hêt cho 105 m` (1983m − 1) − (1983n − 1) = a m − 1983n ) = 1983n (1983m−n − 1). Nhung 1983 v` 105 nguyên , (1983 a , m−n − 1) chia hêt cho 105 . Sô ´ u tô c` ng nhau, do vây phai c´ (1983 . o ´ ´ , a ¯ ` k = m − n thoa m˜n diêu kiên dâu b`i. . ¯` a J
,, ´ . 20 Chuong 2. Sô hoc ´, ` ˘ ` . ˜, ´ 2.10. Chung minh rang tôn tai nhung sô nguyên a, b v` c, không a , ` , dô ¯ o ˘ a a . . ¯ ´ ˜ ´ `ng th`i bang 0 v` gi´ tri tuyêt dôi cua môi sô không qu´ 1000000, a , √ √ −11 . thoa m˜n | a + b 2 + c 3| < 10 a , , , √ √ `, ˘ . a . . ´ ., Loi giai. Ðat S l` tâp hop cua 1018 sô thuc r + s 2 + t 3 voi moi ´, . 6 − 1} v` dat d = (1 + √ √ 6. r, s, t thuôc {0, 1, 2, . . . , 10 . a ¯˘. 2 + 3d)10 , ˜ x trong S dêu nam trong khoang 0 ≤ x < d. Chia ¯´ Khi do môi ¯ ` ` ˘ ˜ ¯ . , doan n`y th`nh 10 ¯ . a a ` ` 18 − 1 phân bang nhau, môi doan nho c´ dô d`i ˘ o ¯. a d e = ` . ´ . Theo nguyên l´ Ðirichlê tôn tai hai sô trong 1018 sô y ´ , 1018 − 1 , , ` ˘ ´ a y . a cua S nam trong c` ng môt doan nho. Hiêu cua hai sô n`y k´ hiêu l` u . ¯ . . √ √ J 107 a + b 2 + c 3 do ch´ l` c´c sô a, b, c v` e < 18 = 10−11 . ¯´ ınh a a ´ ı 10 ` . 2.3. Bai tâp a . . , ´ y ` ´ ., ˜ ´ 2.11. Cho A l` tâp hop bât k` gôm 201 sô tu nhiên, môi sô không ,, , , , , ´ ` ˘ ´ ıt ´ ´ a ´ vuot qu´ 300. Chung minh rang A chua ´ nhât hai sô, m` ty sô cua . a , ch´ ng l` l˜ y th` a bâc ba. u a u u . , , a ´ . ´ y o ´ 2.12. Cho k l` sô tu nhiên bât k`, c`n a v` b l` nh˜ ng sô nguyên a a u ´, ` ´ , sao cho a ≤ b v` b − a < 2k − 2. Chung minh rang nêu M l` tâp hop a ˘ a . . , , ´ ., ` ˘ a a ´ . , k sô tu nhiên nam trong khoang [ a, b], v` l l` sô tu nhiên thoa m˜n a , , 1 ≤ l ≤ 2k + a − b − 2, th` c´ ´ nhâ ı o ıt . . u ` , ´t môt hiêu nh˜,ng phân tu cua ´, M tr` ng voi l. u , , ,, ˜ ´ a ˜ ` , 2.13. Cho dây sô a1 , a2 , a3 , . . . , a41 , m` môi phân tu chı duoc tao ¯ . . ,, , ,, ,, ´ a ´ ¯´ o ıt ´ ´ ¯ . . a ´ boi sô 1 v`, sô 2, trong do c´ ´ nhât 21 sô chı duoc tao boi c´c sô 1. , ,, , , ´ Chung minh ra `ng tôn tai môt sô phân tu liên tiêp cua d˜y c´ tông ˘ ` . . ´ ` ´ a o ` ¯´ ˘ bang dung 20. ´, ` ` . ´ ., ´ ˘ 2.14. Chung minh rang tôn tai môt sô tu nhiên n, sao cho sô .