Câu hỏi 9
Bạn được tặng một $n$-GON thông thường. Mỗi đỉnh được đánh dấu $+1$ hoặc $-1$. Một động thái bao gồm việc thay đổi dấu hiệu của tất cả các đỉnh tạo thành $k$-GON thông thường cho một số $1 \lt k \leq n$. [Một $2$-GON thông thường có nghĩa là hai đỉnh có tâm của $n$-GON là điểm giữa của chúng.] Ví dụ, nếu chúng ta gắn nhãn các đỉnh của một thông thường $6$-GON $1, 2, 3, 4, 5, 6$, sau đó bạn có thể thay đổi dấu hiệu của $\{1, 4\}$, $\{2, 5\}$, $\{3, 6\}$, $\{1, 3, 5\}$, $\{2, 4, 6\}$ hoặc $\{1, 2, 3, 4, 5, 6\}$. Chỉ ra rằng đối với (1) $n = 15$, (2) $n = 30$, (3) bất kỳ $n \gt 2$ nào, chúng ta có thể tìm thấy một số dấu ban đầu không thể thay đổi thành tất cả $+1$ bằng bất kỳ chuỗi các bước di chuyển. Cho $f(n)$ là số lượng dấu hiệu lớn nhất, để không ai có thể lấy được từ bất kỳ người nào khác bằng bất kỳ chuỗi di chuyển nào. Hiển thị rằng $f(200) = 2^{80}$.