Cấu trúc nhóm trong một số bài toán sơ cấp

Dành cho các bạn trẻ
LTS: "Dành cho các bạn trẻ" là mục dành cho Sinh viên, Học sinh và tất cả các bạn trẻ yêu
Toán. Tòa soạn mong nhận được các bài viết hoặc bài dịch có giá trị cho chuyên mục.
Cấu trúc nhóm trong một số
bài toán sơ cấp
Đoàn Trung Cường (Viện Toán học)
1. GIỚI THIỆU
Lý thuyết nhóm có nguồn gốc từ lý
thuyết số, lý thuyết các phương trình
đại số và từ hình học. Việc phát triển lý
thuyết nhóm đã dẫn tới sự ra đời của
đại số trừu tượng, lý thuyết biểu diễn và
nhiều ngành toán học mới khác. Ngày
nay, cấu trúc nhóm xuất hiện và có ứng
dụng trong hầu hết các lĩnh vực của toán
học, xuất hiện trong vật lý, hóa học.
Cấu trúc nhóm xuất hiện tự nhiên
trong các bài toán sơ cấp. Ví dụ đơn giản
nhất là các nhóm Z,Q,R,C với phép toán
+. Ví dụ ít hiển nhiên hơn là các nhóm
hữu hạn (nói chung không abel) xuất
hiện trong lý thuyết số, tổ hợp và đại số.
Trong bài này chúng tôi sẽ điểm lại một
vài ứng dụng của lý thuyết nhóm để giải
một số bài toán sơ cấp. Mặc dù các bài tập
minh họa đều có lời giải sơ cấp, chúng tôi
sẽ không tập trung trình bày các lời giải
này mà chủ yếu phân tích sự xuất hiện
các cấu trúc nhóm như thế nào.
2. MỞ ĐẦU VỀ NHÓM
Nhóm. Ta biết rằng phép cộng trên tập
các số nguyên Z thỏa mãn các tính chất
kết hợp, có phần tử trung hòa (phần tử 0)
và mọi phần tử đều có phần tử đối (phần
tử đối của 𝑛 là −𝑛). Ta gọi tập Z cùng với
phép cộng là một nhóm.
1
Một ví dụ khác là nhóm đối xứng. Cho
𝑛 ∈ N và xét 𝑋 = {1, 2, . . . , 𝑛}. Ký hiệu
𝒮𝑛 là tập tất cả các phép hoán vị trên 𝑋,
nghĩa là, 𝒮𝑛 là tập các song ánh 𝜎 : 𝑋 →
𝑋. Phép hợp thành của các ánh xạ trong
𝒮𝑛 thỏa mãn các tính chất:
(i) ∀𝜎1, 𝜎2, 𝜎3 ∈ 𝒮𝑛, (𝜎1 ∘ 𝜎2) ∘ 𝜎3 =
𝜎1 ∘ (𝜎2 ∘ 𝜎3).
(ii) Gọi id là phép hoán vị đồng nhất,
ta có id ∘𝜎 = 𝜎 ∘ id = 𝜎, với mọi 𝜎 ∈ 𝒮𝑛.
(iii) Với 𝜎 ∈ 𝒮𝑛, ánh xạ nghịch đảo 𝜎−1
cũng nằm trong 𝒮𝑛.
Khi đó 𝒮𝑛 cùng với phép hợp thành các
ánh xạ cũng được gọi là một nhóm.
Không phải một tập hợp với một phép
toán bất kỳ cũng là một nhóm (xem Ví
dụ 2.2(ii) ở dưới). Ta có định nghĩa tổng
quát.
Định nghĩa 2.1. Một nhóm 𝐺 là một tập
hợp cùng với phép toán nhóm 𝐺 × 𝐺 →
𝐺, (𝑎, 𝑏) ↦→ 𝑎𝑏, thỏa mãn
- ∀𝑎, 𝑏, 𝑐 ∈ 𝐺, (𝑎𝑏)𝑐 = 𝑎(𝑏𝑐) (tính chất
kết hợp).
- ∃𝑒 ∈ 𝐺 thỏa mãn 𝑎𝑒 = 𝑒𝑎 = 𝑎, ∀𝑎 ∈ 𝐺
(phần tử đơn vị).
- ∀𝑎 ∈ 𝐺, ∃𝑏 ∈ 𝐺 sao cho 𝑎𝑏 = 𝑏𝑎 = 𝑒
(phần tử nghịch đảo).
𝐺 là một nhóm abel nếu
- ∀𝑎, 𝑏 ∈ 𝐺, 𝑎𝑏 = 𝑏𝑎 (tính chất giao
hoán).
Nếu phép toán nhóm viết theo lối nhân
(tương ứng, lối cộng) thì phần tử đơn vị
còn được ký hiệu là 1 (tương ứng, 0),
phần tử nghịch đảo của 𝑎 ký hiệu là 𝑎−1
(tương ứng, −𝑎 và gọi là phần tử đối).
Một nhóm con của 𝐺 là một tập con
𝐻 ⊆ 𝐺 thỏa mãn 𝑒 ∈ 𝐻 và với 𝑎, 𝑏 ∈ 𝐻
thì 𝑎−1 ∈ 𝐻, 𝑎𝑏 ∈ 𝐻. Như vậy, nếu 𝑎 ∈ 𝐻
thì 𝑎𝑛, 𝑎−𝑛 ∈ 𝐻 với mọi 𝑛 = 1, 2, . . .. Nếu
𝐻 = {𝑎𝑛 : 𝑛 ∈ Z} với một phần tử 𝑎 nào
đó thì𝐻 được gọi là một nhóm xyclic sinh
bởi 𝑎.
Ví dụ 2.2. (i) Một số nhóm abel quen
thuộc là
- Nhóm với phép cộng: Z ⊂ Q ⊂ R ⊂ C.
- Nhóm với phép nhân: {±1} ⊂ Q× ⊂
R× ⊂ C× hoặc R>0 ⊂ R×. Ở đây ký hiệu
𝑘× := 𝑘 ∖ {0}.
(ii) Tập R>0 không là một nhóm đối với
phép cộng vì với 𝑥 ∈ R, 𝑥 > 0 thì −𝑥 ̸∈
R>0.
Nhóm hữu hạn. Nếu nhóm 𝐺 có hữu
hạn phần tử thì ta nói𝐺 là một nhóm hữu
hạn. Cấp của 𝐺 là số phần tử của nhóm
đó và ký hiệu là |𝐺|. Với mỗi 𝑔 ∈ 𝐺 có một
số nguyên dương 𝑛 > 0 sao cho 𝑔𝑛 = 1.
Số nguyên dương nhỏ nhất như vậy được
gọi là cấp của 𝑔 và ký hiệu là ord(𝑔).
Ví dụ 2.3. Xét tập Z/𝑛Z gồm các lớp
thặng dư mod 𝑛. Với �¯�, �¯� ∈ Z/𝑛Z, ta có
�¯� + �¯� = 𝑎 + 𝑏 và �¯�.�¯� = 𝑎𝑏. Tập Z/𝑛Z cùng
với phép cộng là một nhóm abel hữu hạn
cấp 𝑛. Xét tập (Z/𝑛Z)* := {�¯� ∈ Z/𝑛Z :
(𝑎, 𝑛) = 1}. Bằng thuật toán chia Eu-
clide ta chứng minh được (Z/𝑛Z)* cùng
với phép nhân là một nhóm abel hữu hạn,
cấp của nhóm này là 𝜙(𝑛) = #{0 < 𝑎 <
𝑛 : (𝑎, 𝑛) = 1}.
Ví dụ 2.4. Nhóm 𝒮𝑛 là một nhóm hữu hạn
và được gọi là nhóm đối xứng (hay nhóm
các phép thế). 𝒮𝑛 là một nhóm abel khi và
chỉ khi 𝑛 < 3. Cấp của 𝒮𝑛 là |𝒮𝑛| = 𝑛!.
Nếu thay tập {1, . . . , 𝑛} bởi một tập 𝑋 có
𝑛 phần tử thì ta cũng được nhóm đối xứng
trên 𝑋, ký hiệu là 𝒮𝑋 .
Với mỗi nhóm con 𝐻 của một nhóm
hữu hạn 𝐺 và 𝑎 ∈ 𝐺, đặt 𝑎𝐻 := {𝑎𝑏 :
𝑏 ∈ 𝐻}. Dễ thấy với 𝑎, 𝑎′ ∈ 𝐺 thì hoặc
𝑎𝐻 = 𝑎′𝐻 hoặc 𝑎𝐻∩𝑎′𝐻 = ∅ (hoặc trùng
nhau hoặc không giao nhau). Nói riêng,
2
𝐺 có phân tích thành một hợp rời các lớp
kề có dạng 𝑎𝐻.
Mệnh đề 2.5 (Định lý Lagrange). Mọi lớp
tương đương định nghĩa như trên đều có
cùng số phần tử và bằng cấp của 𝐻. Nói
riêng, số lớp tương đương là |𝐺|/|𝐻 |.
Ví dụ 2.6 (p-Nhóm). Cho 𝑝 là một số
nguyên tố. Một 𝑝-nhóm là một nhóm hữu
hạn với các phần tử có cấp là một lũy thừa
của 𝑝. Khi đó, một nhóm 𝐺 là 𝑝-nhóm khi
và chỉ khi 𝐺 có cấp là một lũy thừa của 𝑝.
Thật vậy, giả sử𝐺 có cấp là một lũy thừa
của 𝑝 và 𝑎 ∈ 𝐺. Xét nhóm xyclic𝐻 sinh bởi
𝑎. Rõ ràng |𝐻| = ord(𝑎). Do đó theo định
lý Lagrange, ord(𝑎) là ước của cấp của 𝐺.
Đối với chiều ngược lại, ta chỉ chứng
minh cho trường hợp 𝐺 là abel (trong các
bài tập ở phần sau chỉ có trường hợp này
xảy ra). Giả sử 𝐺 là một 𝑝-nhóm abel
và 𝐻 là một nhóm con lớn nhất của 𝐺
mà có cấp là một lũy thừa của 𝑝. Ta sẽ
chứng minh 𝐻 = 𝐺. Giả sử có một phần
tử 𝑎 ∈ 𝐺 ∖ 𝐻. Khi đó ord(𝑎) = 𝑝𝑛 với
𝑛 > 0 nào đó. Xét tập 𝐻 ′ := {𝑎𝑏 : 𝑏 ∈
𝐻}. Dễ thấy 𝐻 ′ là hợp rời của các tập
hợp𝐻, 𝑎𝐻, 𝑎2𝐻, . . . , 𝑎𝑝
𝑛−1𝐻 và𝐻 ′ là một
nhóm abel. Nói riêng, 𝐻 ′ là một nhóm con
của 𝐺 với cấp là |𝐻 ′| = |𝐻|.𝑝𝑛 > |𝐻|.
Điều này mâu thuẫn với cách chọn 𝐻. Vậy
𝐺 = 𝐻 và 𝐺 có cấp là một lũy thừa của 𝑝.
Tác động nhóm. Xét nhóm đối xứng 𝒮𝑛
và tập 𝑋 = {1, 2, . . . , 𝑛}. Với mỗi 𝜎 ∈ 𝒮𝑛,
𝑖 ∈ 𝑋, ta được 𝜎(𝑖) ∈ 𝑋. Tương ứng này
rõ ràng thỏa mãn (𝜎1 ∘𝜎2)(𝑖) = 𝜎1(𝜎2(𝑖)).
Khi đó ta nói rằng có một tác động của
nhóm 𝒮𝑛 lên tập 𝑋. Tổng quát hơn, ta có
định nghĩa.
Định nghĩa 2.7. Cho 𝐺 là một nhóm
hữu hạn và 𝑋 là một tập hữu hạn. Một
tác động của 𝐺 lên 𝑋 là một ánh xạ
𝐺 × 𝑋 → 𝑋, (𝑔, 𝑎) ↦→ 𝑔(𝑎) thỏa mãn:
với 𝑔, ℎ ∈ 𝐺, 𝑎 ∈ 𝑋, (𝑔ℎ)(𝑎) = 𝑔(ℎ(𝑎))
và 𝑒(𝑎) ≡ 𝑎. Với mỗi 𝑎 ∈ 𝑋, tập con
orb(𝑎) := {𝑔(𝑎) ∈ 𝑋 : 𝑔 ∈ 𝐺} được
gọi là quỹ đạo của 𝑎. Phần tử 𝑎 ∈ 𝑋 cố
định dưới tác động của 𝐺 khi và chỉ khi
orb(𝑎) = {𝑎}. Tập 𝑋 được phân hoạch
thành hợp rời các quỹ đạo.
Ví dụ, xét tác động của nhóm đối xứng
𝒮𝑛 lên tập 𝑋 = {1, . . . , 𝑛}. Với hai phần
tử bất kỳ 𝑖, 𝑗 = 1, . . . , 𝑛, luôn có một phép
thế, ký hiệu là (𝑖, 𝑗) và gọi là phép chuyển
vị, tráo đổi vị trí của 𝑖, 𝑗 và cố định các vị
trí khác. Do đó tác động này chỉ có một
quỹ đạo là cả tập 𝑋.
Với một tập con 𝑌 ⊂ 𝑋, tập Stab(𝑌 ) :=
{𝑔 ∈ 𝐺 : 𝑔(𝑌 ) ⊆ 𝑌 } là một nhóm con của
𝐺 và được gọi là nhóm con ổn định của
𝑌 . Ta có một song ánh {𝑔.Stab(𝑎) : 𝑔 ∈
𝐺} −→ orb(𝑎), 𝑔ℎ ↦→ 𝑔(𝑎). Định lý La-
grange (Mệnh đề 2.5) cho ta
Mệnh đề 2.8. Với mỗi 𝑎 ∈ 𝑋, quỹ đạo
orb(𝑎) có số phần tử bằng |𝐺|/| Stab(𝑎)|.
Nói riêng, | orb(𝑎)| là ước của |𝐺|.
Cho 𝑝 ∈ Z là một số nguyên tố và 𝐺 là
một 𝑝-nhóm. Xét một tác động của 𝐺 lên
một tập hữu hạn 𝑋. Theo Mệnh đề 2.8,
những quỹ đạo có nhiều hơn một phần
tử có số phần tử là lũy thừa của 𝑝. Những
quỹ đạo còn lại ứng với các điểm cố định
của 𝑋. Ký hiệu 𝑋𝐺 là tập các điểm cố
định, ta có mệnh đề.
Mệnh đề 2.9. Có |𝑋| ≡ |𝑋𝐺| (mod 𝑝).
Một ứng dụng thú vị của mệnh đề trên
là định lý số học sau đây.
Định lý 2.10 (Lucas). Cho các số nguyên
𝑚,𝑛 ≥ 0 và một số nguyên tố 𝑝. Ta có(︂
𝑚
𝑛
)︂
≡
𝑘∏︁
𝑖=0
(︂
𝑚𝑖
𝑛𝑖
)︂
(mod 𝑝),
trong đó 𝑚𝑖, 𝑛𝑖 là các chữ số trong biểu
diễn cơ số 𝑝 của 𝑚,𝑛, nghĩa là
𝑚 = 𝑚𝑘𝑝
𝑘 + . . . + 𝑚1𝑝 + 𝑚0,
3
𝑛 = 𝑛𝑘𝑝
𝑘 + . . . + 𝑛1𝑝 + 𝑛0,
với 0 ≤ 𝑚0, . . . ,𝑚𝑘 < 𝑝 và 0 ≤
𝑛0, . . . , 𝑛𝑘 < 𝑝.
Chứng minh. Xét một tập𝑀 gồm𝑚 phần
tử. Chia 𝑀 thành các tập con rời nhau:
𝑚𝑖 tập con có 𝑝𝑖 phần tử, 𝑖 = 0, 1, . . . ,𝑚.
Trên mỗi tập con, có một tác động tự
nhiên của nhóm xyclic Z/𝑝𝑖Z. Do đó
nhóm 𝐺 =
∏︀𝑘
𝑖=0(Z/𝑝𝑖Z)𝑚𝑖 tác động tự
nhiên theo từng thành phần lên tập𝑀 . Ở
đây (Z/𝑝𝑖Z)𝑚𝑖 = Z/𝑝𝑖Z × . . . × Z/𝑝𝑖Z là
tích 𝑚𝑖 lần Z/𝑝𝑖Z.
Gọi 𝑋 là tập tất cả các tập con của 𝑀
có 𝑛 phần tử. Như vậy |𝑋| = (︀𝑚𝑛)︀. Dễ
thấy 𝐺 tác động cảm sinh lên tập 𝑋. Một
tập con 𝑁 thuộc 𝑋 là bất biến dưới tác
động của 𝐺 khi và chỉ khi nó là hợp của
các tập con có 𝑝𝑖 phần tử trong cách chia
ở trên. Với mỗi 𝑝𝑖, có 𝑛𝑖 tập con của 𝑁
như vậy. Do đó số tập con 𝑁 ⊆ 𝑀 có
𝑛 phần tử và bất biến dưới tác động của
𝐺 là
∏︀𝑘
𝑖=0
(︀
𝑚𝑖
𝑛𝑖
)︀
. Khẳng định được suy từ
Mệnh đề 2.9. 
3. TỔ HỢP
3.1. Phép thế. Một phép thế 𝜎 ∈ 𝒮𝑛
được hoàn toàn xác định bởi các giá trị
𝜎(1), . . . , 𝜎(𝑛). Do đó có một cách khác
biểu diễn 𝜎 là(︂
1 2 . . . 𝑛
𝜎(1) 𝜎(2) . . . 𝜎(𝑛)
)︂
.
Chú ý rằng 𝜎 còn được gọi là một hoán
vị của các số 1, 2, . . . , 𝑛 và ký hiệu là
(𝑎1, . . . , 𝑎𝑛) với 𝑎𝑖 = 𝜎(𝑖). Nếu 𝑎𝑖 = 𝑖
thì ta có thể bỏ 𝑎𝑖 trong ký hiệu trên. Tác
động tự nhiên của nhóm xyclic (𝜎) lên tập
𝑋 = {1, 2, . . . , 𝑛} cho ta phân tích của 𝑋
thành hợp rời các quỹ đạo
𝑋 = 𝑋1 ⊔𝑋2 ⊔ . . . ⊔𝑋𝑟,
với mỗi 𝑋𝑖 có dạng {𝑎, 𝜎(𝑎), . . . , 𝜎𝑘𝑖(𝑎)}.
Mỗi 𝑋𝑖 được gọi là một chu trình của 𝜎
và ta có ord(𝜎) = [|𝑋1|, . . . , |𝑋𝑟|] | 𝑛!.
Ví dụ 3.1 (IMO 2001). Cho 𝑛 > 1 là một
số nguyên lẻ và các số nguyên 𝑐1, . . . , 𝑐𝑛.
Với mỗi phép thế 𝑎 = (𝑎1, . . . , 𝑎𝑛) của
1, . . . , 𝑛, định nghĩa 𝑆(𝑎) =
∑︀𝑛
𝑖=1 𝑐𝑖𝑎𝑖.
Chứng minh rằng tồn tại các phép thế
𝑎 ̸= 𝑏 sao cho 𝑛!|𝑆(𝑎)− 𝑆(𝑏).
Lời giải. Nếu tất cả 𝑆(𝑎) khác nhau mod
𝑛! thì do có 𝑛! phép thế nên
{𝑆(𝑎) : 𝑎 ∈ 𝒮𝑛} = {0, 1, . . . , 𝑛!−1}mod𝑛!.
Do đó,
∑︀
𝑎∈𝒮𝑛 𝑆(𝑎) =
(𝑛!−1)𝑛!
2 = −𝑛!2
(mod 𝑛!). Ta có
∑︁
𝑎∈𝒮𝑛
𝑆(𝑎) =
∑︁
𝑎∈𝒮𝑛
𝑛∑︁
𝑖=1
𝑐𝑖𝑎𝑖 =
𝑛∑︁
𝑖=1
𝑐𝑖
∑︁
𝑎∈𝒮𝑛
𝑎𝑖
=
𝑛∑︁
𝑖=1
𝑐𝑖.(𝑛−1)!
𝑛∑︁
𝑖=1
𝑖 =
𝑛∑︁
𝑖=1
𝑐𝑖.𝑛!
𝑛 + 1
2
= 0
(mod 𝑛!).
Điều này mâu thuẫn với khẳng định trên.
Vậy có hai phép thế khác nhau 𝑎, 𝑏 sao cho
𝑆(𝑎) ≡ 𝑆(𝑏) (mod 𝑛!).
Ví dụ 3.2 (IMO 1999 shortlist (Phần
Lan)). Có 𝑛 ≥ 2 cô gái chơi một trò
chơi, mỗi người giữ một quả bóng. Mỗi cặp
trong số tất cả
(︀
𝑛
2
)︀
cặp, theo một thứ tự
nào đó, đổi quả bóng họ đang có cho nhau.
Trò chơi được gọi là "thú vị" nếu cuối cùng
không có cô gái nào nhận lại quả bóng ban
đầu. Ngược lại, nếu cuối cùng tất cả các cô
gái đều nhận lại quả bóng ban đầu thì trò
chơi được gọi là "chán ngắt". Tìm giá trị
của 𝑛 để (a) có một trò chơi thú vị và (b)
có một trò chơi chán ngắt.
Lời giải. Một phép chuyển vị (𝑖, 𝑗) với
𝑖, 𝑗 = 1, . . . , 𝑛, 𝑖 ̸= 𝑗 là một hoán vị hai
vị trí 𝑖, 𝑗 cho nhau và giữ nguyên các vị
trí khác. Một trò chơi là một cách thực
hiện liên tiếp, hay là một cách xếp thứ
4
tự, 𝑁 =
(︀
𝑛
2
)︀
phép chuyển vị (𝑖, 𝑗) của tập
{1, . . . , 𝑛}. Giả sử thứ tự đó là 𝑡1, . . . , 𝑡𝑁 .
Một trò chơi sẽ ứng với phép hoán vị 𝑃 =
𝑡𝑁 𝑡𝑁−1 . . . 𝑡1. Trò chơi là thú vị tương ứng
với 𝑃 không có điểm cố định. Trò chơi là
chán ngắt nếu 𝑃 = id là phép đồng nhất.
(a) Tồn tại một trò chơi thú vị khi và chỉ
khi 𝑛 ̸= 3.
Thật vậy, nếu 𝑛 = 2 thì 𝑃2 := (1, 2) rõ
ràng là thú vị. Nếu 𝑛 = 3 thì mỗi trò chơi
có dạng 𝑃 = (𝑏, 𝑐)(𝑎, 𝑐)(𝑎, 𝑏) = (𝑎, 𝑐) nên
không là thú vị.
Xét 𝑛 > 3. Xét 𝑃𝑛 := (1, 2)(1, 3)(2, 3)
. . . (1, 𝑛)(2, 𝑛) . . . (𝑛 − 1, 𝑛). Khi đó 𝑃𝑛 =
𝑃𝑛−1(1, 𝑛, 𝑛 − 1, . . . , 2) = (1, 𝑛)(2, 𝑛 −
1) . . . (𝑖, 𝑛 + 1 − 𝑖) . . . là thú vị nếu 𝑛
là chẵn. Nếu 𝑛 lẻ thì hoán vị 𝑄𝑛 :=
𝑃𝑛−1(1, 𝑛)(2, 𝑛) . . . (𝑘, 𝑛)(𝑛 − 1, 𝑛)(𝑛 −
2, 𝑛) . . . (𝑘 + 1)𝑛 là thú vị.
(b) Tồn tại một trò chơi chán ngắt khi và
chỉ khi 𝑛 ≡ 0, 1 (mod 4).
Ta có sign(𝑃 ) = (−1)(𝑛2). Do đó nếu
𝑃 = id là phép đồng nhất thì 2|(︀𝑛2)︀, hay
𝑛 ≡ 0, 1 (mod 4).
Ngược lại, giả sử 𝑛 ≡ 0, 1 (mod 4).
Xét trường hợp 𝑛 = 4𝑘. Chia các
cô gái vào 𝑘 nhóm gồm 4 cô gái.
Trong mỗi nhóm xét thứ tự sau
(3, 4)(1, 3)(2, 4)(2, 3)(1, 4)(1, 2) = id.
Giữa hai nhóm khác nhau (ký hiệu là
{1, 2, 3, 4} và {5, 6, 7, 8}), ta có
(4, 7)(3, 7)(4, 6)(1, 6)(2, 8)(3, 8)(2, 7)(2, 6)
(4, 5)(4, 8)(1, 7)(1, 8)(3, 5)(3, 6)(2, 5)(1, 5)
= id .
Trường hợp 𝑛 = 4𝑘 + 1 ta chia thành
𝑘+1 nhóm gồm 𝑘 nhóm có 4 cô gái và một
nhóm chỉ có một cô gái. Giữa hai nhóm có
4 cô gái khác nhau ta làm như trên. Với
mỗi nhóm có 4 cô gái, ký hiệu là 1, 2, 3, 4,
ta thêm cô gái dư, ký hiệu là 5, và tiến
hành theo thứ tự sau
(3, 5)(3, 4)(4, 5)(1, 3)(2, 4)(2, 3)(1, 4)(1, 5)
(1, 2)(2, 5) = id .
Bài 1 (Australia MO 2004). Tìm tất cả các
hoán vị 𝑎1, . . . , 𝑎2004 của 1, . . . , 2004 sao
cho
|𝑎1−1| = |𝑎2−2| = . . . = |𝑎2004−2004| > 0.
Bài 2 (IMO 2005 shortlist (USA)). Cho
một số nguyên dương 𝑛 ≥ 1 và một dãy số
nguyên 𝑎1, . . . , 𝑎𝑛 sao cho 𝑛 | (𝑎1 + . . . +
𝑎𝑛). Chứng minh rằng tồn tại hai phép thế
𝜎 và 𝜏 của 1, . . . , 𝑛 sao cho 𝜎(𝑖)+𝜏(𝑖) ≡ 𝑎𝑖
(mod 𝑛) với mọi 𝑖 = 1, . . . , 𝑛.
Bài 3 (IMO 2008 shortlist (Serbia) & Iran
MO). Với 𝑛 > 0, xác định số các hoán vị
𝑎1, . . . , 𝑎𝑛 của 1, . . . , 𝑛 với tính chất
𝑘 | 2(𝑎1 + . . . + 𝑎𝑘), ∀𝑘 = 1, 2, . . . , 𝑛.
3.2. Bài toán tô màu. Bài toán tô màu
là một ứng dụng điển hình của lý thuyết
nhóm (nhóm đối xứng) trong tổ hợp.
Bài toán. Cho 𝑟 mảnh vải giống hệt nhau
và 𝑛 màu khác nhau. Tô mỗi mảnh vải
bằng một màu nào đó. Cho𝐺 là một nhóm
gồm các phép hoán vị 𝑛mảnh vải. Hai cách
tô màu sẽ được đồng nhất nếu cách này
nhận được từ cách kia bằng một phép hoán
vị trong 𝐺. Hỏi có tất cả bao nhiêu cách tô
màu (sai khác hoán vị bởi nhóm 𝐺)?
Ví dụ 3.3 (HSGQG 2010). Người ta dùng
𝑛 màu để tô tất cả các ô vuông con của
bảng ô vuông kích thước 3× 3, mỗi ô được
tô bởi một màu. Hai cách tô màu được coi
là như nhau nếu cách tô màu này nhận
được từ cách tô màu kia nhờ một phép
quay quanh tâm của bảng ô vuông. Hỏi có
tất cả bao nhiêu cách tô màu khác nhau?
Bài toán tô màu được giải bằng cách sử
dụng bổ đề Burnside.
Bổ đề Burnside. Xét một tập hữu hạn 𝑋
cùng với một tác động của một nhóm hữu
5
hạn 𝐺. Với mỗi 𝑔 ∈ 𝐺, ký hiệu 𝐹 (𝑔) =
{𝑥 ∈ 𝑋 : 𝑔(𝑥) = 𝑥} và 𝑍 = {(𝑔, 𝑥) ∈
𝐺 ×𝑋 : 𝑥 ∈ 𝐹 (𝑔)}. Bằng cách đếm theo
𝑔 ∈ 𝐺 hoặc theo 𝑥 ∈ 𝑋, ta có đồng nhất
thức
|𝑍| =
∑︁
𝑔∈𝐺
|𝐹 (𝑔)| =
∑︁
𝑥∈𝑋
| Stab(𝑥)|.
Mỗi phần tử 𝑥 ∈ 𝑋 xuất hiện đúng
|Stab(𝑥)| lần trong tập 𝑍. Như vậy, các
phần tử trong orb(𝑥) xuất hiện cả thảy
| orb(𝑎)|.| Stab(𝑎)| = |𝐺| lần.
Mệnh đề 3.4 (Bổ đề Burnside). Số quỹ
đạo của tác động nhóm 𝐺 lên tập 𝑋 là
𝑁 =
1
|𝐺|
∑︁
𝑔∈𝐺
|𝐹 (𝑔)| = 1|𝐺|
∑︁
𝑎∈𝑋
| Stab(𝑎)|.
Bổ đề Burnside cũng được một vài
tác giả gọi là Bổ đề Cauchy-Frobenius.
Cauchy là người đầu tiên chứng minh
cho trường hợp tác động chỉ có một quỹ
đạo (tác động bắc cầu). Frobenius chứng
minh trường hợp tổng quát. Theo các tác
giả này, Burnside là người đầu tiên viết
kết quả trên trong một quyển sách.
Định lý đếm của Pólya (dạng đơn giản).
Áp dụng bổ đề Burnside, ta phát biểu lại
bài toán tô màu: Ký hiệu các mảnh vải là
𝑣1, . . . , 𝑣𝑟, các màu là 𝑐1, . . . , 𝑐𝑛. Xét tập
hợp các ánh xạ 𝑋 = {𝑓 : {𝑣1, . . . , 𝑣𝑟} →
{𝑐1, . . . , 𝑐𝑛}}. Mỗi cách tô màu tương ứng
1 − 1 với một hàm 𝑓 ∈ 𝑋. Nhóm 𝐺 ⊆ 𝒮𝑟
tác động lên tập {𝑣1, . . . , 𝑣𝑟} nên có tác
động tự nhiên lên tập 𝑋 cho bởi (𝑔, 𝑓) ∈
𝐺×𝑋 ↦→ 𝑓 ∘𝑔 ∈ 𝑋. Theo bổ đề Burnside,
số các quỹ đạo của tác động này là
𝑁𝐺 =
1
|𝐺|
∑︁
𝜎∈𝐺
|𝐹 (𝜎)|,
với 𝐹 (𝜎) = {𝑓 ∈ 𝑋 : 𝑓(𝜎(𝑣𝑖)) =
𝑓(𝑣𝑖), 𝑖 = 1, . . . , 𝑛}. Gọi các chu trình của
𝜎 là 𝑉1, . . . , 𝑉𝑡. Khi đó 𝑓 ∈ 𝐹 (𝜎) tương
đương với 𝑓 là ánh xạ hằng khi hạn chế
lên từng chu trình 𝑉𝑖, 𝑖 = 1, . . . , 𝑡. Như
vậy, |𝐹 (𝜎)| = 𝑛𝑐(𝜎) với 𝑐(𝜎) = 𝑡 là số chu
trình của 𝜎.
Mệnh đề 3.5 (Định lý đếm của Pólya,
dạng đơn giản). Ta luôn có
𝑁𝐺 =
1
|𝐺|
∑︁
𝜎∈𝐺
𝑛𝑐(𝜎).
Mệnh đề trên là một dạng đơn giản của
định lý đếm của Pólya. Định lý đếm tổng
quát cho ta thông tin cụ thể hơn về số
cách tô màu với những hạn chế về phân
bố là một kết quả quan trọng trong tổ
hợp, tuy nhiên việc trình bày tương đối
dài và vượt ra khỏi phạm vi của bài giới
thiệu này.
Ví dụ 3.3 xét lại. Gọi 𝜏 là phép quay
quanh tâm hình vuông góc 𝜋2 theo chiều
kim đồng hồ. Khi đó 𝐺 = (𝜏) là một
nhóm xyclic cấp 4. Số chu trình của 𝜏
là 3, của 𝜏2 là 5, của 𝜏3 là 3 và của
𝜏4 = id là 9. Theo định lý đếm của
Pólya (Mệnh đề 3.5), số cách tô màu là
𝑁 = 14(𝑛
9 + 𝑛5 + 2𝑛3).
Ví dụ 3.6 (Số Stirling). Ký hiệu số phép
thế trong 𝒮𝑟 có 𝑘 chu trình là
[︀
𝑟
𝑘
]︀
và gọi
là số Stirling. Số Stirling liên quan đến bài
toán tìm số cách xếp 𝑟 quả bóng vào 𝑛 cái
sọt với hai cách xếp là như nhau nếu sai
khác một cách đánh số lại các quả bóng.
Bài toán bóng-sọt thuộc kiểu bài toán
tô màu. Trong trường hợp này, ta không
phân biệt các quả bóng nên nhóm tác động
là 𝒮𝑟. Theo định lý đếm của Pólya, số cách
xếp là
𝑁 =
1
𝑟!
𝑟∑︁
𝑘=0
[︂
𝑟
𝑘
]︂
𝑛𝑘.
Mặt khác, mỗi cách xếp tương ứng với một
chuỗi 𝑛+ 𝑟− 1 ký tự gồm 𝑟 ký tự 𝑏 (bóng)
và 𝑛 − 1 ký tự 𝑠 (sọt). Số cách sắp xếp do
6
đó là 𝑁 =
(︀
𝑛+𝑟−1
𝑟
)︀
. Ta suy ra
(𝑛 + 𝑟 − 1) . . . (𝑛 + 1)𝑛 =
𝑟∑︁
𝑘=0
[︂
𝑟
𝑘
]︂
𝑛𝑘.
Đây là một định nghĩa khác của số Stirling.
Bài 4. Có bao nhiêu cách sơn các mặt của
một hình lập phương bằng 8 màu với điều
kiện mỗi mặt được sơn một màu và hai
cách sơn là như nhau nếu sai khác một
phép xoay hình lập phương.
Bài 5 (AIME 1996). Hai ô của hình vuông
7 × 7 được tô màu vàng. Các ô còn lại
được tô màu đỏ. Hai cách tô được coi là
giống nhau nếu chúng có thể thu được từ
nhau bằng một phép quay trên mặt phẳng
quanh tâm của hình vuông. Hỏi có bao
nhiêu cách tô màu?
Bài 6 (Tô màu vòng cổ). Người ta làm các
chuỗi vòng cổ có 𝑟 hạt đá trong đó mỗi hạt
đá mang một trong 𝑛 màu cho trước. Hai
chuỗi vòng được gọi là cùng kiểu nếu vòng
này nhận được từ vòng kia bằng một phép
tịnh tiến theo các hạt. Hỏi: (a) Có nhiều
nhất bao nhiêu chuỗi vòng cổ thuộc các
kiểu khác nhau? (b) Có bao nhiêu chuỗi
vòng mà với mỗi màu đều có ít nhất 2 hạt
mang màu đó?
Bài 7. Cho tập 𝑉 = {𝑣1, . . . , 𝑣𝑛}. Một đồ
thị 𝐺 trên tập đỉnh 𝑉 được cho bởi một
tập gồm các cặp không sắp thứ tự (𝑣𝑖, 𝑣𝑗),
𝑖 ̸= 𝑗, gọi là các cạnh của 𝐺. Hai đồ thị
là đẳng cấu với nhau nếu đồ thị này nhận
được từ đồ thị kia bằng cách đánh số lại
các đỉnh. Tìm số lớn nhất các đồ thị không
đẳng cấu với nhau.
3.3. Một số bài toán khác. Trong hai
phần trước ta đã thấy ứng dụng của nhóm
đối xứng. Trong phần này ta sẽ xét một số
bài tập với các cấu trúc nhóm khác.
Ví dụ 3.7 (USAMO 2008). Trong một hội
thảo về toán, hai nhà toán học bất kỳ hoặc
là bạn nhau hoặc là người lạ. Trong thời
gian ăn trưa, những người tham dự ăn ở
một trong hai phòng ăn. Mỗi nhà toán học
đều ăn trong một phòng chứa một số chẵn
người bạn của mình. Giả sử có ít nhất một
cách sắp xếp như vậy. Chứng minh rằng số
cách chia các nhà toán học vào hai phòng
là một lũy thừa của 2.
Lời giải. Định nghĩa một lệnh là một tập
các hướng dẫn, mỗi nhà toán học được đề
nghị hoặc ở lại hoặc di chuyển. Giả sử đang
có một cách chia tốt, nghĩa là mỗi nhà toán
học có số chẵn bạn ở trong cùng phòng. Xét
tập 𝐺 tất cả các lệnh sao cho xuất phát từ
cách chia này, sau khi áp dụng một lệnh ta
được một cách chia tốt khác. Các lệnh đó
cũng được gọi là các lệnh tốt. Gọi tập này
là 𝐺. Khi đó lệnh 𝐼 mà mỗi nhà toán học
ở nguyên tại chỗ cũng thuộc tập 𝐺.
G là một nhóm abel: Nếu 𝐴,𝐵 ∈ 𝐺 là
hai lệnh bất kỳ, ta ký hiệu 𝐴.𝐵 là lệnh
nhận được bằng cách áp dụng lần lượt lệnh
𝐵 rồi tiếp lệnh 𝐴. Dễ thấy hai lệnh 𝐴.𝐵 và
𝐵.𝐴 như nhau. Ta chứng minh 𝐴.𝐵 cũng
là một lệnh tốt, nghĩa là thuộc vào tập 𝐺.
Thật vậy, xét một nhà toán học 𝑥 trong hội
thảo. Nếu 𝐵(𝑥) là ở lại thì có chẵn bạn của
𝑥 ở cả hai phòng