Đến nội dung

Hình ảnh

Cơ bản về nguyên lý Đi-rích-lê


  • Please log in to reply
Chủ đề này có 63 trả lời

#21
Trang Linh

Trang Linh

    Lính mới

  • Thành viên
  • 1 Bài viết

xin chào mọi người, mình là mem mới, mong m.n giúp đỡ! :)

m.n giúp mình giải một số bài toán Đi-rích-lê với. tks m.n nhìu

bài 1: kết thúc năm học,mỗi học sinh của một lớp đều gửi ảnh tặng một hay nhiều bạn và ai cũng nhận ít nhất một ảnh. CMR: có ít nhất 2h/s nhận dk một số ảnh giống nhau

bài 2: CMR; tồn tại một bội của 23 có tận cùng bằngg 219



#22
HungHuynh2508

HungHuynh2508

    Thượng sĩ

  • Thành viên
  • 222 Bài viết

Xin đóng góp topic 1 bài:

Trong mặt phẳng có 17 điểm , không có 3 điểm nào thẳng hàng, mỗi đoạn thẳng nối 2 điểm bất kì ( trong 17 điểm) được tô bởi 3 màu: Xanh,Đỏ , vàng . Chứng minh luôn tồn tại tam giác có 3 cạnh cùng màu


Hạnh phúc là cho đi đâu chỉ nhận riêng mình!

7e3c59fbf62d4c5280e6cf2ad53cdcb8.0.gif

#23
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

Xin đóng góp topic 1 bài:

Trong mặt phẳng có 17 điểm , không có 3 điểm nào thẳng hàng, mỗi đoạn thẳng nối 2 điểm bất kì ( trong 17 điểm) được tô bởi 3 màu: Xanh,Đỏ , vàng . Chứng minh luôn tồn tại tam giác có 3 cạnh cùng màu

Một trường hợp của định lí Ramsey



#24
HungHuynh2508

HungHuynh2508

    Thượng sĩ

  • Thành viên
  • 222 Bài viết

Một trường hợp của định lí Ramsey

Cái này tùy vào từng người chứng minh, theo mình thì dùng nguyên tắc Diriclet thì nhanh nhất...


Hạnh phúc là cho đi đâu chỉ nhận riêng mình!

7e3c59fbf62d4c5280e6cf2ad53cdcb8.0.gif

#25
LNH

LNH

    Bất Thế Tà Vương

  • Hiệp sỹ
  • 581 Bài viết

Thì định lí Ramsey dùng Dirichlet để CM mà



#26
hoangmanhquan

hoangmanhquan

    Thiếu úy

  • Thành viên
  • 641 Bài viết

Bài này nha

Một cuộc họp có 100 người tham gia . Giả sử mỗi người đều quen với ít nhất 67 người. CMR: có thể tìm thấy 1 nhóm 4 người mà 2 người bất kì đều quen nhau.


:icon1: Sống là cho, đâu chỉ nhận riêng mình :icon1: 

 

 


#27
lovemathforever99

lovemathforever99

    Thượng sĩ

  • Thành viên
  • 216 Bài viết

1.Cho 2 số tự nhiên a,b sao cho $ab=1996^{1995}$. Hỏi $a+b$ có chia hết cho $1995$ hay không?

2. Trong hình chữ nhật có kích thước $1\times 2$, lấy $6n^{2}+1$ điểm với n nguyên dương. Chứng minh rằng tồn tại 1 hình tròn bán kính $\frac{1}{n}$ chứa không ít hơn 4 trong số các điểm đã cho


Bài viết đã được chỉnh sửa nội dung bởi lovemathforever99: 05-03-2014 - 20:53

                                                 ''Chúa không chơi trò xúc xắc.''

Albert Einstein


#28
angleofdarkness

angleofdarkness

    Thượng sĩ

  • Thành viên
  • 246 Bài viết
 

Bài này nha

Một cuộc họp có 100 người tham gia . Giả sử mỗi người đều quen với ít nhất 67 người. CMR: có thể tìm thấy 1 nhóm 4 người mà 2 người bất kì đều quen nhau.

 

Xét hai người quen nhau A và B. Số người quen của mỗi người ít nhất là 67 nên số người quen chung của A và B ít nhất là 67 + 67 - 100 = 34.

 

Gọi S là tập những người quen chung của A và B thì trong M có ít nhất hai người C và D quen nhau vì nếu C và D không quen nhau thì mỗi nguời trong nhóm S phải quen nhiều nhất là 100 - 34 = 66 người (ít hơn 67) nên loại.

 

Vậy có ít nhất 4 người (VD là A, B, C, D như trên) mà bất kì người nào trong nhóm cũng quen nhau.

 



#29
angleofdarkness

angleofdarkness

    Thượng sĩ

  • Thành viên
  • 246 Bài viết

1.Cho 2 số tự nhiên a,b sao cho $ab=1996^{1995}$. Hỏi $a+b$ có chia hết cho $1995$ hay không?

 

 

Bài này là bài 6 trong đề thi cuối HKI huyện Thanh Chương - Nghệ An, bạn tham khảo đáp án ở đây

 

