: Trong một căn phòng có 25 người. Chứng minh rằng trong 25 người đó luôn có ít nhất 2 người có số người quen như nhau (kể cả quen 0 người).
Trong phòng có 100 người,mỗi người quen ít nhất 67 người khác. chứng minh rằng chắc chắn tìm được 4 người mà 2 người bất kì trong số đó quen nhau
Xét A là 1 người bất kỳ trong phòng
\(\Rightarrow\)A quen ít nhất người
Nếu ta mời những người không quen A ra ngoài thì số người ra nhiều nhất là
Trong phòng còn lại người. \(\Rightarrow\)gọi là 1 người quen \(\Rightarrow\) có nhiều nhất người B không quen trong phòng
\(\Rightarrow\) số nguời còn lại là \(\Rightarrow\)gọi là 1 người quen và \(\Rightarrow\) không quen nhiều nhất người trong phòng
\(\Rightarrow\)trong phòng còn lại 4 người \(\Rightarrow\)ngoài A,B,C còn 1 người giả sử là D,khi đó A,B,C,D đôi 1 quen nhau(đpcm)
Chứng minh rằng trong n người bất kì (n≥2), tồn tại hai người có số người quen như nhau ( kể cả trường hợp quen 0 người )
Lời giải:
Số người quen của 1 người có thể chạy từ $0$ đến $n-1$ người.
Tuy nhiên, nếu 1 người quen 0 người thì sẽ không có ai trong số những người còn lại quen $n-1$ người và ngược lại, nếu 1 người quen $n-1$ người thì sẽ không có ai trong số những người còn lại quen $0$ người.
Tức là, Số người quen của 1 người trong nhóm $n$ người đó có thể chạy từ $0$ đến $n-2$, hoặc từ $1$ đến $n-1$
Coi đây như những chiếc lồng thỏ, thì có $n-1$ lồng.
Có $n$ người.
Theo nguyên lý Dirichlet, tồn tại $[\frac{n}{n-1}]+1=2$ người có số người quen giống nhau.
Ta có đpcm.
Một nhóm học sinh gồm 35 người chơi ở công viên trong đó có những người quen nhau và những người không quen nhau. Chứng minh rằng có ít nhất một người có số người quen trong nhóm là số chẵn.
chứng minh rằng trong n người bất kỳ ( n lớn hơn hoặc bằng 2 ) , tồn tại hai người có cùng số người quen như nhau ( kể cả trường hợp quen 0 người )
Vì quan hệ quen biết có tính chất 2 chiều: Nếu a quen b thì b quen a
Ta chia n người đã cho vào n nhóm:
+Nhóm 0: Gồm những người có số người quen là 0 ( ko quen ai trong số n-1 người còn lại)
+Nhóm 1: Gồm những người có số người quen là 1
+Nhóm 2: Gồm những người có số người quen là 2
.....................
+Nhóm n-1: gồm những người có số người quen là n-1 ( quen cả n-1 người còn lại)
Ta thấy nhóm 0 và nhóm n-1 ko đồng thời xảy ra vì nếu cóa người quen cả n-1 người còn lại thì ko thể có người nào ko quen ai trong n-1 người còn lại
Như vậy có n người (n\(\geq\)2) mà chỉ có nhiều nhất n-1 nhóm đó là: Nhóm 0;1;2;...;n-2 hoặc nhóm 1;2;3;...;n-1. Nên phải tồn tại ít nhất 2 người cùng 1 nhóm
Tức là tồn tại ít nhất 2 người có số người quen như nhau. (ĐPCM)
k and kb nha!!!!!
trong phòng họp có 100 người, mỗi người quen ít nhất 67 người còn lại. chứng minh chắc chắn tìm được 4 người mà 2 người bất kì trong số đó đều quen nhau
trong phòng họp có 100 người, mỗi người quen ít nhất 67 người còn lại. chứng minh chắc chắn tìm được 4 người mà 2 người bất kì trong số đó đều quen nhau
Do trong phòng có 100 người, mỗi người quen it nhất 67 người còn lại nên số người mà người đó không quen nhiều nhất là:
100-67-1= 32( người)
Ta giả sử 1 người bất kỳ trong 100 người đó là A. Nếu ta loại những người mà A không quen ra khỏi phòng thì trong phòng sẽ còn ít nhất 68 người( trong đó có A).
Ta lại giả sử 1 trong 68 người còn lại trong phòng( khác A) là B. Nếu ta loại đi những người mà B không quen ra khỏi phòng thì trong phòng sẽ còn ít nhất 68-32=36( người) trong đó có A và B.
............................. 36......................................(khác A,B) là C.............................................C................................................
.....................................36-32=4( người) trong đó có A,B và C.
Trong 4 người còn lại ta giả sử người khác A,B,C là D thì khi đó trong phòng có 4 người: A,B,C và D suy ra A,B,C,D đôi một quen nhau. Do đó tìm được 4 người mà 2 người bất kì trong số đó đều quen nhau( đpcm)
Trong một lớp học có ít nhất 2 bạn quen nhau. Biết rằng nếu hai bạn có cùng một số lượng người quen thì không có người quen chung. Chứng minh rằng trong lớp có bạn chỉ quen có đúng 1 người.
áp dụng tính châts sơn tùng vẽ nên thôi thì có đpcm
trong phòng họp có 100 người, mỗi người quen ít nhất 67 người còn lại. chứng minh chắc chắn tìm được 4 người mà 2 người bất kì trong số đó đều quen nhau
Trong một lớp học có ít nhất hai bạn quen nhau. Biết rằng nếu hai bạn có cùng một số lượng người quen thì không có người quen chung. Chứng minh rằng trong lớp có bạn chỉ quen đúng một người.