Nguyên lý Dirichlet

Nơi trao đổi các kiến thức Toán hỗ trợ cho môn Vật Lý

Nguyên lý Dirichlet

Bài viết chưa xemgửi bởi dungbaby » Thứ 5 Tháng 2 14, 2008 7:24 am

I.Định nghĩa:
Nguyên lý Đirichlê còn gọi là "nguyên tắc nhốt thỏ vào lồng " hoặc "nguyên tắc xếp đồ vật vào ngăn kéo" hoặc nguyên tắc lổ chuồng câu". Nội dung của nguyên lý này hết sức đơn giản và dễ hiểu, nhưng lại có tác dụng rất lớn trong giải toán. Nhiều khi có những bài toán, người ta đã dùng rất nhiều phương pháp toán học để giải mà vẫn chưa đi đến kết quả, nhưng nhờ nguyên lý Đirichlê mà bài toán trở nên dễ dàng giải quyết.
Nguyên tắc Đirichlê được phát biểu dưới dạng bài toán sau đây:
1. Nếu đem nhốt m con thỏ vào n chiếc lồng, với m>n (nghĩa là số thỏ nhiều hơn số lồng) thì ít nhất cũng có một lồng nhốt không ít hơn 2 thỏ.
Hoặc là:
2. Nếu đem xếp m đồ vật vào n ô ngăn kéo, với m>n (nghĩa là số đồ vật nhiều hơn số ngăn kéo), thì ít nhất cũng phải có một ô ngăn kéo chứa không ít hơn 2 đồ vật.
Chứng minh (dùng phương pháp phản chứng):
Giả sử không có lồng nào nhốt từ 2 thỏ trở nên, thế thì cho dù mỗi lồng đều có nhốt một thỏ thì tổng số thỏ bị nhốt cũng chỉ là n thỏ, trong khi đó tổng số thỏ là m. Điều này vô lý. Vậy ít nhất cũng phải có 1 lồng nhốt từ 2 thỏ trở nên.(đpcm)
Nguyên lí Dirichlet là một định lí về tập hợp hữu hạn.Phát biểu chính xác nguyên lí này như sau
Cho A vàB là 2 tập không rỗng có số phần tử hữu hạn mà số phần tử ở A lớn hơn số lượng phần tử của B ,Nếu với quy tắc nào đấy, mỗi phần tử của A tương ứng với 1 phần tử của B thì tồn tại 2 phần tử khác nhau của A mà chúng tương ứng với cùng 1 phần tử của B
II)Mở rộng nguyên lí Dirichlet
Cho A là tập hữu hạn những phần tử , Kí hiệu s(A) là số lượng các phần tử thuộc A.Nguyên lý Dirichlet có thể phát biểu như sau
Nếu A và B là những tập hợp hữu hạn và s(A) > ks(B) ở đây k là 1 số tự nhiên nào đó và nếu mỗi phần tử của A cho tương ứng với 1 phần tử nào đó của B thì tồn tại ít nhất k+1 phần tử của A mà chúng tương ứng với cùng một phần tử của B
Mọi việc đều khởi đầu từ sự lắng nghe
Hình đại diện của thành viên
dungbaby
Thành viên nhiệt tình
Thành viên nhiệt tình
 
Bài viết: 236
Ngày tham gia: Thứ 7 Tháng 12 08, 2007 1:10 pm
Đến từ: Nghệ An

Re: Nguyên lý Dirichlet

Bài viết chưa xemgửi bởi dungbaby » Thứ 5 Tháng 2 14, 2008 7:24 am

II. Các ví dụ:
A.Các bài toán số học:
1. Toán suy luận:
Ví dụ 1: Có 10 đội bóng thi đấu với nhau mỗi đội phải đấu một trận với các đội khác. CMR vào bất cứ lúc nào cũng có hai đội đã đấu số trận như nhau.
GIẢI: Rõ ràng nếu trong 10 đội bóng có 1 đội chưa đấu một trận nào thì trong các đội còn lại không có đội nào đã thi đấu 9 trận như vậy 10 đội chỉ có số trận đấu hoặc từ 0 đến 8 hoặc từ 1 đến 9. Vậy theo nguyên lý Đirichlê phải có ít nhất 2 đội có số trận đấu như nhau.
Ví dụ 2: Có 6 đội bóng thi đấu với nhau (mỗi đội phải đấu 1 trận với 5 đội khác). CMR vào bất cứ lúc nào cũng có 3 đội trong đó từng cặp đã đấu với nhau hoặc chưa đấu với nhau trận nào.
GIẢI: Giả sử 6 đội bóng đó là A,B,C,D,E,F. Xét đội A.
Theo nguyên lý Đirichlê ta suy ra: A phải đấu hoặc không đấu với ít nhất 3 đội khác. Không mất tính tổng quát, giả sử A đã đấu với B,C,D.
Nếu B,C,D từng cặp chưa đấu với nhau thì bài toán được chứng minh.
Nếu B,C,D có 2 đội đã đấu với nhau, ví dụ B và C thì 3 đội A,B,C từng cặp đã đấu với nhau.
Như vậy bất cứ lúc nào cũng có 3 đội trong đó từng cặp đã đấu với nhau hoặc chưa đấu với nhau trận nào.
Ví dụ 3: CMR trong n người bất kì, tồn tại hai người có số người quen như nhau (kể cả trường hợp quen 0 người)
GIẢI: Tương tự ví dụ 1, ta xét n nhóm...
Ví dụ 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. CMR í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 từ 0 đến 10)
GIẢI: Có 43 học sinh phân chia vào 8 loại điểm (từ 2 đến 9). Giả sử mỗi loại 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ó không quá 5.8=40 học sinh, ít hơn 43 học sinh. Vậy tồn tại 6 học sinh có điểm kiểm tra bằng nhau.


