Chủ đề này có 1 trả lời

[hoangkimca2k2]

 Có bao nhiêu cách tô màu các đỉnh của n-đa giác đều bằng k màu sao cho 2 cách tô giống nhau là ảnh của nhau qua phép vị tự quay tâm đa giác. 

Bài viết đã được chỉnh sửa nội dung bởi hoangkimca2k2: 11-04-2024 - 23:14

[nmlinh16]

"Phép vị tự quay tam đa giác" nghĩa là gì? Tôi giả định câu hỏi ở đây là "phép quay một góc $\frac{2 i\pi}{n}$ quanh tâm đa giác, với $i \in \mathbb{Z}$".

 

Những bài đếm này giải bằng cách dùng bổ đề Burnside, tất nhiên có thể trình bày theo ngôn ngữ sơ cấp như sau.

 

Ký hiệu $S = S_k(n)$ là giá trị cần tìm, và xét bài toán mới:

Đánh số $n$ đỉnh của đa giác lần lượt là $1,2,\ldots,n$, và xét tập hợp $A = \{1,\ldots,k\}^n$ các bộ $(a_1,\ldots,a_n)$, với $a_i \in \{1,\ldots,k\}$. Với $1 \le i \le n$, ký hiệu $T_i: A \to A$ là ánh xạ cho bởi $T_i(a_1,\ldots,a_n) = (a_{i+1},\ldots,a_{i+n})$, ở phép cộng được hiểu là phép cộng modulo $n$ (nói cách khác là $T_i(a_1,\ldots,a_n) = (a_{i+1},a_{i+2},\ldots,a_n,a_1,\ldots,a_i)$.

Ta đếm số cặp $(a,i)$ thỏa mãn $a \in A$, $i \in \{1,\ldots,n\}$ và $T_i(a) = a$ theo hai cách.

 

Cách thứ nhất:

Với mỗi $a \in A$, gọi $O(a):=\{T_1(a),\ldots,T_n(a)\}$ là quỹ đạo của $a$. Dễ thấy hai phần tử $a,b \in A$ có cùng quỹ đạo khi và chỉ khi tồn tại $i \in \{1,\ldots,n\}$ sao cho $T_i(a) = b$. Số quỹ đạo chính là là $S$. Ta phân hoạch $A$ thành $S$ quỹ đạo phân biệt $A_1,\ldots,A_S$.

 

Mặt khác, ký hiệu $i_a \in \{1,\ldots,n\}$ là chỉ số $i$ nhỏ nhất sao cho $T_i(a) = a$ (một chỉ số $i$ như vậy tồn tại vì $T_n(a) = a$). Thế thì $T_j(a) = T_i(a)$ khi và chỉ khi $i_a | j-i$. Nói riêng, ta có $i_a | n$, $|O(a)| = i_a$, và số $s_a$ các chỉ số $i$ thỏa mãn $T_i(a) = a$ chính là $s_a = \frac{n}{i_a}$. Từ đó suy ra với mọi $j \in \{1,\ldots,S\}$, ta có $$\sum_{a \in A_j} s_a = |A_j| \cdot \frac{n}{|A_j|} = n.$$ Vậy số cặp $(a,i)$ cần tìm là $$\sum_{a \in A} s_a = \sum_{j=1}^S \sum_{a \in A_j} s_a = nS.$$

 

Cách thứ hai:

Với mỗi $i \in \{1,\ldots,n\}$, một phần tử $a = (a_1,\ldots,a_n) \in A$ thỏa mãn $T_i(a) = a$ khi và chỉ khi $a_{j+i} = a_j$ với mọi $j \in \{1,\ldots,n\}$ (phép cộng được hiểu là phép cộng modulo $n$). Nếu đặt $d = \gcd(i,n)$ thì điều này tương đương với $a_t = a_{d+t} = a_{2d+t} = \cdots = a_{n-d + t}$ với mọi $1 \le t \le d$. Vậy số phần tử $a \in A$ thỏa mãn $T_i(a) = a$ là $k^d = k^{\gcd(n,i)}$.

Với mỗi ước $d|n$, số chỉ số $i \in \{1,\ldots,n\}$ thỏa mãn $\gcd(n,i) = d$ là $\varphi\left(\frac{n}{d}\right)$, vì một chỉ số $i$ như vậy thì có dạng $dt$, với $t \in \left\{1,\ldots,\frac{n}{d} \right\}$ và nguyên tố cùng nhau với $\frac{n}{d}$. 

Vậy số cặp $(a,i)$ cần tìm là $$\sum_{i=1}^n k^{\gcd(n,i)} = \sum_{d|n} \varphi\left(\frac{n}{d}\right) k^d.$$

 

Kết luận: tổng cần tính ban đầu là $$S_k(n) = S = \frac{1}{n} \sum_{d|n} \varphi\left(\frac{n}{d}\right) k^d.$$

Bài viết đã được chỉnh sửa nội dung bởi nmlinh16: 11-04-2024 - 01:42