Question

[girl đẹp]

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 )

Answer 1

[Kade Phạm]

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!!!!!