2.Sự chia hết:
Trong các phép tính trên số nguyên thì phép chia là rất đặc biệt.Phép chia có hàng loạt các tính chất mà các phép còn lại không có. Ví dụ các phép toán cộng , trừ , nhân đều thực hiện với số 0 còn phép chia thì không thể.Vì những lí do đặc biệt đó mà trong toán học xây dựng hẳn 1 lý thuyết về phép vchia . Những ví dụ sau có liên quan mật thiết giữa phép chia và nguyên lý Dirchlet
Ví dụ 1: CMR tồn tại một số tự nhiên gồm toàn chữ số 1 chia hết cho 2007.
GIẢI: Xét 2008 số có dạng 1,11,...,11...11. Theo nguyên tắc Đirichlê thì tồn tại hai số có cùng số dư khi chia cho 2007. Giả sử hai số đó là:
A={11...1}_{n} và B={11...1}_{k} với k<n.
Khi đó A-B={11...1}_{n-k}.10^k chia hết cho 2007
Do (2007, 10^k)=1 nên C={11...1}_{n-k} chia hết cho 2007.
Ví dụ 2: CMR trong n+1 số bất kì thuộc tập hợp \{1,2,3,...,2n\} luôn chọn được hai số mà số này là bội của số kia.
GIẢI: Viết n+1 số đã cho dưới dạng:
a_1=2^{k_1}b_1, a_2=2^{k_2}b_2,..., a_{n+1}=2^{k_{n+1}}b_{n+1}
Trong đó b_1,b_2,...,b_{n+1} là các số lẻ. Ta có: 1<= b_1, b_2,...,b_{n+1}<= 2n-1. Mặt khác trong khoảng từ 1 đến 2n-1 có đúng n số lẻ nên tồn tại hai số m<= n sao cho b_n=b_m. Khi đó, trong hai số a_n và a_m có một số là bội của số kia.
Ví dụ 3: Cho 5 số nguyên phân biệt a_i (i=1,2,3,4,5). Xét tích:
P=(a_1-a_2)(a_1-a_3)(a_1-a_4)(a_1-a_5)(a_2-a_3)(a_2-a_4)(a_2-a_5)(a_3-a_4)(a_3-a_5)(a_4-a_5).
CMR P chia hết cho 288
GIẢI: 288=3^2.2^5
-Chứng minh P chia hết cho 9.
Xét 4 số a_1,a_2,a_3,a_4 tồn tại 2 số có cùng số dư khi chia cho 3. Giả sử a_1 đồng dư a_2 (mod 3) thì a_1-a_2 chia hết cho 3.Lại xét a_2,a_3,a_4,a_5 trong 4 số này lại tồn tại 2 số có cùng số dư khi chia cho 3. Suy ra P chia hết cho 9.
-Chứng minh P chia hết cho 2^5
Trong 5 số đã cho có 3 số cùng tính chẵn lẻ.
-Nếu có 4 số chẵn, chẳng hạn a_1=2k_1, a_2=2k_2, a_3=2k_3, a_4=2k_4 thì :
P=32(k_1-k_2)(k_1-k_3)(k_1-k_4)(a_1-a_5)(k_2-k_4)(k_2-k_3)(a_2-a_5)(a_3-a_4)(a_3-a_5)(a_4-a_5) chia hết cho 32.
-Nếu có 3 số chẵn, 2 số lẻ thì đặt:
a_1=2k_1, a_2=2k_2, a_3=2k_3, a_4=2k_4+1, a_5=2k_5+1
Ta có P=16(k_1-k_2)(k_1-k_3)(k_2-k_3).M
Trong 3 số k_1,k_2,k_3 có 2 số cùng tính chẵn lẻ. Giả sử k_1 đồng dư k_1 (mod 2) thì k_1-k_2 chia hết cho 2 nên P chia hết cho 32.
-Nếu có 3 số lẻ là a_1,a_2,a_3 còn a_4,a_5 chẵn thì đặt a_1=2k_1+1, a_2=2k_2+1, a_3=2k_3+1, a_4=2k_4, a_5=2k_5
Xét tương tự cũng có P chia hết cho 32.
Vậy ta có P chia hết cho 288.
3. Toán về tổng, hiệu, chữ số tận cùng...các loại:
Ví dụ 1: Cho 51 số nguyên dương khác nhau có 1 chữ số và có 2 chữ số. CMR ta có thể chọn ra 6 số nào đó mà bất cứ 2 số nào trong số đã lấy ra ấy không có chữ số hàng đơn vị giống nhau cũng không có chữ số hàng chục giống nhau.
GIẢI:
Vì có 51 số nên tìm được 6 chục sao cho một nhóm có không ít hơn 6 số rơi vào một trong các số chục đó, một nhóm có không ít hơn 5 số rơi vào chục khác... Cuối cùng có ít nhất một trong các số đã cho rơi vào một chục nào đó (như vậy số các chục khác nhau không ít hơn 6) về các số đã cho là khác nhau (chú ý các số dạng xét nhiều nhất có 2 chữ số ) do đó ở nhóm cuối cùng ta lấy một số , sau đó nhóm trước đó (vì có ít nhất 2 chữ số hàng đơn vị của hai số trong nhóm ấy khác nhau) ta lấy một số khác với chữ số hàng đơn vị khác số chọn trước, rồi nhóm trước đó lại lấy 1 số có chữ số hàng đơn vị khác 2 số chọn trước... Cuối cùng sẽ được 6 số phải tìm với các chữ số khác nhau.
Ví dụ 2: Chọn bất kì n+1 số trong 2n số tự nhiên từ 1 đến 2n (n>=2). CMR trong các số được chọn có ít nhất 1 số bằng tổng của 2 số được chọn (kể cả các trường hợp 2 số hạng của tổng bằng nhau ).
GIẢI:Giả sử a_1<a_2<...<a_n<a_{n+1} là n+1 số được chọn.
Xét n số: a_{n+1}-a_1=b_1
a_{n+1}-a_2=b_2
........................ (mỗi hiệu đều nhỏ hơn 2n)
a_{n+1}-a_n=b_n
Trong tập 2n+1 số đó là a_1,a_2,...,a_{n+1}, b_1,b_2,...,b_n tồn tại 2 số bằng nhau, hai số ấy không thể cùng thuộc dãy a_1,a_2,...,a_{n+1} cũng không thể cùng thuộc dãy b_1,b_2,...,b_n . Ta có:
a_{n+1}-a_1=a_i suy ra a_{n+1}=a_1+a_i (đpcm)
Sửa lần cuối bởi dungbaby vào ngày Chủ nhật Tháng 2 24, 2008 5:24 am với 1 lần sửa trong tổng số.
Mọi việc đều khởi đầu từ sự lắng nghe
Hình đại diện của thành viên
dungbaby
Thành viên nhiệt tình
Thành viên nhiệt tình
 
