1 reply to this topic

[NamUS]

Có 2k trạm điện thoại sao cho mỗi trạm nối trực tiếp với k trạm khác. Chứng minh rằng bất kỳ 2 trạm nào cũng liên lạc được với nhau (trực tiếp hoặc qua trung gian các trạm khác).

[Konstante]

Xét 2 trạm bất kỳ, mỗi trạm nối với $k$ trạm khác, nên số các trạm nối trực tiếp từ 2 trạm này là $2k$, mà chỉ có $2k-2$ trạm khác hai trạm đã chọn. Theo nguyên tắc Dirichlet thì phải có ít nhất hai trạm trong số $2k$ trạm được nối trực tiếp là trùng nhau, do vậy hai trạm đã chọn ban đầu là liên lạc được với nhau qua trạm chung này.