CÁC BÀI TẬP ÁP DỤNG NGUYÊN LÝ DIRICHLET

I.                   NGUYÊN LÝ DIRICHLET
Nguyên lí Dirichlet:

Không thể nhốt $7$ chú thỏ vào $3$ cái lồng sao cho mỗi lồng không quá $2$ chú thỏ.

Nguyên lí Dirichlet tổng quát:
Nếu đặt $n$ viên bi vào $k$ cái hộp ($n,k$ nguyên dương), thì sẽ tồn tại một hộp chứa ít nhất $ \left\lceil \frac{n}{k} \right\rceil$ viên bi, với
$ \left\lceil x \right\rceil$ là số nguyên bé nhất không nhỏ hơn $x$.

Nguyên lí Dirichlet (còn gọi là nguyên lí chuồng bồ câu) tuy có phát biểu đơn giản nhưng lại được vận dụng rất nhiều trong thực tế. Nhờ nguyên lí này mà trong nhiều trường hợp, người ta dễ dàng chứng minh được sự tồn tại mà không đưa ra được phương pháp tìm kiếm cụ thể.

 

II.                BÀI TẬP CĂN BẢN

Bài 1:

Một trường học có $1000$ học sinh gồm $23$ lớp. Chứng minh rằng phải có ít nhất một lớp có từ $44$ học sinh trở lên

Giải:
Giả sử $23$ lớp mỗi lớp có không quá $43$ học sinh.
Khi đó số học sinh là:
$43.23 = 989$ học sinh (ít hơn $1000 – 989 = 11$ học sinh)
Theo nguyên lí Dirichlet phải có ít nhất một lớp có từ $44$ học sinh trở lên

Bài 2:

Một lớp có $50$ học sinh. Chứng minh rằng có ít nhất $5$ học sinh có tháng sinh giống nhau

Giải:
Giả sử có không quá $4$ học sinh có tháng sinh giống nhau
Một năm có $12$ tháng, khi đó số học sinh của lớp có không quá: $12 . 4 = 48$ (học sinh)
Theo nguyên lí Dirichlet phải có ít nhất $5$ học sinh có tháng sinh giống nhau

 

Bài 3:

Có năm loại học bổng khác nhau. Hỏi rằng phải có ít nhất bao nhiêu sinh viên để chắc chắn rằng có ít ra là $6$ người cùng nhận học bổng như nhau.

Giải:

Gọi $N$ là số sinh viên, khi đó:
$ \left\lceil \frac{N}{5} \right\rceil =6 \Rightarrow 5 < \frac{N}{5}≤ 6$ hay  $25 < N ≤ 30$.
Vậy số N bé nhất thỏa mãn là $26$.
 

Bài 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$. Chứng minh rằng í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)

Giải:
Có $43$ học sinh phân thành $8$ loại điểm (từ $2$ đến $9$)
Giả sử 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ó:
$5 . 8 = 40$ học sinh, ít hơn $3$ học sinh so với $43$.
Theo nguyên lý Dirichlet tồn tại $6$ học sinh có điểm kiểm tra bằng nhau.

 

Bài 5:

Một lớp học có $50$ học sinh, có duy nhất một học sinh thiếu nhiều bài tập nhất là thiếu $3$ bài tập. Chứng minh rằng tồn tại $17$ học sinh thiếu $1$ số bài tập như nhau (trường hợp không thiếu bài tập coi như thiếu $0$ bài)

Giải:
Giả sử mỗi loại bài tập có $16$ học sinh.
Số học sinh không quá $16 × 3 = 48$ (thiếu $2$ học sinh).
Theo nguyên lí Dirichlet có ít nhất $17$ học sinh thiếu một số bài tập như nhau

III.             BÀI TẬP NÂNG CAO

Bài 1:

Trong một phòng họp có $n$ người, bao giờ cũng tìm được $2$ người có số người quen trong số những người dự họp là như nhau.

Giải:

Số người quen của mỗi người trong phòng họp nhận các giá trị từ $0$ đến $n – 1$. Rõ ràng trong phòng không thể đồng thời có người có số người quen là $0$ (tức là không quen ai) và có người có số người quen là $n – 1$ (tức là quen tất cả). Vì vậy theo số lượng người quen, ta chỉ có thể phân n người ra thành $n – 1$ nhóm.

