Về phép đếm quay quanh tâm

Ví dụ 1(VMO 2010): Cho bảng 3x3 và n là một số nguyên dương cho trước. Tìm số các cách tô màu không như nhau khi tô mỗi ô bởi 1 trong n màu.
Hai cách tô màu được gọi là như nhau nếu 1 cách nhận được từ cách kia bởi 1 phép quay quanh tâm.
Lời giải:
Cách của thầy Trần Nam Dũng:

Ví dụ 2: (AIME 1996) Hai ô của hình vuông 7 × 7 được tô bằng màu vàng. Các ô còn lại được tô bằng màu đỏ. Hai cách tô đượcc coi là tương đươ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 của hình vuông. Đếm sô các cách tô màu không tương đương.

Lời giải:
(Xây dựng hệ trục trên hình vuông ô đầu tiên đánh số 1 từ trái sang đánh đến số 7, từ trên xuống đánh từ 1 đến 7)
Ta chia hai ô màu vàng của hình vuông thành 3 loại:

Loại 1: có 1 ô (4;4), thì ô còn lại có 48 cách chọn ( có thể bị lặp). Do các phép quay 90 độ, 180 độ, 270 độ tạo thành những cách khác ta phải loại bớt nên có 48/4=12 cách chọn

Loại 2: các ô có tọa độ là (4,x), (4, 8-x) và (x,4), (8-x, 4) và các ô chéo của hình vuông con ở trong thì khi đó sẽ có 4.3=12 cách chọn như vậy.(Do có 3 hình vuông con mà tâm là (4;4))

Loại 3: Không tính loại 2. Rõ ràng là $\frac{\mathbb{C}_2^{49}-24}{4}$

Tổng cộng có: $\frac{\mathbb{C}_2^{49}-24}{4}+12=300$ cách chọn.
Có thể thấy rõ qua hình sau:

Chú ý: -Có thể không xài loại 1 làm gì nhưng viết vào để cho dễ hình dung.
-Đây là trường hợp của bổ đề Burnside

Ví dụ 3 (tạp chí Kvant số 5 năm 2000): Một đường tròn chia làm p cung bằng nhau. Hỏi có bao nhiêu cách tô các cung bằng a màu. Hai cách tô được gọi là giống nhau nếu có thể thu được từ nhau bởi 1 phép quay.

Với bài toán trên, có $ a^p $ cách tô màu p cung. Trong những số cách ấy, có những cách ta đếm lặp, cần loại đi. Ta thấy rằng nếu p cung được tô bởi 1 màu thì khi quay các góc 2pi/p, 4pi/p,..., 2(p-1)pi/p không thu được những cách tô khác. (ta có thể chứng minh rằng nếu $n \vdots k$ khi đó tồn tại phép quay góc 2kpi/p biến đường tròn này thành đường tròn kia) . Trong khi đó, những cách tô sử dụng 2 màu trở lên khi quay sẽ cho ra các cách tô khác (chú ý tính nguyên tố của p). Vì vậy, mỗi một cách tô sử dụng 1 màu (có a cách tô như vậy) chỉ được đếm 1 lần trong tổng $a^p $cách tô, trong khi đó mỗi cách tô sử dụng 2 màu trở lên (có $a^p - a$ cách tô như vậy) được đếm p lần trong tổng nói trên.

Từ đó suy ra số cách tô cần tìm bằng $ a + \dfrac{a^p-a}{p} $.

Chú ý: Từ kết quả này có thể suy ra định lí Fermat nhỏ.

Đồ thị lưỡng phân

Định nghĩa:

Đồ thị lưỡng phân là đồ thị G=(V; E) mà tập đỉnh V có thể phân hoạch thành hai tập hợp X, Y sao cho tập cạnh E chỉ gồm các cạnh nối hai đỉnh không cùng một tập hợp. Ta còn kí hiệu đồ thị lưỡng phân này là G=(X,Y;E)

Một tính chất cơ bản để nhận biết đồ thị lưỡng phân là định lý sau đây

Định lý: Một đồ thị G là đồ thị lưỡng phân khi và chỉ khi mọi chu trình của nó có độ dài chẵn.

