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 )
Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lờ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!!!!!
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)
Giả sử 6 người đó là A; B; C; D; E; F
Chọn một ngươì bất kì trong 6 người thì người đó quen hoặc không quen với mỗi người trong 5 người còn lại. Coi người đó là A
Trong 5 người còn lại, chắc chắn có ít nhất 3 người quen hoặc không quen A. Gọi 3 người đó là B; C; D
+) Trường hợp 1: A quen B; C; D.
Nếu B; C; D đôi một không quen nhau thì chọn luôn 3 người B; C; D
Nếu có 2 trong 3 người quen nhau , coi là B; C thì ta có 3 người A; B; C đôi một quen nhau
+) Trường hợp: A không quen B; C; D
Nếu B; C; D đôi một quen nhau ta chọn luôn 3 người B; C; D
Nếu 2 trong 3 người B; C không quen nhau ta có 3 người A; B; C không quen nhau
Vậy Trong 6 người bất kì, luôn chọn được 3 người quen hoặc không quen nhau
fghjklkjhgfdsdfghjkllllllllllkjhghjklkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllliiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiihhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
Gọi 6 người bất kì là A, B, C, D, E
Trong 6 người đó ta chọn ra một người A.Trong 5 người còn lại ta chia thành 2 nhóm:
+Nhóm 1 gồm những người quen A
+Nhóm 2 gồm những người ko quen A
Có 5 người mà chỉ có 2 nhóm\(\implies\)Tồn tại ít nhất 3 người thuộc cùng một nhóm.Tức là tồn tại ít nhất 3 người quen A hoặc tồn tại ít nhất 3 người ko quen A
⊛Nếu tồn tại ít nhất 3 người quen A. Gọi 3 người đó là B, C, D
+Nếu trong 3 người B, C, D có 2 người nào đó quen nhau.Giả sử 2 người đó là B và C thì ta có 3 người A, B, C là 3 người đôi một quen nhau
+Nếu trong 3 người B, C, D ko có 2 người nào đó quen nhau thì 3 người B, C, D là 3 người đôi một ko quen nhau
⊛Nếu tồn tại 3 người ko quen A.Giả sử 3 người đó là D, E, G
+Trong 3 người D, E, G nếu có 2 người nào đó ko quen nhau.Giả sử 2 người đó là D và E thì 3 người A, D, E là 3 người đôi một ko quen nhau
+Nếu trong 3 người D, E, G ko có 2 người nào ko quen nhau thì 3 người D, E, G là 3 người đôi một quen nhau
Vậy trong 6 người bất kì luôn tồn tại 3 người đôi một quen nhau hoặc 3 người đôi một ko quen nhau (ĐPCM)
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.