Một chứng minh của định lí Fermat nhỏ

Trong bài này chúng tôi sẽ giới thiệu một chứng minh của định lí Fermat nhỏ, chứng minh này của Euler.

Định lí. Cho số nguyên tố $p$ và số nguyên $a$ không chia hết cho $p.$ Khi đó $a^{p-1}\equiv 1\pmod{p}.$

Chứng minh. Vì có hai trong các số $a^1,a^2,\ldots,a^p$ có cùng số dư khi chia cho $p$ nên tồn tại số nguyên dương $k$ sao cho $k<p$ và $a^{k}\equiv 1\pmod{p},$ chọn $k$ nhỏ nhất có tính chất này. Nếu $k=p-1$ thì ta có điều cần chứng minh, sau đây ta xét trường hợp $k<p-1.$ Continue reading “Một chứng minh của định lí Fermat nhỏ” →

Việt Nam TST 2020

Ngày thứ nhất

Bài 1. Cho trước $n>2$ là số nguyên dương và dãy số nguyên dương ${{a}_{1}}<{{a}_{2}}<\ldots <{{a}_{n}}$ . Trong các tập con của tập hợp $\{1,2,\ldots ,n\}$ , gọi $X$ là một tập sao cho $\left| \sum\limits_{i\notin X}{{{a}_{i}}}-\sum\limits_{i\in X}{{{a}_{i}}} \right|$ là nhỏ nhất. Chứng minh rằng tồn tại dãy số nguyên dương ${{b}_{1}}<{{b}_{2}}<\cdots <{{b}_{n}}$ sao cho $\displaystyle \sum\limits_{i\notin X}{{{b}_{i}}}=\sum\limits_{i\in X}{{{b}_{i}}}$ .

Bài 2. Cho tam giác $ABC$ nhọn, không cân nội tiếp đường tròn $(O)$ , có đường tròn nội tiếp $(I)$ tiếp xúc với các cạnh $BC,CA,AB$ lần lượt ở $D,E,F.$ Gọi $K,M,N$ lần lượt là trung điểm các cạnh $BC,CA,AB.$

1) Chứng minh rằng các đường thẳng qua $D,E,F$ lần lượt song song với $IK,IM,IN$ đồng quy.

2) Gọi $T,P,Q$ lần lượt là điểm chính giữa các cung lớn $BC,CA,AB$ của $(O).$ Chứng minh rằng đường thẳng qua $D,E,F$ và song song với $IT,IP,IQ$ cũng đồng quy.

Bài 3. Với số nguyên dương $n$ cho trước, xét một giải bóng đá có $4n$ đội bóng được tổ chức thi đấu với nhau qua các lượt trận. Ở mỗi lượt trận, người ta chia $4n$ đội bóng thành $2n$ cặp thi đấu với nhau. Biết rằng sau giải đấu thì hai đội bất kỳ đấu với nhau không quá một lần. Tìm số nguyên dương $a$ nhỏ nhất để có thể sắp xếp một lịch thi đấu gồm $a$ lượt trận thỏa mãn điều kiện trên và sau $a$ lượt thi đấu đó, với mọi cách chia các đội bóng thành $2n$ cặp thì luôn có ít nhất một cặp đã thi đấu với nhau.

Ngày thứ hai

Bài 4. Với $n$ là số nguyên dương, xét bảng ô vuông $(2n+1)\times (2n+1)$ và ban đầu, mỗi ô có tô màu trắng hoặc đen. Ở mỗi hàng và cột, nếu số ô trắng ít hơn số ô đen thì đánh dấu tất cả ô trắng (nếu có) và ngược lại; nếu số ô trắng nhiều hơn số ô đen thì đánh dấu tất cả ô đen. Gọi $a$ là số ô đen, $b$ là số ô trắng và $c$ là số ô được đánh dấu. Chứng minh rằng $\displaystyle c\ge \frac{\min \{a,b\}}{2}.$

Bài 5. Tìm tất cả các số nguyên dương $k$ sao cho tồn tại hữu hạn số nguyên dương $n$ lẻ thỏa mãn $n|{{k}^{n}}+1.$