Chứng minh. Giả sử G=(X,Y; E) là một đồ thị lưỡng phân. Khi đó dọc theo chu trình bất kỳ của G các đỉnh thuộc tập X và tập Y lần lượt kế tiếp nhau. Do đó, khi trở về đỉnh xuất phát đầu tiên, ta phải đi qua một số chẵn các đỉnh, do đó số cạnh ( bằng số đỉnh) của chu trình là một số chẵn.

Đảo lại, giả sử rằng G là một đồ thị mà tất cả các chu trình của G đều có độ dài chẵn. Ta sẽ chứng minh rằng tất cả các thành phần liên thông của G đều là các đồ thị lưỡng phân, và do đố G cũng là đồ thị lưỡng phân.

Thật vậy, giả sử rằng $G_1$ là một thành phần liên thông của G và $P_0$ là một đỉnh của đồ thị $G_1$. Với mỗi đỉnh P của đồ thị $G_1$, ta chọn một đường đi W nối đỉnh $P_0$ với đỉnh P. Nếu đường đi W có độ dài chẵn thì đỉnh P thuộc tập X, còn nếu đường đi W có độ dài lẻ thì đỉnh P được lấy vào tập Y. Sự phân loại các đỉnh của đồ thị $G_1$ không phụ thuộc vào cách chọn đường đi W. thật vậy, nếu có đường đi W với độ dài chẵn và đường đi W' với độ dài lẻ nối đỉnh $P_0$ với đỉnh P thì đồ thị $G_1$ sẽ có chu trình với độ dài lẻ, mâu thuẫn với giả thiết ban đầu.

Với các thiết lập tập hợp X và Y này, các đỉnh của đồ thị $G_1$ hoặc thuộc tập hợp X hoặc thuộc tập hợp Y. Bây giờ ta chuwgns minh rằng $G_1$ chỉ có các cạnh nối các đỉnh không cùng mọt tập hợp với nhau mà thôi. Thật vậy, giả sử rằng có hai đỉnh P và Q kề nhau trong đồ thị $G_1$ thì chugns không thể cùng thuộc một tập hợp X hoặc Y, nếu không từ $P_0$ ta có thể đi đến đỉnh P rồi tới đỉnh Q bởi cạnh (P,Q) và trở về đỉnh $P_0$ với một đường đi lẻ cạnh, điều không thể xảy ra trong đồ thị G do G chỉ có chu trình với số chẵn cạnh mà thôi. Như vậy đồ thị G là đồ thị lưỡng phân với hai tập đỉnh X và Y.

Mở rộng của định lý Dirac

Định lý Ore: Nếu đồ thị vô hướng G=(V,E) có số đỉnh là $n \ge 3$ và $deg(u)+deg(v) \ge n$ thỏa mãn cho mọi cặp đỉnh không kề nhau u và v của G, thì G là đồ thị Hamilton.

Chứng minh.

Giả sử định lý không đúng và G=(V, E) có cỡ cực đại cấp n thỏa mãn các điều kiện của Định lý nhưng không là đồ thị Hamilton. Dễ thấy rằng thêm một cạnh bất kỳ vào một đồ thị có những tính chất chỉ ra trong định lý sẽ tạo ra một đồ thị cũng có những tính chất ấy. Vì G là đồ thị không là Hamilton cấp n có cỡ cực đại thỏa mãn các điều kiện , nên đồ thị nhận được khi thêm vào G một cạnh bất kì nối hai đỉnh không kề nhau trong G là đồ thị có chu trình Hamilton cạnh thêm đó. Suy ra hai đỉnh bất kỳ không kề nhau trong G được nối với nhau bằng một đường Hamilton

Vì G không là đồ thị Hamilton nên G khác đồ thị đầy đủ $K_n$. Do đó tồn tại hai đỉnh không kề nhau trong G, chẳng hạn $v_1$ và $v_n$. Theo khẳng định vừa chứng minh ở đoạn trên tồn tại trong G đường Hamilton nối $v_1$ với $v_n$ chẳng hạn $v_1v_2..v_n$.

Kí hiệu các đỉnh kề với $v_1$ bằng $v_{i_1},v_{i_2},..v_{i_k}$ trong đó k là bậc của đỉnh $v_1$ và $2=i_1<i_2<..<i_k$. Hiền nhiên là $v_n$ không thể kề với một đỉnh nào của G dạng $v_{i_j-1}$ bởi vì khi đó G sẽ có chu trình Hamilton là $v_1v_2..v_{i_j-1}v_nv_{n-1}..v_{i_j}v_1$.