Bài viết: 236
Ngày tham gia: Thứ 7 Tháng 12 08, 2007 1:10 pm
Đến từ: Nghệ An

Re: Nguyên lý Dirichlet

Bài viết chưa xemgửi bởi dungbaby » Thứ 5 Tháng 2 14, 2008 7:25 am

B. Các bài toán hình học:
1. Đánh giá các điểm, các đường thẳng:
Ví dụ 1: Cho một hình vuông và 13 đường thẳng, mỗi đường thẳng đều chia hình vuông thành hai tứ giác có tỉ số diện tích 2:3. CMR trong số 13 đường thẳng đó, có ít nhất 4 đường thẳng cùng đi qua một điểm.
GIẢI: Gọi d là đường thẳng chia hình vuông ABCD thành hai tứ giác có tỉ số diện tích 2:3. Đường thẳng d không thể cắt hai cạnh kề nhau của hình vuông vì khi đó không tạo thành hai tứ giác. Giả sử d cắt hai cạnh AB và CD tại M và N, khi đó nó cắt đường trung bình EF tại Ị
Giả sử S_{AMND}=\frac{2}{3}S_{BMNC} thì EI=\frac{2}{3}IF
Như vậy mỗi đường thẳng đã cho chia các đường trung bình của hình vuông theo tỉ số 2:3. Có 4 điểm chia các đường trung bình của hình vuông ABCD theo tỉ số 2:3.
Có 13 đường thẳng, mỗi đường thẳng đi qua một trong 4 điểm. Vậy theo nguyên lý Đirichlê có ít nhất 4 đường thẳng đi qua.
Ví dụ 2: Bên trong tam giác đều ABC cạnh 1 đặt 5 điểm. CMR tồn tại 2 điểm có khoảng cách nhỏ hơn 0,5.
GIẢI: Các đường trung bình của tam giác đều cạnh 1 sẽ chia nó ra làm 4 tam giác đều cạnh 0,5. Do đó trong một tam giác nhỏ đó có ít nhất 2 điểm đã cho, và các điểm đó không thể rơi vào các đỉnh của tam giác. Vậy khoảng cách giữa hai điểm đó nhỏ hơn 0,5.
2. Đánh giá góc và độ dài:
Ví dụ 1: Trên mặt phẳng cho n đường thẳng từng đôi một không song song với nhau. CMR góc giữa hai đường thẳng nào đó trong số đó không lớn hơn \frac{\180^ \circ}{n}
GIẢI: Lấy trên mặt phẳng một điểm bất kì và kẻ qua đó các đường thẳng song song với các đường thẳng đã cho. Chúng chia mặt phẳng ra làm 2n góc, có tổng các góc bằng \360^ \circ. Do đó tồn tại một góc không lớn hơn \frac{\180^ \circ}{n}
Ví dụ 2: Bên trong một đường tròn bán kính n đặt 4n đoạn thẳng có có độ dài 1. CMR có thể kẻ một đường thẳng song song hoặc vuông góc với đường thẳng l cho trước và cắt ít nhất hai đoạn thẳng đã cho.
GIẢI: Giả xử lý là đoạn thẳng bất kì vuông góc với l. Kí hiệu độ dài các hình chiếu của đoạn thẳng thứ i lên các đường thẳng l và l_1 là a_i và b_i tương ựng Vì độ dài của mỗi đoạn thẳng bằng 1 nên a_i+b_i\geq 1. Do đó (a_1+..+a_{4n})+(b_1+...+b_{4n})\geq 2n. Không mất tính tổng quát giả sử a_1+...+a_{4n}\geq b_1+...+b_{4n} . Khi đó a_1+...+a_{4n}\geq 2n. Tất cả các đoạn thẳng đã cho đều được chiếu xuống đoạn thẳng có độ dài 2n, vì chúng đều nằm trong đường tròn bán kính n.Nếu như các hình chiếu của các đoạn thẳng đã cho lên đường thẳng l không có điểm chung, thì sẽ có a_1+...+a_{4n}<2n. Do đó trên l phải có một điểm bị các điểm của ít nhất 2 trong số các đoạn thẳng đã cho chiếu lên nó. Đường vuông góc với l tại điểm đó sẽ cắt ít nhất hai đoạn thẳng đã cho.
Mọi việc đều khởi đầu từ sự lắng nghe
Hình đại diện của thành viên
dungbaby
Thành viên nhiệt tình
Thành viên nhiệt tình
 
Bài viết: 236
Ngày tham gia: Thứ 7 Tháng 12 08, 2007 1:10 pm
Đến từ: Nghệ An

Re: Nguyên lý Dirichlet

Bài viết chưa xemgửi bởi dungbaby » Thứ 5 Tháng 2 14, 2008 7:26 am

Các bài toán về tô màu
Bài 1 : Giả sử mỗi điểm trong mặt phẳng được tô bằng một trong 2 màu đỏ và xanh
Chứng minh tồn tại 1 hình chữ nhật có các đỉnh cùng màu

Giải : Giả sử ta có một lưới ô vuông tạo bởi 3 đường nằm ngang và 9 đường thẳng đứng , mỗi nút lưới được tô bởi một màu xanh hoặc đỏ.
Xét 3 nút lưới của một đường dọc , mỗi nút có hai cách tô màu nên mỗi bộ ba nút trên đường dọc ấy có 2.2.2=8 cách tô màu.
Có 9 đường dọc, mỗi đường có 8 cách tô màu nên tồn tại hai đường có cách tô màu như nhau.
Chẳng hạn hai bộ ba điểm đó là A_1, A_2, A_3 và B_1, B_2, B_3
Vì 3 điểm A_1, A_2, A_3 chỉ được tô bởi hai màu nên tồn tại hai điểm cùng màu , chẳng hạn A_1 và A_2, khi đó hình chữ nhật A_1A_2B_2B_1 có 4 đỉnh cùng một màu.

Bài 2 :Giả sử 1 bàn cờ hình chữ nhật có 3x7 ô vuông được sơn đen hoặc trắng.Chứng minh rằng với cách sơn màu bất kì ,trong bàn cờ luôn tồn tại hình chữ nhật gồm các ô ở 4 góc là các ô cùng màu
Lời giải :

Mẫu sơn màu có thể xảy ra với bàn cờ này có dạng từ 1 đến 8.Giả sử một trong số các cột thuộc dạng 1.Bài toán sẽ được chứng minh nếu tất cả các cột còn lại thuộc dạng 1,2,3 hoặc 4.Giả sử tất cả các cột còn lại thuộc dạng 5,6,7,8 Khi đó theo nguyên lí Dirichlet 2 trong số 6 cột có 2 cột cùng 1 dạng và như vậy bài toán cũng được chứng minh
Chứng minh hoàn toàn tương tự nếu 1 cột có dang 8 .Giả sử không có cột nào trong các cột 1,8 thì theo nguyên lí Dirichlet cũng có 2 cột cùng dạng và bài toán cũng đựoc chứng minh
Mọi việc đều khởi đầu từ sự lắng nghe
Hình đại diện của thành viên
dungbaby
Thành viên nhiệt tình
Thành viên nhiệt tình
 
