Question

[Nguyễn Thanh Phong]

2. Có 20 người gặp nhau. Một số trong họ bắt tay nhau. Chứng minh rằng có 2 người có số cái bắt tay giống nhau.

Answer 1

[Lê Song Phương]

 Một người có thể bắt tay tối đa với \(0,1,2,...,19\) người khác.  Nhưng nếu có người bắt tay với 0 người thì sẽ không thể có người bắt tay với 19 người. Ngược lại, nếu có người bắt tay với 19 người thì sẽ không có ai bắt tay với 0 người. 

 Do đó, số các số cái bắt tay khác nhau có thể xảy ra là 19. Nhưng do có 20 người nên theo nguyên lí Dirichlet, chắc chắn sẽ tồn tại 2 người có số cái bắt tay là như nhau.