Vậy theo nguyên lí Dirichlet tồn tai một nhóm có ít nhất $2$ người, tức là luôn tìm được ít nhất $2$ người có số người quen là như nhau.

 

Bài 2:

Trong một lưới ô vuông kích thước $5.5$, người ta điền ngẫu nhiên vào các ô một trong các giá trị $-1, 0$ hoặc $1$, sau đó tính tổng tất cả các ô theo hàng ; theo cột và theo hai đường chéo. Chứng minh rằng tồn tại ít nhất hai tổng có giá trị bằng nhau.

Giải:

Gọi các tổng lần lượt là $S_1, S_2,..S_{12}$.
Có tất cả $12$ tổng. Ta nhận thấy rằng các tổng này chỉ có thể nhận các giá trị là $\{ -5, -4…0,…4, 5\}$. Có tất cả $11$ giá trị khác nhau. Từ đó, theo nguyên lý Dirichlet ta suy ra điều cần chứng minh. 

 

Bài 3:

Giả sử trong một nhóm $6$ người mỗi cặp hai hoặc là bạn hoặc là thù. Chứng tỏ rằng trong nhóm có ba người là bạn lẫn nhau hoặc có ba người là kẻ thù lẫn nhau.

Giải:

Gọi $A$ là một trong $6$ người. Trong số $5$ người của nhóm hoặc là có ít nhất ba người là bạn của $A$ hoặc có ít nhất ba người là kẻ thù của $A$, điều này suy ra từ nguyên lí Dirichlet, vì những người khác chỉ có thể là bạn hoặc thù của $A$.
Trong trường hợp đầu ta gọi $B, C, D$ là bạn của $A$. nếu trong ba người này có hai người là bạn thì họ cùng với $A$ lập thành một bộ ba người bạn lẫn nhau, ngược lại, tức là nếu trong ba người $B, C, D$ không có ai là bạn ai cả thì chứng tỏ họ là bộ ba người thù lẫn nhau.
Tương tự có thể chứng minh trong trường hợp có ít nhất ba người là kẻ thù của $A$. (ĐPCM)

 

Bài 4:

Có $5$ đấu thủ thi đấu cờ, mỗi người đấu một trận với mỗi đấu thủ khác. Chứng minh rằng trong suốt thời gian thi đấu, luôn tồn tại hai đấu thủ có số trận đã đấu bằng nhau.

Giải:

Ta có số trận đã đấu của mỗi người có thể là $0, 1, 2, 3,4$. Nhưng vì không thể có cùng lúc một người đã đấu $4$ trận và một người chưa đấu trận nào, nên có tối đa $4$ loại số trận đã đấu.

Vận dụng nguyên lý Dirichlet ta có ít nhất có $2$ người có cùng số trận đã đấu.

 

IV.             BÀI TẬP TỰ GIẢI

Bài 1:

Chia $50$ kẹo cho $10$ em bé (em nào cũng được chia kẹo). Chứng minh rằng dù chia cách nào đi nữa cũng tồn tại hai em có số kẹo bằng nhau.

Bài 2:

Bốn lớp $11A, 11B, 11C, 11D$ có tất cả $44$ học sinh giỏi, trong đó số học sinh giỏi của lớp $11D$ không quá $10$ người. Chứng minh rằng ít nhất một trong $3$ lớp $11A, 11B, 11C$ có số học sinh giỏi từ $12$ em trở lên.

Bài 3:

Có $33$ con chim đậu trên một sân vuông hình vuông cạnh $4m$.

Chứng minh rằng có ít nhất $3$ con đậu trong một đường tròn có bán kính $1m$

Bài 4:

Một cuộc họp gồm $12$ người tham dự để bàn về $3$ vấn đề. Có $8$ người phát biểu về vấn đề $I$, $5$ người phát biểu về vấn đề $II$ và $7$ người phát biểu về vấn đề $III$. Ngoài ra, có đúng $1$ người không phát biểu vấn đề nào.

Hỏi nhiều nhất là có bao nhiêu người phát biểu cả $3$ vấn đề.

