nhoccoi

Bài 2:
Giả sử chỉ tìm được nhiều nhất 40 người, mỗi người quen nhiều nhất 1958 người khác:
Nghĩa là có ít nhất 1959 người, mỗi người quen ít nhât 1959 người khác
Khi đó, ta sẽ chỉ ra tồn tại 50 người trong 1959 người này đôi 1 quen biết nhau:
+) Xét 2 người bất kì, có ít nhất 1959*2- 1999 người quen chung
+) Xét 3 người, trong đó gồm 2 người nói trên và 1 người quen chung của 2 người đó, 3 người này có ít nhất 1959*2- 1999+ 1959_ 1999=1959* 3- 2*1999
......................
+)Xét như trên đến 49 người, có it nhất 1959* 49- 1999* 48= 39 người quen chung
Chọn bất kì 1 trong 39 người trên ta được 50 người đôi 1 quen biết nhau
=>mâu thuẫn