Câu hỏi 76
Trên một mặt phẳng ở Camelot, Vua Arthur xây một mê cung $\mathfrak{L}$ gồm $n$ bức tường, mỗi bức tường là một đường thẳng vô hạn. Không có hai bức tường nào song song và không có ba bức tường nào có điểm chung. Sau đó Merlin sơn toàn bộ một mặt của mỗi bức tường màu đỏ và mặt còn lại màu xanh.
Tại giao điểm của hai bức tường có bốn góc: hai góc đối đỉnh nhau tại đó một mặt đỏ và một mặt xanh gặp nhau, một góc tại đó hai mặt đỏ gặp nhau, và một góc tại đó hai mặt xanh gặp nhau. Tại mỗi giao điểm như vậy có một cánh cửa hai chiều nối hai góc đối đỉnh mà tại đó các mặt khác màu gặp nhau.
Sau khi Merlin sơn xong các bức tường, Morgana đặt một số hiệp sĩ vào mê cung. Các hiệp sĩ có thể đi qua các cánh cửa nhưng không thể đi xuyên qua tường.
Gọi $k(\mathfrak{L})$ là số $k$ lớn nhất sao cho, dù Merlin sơn mê cung $\mathfrak{L}$ như thế nào, Morgana luôn có thể đặt ít nhất $k$ hiệp sĩ sao cho không có hai hiệp sĩ nào có thể gặp nhau. Với mỗi $n$, hãy tìm tất cả các giá trị có thể của $k(\mathfrak{L})$, trong đó $\mathfrak{L}$ là một mê cung gồm $n$ bức tường.
Tại giao điểm của hai bức tường có bốn góc: hai góc đối đỉnh nhau tại đó một mặt đỏ và một mặt xanh gặp nhau, một góc tại đó hai mặt đỏ gặp nhau, và một góc tại đó hai mặt xanh gặp nhau. Tại mỗi giao điểm như vậy có một cánh cửa hai chiều nối hai góc đối đỉnh mà tại đó các mặt khác màu gặp nhau.
Sau khi Merlin sơn xong các bức tường, Morgana đặt một số hiệp sĩ vào mê cung. Các hiệp sĩ có thể đi qua các cánh cửa nhưng không thể đi xuyên qua tường.
Gọi $k(\mathfrak{L})$ là số $k$ lớn nhất sao cho, dù Merlin sơn mê cung $\mathfrak{L}$ như thế nào, Morgana luôn có thể đặt ít nhất $k$ hiệp sĩ sao cho không có hai hiệp sĩ nào có thể gặp nhau. Với mỗi $n$, hãy tìm tất cả các giá trị có thể của $k(\mathfrak{L})$, trong đó $\mathfrak{L}$ là một mê cung gồm $n$ bức tường.