Giải bài toán thang máy

Nhiều độc giả đã giải đúng bài toán với đáp án tòa nhà có nhiều nhất 5 tầng. 

Đề bài:

Một tòa nhà chung cư có 4 thang máy. Mỗi thang máy có 3 điểm dừng tại các tầng trong đó tính cả tầng 1.

Với mỗi cặp 2 tầng bất kỳ, luôn có ít nhất 1 thang máy dừng ở cả 2 tầng đó.

Tính số tầng tối đa của tòa nhà?

Hướng dẫn giải:

Tất cả có 12 lần thang máy dừng.

Giả sử toà nhà có 6 tầng. Theo Nguyên lý Drichle luôn có tầng M nào đó mà nhiều nhất là 2 thang máy dừng ở M.

Mỗi thang máy kết nối tầng M với 2 tầng khác, do đó có nhiều nhất 4 trong số 5 tầng khác kết nối với tầng M.

Suy ra có ít nhất một tầng không kết nối với tầng M, loại.

Từ đó, nếu có lớn hơn 6 tầng thì không thể sắp xếp các thang máy thỏa mãn.

Do đó có nhiều nhất là 5 tầng.

Bây giờ ta chỉ ra một trường hợp 4 thang máy kết nối 5 tầng thoả mãn yêu cầu bài toán: Thang máy thứ nhất dừng ở các tầng (1, 4, 5); thang máy thứ hai dừng ở các tầng (2, 4, 5); thang máy thứ ba dừng ở các tầng (3, 4, 5) và thang máy thứ 4 dừng ở các tầng (1, 2, 3).