Bài 5:

Có $17$ nhà bác học viết thư cho nhau trao đổi $3$ vấn đề. Chứng minh rằng luôn tìm được $3$ người cùng trao đổi một vấn đề.
 

Thẻ

× 156
× 25

Lượt xem

10285
Chat chit và chém gió
  • Rainy: chúc mừng sn gió 7/23/2014 11:52:23 PM
  • Min: gió nhá 7/23/2014 11:52:28 PM
  • Rainy: muôn 7/23/2014 11:52:28 PM
  • Min: nhắc hoài 7/23/2014 11:52:30 PM
  • Rainy: 7 ngày nhỉ 7/23/2014 11:52:32 PM
  • Min: xí hổ ghê 7/23/2014 11:52:34 PM
  • Rainy: ==" 7/23/2014 11:52:40 PM
  • Windy: qua lâu r==' 7/23/2014 11:52:43 PM
  • Rainy: hôm qua e mới biết 7/23/2014 11:52:57 PM
  • Rainy: cơ m 7/23/2014 11:52:59 PM
  • Rainy: c lại off 7/23/2014 11:53:02 PM
  • Windy: crying 7/23/2014 11:53:08 PM
  • Rainy: thôi để còn vài ngày nữa sn mama e 7/23/2014 11:53:48 PM
  • Min: biết j e 7/23/2014 11:53:55 PM
  • Rainy: e mời c đến ăn bánh kem 7/23/2014 11:54:06 PM
  • Rainy: e mới biết sn gió 7/23/2014 11:54:17 PM
  • Rainy: hôm qua 7/23/2014 11:54:34 PM
  • Windy: cơ mà gió làm sao vi vu đến đc tận Huế -_- 7/23/2014 11:54:41 PM
  • Rainy: thôi thì đến BG cx đc 7/23/2014 11:55:01 PM
  • Rainy: ăn sn baba c min laughing 7/23/2014 11:55:11 PM
  • Min: ai mời mà đến laughing 7/23/2014 11:55:27 PM
  • Windy: đến đấy biết đâu c í lại tảh chó ra í 7/23/2014 11:55:33 PM
  • Windy: biết mà 7/23/2014 11:55:38 PM
  • Windy:7/23/2014 11:55:40 PM
  • Windy: e cũng k thèm nhá 7/23/2014 11:55:46 PM
  • Min: ý c là 7/23/2014 11:55:47 PM
  • Windy: no_talking 7/23/2014 11:55:49 PM
  • Min: c sẽ mời gió 7/23/2014 11:55:54 PM
  • Min: nhưng 7/23/2014 11:55:56 PM
  • Min: k mời Q 7/23/2014 11:55:58 PM
  • Min: thôi 7/23/2014 11:55:59 PM
  • Min: big_grin 7/23/2014 11:56:01 PM
  • Windy: hee_hee 7/23/2014 11:56:08 PM
  • Min: k đọc câu trên. híhí 7/23/2014 11:56:09 PM
  • Rainy: frustrated 7/23/2014 11:56:25 PM
  • Rainy:7/23/2014 11:56:28 PM
  • Rainy: e k thèm nhá 7/23/2014 11:56:38 PM
  • Min: thèm mà đc à 7/23/2014 11:56:48 PM
  • Rainy: e ăn sn mama e r 7/23/2014 11:56:48 PM
  • Min: đùa chứ 7/23/2014 11:56:53 PM
  • Rainy: ko thèm 7/23/2014 11:56:54 PM
  • Min: c đag bận 7/23/2014 11:56:58 PM
  • Rainy: frustrated 7/23/2014 11:57:01 PM
  • Min: mấy đứa nc đi 7/23/2014 11:57:02 PM
  • Min: straight_face 7/23/2014 11:57:05 PM
  • Rainy: bận lm quà sn 7/23/2014 11:57:14 PM
  • Min: bận dỗ trẻ 7/23/2014 11:57:20 PM
  • Rainy: laughing 7/23/2014 11:57:22 PM
  • Min: rolling_on_the_floor 7/23/2014 11:57:24 PM
  • diendien_01: van chưa ngủ sao mà chém gió khoẻ thế các em 7/23/2014 11:57:37 PM
  • Windy: klq nhưng e biết cái phi vụ 2 người đang nói r nhá 7/23/2014 11:57:38 PM
  • Windy: k phải dấu e 7/23/2014 11:57:44 PM
  • Rainy: nhà c nhiều trẻ thế 7/23/2014 11:57:47 PM
  • Min: liên quan mà sad 7/23/2014 11:57:51 PM
  • Rainy: gió *suỵt* 7/23/2014 11:57:56 PM
  • Min: thế c mới nhờ e giúp 7/23/2014 11:57:56 PM
  • Windy: à à 7/23/2014 11:58:07 PM
  • Min: gió ơi 7/23/2014 11:58:07 PM
  • Windy: dạ 7/23/2014 11:58:11 PM
  • Min: lát rảnh thì nhắn tin đt vs c 7/23/2014 11:58:19 PM
  • Min: đc ko e 7/23/2014 11:58:21 PM
  • Windy: e k ở nhà c ạ 7/23/2014 11:58:29 PM
  • Min: ủa 7/23/2014 11:58:33 PM
  • Min: chứ e ở đâu 7/23/2014 11:58:37 PM
  • Windy: e lên nhà mợ e 7/23/2014 11:58:52 PM
  • Min: oh 7/23/2014 11:58:59 PM
  • Min: giống c 7/23/2014 11:59:02 PM
  • Min: cx ko ở nhà 7/23/2014 11:59:07 PM
  • Min: winking 7/23/2014 11:59:10 PM
  • Windy: big_grin 7/23/2014 11:59:18 PM
  • Windy: chả là 7/23/2014 11:59:22 PM
  • Windy: mấy hôm nữa gió sẽ vi vu ra hà nội 7/23/2014 11:59:41 PM
  • Windy: hí hí 7/23/2014 11:59:46 PM
  • Min: ra hú hí vs jea chăng surprise 7/24/2014 12:00:07 AM
  • Nhọ: laughing) 7/24/2014 12:00:11 AM
  • Rainy: về hà đông chơi vs jea đê laughing 7/24/2014 12:00:18 AM
  • Windy: nài c min 7/24/2014 12:00:21 AM
  • Min: cơ mà 7/24/2014 12:00:33 AM
  • Min: jea ko ở hn đâu 7/24/2014 12:00:33 AM
  • Windy: e đang nghiêm túc mờ 7/24/2014 12:00:33 AM
  • Min: laughing 7/24/2014 12:00:33 AM
  • Rainy: nghe giang hồ đồn đại 7/24/2014 12:00:37 AM
  • Nhọ: jea nào ở hn hđ 7/24/2014 12:00:46 AM
  • Rainy: nhọ là ny của Việt Anh laughing 7/24/2014 12:00:47 AM
  • Nhọ: laughing 7/24/2014 12:00:49 AM
  • Windy: khoan 7/24/2014 12:00:54 AM
  • Windy: cho gió phát biểu cái nào 7/24/2014 12:01:03 AM
  • Min: ko p giang hồ đồn mà là Nhọ tự nhận rolling_on_the_floor 7/24/2014 12:01:12 AM
  • Min: gì v gió 7/24/2014 12:01:18 AM
  • Rainy: èo 7/24/2014 12:01:36 AM
  • Rainy: e đi ngủ đây yawn 7/24/2014 12:01:46 AM
  • Rainy: m.n ngủ ngon 7/24/2014 12:01:51 AM
  • Windy: e ra hà nội xem đôi mắt thiên thần này có tăng đi ốp nào k mừ 7/24/2014 12:01:52 AM
  • Windy: ==' 7/24/2014 12:01:56 AM
  • Nhọ: laughing 7/24/2014 12:02:12 AM
  • Windy: Q ngủ ngon 7/24/2014 12:02:18 AM
  • Nhọ: thui ngủ náo 7/24/2014 12:02:23 AM
  • Windy: yawn 7/24/2014 12:04:16 AM
  • Min: big_grin 7/24/2014 3:12:17 AM
  • Min: ai dậy chưa big_grin 7/24/2014 4:13:29 AM