Bài 6. Cho tam giác $ABC$ nhọn, không cân nội tiếp trong đường tròn $(O)$ có các đường cao $AD,BE,CF$ đồng quy tại trực tâm $H.$ Gọi $G$ là điểm đối xứng với $O$ qua $BC.$ Kẻ các đường kính $EK,FL$ theo thứ tự của các đường tròn $(GHE),(GHF).$

1) Giả sử $AK,AL$ lần lượt cắt $DE,DF$ ở $U,V.$ Chứng minh rằng $UV$ song song với $EF.$

2) Gọi $S$ là giao điểm hai tiếp tuyến của $(O)$ ở $B,C.$ Gọi $T$ là giao điểm của $DS,HG.$ Gọi $M,N$ là hình chiếu của $H$ lên các đường thẳng $TE,TF.$ Chứng minh rằng $M,N,E,F$ cùng thuộc một đường tròn.

Một chứng minh của định lí Pick

Hình tạo bởi một đường gấp khúc đóng và không tự cắt được gọi là đa giác đơn. Một tam giác cơ bản là một tam giác trong mặt phẳng tọa độ có các đỉnh là các điểm nguyên đồng thời trên biên và phần trong của nó không còn điểm nguyên nào khác. Định lí Pick cho một cách đơn giản tính diện tích đa giác đơn có các đỉnh nguyên.

Trong chứng minh định lí Pick ta cần dùng công thức tích diện tích của tam giác trong mặt phẳng tọa độ.

Định lí 1. Trong mặt phẳng tọa độ $Oxy$ , cho tam giác $ABC.$ Khi đó diện tích của tam giác $ABC$ bằng $\displaystyle \frac{1}{2}\left|(x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A)\right|.$ Nói riêng, với mỗi hai điểm $M$ và $N$ ta có diện tích của tam giác $OMN$ bằng $\dfrac{1}{2}\mid x_My_N-y_Mx_N\mid.$

Định lí 2. Mọi tam giác cơ bản đều có diện tích bằng $\dfrac{1}{2}.$

Chứng minh. Giả sử $TAB$ là một tam giác cơ bản bất kỳ. Không mất tính tổng quát, xem $T$ trùng với gốc tọa độ $O.$ Ta cần chứng minh $\mid x_1y_2-x_2y_1\mid =1,$ với $(x_1;y_1)$ và $(x_2;y_2)$ lần lượt là tọa độ của $A$ và $B.$

Gọi $K$ là điểm sao cho $OAKB$ là hình bình hành. Giả sử $M$ là một điểm nguyên nằm trong hoặc trên biên hình bình hành sao cho $M$ khác các đỉnh. Khi đó $M$ thuộc tam giác $ABK$ và điểm $N$ đối xứng với $M$ qua tâm hình bình hành là điểm nguyên thuộc tam giác $OAB$ nhưng khác các đỉnh, không thể xảy ra điều này do $OAB$ là một tam giác cơ bản. Như vậy hình bình hành $OAKB$ không chứa điểm nguyên nào khác bốn đỉnh của nó.

Giả sử $P$ là một điểm nguyên bất kỳ. Vì $\overrightarrow{OA}$ và $\overrightarrow{OB}$ là hai vector không cùng phương nên tồn tại cặp số thực $(\alpha,\beta)$ để $\overrightarrow{OP}=\alpha \overrightarrow{OA}+\beta \overrightarrow{OB}.$ Gọi $P'$ là điểm xác định bởi $\overrightarrow{OP'}=\{\alpha\} \overrightarrow{OA}+\{\beta\} \overrightarrow{OB}.$ Vì $\{\alpha\}$ và $\{\beta\}$ thuộc $[0;1)$ nên $P'$ thuộc hình bình hành $OAKB$ , nhưng $P'$ lại là một điểm nguyên, suy ra $P'$ phải là một trong bốn đỉnh của hình bình hành. Dễ thấy $P'\equiv O$ và do đó $\alpha$ và $\beta$ là hai số nguyên.

Gọi $\overrightarrow{i}$ và $\overrightarrow{j}$ lần lượt là các vector đơn vị đặt trên $Ox$ và $Oy$ . Khi đó theo lập luận trên, tồn tại các cặp số nguyên $(u,v)$ và $(u',v')$ để $\overrightarrow{i}=u \overrightarrow{OA}+v \overrightarrow{OB}$ và $\overrightarrow{j}=u' \overrightarrow{OA}+v' \overrightarrow{OB}.$ Từ hai đẳng thức này ta có $\begin{cases} 1=ux_1+vx_2\\ 0=uy_1+vy_2\end{cases}$ và $\begin{cases}0=u'x_1+v'x_2\\ 1=u'y_1+v'y_2,\end{cases}$ suy ra $\displaystyle u=\frac{y_2}{D},v=-\frac{y_1}{D},u'=-\frac{x_2}{D}$ và $\displaystyle v'=\frac{x_1}{D},$ trong đó $D=x_1y_2-x_2y_1\not =0$ do $O,A$ và $B$ không thẳng hàng. Vì $u,$ $v,$ $u'$ và $v'$ là các số nguyên nên $x_1,x_2,y_1$ và $y_2$ đều là bội của $D$ , do đó $D^2\mid D$ và bởi thế, $D=\pm 1.$

Định lí Pick. Cho $P$ là một đa giác đơn có các đỉnh là các điểm nguyên, $I$ là số điểm nguyên nằm trong và $B$ là số điểm nguyên nằm trên biên của $P$ . Khi đó ta có đẳng thức $\displaystyle S_P=I+\frac{1}{2}B-1.$

Chứng minh. Chia $P$ thành $N$ tam giác cơ bản. Gọi $S$ là tổng các góc trong của tất cả các tam giác cơ bản đó. Ta sẽ tính $S$ theo hai cách. Vì số tam giác là $N$ nên $S=N\pi.$

Tổng tất cả các góc có đỉnh là một điểm nguyên nằm trong $P$ bằng $2\pi$ , tổng tất cả các góc có đỉnh là một điểm nguyên nằm trên biên của $P$ nhưng không phải đỉnh của $P$ bằng $\pi$ và tổng của tất cả các góc có đỉnh là đỉnh của $P$ bằng $(n-2)\pi$ , ở đây $n$ là số đỉnh của $P$ . Do đó $S=2\pi I+\pi B-2\pi$ .

Suy ra $N\pi=2\pi I+\pi B-2\pi\Rightarrow N=2I+B-2$ , mà $S_P=\dfrac{1}{2}N$ , suy ra điều phải chứng minh.

APMO 2020

Olympic Toán học châu Á Thái Bình Dương (APMO) là cuộc thi toán học dành cho các quốc gia trong Khu vực Vành đai Thái Bình Dương.

APMO được tổ chức hàng năm. Mỗi quốc gia tham gia có một đại diện phụ trách tổ chức APMO tại địa phương. Một ủy ban chọn một đề thi với 5 câu hỏi được giải trong 4 giờ, gửi đáp án và biểu điểm và xác định các thi sinh đạt giải.

APMO được tổ chức lần đầu năm 1989. Các mục tiêu của nó là:

1) Phát hiện, khuyến khích và thử thách các học sinh trung học có năng khiếu toán.

2) Thúc đẩy quan hệ và hợp tác giữa học sinh và giáo viên trong khu vực.

3) Tạo cơ hội cho việc trao đổi thông tin về giáo trình ở các nhà trường.

4) Khuyến khích và hỗ trợ phong trào Olympic toán ở các nước tham gia và các nước khác trong khu vực.

Website chính thức của kỳ thi: http://www.apmo-official.org/.

Dưới đây là đề thi năm 2020.

Continue reading “APMO 2020” →

Đề thi chọn đội tuyển Hà Nội

Trong tài liệu này tôi sẽ giới thiệu một số đề thi chọn đội tuyển học sinh giỏi toán lớp 12 của Hà Nội, đội tuyển này sẽ tham dự kỳ thi chọn học sinh giỏi quốc gia cùng năm.

Download

USEMO – United States Ersatz Math Olympiad

USEMO là một cuộc thi toán dành cho tất cả học sinh trung học cơ sở và trung học phổ thông Hoa Kỳ. Giống như nhiều cuộc thi, mục tiêu của nó là phát triển sự quan tâm và khả năng trong toán học (chứ không phải là đo lường nó). Tuy nhiên, đây là một trong số ít các cuộc thi cho tất cả học sinh trung học cơ sở và trung học phổ thông Hoa Kỳ.

USEMO được lưu trữ trên trang AoPS. Cuộc thi này không được tài trợ bởi MAA.

Độ khó của các bài toán của cuộc thi tương tự như IMO.

Các bạn có thể tìm hiểu thêm về cuộc thi ở đây, hoặc download.

Sau đây là đề thi của USEMO lần thứ nhất.

USEMO 2019-2020

Ngày thứ nhất

Bài 1. Cho $ABCD$ là một tứ giác nội tiếp. Một đường tròn tâm $O$ qua $B$ và $D$ cắt lại $BA$ và $BC$ lần lượt tại $E$ và $F$ (khác $A,B,C$ ). Gọi $H$ là trực tâm của tam giác $DEF.$ Chứng minh rằng nếu $AC,$ $DO,$ $EF$ đồng quy thì hai tam giác $ABC$ và $EHF$ đồng dạng.
Bài 2. Tìm tất cả các ánh xạ $\theta : \mathbb{Z}[x] \to \mathbb{Z}[x]$ thỏa mãn đồng thời hai điều kiện
1) $\forall p, q \in \mathbb{Z}[x], \quad \theta(p + q) = \theta(p) + \theta(q)$ .
2) với mỗi $p \in \mathbb{Z}[x]$ , $p$ có nghiệm nguyên khi và chỉ khi $\theta(p)$ có nghiệm nguyên.
Bài 3. Xét một lưới vô hạn $\mathcal G$ các ô vuông đơn vị. Một đa giác bàn cờ là một đa giác đơn có các cạnh nằm dọc theo đường lưới của $\mathcal G.$
Nikolai chọn một đa giác bàn cờ $F$ và đố bạn tô một số ô của $\mathcal G$ màu xanh, sao cho bất kỳ đa giác bàn cờ nào bằng $F$ đều có ít nhất $1$ ô xanh nhưng nhiều nhất là $2020.$ Hỏi Nikolai có thể chọn $F$ để bạn không thể thực hiện được công việc?

Ngày thứ hai

Bài 4. Chứng minh rằng với mỗi số nguyên tố $p,$ tồn tại số nguyên dương $n$ sao cho $1^n+2^{n-1}+3^{n-2}+\cdots+n^1\equiv 2020\pmod{p}.$

Bài 5. Cho $\mathcal{P}$ là một đa giác đều và $\mathcal{V}$ là tập đỉnh của nó. Mỗi điểm trong $\mathcal{V}$ được tô màu đỏ, trắng hoặc xanh. Một tập hợp con của $\mathcal{V}$ được gọi là yêu nước nếu nó chứa một số điểm bằng nhau mang mỗi màu và một cạnh của $\mathcal{P}$ được gọi là chói nếu các đầu mút của nó có màu khác nhau.
Giả sử $\mathcal{V}$ yêu nước và số cạnh chói của $\mathcal{P}$ là chẵn. Chứng minh rằng tồn tại một đường thẳng không đi qua bất kỳ điểm nào trong $\mathcal{V}$ và chia $\mathcal{V}$ thành hai tập con yêu nước khác rỗng.
Bài 6. Cho $ABC$ là một tam giác nhọn với tâm đường tròn ngoại tiếp $O$ và các đường cao $AD$ , $BE$ , $CF$ . Gọi $X$ , $Y$ , $Z$ lần lượt là trung điểm của $AD$ , $BE$ , $CF$ . $AD$ cắt $YZ$ tại $P$ , $BE$ cắt $ZX$ tại $Q$ , $CF$ cắt $XY$ tại $R$ .
Giả sử $YZ$ cắt $BC$ tại $A'$ , $QR$ cắt $EF$ tại $D'$ . Chứng minh rằng các đường thẳng qua $A$ , $B$ , $C$ , $O$ lần lượt vuông góc với $QR$ , $RP$ , $PQ$ , $A'D'$ đồng quy.

Iran TST 2020 – Test 1

Ngày thứ nhất

Bài 1. Cho một đồ thị đủ có trọng số với các trọng số dương và đôi một khác nhau. Giả sử rằng mọi tam giác đều suy biến, nghĩa là trọng số của một cạnh bằng tổng hai trọng số của hai cạnh còn lại. Chứng minh rằng có thể gán số cho mỗi đỉnh của đồ thị này sao cho trọng số của mỗi cạnh bằng hiệu hai số được gán trên hai đầu mút của cạnh đó.
Bài 2. Cho tam giác $ABC$ với tâm đường tròn ngoại tiếp $O.$ Gọi $D,E$ lần lượt là các điểm nằm trên các cạnh $AC,AB.$ Lấy các điểm $P,Q,R,S$ nằm trên mặt phẳng sao cho $P,C$ và $R,C$ nằm về hai phía khác nhau của $AB$ , $Q,B$ và $S,B$ nằm trên hai phía khác nhau của $AC$ , và $R,S$ lần lượt thuộc $(DAP),(EAQ)$ , $\triangle BCE \sim \triangle ADQ , \triangle CBD \sim \triangle AEP$ , $\angle ARE=\angle ASD=\angle BAC$ . Chứng minh rằng nếu $RS|| PQ$ thì $RE ,DS$ cắt nhau trên $AO.$
Bài 3. Ta gọi số nguyên dương $n$ là tốt nếu với mỗi hoán vị $\sigma$ của $[n],$ tồn tại các đa thức $P_1,$ $P_2,\ldots ,$ $P_n$ với hệ số thực và $\epsilon > 0$ để các điều kiện sau được thỏa mãn đồng thời:
1) $P_1(0)=P_2(0)=\ldots =P_n(0).$
2) $P_1(x)>P_2(x)>\ldots >P_n(x)$ với $-\epsilon<x<0$ .
3) $P_{\sigma (1)} (x)>P_{\sigma (2)}(x)> \ldots >P_{\sigma (n)} (x)$ với $0<x<\epsilon$ .
Tìm tất cả số tốt.

Ngày thứ hai

Bài 4. Cho $g:[0,1] \to \mathbb{R}$ có tính chất: Với mọi cách chia đoạn $[0,1]$ thành hai tập khác rỗng $A$ và $B,$ $\exists x \in A,\, g(x) \in B$ hoặc $\exists x \in B,\, g(x) \in A$ và $g(x)>x$ với mọi $x \in [0,1].$ Chứng minh có vô hạn $x \in [0,1]$ để $g(x)=1.$
Bài 5. Cho số nguyên $k.$ Chứng minh rằng có vô hạn cặp số nguyên dương $(m,n)$ để $n+s(2n)=m+s(2m)$ và $kn+s(n^2)=km+s(m^2).$
Bài 6. Cho số nguyên dương $n$ và $n$ số dương. Liệu có thể tìm một $(n+3)-$ giác lồi và một cách tam giác hóa nó sao cho các đường kính trong phép tam giác hóa là $n$ số đã cho?

Công thức Popoviciu

Trong bài này chúng tôi sẽ giới thiệu một công thức tính số nghiệm tự nhiên của phương trình $ax+by=n,$ ở đây $a,b$ là các số nguyên dương thỏa mãn $(a,b)=1$ và $n$ là số tự nhiên.

Định lí. (Công thức Popoviciu) Gọi $N(a,b;n)$ là số các cặp số tự nhiên $(x,y)$ sao cho $ax+by=n$ , ở đây $a,b$ là các số nguyên dương thỏa mãn $(a,b)=1$ và $n$ là số tự nhiên. Khi đó

$\displaystyle N(a,b;n)=\frac{n}{ab}-\left\{\frac{a^{-1}n}{b}\right\}-\left\{\frac{b^{-1}n}{a}\right\}+1,$ với $a^{-1}$ là nghịch đảo modulo $b$ của $a$ và $b^{-1}$ là nghịch đảo modulo $a$ của $b$ .

Chứng minh. Gọi $\displaystyle F(z)=\sum_{n=0}^{+\infty}N(a,b;n)z^n$ là hàm sinh của dãy số $\{N(a,b;n)\}_{n\geq 0}$ . Ta có

$\displaystyle F(z)=\sum_{k\in\mathbb{N}}\sum_{l\in\mathbb{N}}z^{ak}z^{bl}=\frac{1}{(1-z^a)(1-z^b)}.\quad (1)$

Vì $(a,b)=1$ nên đa thức $(1-z^a)(1-z^b)$ có nghiệm là $1$ với bội $2$ và các nghiệm đơn $\xi_a^k$ $(k=1,2,\ldots,a-1)$ , $\xi_b^l$ $(l=1,2,\ldots,b-1)$ , ở đây $\xi_a=\cos\dfrac{2\pi}{a}+i\sin \dfrac{2\pi}{a}$ và $\xi_b=\cos\dfrac{2\pi}{b}+i\sin \dfrac{2\pi}{b}.$ Kết hợp với $(1)$ ta có tồn tại các số phức $C_1,C_2; A_i; B_i$ sao cho

$\displaystyle F(z)=\frac{C_1}{1-z}+\frac{C_2}{(1-z)^2}+\sum_{k=1}^{a-1}\frac{A_k}{1-\xi_a^{-k}z}+\sum_{l=1}^{b-1}\frac{B_l}{1-\xi_b^{-l}z}.\quad (2)$

Để ý đến hệ số của $z^n$ , từ $(2)$ ta có

$\displaystyle N(a,b;n)=C_1+C_2(n+1)+\sum_{k=1}^{a-1}A_k\xi_a^{-nk}+\sum_{l=1}^{b-1}B_l\xi_b^{-nl}.\quad (3)$

Bây giờ ta sẽ đi tìm các số phức $C_1,C_2; A_i; B_i$ từ đẳng thức

$\displaystyle \frac{1}{(1-z^a)(1-z^b)}=\frac{C_1}{1-z}+\frac{C_2}{(1-z)^2}+\sum_{k=1}^{a-1}\frac{A_k}{1-\xi_a^{-k}z}+\sum_{l=1}^{b-1}\frac{B_l}{1-\xi_b^{-l}z}.\quad (4)$

Nhân hai vế của $(4)$ với $(1-z)^2$ và cho $z\to 1$ ta có $C_2=\dfrac{1}{ab}$ , sau đó nhân hai vế của $(4)$ với $1-z$ , để $C_1$ một bên và cho $z\to 1$ ta được $C_1=\dfrac{a+b-2}{2ab}$ . Theo cùng một cách ta có

$\displaystyle A_k=\frac{1}{a(1-\xi_a^{kb})},\quad B_l=\frac{1}{b(1-\xi_b^{la})}.$

Thay vào $(3)$ ta được

$\displaystyle N(a,b;n)=\frac{n}{ab}+\frac{a+b}{2ab}+\frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{bk}}+\frac{1}{b}\sum_{l=1}^{b-1}\frac{\xi_b^{-nl}}{1-\xi_b^{al}}.\quad (5)$

Từ $(5)$ ta có $\displaystyle N(a,1;n)=\frac{n}{a}+\frac{a+1}{2a}+\frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{k}}$ , mà $\displaystyle N(a,1;n)=\left[\frac{n}{a}\right]+1$ , suy ra

$\displaystyle \frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{k}}=\frac{1}{2}-\left\{\frac{n}{a}\right\}-\frac{1}{2a},$

do đó $\displaystyle \frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{bk}}=\frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nb^{-1}k}}{1-\xi_a^{k}}=\frac{1}{2}-\left\{\frac{nb^{-1}}{a}\right\}-\frac{1}{2a},$

chứng minh tương tự ta được

$\displaystyle \frac{1}{b}\sum_{l=1}^{b-1}\frac{\xi_b^{-nl}}{1-\xi_b^{al}}=\frac{1}{2}-\left\{\frac{na^{-1}}{b}\right\}-\frac{1}{2b},$

thay hai đẳng thức cuối cùng vào $(5)$ ta có điều cần chứng minh. $\Box$

Một số trang về Olympic Toán

Tôi có post một số trang về Olympic Toán trên facebook nhưng nó cứ chìm xuống khi đăng một bài khác, vì thế nên tôi lập topic này để lưu các link đó lại.

P. S. Hãy góp link bằng cách comment các bạn nhé! 🙂

Continue reading “Một số trang về Olympic Toán” →

Burnside’s lemma

Cho $X$ là một tập hợp và $G$ là một nhóm. Ta nói $G$ tác động trên $X$ , hay $X$ là một $G-$ tập, nếu có hàm $G\times X\to X$ , $(g,x)\mapsto gx$ thoả mãn $ex=x\forall x\in X$ và $g_1(g_2x)=(g_1g_2)x\forall x\in X\forall g_1,g_2\in G$ , ở đây $e$ là phần tử đơn vị của $G$ .

Gìơ ta xét một $G-$ tập $X$ , với mỗi $x\in X$ , ta gọi quỹ đạo của $x$ là tập $\{gx|g\in G\}$ . Các quỹ đạo khác nhau của các phần tử trong $X$ làm thành một phân hoạch của $X$ , thật vậy, quan hệ $xRy$ nếu có $g\in G$ để $x=gy$ là một quan hệ tương đương trên $X$ . Khi $X$ và $G$ là các tập hữu hạn thì ta có thể tính số khối của phân hoạch này theo bổ đề sau đây.

Bổ đề Burnside. Nếu $X$ là một $G-$ tập hữu hạn (nghĩa là $X$ và $G$ là các tập hữu hạn và $X$ là một $G-$ tập) và $N$ là số các quỹ đạo khác nhau của các phần tử trong $X$ thì $N=\dfrac{1}{|G|}\sum_{g\in G}F(g)$ , trong đó với mỗi $g\in G$ , $F(g)$ là số phần tử của tập $\{x\in X|gx=x\}$ .

Tôi sẽ không đưa ra chứng minh nào của bổ đề này ở đây, các bạn có thể tìm một chứng minh trong sách Tổ hợp của Ngô Đắc Tân hay sách về lý thuyết nhóm của Rotman. Gìơ ta đi xét các áp dụng của bổ đề này vào giải các bài toán đếm, các bài tập này đều có trong sách của Rotman.

Bài 1. Cho $n$ và $q$ là các số nguyên dương. Hỏi có bao nhiêu lá cờ gồm $n$ mảnh sao cho mỗi mảnh mang một trong $q$ màu cho trước?(Ví dụ một lá cờ như vậy là cờ của Pháp gồm $3$ mảnh).

Lời giải. Vì khi ta tô màu một mặt của lá cờ thì mặt sau sẽ được xác định hoàn toàn màu. Nên số lá cờ bằng số cách tô bảng $1\times n$ bởi $q$ màu, hai cách tô là như nhau nếu nó ở dạng như hình dưới đây.

(Trong hình trên các $c_i$ là các màu.)

Gọi $X$ là tập các bộ $(c_1,c_2,\cdots,c_n)$ với $c_i$ là một trong $q$ màu đã cho với mỗi $i$ . Ký hiệu $S_n$ là nhóm các hoán vị trên $\{1,2,\cdots,n\}$ , $G$ là nhóm con cyclic sinh bởi hoán vị $f$ của $S_n$ , ở đây $f(i)=n+1-i\forall i$ . Ta cho $G$ tác động trên $X$ theo luật $f(c_1,c_2,\cdots,c_n)=(c_n,c_{n-1},\cdots,c_1)$ . Như trên đã phân tích, ta chỉ cần đếm số $N$ các quỹ đạo của các phần tử của $x$ theo tác động này là xong. Theo bổ đề Burnside, ta chỉ cần tính $F(id)$ và $F(f)$ . Dễ thấy $F(id)=|X|=q^n$ theo quy tắc nhân. Để tính $F(f)$ , ta chú ý rằng $(c_1,c_2,\cdots,c_n)\in X$ không thay đổi khi tác động $f$ nếu và chỉ nếu $c_1=c_n,c_2=c_{n-1},\cdots$ , vậy cùng theo quy tắc nhân ta có $F(f)=q^{[\dfrac{n+1}{2}]}$ . Như thế đáp số của bài toán là $\dfrac{1}{2}(q^n+q^{[\dfrac{n+1}{2}]}).$

Bài 2. Cho $n$ và $q$ là các số nguyên dương. Chứng minh rằng có

$\dfrac{1}{4}(q^{n^2}+2q^{[\dfrac{n^2+3}{4}]}+q^{[\dfrac{n^2+1}{2}]})$ cách tô màu bảng vuông $n\times n$ bởi $q$ màu.

Lời giải sơ lược. Lời giải y hệt như trường hợp trên. Ta đánh số các ô của bảng theo kiểu xoáy ốc, chia hai trường hợp $n$ chẵn, lẻ cho dễ đánh số. Tập $X$ bây giờ là tập tất cả các bộ $(c_1,c_2,\cdots,c_{n^2})$ , nhóm $G$ bây giờ là nhóm con cyclic cấp $4$ sinh bởi phép quay $+90^0$ của $S_{n^2}$ .

Chú ý. Khi $n=3,q=n$ ta có bài số 5 trong VMO 2010.