Bài viết: 236
Ngày tham gia: Thứ 7 Tháng 12 08, 2007 1:10 pm
Đến từ: Nghệ An

Re: Nguyên lý Dirichlet

Bài viết chưa xemgửi bởi dungbaby » Thứ 5 Tháng 2 14, 2008 7:28 am

Nguyên lý Dirichlet cho diện tích
Nếu A là một bề mặt và A_1 , A_2..A_n là các bề mặt sao cho A_i \subset A_n và S(A)<S(A_1)+S(A_2)+...+S(A_n) thì ít nhất có 2 bề mặt trong số các bề mặt trên có điểm trong chung
Cụ thể hoá
1.Cho những đoạn thẳng \Delta_1 ,\Delta_2...\Delta_n nằm trong đoạn \Delta và tổng độ dài của \Delta_1 ,\Delta_2...\Delta_n lớn hơn độ dài của \Delta.Khi đó ít nhất 2 đoạn trong số những đoạn \Delta_1 ,\Delta_2...\Delta_n có điểm trong chung
2.Cho những đa diện P_1 ,P_2...P_n nằm trong đa diện P và tổng thể tích của P_1 ,P_2...P_n lớn hơn thể tích của P.Khi đó ít nhất 2 trong số những đa diện P_1 ,P_2...P_n có điểm trong chung
3.Cho những cung C_1 ,C_2...C_n nằm trên đường tròn C và tổng độ dài của C_1 ,C_2...C_n lớn hơn C.Khi đó ít nhất 2 trong số những cung C_1 ,C_2...C_n có điểm trong chung
Mọi việc đều khởi đầu từ sự lắng nghe
Hình đại diện của thành viên
dungbaby
Thành viên nhiệt tình
Thành viên nhiệt tình
 
Bài viết: 236
Ngày tham gia: Thứ 7 Tháng 12 08, 2007 1:10 pm
Đến từ: Nghệ An

Re: Nguyên lý Dirichlet

Bài viết chưa xemgửi bởi dungbaby » Thứ 5 Tháng 2 14, 2008 7:31 am

I. Toán suy luận:
Bài 1: Trong lớp học có 30 học sinh. Khi viết chính tả em A phạm 14 lỗi, các em khác phạm ít lỗi hơn. CMR có ít nhất là 3 học sinh đã mắc số lỗi bằng nhau(kể cả những người mắc 0 lỗi )
Bài 2: Cho 5 người tùy ý. CMR trong số đó có ít nhất 2 người có số người quen như nhau trong số 5 người đã chọn (hiểu rằng A quen B thì B quen A)
Bài 3: Trong 1 giải bóng đá có 10 đội tham gia, bất cứ hai đội nào trong số đó cũng phải đấu với nhau 1 trận. CMR tại bất cứ thời điểm nào cũng có 2 đội đã đấu được cùng số trận.
II.Sự chia hết:
Bài 4: CMR trong 100 số tùy ý thì có ít nhất 10 số đôi một có hiệu chia hết cho 11.
Bài 5: CMR nếu (n,19)=1 thì luôn luôn tồn tại một số tự nhiên k khác 0 sao cho (n^k-1) \vdots 19.
Bài 6: CMR luôn tồn tại một số gồm toàn chữ số 7 chia hết cho 2121992.
Bài 7: Cho 20 số tự nhiên khác nhau a_1, a_2,...,a_{20} không vượt quá 70. CMR giữa các hiệu a_i-a_k (i>k) luôn tìm được ít nhất 4 hiệu bằng nhau.
III. Các vấn đề khác:
Bài 8: CMR tồn tại vô số số tự nhiên n sao cho trong dạng thập phân của S^n có ít nhất 2000 chữ số 0 đứng kề nhau.
Bài 9: Trong 2n số từ 1 đến 2n (n\geq 2) có thể lấy bao nhiêu số để tổng của hai số đã chọn (có thể bằng nhau ) không bằng số nào trong các số được chọn.
Bài 10: Cho dãy n số tự nhiên khác nhau. Từ dãy số đó lập các tổng 1 số hạng tùy ý.(trong mỗi tổng các số hạng đôi một khác nhau ). CMR có ít nhất \frac{n(n+1)}{2} các tổng không bằng nhau.
IV. Đánh giá các điểm, đường thẳng:
Bài 11: Trong hình chữ nhật 3.4 đặt 6 điểm.CMR trong các điểm này tìm được 2 điểm mà khoảng cách trong chúng không lớn hơn \sqrt{5}
Bài 12: Tô màu đỏ các cung của một đường tròn một cách tùy ý, biết rằng tổng độ dài các cung bị tô nhỏ hơn nửa chu vi đường tròn.
a, CMR luôn vẽ được 1 đường kính mà cả 2 đầu không bị tô màu.
b, CMR luôn tồn tại 1 dây cung của đường tròn có độ dài cho trước bé hơn đường kính mà 2 đầu của nó không bị tô.
V. Góc và độ dài:
Bài 13: Bên trong đường tròn bán kính n đặt 4n đoạn thẳng có độ dài 1.CMR có thể kẻ một đường thẳng song song hoặc vuông góc với đường thẳng 1 cho trước và cắt ít nhất 2 đoạn thẳng đã cho.
Bài 14: Bên trong hình vuông cạnh 1 đặt một số đường tròn có tổng độ dài bằng 10. CMR luôn tìm được 1 đường thẳng cắt ít nhất 4 trong số các đường tròn đã cho.
________________________________________

em thấy nhiều người còn chưa rõ lắm về nguyên lí này nên em post lên đây ạ :clap :clap :clap
Mọi việc đều khởi đầu từ sự lắng nghe
Hình đại diện của thành viên
dungbaby
Thành viên nhiệt tình
Thành viên nhiệt tình
 
Bài viết: 236
Ngày tham gia: Thứ 7 Tháng 12 08, 2007 1:10 pm
Đến từ: Nghệ An

Re: Nguyên lý Dirichlet

Bài viết chưa xemgửi bởi dungbaby » Thứ 5 Tháng 2 14, 2008 11:38 am

ai có vấn đề gì về nguyên lý này thì xin bổ sung vào đây ạ
nguyên lý Dỉichlet về định nghĩa tuy đơn giản dễ hiểu nhưng ứng dụng của nó lại rất nhiều, vấn đề cơ bản là phải nắm chắc về nó, năm vừa rồi đề thi vào trường Phan Bội Châu cũng có 1 bài diện tích cần dùng đến nguyên lí Dỉichlet
Mọi việc đều khởi đầu từ sự lắng nghe
Hình đại diện của thành viên
dungbaby
Thành viên nhiệt tình
Thành viên nhiệt tình
 
Bài viết: 236
Ngày tham gia: Thứ 7 Tháng 12 08, 2007 1:10 pm
Đến từ: Nghệ An

Re: Nguyên lý Dirichlet

Bài viết chưa xemgửi bởi nhoc93 » Thứ 5 Tháng 2 14, 2008 4:05 pm

mình ko hiểu lắm. Bạn có thể giải thích tỉ mỉ hơn đc ko?
***************************************
Hình ảnh
Hình đại diện của thành viên
nhoc93
Thành viên nhiệt tình
Thành viên nhiệt tình
 
Bài viết: 120
Ngày tham gia: Thứ 4 Tháng 9 26, 2007 10:25 am

Re: Nguyên lý Dirichlet

Bài viết chưa xemgửi bởi Ruby » Thứ 5 Tháng 2 14, 2008 4:42 pm

Chà, phổ thông đã học Nguyên lý Dirichletrồi cơ à? Theo những gì R được học thì Nguyên lý Dirichlet hay còn gọi là nguyên lý chuồng chim bồ câu, về nguyên lý thì phát biểu như trên thay thỏ bằng cách nhốt chim bồ câu vào lồng mà thôi.
Ứng dụng của nó khá rộng và áp dụng cho chứng minh như trên, nguyên lý này Ruby học trong môn Toán rời rạc
Còn nhoc93: em hiểu cũng được, còn chưa hiểu thì khoan hãy tìm hiểu đã, toán đại học chưa cần thiết cho bọn em nghiên cứu sâu đâu, đọc nguyên lý và ráng hiểu đã, còn áp dụng chứng mình thì thật sự không dễ đâu!
Nếu tụi em cần thì R sẽ post lên 1 số bài tập áp dụng nguyên lý này, cách chứng minh kèm theo luôn! Hoan nghênh tinh thần ham học hỏi. :clap
Aks me nothing and I will told you no lie

Hình ảnh
Hình đại diện của thành viên
Ruby
Thành viên nhiệt tình
Thành viên nhiệt tình
 
Bài viết: 289
Ngày tham gia: Thứ 6 Tháng 2 09, 2007 8:07 am
Đến từ: ..lề đường!

Re: Nguyên lý Dirichlet

Bài viết chưa xemgửi bởi funny » Thứ 6 Tháng 2 15, 2008 4:26 am

Hoan nghênh em Dung chăm chỉ post bài :)
@ Chị Ruby: cái này đội tuyển mới được học chị à:)
@ ku93: Nếu em có ý định thi chuyên toán hoặc thi HSG toán thì nên tìm hiểu cái nguyên lý này. Không thì từ từ sẽ được học (Như chị Ruby nói ý), cứ yên tâm, thi chuyên cũng ko đụng đến nó đâu. Nguyên lý này nó là kiểu xác xuất, khó hiểu cũng phải. Nếu làm BT thì cứ áp dụng cái định nghĩa mà làm.