Do đó ký hiệu $N(v_1)=\begin{Bmatrix}
v_{i_j} \in V|j=1,2,..k
\end{Bmatrix}$ và $N*(v_n)=\begin{Bmatrix}
v_{i+1} \in V | v_i \ne v_n, \begin{Bmatrix}
v_i,v_n
\end{Bmatrix} \in E
\end{Bmatrix}$

Thì $N(v_1) \cap N^*(v_n)$ là rỗng.

Vì thế: $n \le deg(v_1)+deg(v_n) = k+(n-1-k)=n-1$ (mâu thuẫn)

Như vậy ta có điều phải chứng minh.

Có thể thấy rằng định lý Dirac  này là hệ quả của định lý Ore do:

nếu có hai đỉnh trong đồ thị không kề nhau bất kì u và v trong G ta có $deg(u)+deg(v) \ge n/2+n/2=n$ áp dụng định lý Ore ta có điều phải chứng minh.

Định lý Dirac và ứng dụng

Định lý  (Dirac 1952)

Đơn đồ thị vô hướng G với n>2 đỉnh, mỗi đỉnh có bậc không nhỏ hơn n/2 là đồ thị Hamilton.

Chứng minh:

Ký hiệu n đỉnh của G là ${\displaystyle v_{1},v_{2},v_{3},...,v_{n}}$.

Không mất tính tổng quát giả sử đường đi H dài nhất của G là ${\displaystyle v_{1}v_{2}v_{3}...v_{l}}$. H có độ dài là l. Như vậy mọi đường đi đơn của G có độ dài nhỏ hơn l+1.

Nếu ${\displaystyle l=n}$ thì suy ra luôn điều phải chứng minh.

Xét trường hợp ${\displaystyle l<n}$.

Gọi tất cả các đỉnh liền kề với ${\displaystyle v_{l}}$ là ${\displaystyle v_{i_{1}},v_{i_{2}},...,v_{i_{t}}}$ (với ${\displaystyle 0<i_{1}<i_{2}<...<i_{t}<n+1}$ và ${\displaystyle t}$≥${\displaystyle {\frac {n}{2}}}$). Dễ thấy ${\displaystyle {i_{j}}<l}$ với mọi j chạy từ 1 tới t, vì nếu tồn tại ${\displaystyle {i_{j}}>l}$, thì suy ra tồn tại đường đi có độ dài l+1:

${\displaystyle v_{1}v_{2}v_{3}...v_{l}v_{i_{j}}}$.

Nếu đỉnh ${\displaystyle v_{l+1}}$ mà liền kề với đỉnh ${\displaystyle v_{i_{j}+1}}$ thì ta sẽ tạo được đường đi có độ dài l+1:

${\displaystyle v_{1}v_{2}...v_{i_{j}-1}v_{i_{j}}v_{l}v_{l-1}...v_{i_{j}+1}v_{l+1}}$

(vô lý).

Vậy ${\displaystyle v_{l+1}}$ không liền kề với các đỉnh ${\displaystyle v_{i_{j}+1}}$, với j chạy từ 1 đến t. Mà ${\displaystyle t}$≥${\displaystyle {\frac {n}{2}}}$, nên suy ra bậc của ${\displaystyle v_{l+1}}$ nhỏ hơn ${\displaystyle {\frac {n}{2}}}$ (vô lý).

Vậy trường hợp l<n là không tồn tại.

Suy ra điều phải chứng minh.

Ứng dụng của nó là bài toán nổi tiếng sau:

Bài toán: Tại một hội nghị có 2n quan khách.trong đó mỗi quan khách có nhiều nhất n-1 kẻ thù.chứng minh rằng có thể xếp 2n nguời đó trên 1 vòng tròn sao cho không ai ngồi cạnh kẻ thù của mình 

Lời giải:

Ta xây dựng đồ thị G như sau:

-Đỉnh: là các điểm trong mặt phẳng hay trong không gian tương ứng với các quan khách, dùng mã số của các quan khách để ghi trên các đỉnh tương ứng.