2. Trong hình chữ nhật có kích thước $1\times 2$, lấy $6n^{2}+1$ điểm với n nguyên dương. Chứng minh rằng tồn tại 1 hình tròn bán kính $\frac{1}{n}$ chứa không ít hơn 4 trong số các điểm đã cho

 

Còn bài này là đề thi HSG 9 trường Nguyễn Trãi đáp án tham khảo ở đây 

 

:D



#30
lethanhson2703

lethanhson2703

    Thượng sĩ

  • Thành viên
  • 297 Bài viết

Đóng góp cho topic 1 bài diriclet

Có 9 điểm trên mặt phẳng, bất cứ điểm nào cũng là đỉnh của một tam giác mà cạnh được tô bởi màu xanh hoặc đỏ trong đó bao giờ cũng có cạnh màu đỏ. CMR tồn tại 1 tứ giác có các cạnh và đường chéo cùng màu đỏ



#31
grigoriperelmanlapdi

grigoriperelmanlapdi

    Trung sĩ

  • Thành viên
  • 117 Bài viết

Chào mừng VMF vừa mới trở lại khac.gif Mình xin post một chuyên đề về nguyên tắc Đi-rích-lê, hay còn gọi là nguyên tắc nhốt thỏ vào lồng. Bài viết có sử dụng nguồn từ khá nhiều sách, các bạn đọc tạp chí Toán học tuổi trẻ để biết thêm
Nguyên tắc Đi-rích-lê được phát biểu dưới dạng bài toán như sau:
Nếu đem m thỏ vào n lồng với m>n thì ít nhất cũng có một lồng nhốt không ít hơn 2 thỏ. Tương tự, nếu đem m đồ vật vào n ô ngăn kéo, với m>n, thì ít nhất cũng phải có 1 ô ngăn kéo chứa không ít hơn 2 đồ vật
Phần chứng minh bài toán, các bạn chắc gần như ai cũng biết, mình chỉ xin nêu một vài bài toán vận dụng cơ bản.

Ví dụ 1:
Trong một lớp chuyên toán có 40 học sinh. Trong một kỳ kiểm tra chất lượng môn toán chỉ có một em đạt điểm tối đa là 10, và một em đạt điểm 4, các em khác đạt từ điểm 5 trở lên. Chứng minh rằng trong lớp ít nhất cũng có 8 em có điểm số như nhau, biết rằng điểm số các em đều là các số nguyên.

Lời giải:
Theo giả thiết của bài toán thì chỉ có một em đạt điểm 10 và một em đạt điểm 4, do đó sẽ có $40-2=38$ em đạt điểm 5 đến điểm 9. Coi mỗi học sinh là một "thỏ", mỗi loại điểm là 1 "lồng", như vậy ta sẽ có các lồng sau:
"Lồng 5": nhốt những ai đạt điểm 5
"Lồng 6": nhốt những ai đạt điểm 6
"Lồng 7": nhốt những ai đạt điểm 7
"Lồng 8": nhốt những ai đạt điểm 8
"Lồng 9": nhốt những ai đạt điểm 9
Với 5 lồng nhốt 38 thỏ, vậy có ít nhất một lồng nhốt không ít hơn 8 thỏ, bài toán được chứng minh.
Ví dụ 2:
Cho 10 số tự nhiên bất kỳ: $a_1, a_2, a_3...,a_9,a_10$
Chứng minh rằng thế nào cũng có một số hoặc tổng một số số liên tiếp nhau trong dãy 10 số đã cho chia hết cho 10.
Lời giải:

Để làm xuất hiện khái niệm "thỏ", "lồng", ta thành lập dãy số mới sau đây:
Đặt $B_1=a_1$
$B_2=a_1+a_2$
$B_3=a_1+a_2+a_3$
$B_4=a_1+a_2+a_3+a_4$
...
$B_10=a_1+...+a_10$
Ta thấy rằng:
- Nếu tồn tài một $B_i$ nào đó (i=1,2,3,...,10) chia hết cho 10 thì bài toán đã được chứng minh.
- Nếu không tồn tại một $B_1$ nào đó chia hết cho 10 thì ta chỉ việc đem tất cả $B_i$ chia cho 10, lúc đó được 10 số dư từ 1-9, trong khi đó các số tự nhiên từ 1-9 chỉ có 9 số (như vậy tương đương với việc nhốt 10 chủ thỏ vào 9 lồng), theo nguyên tắc Đi-rích-lê, tồn tại 1 lồng nhốt không ít hơn 2 chú thỏ, tương đương với việc tồn tại hai số có cùng số dư, như vậy có hiệu chia hết cho 10, bài toán được chứng minh

Còn tiếp.....

mình chưa hiểu chỗ này tại sao có hiệu chia hết cho $10$ thì bài toán được chứng minh



#32
foollock holmes

foollock holmes

    Thượng sĩ

  • Thành viên
  • 220 Bài viết

mình chưa hiểu chỗ này tại sao có hiệu chia hết cho $10$ thì bài toán được chứng minh

có 1 hiệu chia hết cho 10, ví dụ như $B_{10} -B_1$ chia hết cho 10, vậy $a_2 +a_3+....+a_10$ chia hết cho 10, bài toán được chứng minh