Tổng quát của nguyên tắc Diricle nó như thế này (chỉ ngắn gọn hơn một chút thôi!):
Nếu nhốt a con thỏ vào b cái lồng mà a= b*q +r (0< r <b) thì ít nhất cũng có một cái lồng nhốt từ q + 1 con thỏ trở lên.
Vấn đề khi làm bài là xác định được "số thỏ" và "số lồng"

VD: Cm rằng trong 11 số tự nhiên bất kỳ bao giờ cũng có ít nhất 2 số có chữ số tận cùng giống nhau.
Phân tích: 11 số là 11 "con thỏ", Có 10 chữ số tận cùng là "10 cái lồng"
GIải: Ta có: 11=10*1 + 1 => theo nguyên tắc Diricle thì ít nhất cũng có 2 số có chữ số tận cùng giống nhau.
Hình đại diện của thành viên
funny
Thành viên nhiệt tình
Thành viên nhiệt tình
 
Bài viết: 194
Ngày tham gia: Thứ 3 Tháng 8 21, 2007 4:15 pm
Đến từ: Vũng Tàu

Re: Nguyên lý Dirichlet

Bài viết chưa xemgửi bởi dungbaby » Thứ 6 Tháng 2 15, 2008 4:50 am

nhoc93 đã viết:mình ko hiểu lắm. Bạn có thể giải thích tỉ mỉ hơn đc ko?

về nguyên lý Dirichlet thì ở cấp 2 nếu Nhật Anh ko thi chuyên toán thì cũng chưa cần biết lắm, tại vì ngay cả thi tỉnh cũng chưa có đâu, chỉ có thi trường chuyên thôi
không hiểu chỗ nào thì nói đi Dung giải thích cho, thực ra nêu định nghĩa thì dễ còn biết cách ứng dụng nó thì cần có kĩ năng và hiểu được cơ bản, giống như định lí ptôlêmê nổi tiếng: trong 1 tứ giác nội tiếp tích của 2 đường chéo bằng tổng tích các cặp cạnh đối, nghe đơn giản nhưng có rất nhiều ứng dụng, bạn có thể tìm đọc trong quyển Ẩn sau định lý ptôleme cũng hay
đề thi vào trường ĐHSP Vinh ở Nghệ An có năm ra bài như sau:
có tồn tại hay không số có dạng:
20022002....20022002 chia hết cho 2003
ta có thể giải:
có 2003 số: 2002
20022002
200220022002
....................
2002...2002
giả sử ko có số nào chia hết cho 2003, thì số dư có thể là 1,2,3,...,2002
có 2003 số mà chỉ có 2002 số dư nên tồn tại 2 số có cùng số dư khi chia cho 2003 nên hiệu của chúng chia hết cho 2003, tức là : 20022002...200210..00=2002..2002x10^k chia hết cho 2003
vì (2003; 10^k)=1 nên 2002...2002 chia hết cho 2003
Mọi việc đều khởi đầu từ sự lắng nghe
Hình đại diện của thành viên
dungbaby
Thành viên nhiệt tình
Thành viên nhiệt tình
 
Bài viết: 236
Ngày tham gia: Thứ 7 Tháng 12 08, 2007 1:10 pm
Đến từ: Nghệ An

Re: Nguyên lý Dirichlet

Bài viết chưa xemgửi bởi dungbaby » Thứ 6 Tháng 2 15, 2008 5:03 am

nhân tiện cho em hỏi luôn
em thấy rất ngán cái chuyên đề phần nguyên và dãy số, mà lại rất ít sách nói về nó, em mới tìm được 13 tính chất về phần nguyên, nhưng ngại post quá để hôm sau em post luôn, em thấy có sách nào nói về nó đều viết giống nhau cả không được gì thêm, ai có gì khác sách thì post giùm em tham khảo với
quyển sách Nâng cao&phát triển toán 9 cũng nói sơ sơ rồi đấy ạ, ai có gì khác giúp em với
Mọi việc đều khởi đầu từ sự lắng nghe
Hình đại diện của thành viên
dungbaby
Thành viên nhiệt tình
Thành viên nhiệt tình
 
Bài viết: 236
Ngày tham gia: Thứ 7 Tháng 12 08, 2007 1:10 pm
Đến từ: Nghệ An

Re: Nguyên lý Dirichlet

Bài viết chưa xemgửi bởi dungbaby » Chủ nhật Tháng 2 24, 2008 5:27 am

có 1 bài này nữa nè:
cho hình vuông ABCD có AB=14cm. Trong hình vuông có đánh dấu 76 điểm phân biệt. Chứng minh rằng tồn tại một đường tròn có bán kính 2cm chứa trong nó ít nhất 4 điểm trong số các điểm trên
Mọi việc đều khởi đầu từ sự lắng nghe
Hình đại diện của thành viên
dungbaby
Thành viên nhiệt tình
Thành viên nhiệt tình
 