Đăng nhập để chém gió cùng mọi người
  • Đỗ Quang Chính
  • Lê Thị Thu Hà
  • dvthuat
  • Học Tại Nhà
  • newsun
  • khangnguyenthanh
  • roilevitinh_hn
  • Đỗ Đức Vỹ
  • Trần Nhật Tân
  • GreenmjlkTea FeelingTea
  • nguyenphuc423
  • Xusint
  • htnhoho
  • tnhnhokhao
  • hailuagiao
  • babylove_yourfriend_1996
  • tuananh.tpt
  • dungtth82
  • watashitipho
  • thienthan_forever123
  • hanhphucnhe989
  • xyz
  • Bruce Lee
  • mackhue59
  • sock_boy_xjnh_95
  • nghiahongoanh
  • HọcTạiNhà
  • super.aq.love.love.love
  • mathworld1999
  • phamviet2903
  • ducky0910199x
  • vet2696
  • ducdanh97
  • dangphuonganhk55a1s.hus
  • ♂Vitamin_Tờ♫
  • leeminhorain
  • binhnguyenhoangvu
  • leesoohee97qn
  • hnguyentien
  • Vô Minh
  • AnAn
  • athena.pi98
  • Park Hee Chan
  • cunglamhong
  • khoaita567
  • huongtrau_buffalow
  • nguyentienha95
  • thattiennu_kute_dangiu
  • ekira9x
  • ngolam39
  • thiếu_chất_xám
  • Nguyễn Đức Anh
  • doan.khoa
  • phamngocquynh19
  • chaicolovenobita
  • thanhgaubong
  • lovesong.2k12
  • NguyễnTốngKhánhLinh
  • yesterdayandpresent_2310
  • vanthoacb
  • caheoxanh_99
  • h0tb0y_94
  • quangtung237
  • vietphong9x
  • caunhocngoc_97
  • thanhnghia96
  • bbzzbcbcacac
  • hoangvuly12
  • hakutelht_94
  • thanchet_iu_nuhoang_banggia
  • worried_person_zzzz
  • bjgbang_vn
  • trai_tim_bang_gia_1808
  • shindodark112
  • ngthanhhieu88
  • zb1309
  • kimvanthao
  • hongnhat74
  • i_crazy_4u101
  • sweet_memory0912
  • hoiduong698
  • ittaitan
  • Chuyên Cơ Cuối Cùng
  • thanhnguyen5718
  • dongson.nd
  • anhthong.1996
  • Trần Phú
  • truoctran2007
  • hoanghon755
  • phamphuckhoinguyen
  • tabaosiphu1991
  • adjmtwpg2
  • khoibayvetroi
  • nhunglienhuong
  • justindrewd96
  • huongtraneni
  • minato_fire1069
  • justateenabi
  • soohyna
  • candigillian
  • terrible987654
  • trungha_tran
  • tranxuanluongcdspna_k8bcntt
  • dolaemon98
  • dolequan06
  • hoaithanhtnu
  • songotenf1
  • keo.shandy
  • vankhanhpf96
  • Phạm Anh Tuấn
  • thienbinh1001
  • phhuynh.tt
  • ductoan933
  • ♥♥♥ Bảo Bảo ♥♥♥
  • nguyen_lou520
  • Phy Phy ♥ ヾ(☆▽☆) ♥
  • gnolwalker
  • dienhoakhoinguyen
  • jennifer.generation22
  • nvrinh
  • Tiến Thực
  • kratoss1407
  • cuongtrang265
  • giola_2503
  • iamsuprael01
  • phamngocthao262
  • nguyenthanhnam488
  • thubi_panda
  • duyphong1969
  • sonnguyen846
  • woodknight22
  • trymybest123456789
  • ngothiphuong211
  • m_internet001
  • buihuyenchang
  • vlinh51
  • hoabachhop123ntt
  • honey.cake313
  • prokiller310
  • ducthieugia1998
  • phuoclinh0181
  • caolinh111111
  • vitvitvit29
  • vitxinh0902
  • anh_chang_co_don_3ky
  • successonyourhands
  • vuonlenmoingay
  • nhungcoi2109
  • vanbao2706
  • Billy Ken
  • vienktpicenza
  • stonecorter
  • botrungyc
  • nhoxty34
  • chonhoi110
  • tuanthanhvl
  • todangtvd
  • noluckhongngung1
  • tieulinhtinh102
  • vuongducthuanbg
  • ♥♂Ham٩(͡๏̮͡๏)۶Học♀♥
  • rabbitdieu
  • phungthoiphong1999
  • luubkhero
  • luuvanson35
  • neymarjrhuy
  • monkey_tb_96
  • ttbn841996
  • nhathuynh245
  • necromancy1996s
  • godfather9xx
  • phamtrungnhan122272
  • nghia7btq1234
  • thuỷ lê
  • thangha1311999
  • jea¤¤student
  • Death
  • devilphuong96
  • tqmaries34
  • bontiton96
  • hoang10a5.bc
  • mikicodon
  • nhephong2
  • hy_nho_ai
  • vanduc040902
  • sweetmilk1412
  • phamvanminh_812
  • deptrai331
  • ttsondhtg
  • phuonghoababu
  • taknight92
  • theduong90
  • hiephiep008
  • phathero99
  • ki_niem_voi_toi
  • Mun Sociu
  • vinh.s2_ai
  • tuongquyenn
  • hey
  • Thịnh Hải Yến
  • transon123456789123456789
  • thanhnienkosonga921996
  • trangiang1210
  • Lăn tăn
  • hang73hl
  • Bỗng Dưng Muốn Chết
  • Tonny_Mon_97
  • letrongduc2410
  • tomato.lover98
  • nammeo051096
  • phuongdung30497
  • zerokool020596
  • nguyenbahoangbn97
  • ẩn ngư
  • choihajin89
  • danglinhdt8a
  • Đỗ Bằng Được
  • yuka loan
  • duychuan95
  • sarah_curie
  • alexangđơ
  • sakurakinomoto199
  • luush06
  • phi.ngocanh8
  • hoanghoai1982000
  • iwillbestrong1101
  • quangtinh112
  • thuphuong10111997
  • tayduky290398
  • buoncuoi012
  • minh_thúy
  • mylove11a1pro
  • akaryzung
  • chauvantrung2995
  • anhdao
  • Nero
  • longthienxathu
  • loptruongnguyen
  • leejongsukleejongsuk
  • bồ công anh
  • Lone star
  • never give up
  • tramy_stupid2
  • mousethuy
  • Sam
  • babie_icy.lovely
  • cobemotmi10
  • ღ S' ayapo ღ
  • john19x6
  • giangkoi11196
  • tranhuyphuong99
  • namha500
  • Meoz
  • saupc7
  • Tonny_Mon_97
  • boyhandsome537
  • tinh_than_96
  • changngocxuan151095
  • gaconcute_2013
  • Sin
  • casio8tanyen
  • Choco*Pie
  • thusarah
  • tadaykhongsoai
  • seastar2592
  • lmhlinh1997
  • munkwonkang
  • fighting
  • tart97
  • dieu2102
  • cuonglapro97
  • fan.arsenalfc
  • luckyboy_kg1998
  • Nobi Nobita
  • akhoa13579
  • nguyenvantoan140dinhdong
  • anhquan9696
  • a5k67.lnq
  • Không Ai Cả
  • tozakendo
  • phudongphu12
  • luuphuongthao62
  • Min
  • lexuanmanh98
  • diendien_01
  • luongkimhien98
  • duanmath_xh
  • datk713kx
  • huynhtanhao_95_1996
  • peboo611998
  • kiemgo1999
  • luong.thanhtruong
  • nguyenduythong.2012
  • soi.1stlife
  • nguyenthily257
  • nguyenconguoc1996
  • dongthoigian1096
  • thanhthaiagu
  • thanhhoapro056
  • thukiet1979
  • xuanhuy164
  • kto138
  • Rainy
  • teengirl_hn1998
  • trilac2013
  • Windy
  • kuzulies
  • ♥♥Hoàng Huy♥♥
  • nhoknana95
  • hoctainha
  • fglory2912
  • Togo
  • hothinhtls
  • hoangloclop4
  • gautruc_199854
  • cuoidiem035
  • giam_chua
  • maitrangvnbk47
  • nhi.angel0809
  • nguyenhuuminh22