Tìm kiếm
Nam
"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.$$