Bài viết: 236
Ngày tham gia: Thứ 7 Tháng 12 08, 2007 1:10 pm
Đến từ: Nghệ An

Re: Nguyên lý Dirichlet

Bài viết chưa xemgửi bởi Ruby » Chủ nhật Tháng 3 02, 2008 3:54 am

1 số nội dung cơ bản để mọi nguời dễ hiểu về nguyên lý này:
Nguyên lý Dirichlet thường dùng nhắm trả lời cho câu hỏi: Có tồn tại 1 phần tử thoả tính chất cho trước hay không? Khi áp dụng thành công nguyên lý này chỉ ra rằng đối tượng tồn tại; tuy nhiên không chỉ ra cách tìm nó như thế nào và có bao nhiêu phần tử tồn tại.
1> Dạng đầu tiên của nguyên lý chuồng chim bồ câu khẳng định rằng nếu có n vật cần cần xếp vào k hộp và n>k thì có ít nhất có 1 hộp chứa 2 hoặc nhiều hơn hai vật. Lý do khẳng định này đúng có thể chứng minh bằng phản chứng: Nếu kết luận là sai, mỗi hộp chứ nhiều nhất 1 vật và do đó trong trường hợp này có nhiều nhất k vật, nhưng có n vật nên n<=k là vô lý.VD1: Số các học viên của một lớp học ít nhất là bao nhiêu để có ít nhất 2 học viên có số điểm như nhau trong kỳ thi môn Toán rr, nếu dự định thang điểm là 0-10?
 Có 11 thang điểm, theo nguyên lý chuồng chim bồ câu, cần có ít nhất 11+1=12 học viên
2> Dạng thứ 2 cùa nguyên lý này: Nếu f là ánh xạ từ tập hữu hạn X đến tập hữu hạn Y và #X>#Y thì tồn tại x1,x2 thuộc X, x1khác x2/ f (x1)=f(x2)
VD2:Nếu 20 bộ vi xử lý được nối với nhau thì có ít nhất 2 bộ vi xử lý được nối trực tiếp tới cùng các bộ vi xử lý?
 Ký hiệu các bộ vi xử lý là 1,2,…,20. Đặt ai là số các bộ vi xử lý được nối trực tiếp với bộ cvi xử lý I, chúng ta cần chứng minh rằng ai=aj, với i khác j nào đó, miền xác định và miền giá trị của A tương ứng là X:={1,2,…,20} và Y:={0,1,…,9}. Tuy nhiên #X = #{0,1,..,19} nên không áp dụng trực tiếp nguyên lý chim bồ câu dạng 2 được.
VD2’: Chứng mình rằng nếu chọn 151 giáo trình máy tính phân bịêt được đánh số thứ tự từ 1 đến 300 thì có ít nhất 2 giáo trình có số thứ tự liên tiếp?
3> Dạng thứ 3: Cho f là ánh xạ từ tập hữu hạn X đến tập hữu hạn Y. Giả sử n:=#X, m:=#Y, k:=[n/m]. Khi đó tồn tại ít nhất k giá trị n1,n2…nk sao cho:
f(a1)=f(a2)=…=f(ak)

VD3: Số học viên tối thiểu là bao nhiêu để đảm bảo ít nhất có 6 người cùng thang điểm, nếu giáo viên cho điểm theo thang điểm A, B, C, D, E, F?
Aks me nothing and I will told you no lie

Hình ảnh
Hình đại diện của thành viên
Ruby
Thành viên nhiệt tình
Thành viên nhiệt tình
 
Bài viết: 289
Ngày tham gia: Thứ 6 Tháng 2 09, 2007 8:07 am
Đến từ: ..lề đường!

Re: Nguyên lý Dirichlet

Bài viết chưa xemgửi bởi dungbaby » Thứ 5 Tháng 3 20, 2008 1:16 pm

VD3: Số học viên tối thiểu là bao nhiêu để đảm bảo ít nhất có 6 người cùng thang điểm, nếu giáo viên cho điểm theo thang điểm A, B, C, D, E, F?

bài này thì số học sinh tối thiểu em nghĩ là 31 vì có 6 thang điểm mà có 31 người nên tồn tại 6 người có số điểm bằng nhau
Mọi việc đều khởi đầu từ sự lắng nghe
Hình đại diện của thành viên
dungbaby
Thành viên nhiệt tình
Thành viên nhiệt tình
 
Bài viết: 236
Ngày tham gia: Thứ 7 Tháng 12 08, 2007 1:10 pm
Đến từ: Nghệ An

Trang kế tiếp

Quay về Toán cho Vật lý

Ai đang trực tuyến?

Đang xem chuyên mục này: Không có thành viên nào đang trực tuyến2 khách