Câu hỏi 9
Alice và Bob đang ở trong một cửa hàng phần cứng. Cửa hàng bán các loại tay áo màu vừa vặn để phân biệt chúng. Cuộc trò chuyện sau đây diễn ra: Alice: Bạn có định che chìa khóa của mình không? Bob: Tôi muốn, nhưng chỉ có 7 màu và tôi có 8 phím. ALICE: Có, nhưng bạn luôn có thể phân biệt một phím bằng cách nhận thấy rằng chìa khóa màu đỏ bên cạnh phím màu xanh lá cây khác với phím màu đỏ bên cạnh phím màu xanh lam. Bob: Bạn phải cẩn thận với ý của bạn khi "bên cạnh" hoặc "ba phím trên từ" vì bạn có thể lật vòng chìa khóa và các phím được sắp xếp thành một vòng tròn. Alice: Mặc dù vậy, bạn không cần 8 màu. Vấn đề: Số lượng màu nhỏ nhất cần thiết để phân biệt các phím $n$ là bao nhiêu nếu tất cả các phím được che phủ.