#33
foollock holmes

foollock holmes

    Thượng sĩ

  • Thành viên
  • 220 Bài viết

mọi người giúp em bài này

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 đề II7 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 đề.



#34
ducna2002

ducna2002

    Binh nhì

  • Thành viên
  • 18 Bài viết

Dirichlet được sinh ra ở Düren, nơi cha ông là một đứng đầu một trạm bưu điện. Ông được giáo dục ở Đức, và sau đó là Pháp, nơi ông học hỏi từ hầu hết các nhà toán học nổi tiếng nhất thời đó. Ông cũng học từ Georg Ohm. Bài báo đầu tiên của ông là vềđịnh lý Fermat bao gồm một phần của chứng minh cho trường hợp 44d21af66b0874d9b45905ea79807cb3.png, được hoàn thiện bởi Adrien-Marie Legendre, một trong những người referees. Dirichlet cũng hoàn thiện chứng minh của ông trong cùng một thời gian; sau đó ông đã đưa ra toàn bộ lời giải cho trường hợp 081242d676ae2969a930140e1e7274a4.png.



#35
ducna2002

ducna2002

    Binh nhì

  • Thành viên
  • 18 Bài viết

xin chào mọi người, mình là mem mới, mong m.n giúp đỡ! :)

m.n giúp mình giải một số bài toán Đi-rích-lê với. tks m.n nhìu

bài 1: kết thúc năm học,mỗi học sinh của một lớp đều gửi ảnh tặng một hay nhiều bạn và ai cũng nhận ít nhất một ảnh. CMR: có ít nhất 2h/s nhận dk một số ảnh giống nhau

bài 2: CMR; tồn tại một bội của 23 có tận cùng bằngg 219

bài 2: xét 23 số:219, 219219,... ,219219,,,219 (23 số 219)

Th1: ko số nào cùng số dư khi chia cho 23.

có 1 số là bội của 23.

Th2: có ít nhất 2 số nào cùng số dư khi chia cho 23.

G/s 2 số đó là: A= 219219...219 (j số 219) và B=219219...219 (k số 219)(j > k).

A-B $\vdots$23

219219...000000(j-k số 219) $\vdots$23

mà 100..000 nguyên tố cùng nhau 23

suy ra 219219..219(j-k số 219) $\vdots$23

đpcm


Bài viết đã được chỉnh sửa nội dung bởi ducna2002: 28-06-2015 - 11:25


#36
ducna2002

ducna2002

    Binh nhì

  • Thành viên
  • 18 Bài viết

Chứng minh rằng mọi số nguyên tố p ta có thể tìm được một số được viết bởi hai chữ số chia hết cho p. 



#37
ducna2002

ducna2002

    Binh nhì

  • Thành viên
  • 18 Bài viết
 
Trên một tờ giấy kẻ ô vuông, chọn 101 ô bất kì. Chứng minh rằng trong 101 ô đó
có ít nhất 26 ô không có điểm chung.

Bài viết đã được chỉnh sửa nội dung bởi ducna2002: 05-07-2015 - 11:19


#38
kimchitwinkle

kimchitwinkle

    Thiếu úy

  • Điều hành viên THCS
  • 526 Bài viết

Cho $a_{1};a_{2};...............a_{44}$ là các số nguyên thỏa mãn : $0< a_{1}< a_{2}< ..............< a_{44}\leq 125$ . CMR tồn tại ít nhất 1 trong số 43 hiệu $d_{j}=a_{j+1}-a_{j}$ lặp lại ít nhất 10 lần .



#39
toanhocvuive123

toanhocvuive123

    Binh nhì

  • Thành viên
  • 18 Bài viết

Các bạn cho mình hỏi sao để cmr trong 8 số tự nhiên có 3 chữ số bao giờ cũng chọn được 2 số mà khi viết liền nhau ta được một số có 6 chữ số và chia hết cho 7?


When you have eliminated the impossible, whatever remains,however improbable, must be the truth. :lol:  :lol:  :lol: 


#40
gianglqd

gianglqd

    Trung úy

  • Thành viên
  • 894 Bài viết

Các bạn cho mình hỏi sao để cmr trong 8 số tự nhiên có 3 chữ số bao giờ cũng chọn được 2 số mà khi viết liền nhau ta được một số có 6 chữ số và chia hết cho 7?

Trong 8 số đó bao giờ cũng có 2 số có cùng số dư khi chia cho 7 (Dirichlet)

Gọi 2 số đó là $\overline{abc}, \overline{def}$ cùng chia 7 dư m$1000(100a+10b+c)+100d+10e+f\equiv 1000m+m(mod7)$

Ta CM $\overline{abcdef} \vdots 7$ 

Thật vậy $\overline{abcdef}$ = $1000(100a+10b+c)+100d+10e+f\equiv 1000m+m(mod7)$$\equiv 1001m\equiv 0(mod7)$

Suy ra Đpcm


Bài viết đã được chỉnh sửa nội dung bởi gianglqd: 29-07-2015 - 07:51

Mabel Pines - Gravity Falls

 

 

                                                        

 





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh