đánh dấu số người là ai(i chạy từ 1->100)

Giả sử tồn tại a_j quen a_k nào đó

Khi đó a_i sẽ quen ít nhất 67 người khác.

a_j cũng sẽ quen ít nhất 67 người.

số người quen chung ít nhất của cả a_i và a_j là:67+67-100=34(người)

gỉa sử trong nhóm này không tồn tại 2 người nào đôi một quen nhau khi đó trong nhóm người này chỉ quen với tối đa:100-34=66(người) mà giả thuyết lại quen ít nhất là với 67 người.=>tồn tại ít nhất 2 người trong nhóm này quen nhau gọi là a_m,a_n.

Khi đó người a_i,a_j,a_m,a_n thỏa mãn đề bài :v 

P/s: Các câu này là trong các đề thi chuyên KHTN hồi lâu lắc rồi :v. Có gì bạn vào trang cá nhân vote sao cho mình nhé

1) Chứng minh bằng phản chứng giả sử không có một học sinh đứng cách hai bạn cùng lớp với mình một khoảng cách như nhau.

Đánh dấu số h/s đó lần lượt là: a1,a2,....a9

Giả sử: a5 là học sinh lớp B

=>a4,a6 không thể cùng là học sinh lớp B

Th1:a4,a6 cùng thuộc lớp A khi đó a2,a6 cách đều a4.

a4,a8 cách đều a6 và a8 thuộc lớp B nên hiển nhiên a5 sẽ cách đều a2 và a8 (trái với giả thuyết)

Th2:a4 ,a6 cùng thuộc một lớp khác nhau.

Kmttq giả sử: a4 lớp A,a6 lớp B

Do a4 cách đều a3,a5 nên a4 thuộc lớp B. Do a6 cách đều a3 và a9 nên a9 thuộc lớp A.a5 cách đều a1 và a9 nên a1 thuộc lớp B....

tương tự như vậy hiển nhiên có:a7 đứng cách đều hai bạn cùng lớp A là a5,a9.(trái với giả thuyết)