Question

[Minh Nguyễn]

Trong một cuộc họp có 10 người. CMR: Luôn tìm được 2 người có số người quen trong số dự họp là như nhau (Áp dụng nguyên lý Dirichlet)

Answer 1

[Akai Haruma]

Lời giải:

Trong cuộc họp không thể đồng thời có người quen $0$ người (không quen biết ai cả) và có người quen $9$ người (quen hết). Do đó số người quen của mỗi người trong cuộc họp có thể rơi vào các giá trị $0,1,...,8$ hoặc $1,2,...,9$. Tóm lại, số người quen biết của mỗi người trong cuộc họp có thể là 1 trong 9 giá trị (tương ứng có 9 nhóm)

Theo nguyên lý Dirichlet, tồn tại ít nhất $\left[\frac{10}{9}\right]+1=2$ người có cùng số người quen.