Một tòa nhà có $n$ tầng, các tầng được đánh số từ 1 đến $n$ theo thứ tự từ dưới lên. Có 4 thang máy đang ở tầng 1. Biết rằng mỗi thang máy có thể dừng ở đúng 3 tầng (không kể tầng 1) và 3 tầng này không là 3 số nguyên liên tiếp, đồng thời: với hai tầng bất kỳ của tòa nhà luôn có một thang máy dừng được ở cả hai tầng này. Hỏi giá trị lớn nhất của $n$ là bao nhiêu?

Gọi tập hợp các tầng của tòa nhà (không tính tầng 1) là $F = \{2; 3; \dots; n\}$. Số phần tử của tập hợp $F$ là $|F| = n - 1$. Theo giả thiết, mỗi thang máy dừng ở đúng 3 tầng thuộc $F$. Do đó, mỗi thang máy có thể giúp hành khách di chuyển giữa tối đa $\binom{3}{2} = 3$ cặp tầng khác nhau. Vì có 4 thang máy, tổng số cặp tầng tối đa mà các thang máy có thể phục vụ kết nối chéo là: $$4 \times 3 = 12\text{ (cặp tầng)}$$ Mặt khác, đề bài yêu cầu với hai tầng bất kỳ của tòa nhà luôn có một thang máy dừng được ở cả hai tầng này. Do tất cả các thang máy đều đỗ ở tầng 1 nên các cặp tầng chứa tầng 1 đã luôn được thỏa mãn. Đối với các cặp tầng thuộc tập $F$, tổng số cặp tầng cần được kết nối là $\binom{n-1}{2}$. Từ đó, ta có điều kiện cần để thỏa mãn bài toán: $$\binom{n-1}{2} \le 12 \Leftrightarrow \frac{(n-1)(n-2)}{2} \le 12 \Leftrightarrow (n-1)(n-2) \le 24$$ Ta thử các giá trị nguyên của $n$: - Nếu $n = 7$: $(7-1)(7-2) = 6 \times 5 = 30 > 24$ (không thỏa mãn). - Nếu $n = 6$: $(6-1)(6-2) = 5 \times 4 = 20 \le 24$ (thỏa mãn điều kiện cần). Với $n = 6$, có thể bố trí bốn thang máy thỏa mãn mọi yêu cầu của đề bài (mỗi thang dừng ở đúng 3 tầng không liên tiếp trong số các tầng $2, 3, 4, 5, 6$, sao cho mọi cặp tầng đều được ít nhất một thang máy phục vụ), nên điều kiện cần cũng là điều kiện đủ. Vậy giá trị lớn nhất của $n$ là $6$.