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).
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).
Bắt đầu bởi NamUS, 13-10-2023 - 20:29
#2
Đã gửi 15-10-2023 - 00:14
Konstante
-
- Thành viên
-
- 104 Bài viết
Trung sĩ
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.
- perfectstrong và DOTOANNANG thích
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh
