Cho 40 cột đèn và 35 trạm điện được kết nối với nhau bởi 1 máy

* Hướng dẫn giải

Ta xét một cách kết nối máy tính giữa cột đèn và trạm điện thoả mãn đề bài như sau: Với 35 cột đèn đầu tiên mỗi cột kết nối với một trạm; với 5 cột đèn còn lại, mỗi cột kết nối với tất cả 35 trạm. Số máy cần dùng để kết nối là: MT = 35 + 35 x 5 = 210. Ta sẽ chỉ ra rằng nếu số máy tính nhỏ hơn 210 thì không thoả mãn điều kiện đã cho.Thật vậy, do MT < 210 nên có ít nhất một trạm điện x nào đó được kết nối với không quá 5 cột đèn. Suy ra có 40 cột đèn mà trong số ấy có cột nào đó không được kết nối với máy tính x , nghĩa là cột đó không thể nào đồng thời sáng được. Kết luận: Số máy tính ít nhất cần dùng là 210