-Cạnh: hai đỉnh được nối với nhau bằng cạnh khi và chỉnh khi hai quan khác tương ứng thuộc hai đỉnh đó không là kẻ thù của nhau.

Khi đó ta được một đồ thị G mô tả toàn bộ quan hệ giữa các quan khách. Vì đồ thị G có đúng 2n đỉnh, và mỗi đỉnh có bậc không nhỏ hơn n nên theo định lý Dirac ta có G có chu trình Halminton. Dựa vào chu trình này ta có thể xếp tất cả các quan khách thỏa mãn yêu cầu đề bài

Định lý Dirichle

(Định lí Dirichle) Cho $\alpha$ là một số vô tỉ. Chứng minh rằng, tồn tại vô hạn các số nguyên p,q với q>0 sao cho:

$|\alpha -\frac{p}{q}| <\frac{1}{q^2}$

Lời giải:

Trước hết ta chứng minh với mọi $ N \ge q$ luôn tồn tại p,q thỏa mãn:

$|\alpha -\frac{p}{q}| <\frac{1}{qN}$

Thật vậy ta chia các [0;1) thành các khoảng $[\frac{k-1}{N};\frac{k}{N})(k =\overline{1,N})$

Thì theo nguyên lý Dirichle sẽ tồn tại hai số { $\alpha q_i$ } và { $\alpha q_j$ } thuộc vào một đoạn (  q= 0,1,..N)

$\Rightarrow \left | \begin{Bmatrix}
\alpha q_i
\end{Bmatrix}- \begin{Bmatrix}
\alpha q_j
\end{Bmatrix} \right |<\frac{1}{N(q_i-q_j)}\\\Rightarrow \left | \alpha -\frac{\begin{bmatrix}
\alpha q_i
\end{bmatrix}-\begin{bmatrix}
\alpha q_j
\end{bmatrix}}{q_i-q_j} \right | <\frac{1}{N(q_i-q_j)}$ Điều phải chứng minh.

Ta giả sử chỉ có hữu hạn các số p,q thỏa mãn đề bài Kí hiệu tập này là X.

Khi đó sẽ tồn tại M sao cho $|\alpha -\frac{p}{q}| >M$

Chọn N sao cho $\frac{1}{M}<N$ Khi đó tồn tại các số nguyên dương $p_i, q_i$ sao cho
$|\alpha -\frac{p_i}{q_i}| <\frac{1}{q_iN} <\frac{1}{q_iN}<\frac{1}{q_i^2}$

Suy ra $p_i,q_i$ thuộc X, nhưng $M >\frac{1}{q_iN} $ (mâu thuẫn)

Vậy ta có điều phải chứng minh.

Bài tổ hợp nhỏ

Bài toán: Có một số học sinh xếp thành một vòng tròn. Cô giáo yêu cầu các bạn học sinh đứng cạnh nhau bắt tay nhau. Gọi b là số học sinh nam, g là số học sinh nữ, B là số cặp học sinh nam bắt tay nhau và G là số cặp học sinh nữ bắt tay nhau. Chứng minh rằng: b-g=B-G. 

Lời giải của bài toán rất đơn giản như sau:

Dĩ nhiên số học sinh là $1$ thì không có gì để nói. Ta sẽ xét số học sinh từ $2$ trở lên
i) Với số học sinh là hai, ta xét là TRAI - TRAI, GÁI - GÁI, GÁI - TRAI thì thấy khẳng định bài toán đúng.
ii) Bây giờ giả sử bài toán đúng với số học sinh $n$. Bây giờ ta thêm một em học sinh vô. Vai trò mấy em này như nhau, nên giả sử ta thêm bạn nữ vào
Khi đó $B' = B$ và $G' = G + 1$.
a) TH1. Ta nhét em ấy vào giữa GÁI - GÁI thì $b' = b$ và $g' = g + 1$. Khi đó $B' - G' = B - G - 1 = b - g - 1 = b' - g'$.
b) TH2. Ta nhét em ấy vào giữa TRAI - GÁI thì $b' = b$ và $g' = g + 1$. Tương tự trên ta cũng có đpcm.
c) TH3. Ta nhét em ấy vào giữa TRAI - TRAI thì $b' = b - 1$ và $g' = g$. Lúc đó $B' - G' = B - G - 1 = b - 1 - g = b' - g'$. Xong.