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ỏ.

Dùng cấp để tìm các số thỏa mãn bài toán

Đề bài: Tìm $p,q$ nguyên tố sao cho $2^{p}+2^{q}\vdots (pq).$

Lời giải:

Dễ thấy $(p,q)=(2,2),(3,2),(2,3)$.

Nếu $p,q \ge 3$. Dùng định lý Fermat nhỏ, ta có $2^{p} \equiv 2 \pmod{p}$. Vì thế $p|2^{q-1}+1$. Ta được $2^{q-1} \equiv -1 \pmod{p}$.

Đặt $q-1=2^x \cdot y$ với $x,y \in \mathbb{N}^*, \; \gcd(y,2)=1$ và đặt $2^y=k$, ta được $2^{q-1}=(2^y)^{2^x} \equiv -1 \pmod{p} \Rightarrow k^{2^{x+1}} \equiv 1 \pmod{p}$.

Ta có $\text{ord}_p(k) |2^{x+1}$.

Vì $k^{2^x} \equiv -1 \pmod{p}$ nên $p \nmid k^{2^x}$. Vì thế $\text{ord}_p(k) \nmid 2^x$. 

Vậy $\text{ord}_p(k)=2^{x+1}$. 

Ta cũng có $2^{p-1} \equiv 1 \pmod{p}$. Nên $2^{x+1}|p-1$. Đặt $p=2^{u} \cdot l+1$ với $u,l \in \mathbb{N}^*, \; \gcd (l,2)=1$ thì $u \ge x+1$.

Tương tự ta cũng được $x \ge u+1$, mâu thuẫn

Vậy câu trả lời là $\boxed{ (x,y)=(2,2),(3,2),(2,3) $

Bài tập tương tự: Tìm $p,q$ nguyên tố sao cho $5^p+5^q \vdots pq$ ( lưu ý là phải xét thêm $p,q =2$)

Tính chất của số nguyên tố có dạng $3k+2$

Cho $p$ là số nguyên tố thỏa mãn $3 | p-2$ khi đó $p | x^3 -y^3$ khi và chỉ khi $p | x-y$

Chứng minh:

Ta xét $ x,y $ không chia hết cho $p$ vì nếu chia hết cho p là hiển nhiên.
Nếu $ x \equiv y (mod p)$ thì $ x^3 \equiv y^3 (mod p)$
Ta chứng minh Nếu $ x^3 \equiv y^3 (mod p)$ thì $ x \equiv y (mod p)$

$x^{3} \equiv y^3 (mod p)  \Rightarrow x^{p-2}\equiv y^{p-2}(mod p)$

Theo định lý Fermat nhỏ:

$x^{p-1}\equiv y^{p-1} \equiv 1(mod p) \Rightarrow x^{p-2}(x-y) \equiv 0 (mod p) \Rightarrow x \equiv y (mod p)$

Xét ứng dụng của bổ đề trên:

Bài toán ( Chọn đội tuyển QG tỉnh Lạng Sơn 2016): Cho đa thức $P(x)=4x^3-18x^2+27x+m$. CMR: Với mỗi $m\in\mathbb{Z}$, $\exists n\in\mathbb{Z}$ sao cho $P(n)\vdots 107$

Lời giải:
Do (2, 107)=1 nên:
$P(n)\vdots 107 \Leftrightarrow  2P(n)\vdots 107$

Xét $G(x)=2P(x)=(2x-3)^2+27+2m$

Với mỗi $m$ ta có $G(0), G(1), . G(106)$ lập thành một hệ thặng dư đầy đủ mod 107. Thật vậy:

Nếu có $i ,j $ mà $  0\ge i, j \le 106$ mà $G(i) \equiv G(j) (mod 107)$ Thì khi đó theo bổ đề trên:
 $i \equiv j (mod 107)$ hay $ i=j$.

Vậy luôn tồn tại $n$ sao cho $P(n)\vdots 107$

Đa thức hệ số hữu tỉ

Đề bài: Tìm tất cả đa thức hệ số hữu tỷ $P(n)$ thoả $P(n)\mid 2^{n} - 1$ với mọi số tự nhiên $n$.

Lời giải:

Các kết quả cơ bản dùng cho lời giải
i) $n = \pm 1$ là số nguyên duy nhất thoả mãn $\pm n\mid 2^{|n|} - 1$
ii) $P(n) \mid P(P(n) + n)$
Lưu ý là ta chỉ quan tâm các đa thức nhận giá trị nguyên với $n$ tự nhiên nên ii) vẫn đúng.
Theo đó, ta có $P(n) \mid P(P(n) + n) \mid 2^{P(n) + n} - 1$. Mặt khác, $P(n)\mid 2^{n} - 1$
Tóm lại ta thu được $P(n) \mid 2^{P(n)}$. Suy ra $P(n) = 1$ hoặc $P(n) = -1$ có vô hạn nghiệm, đến đây dễ suy ra rằng $P(x) = 1$ với mọi $x$ hay $P(x) = -1$ với mọi $x$

Chứng minh i)

Giả sử p là ước nguyên tố nhỏ nhất của $n$ theo Định lý Fermat nhỏ:

 

$2^{p-1} \equiv 1 (mod p)$

mà $(p-1, n)=1$ Suy ra $ord_p(2)=1$ hoặc bằng $p-1$ trường hợp bằng 1 là đơn giản.

Xét trường hợp $ord_p(2)=p-1$ Khi đó: $n=(p-1)k+r( 0<r<p-1)$

Suy ra: $2^n \equiv 2^r \equiv 1 (mod p)$ vô lí do $ord_p(2)=p-1 >r$

Vậy ta có đpcm.

ii) Ta dùng bổ đề đơn giản sau: $P(a)-P(b) \vdots a-b$