Category: College Math

Một bài toán có nhiều cách giải (1)


Hãy giải bài toán sau theo ít nhất 3 cách:

Bài toán. Cho q là số nguyên dương không phải là lập phương của một số nguyên. Chứng minh rằng tồn tại hằng số dương C sao cho với mỗi số nguyên dương n, ta có
\displaystyle \{nq^{\frac{1}{3}}\} + \{ nq^{\frac{2}{3}} \} \geq Cn^{-\frac{1}{2}}.

Chu kỳ cơ sở của dãy Fibonacci modulo m là một số chẵn


Chúng ta đã biết là với mỗi số nguyên dương m, dãy Fibonacci modulo m là một dãy tuần hoàn. Với mọi số nguyên dương m, gọi \pi (m) là chu kỳ cơ sở của dãy đó. Trong bài này tôi sẽ giới thiệu một chứng minh cho kết quả sau:

Định lí (D. D. Wall, 1960). Với mọi số nguyên m>2, \pi (m) là một số chẵn.

Chứng minh. Với mỗi số nguyên dương m, cố định nó. Gọi k là số nguyên dương bé nhất sao cho F_k chia hết cho m, và \varphi là tỷ số vàng.

Vì F_k\equiv 0\pmod{m} nên F_{k+1}\equiv F_{k-1}\pmod{m}, do đó F_{k+i}\equiv F_{k+1}F_i\pmod{m},\quad\forall i\in\mathbb{N}^*.

Từ kết quả trên ta có F_{k\text{ord}_m(F_{k+1})+1}\equiv F_{k\text{ord}_m(F_{k+1})+2}\equiv F_{k+1}^{\text{ord}_m(F_{k+1})}\equiv 1\pmod{m}, suy ra \pi (m)=k\text{ord}_m(F_{k+1}).\quad (*)

Bây giờ trong \mathbb{Z}[\varphi], ta có \varphi^k\equiv (1-\varphi)^k\pmod{m}, suy ra F_{k+1}\equiv \varphi^k\pmod{m}, nhưng ta biết \varphi^{4k}\equiv 1\pmod{m}, do đó \pi (m)\in \{k,2k,4k\}. Nếu \pi (m) không phải là số chẵn thì \pi (m)=k và k là số lẻ. Khi đó từ (*) ta được \text{ord}_m(F_{k+1})=1, suy ra 1\equiv \varphi^k\pmod{m}. Kết hợp điều này với \varphi^{2k}\equiv (-1)^k\pmod{m} ta thu được m\mid 2, vô lý.

Một chứng minh khác có trong bài của Wall ở AMM, Vol 67, trang 525.

Các căn bậc hai là độc lập nguyên


Bài toán. Cho a_1,\ldots,a_k là các số nguyên không đồng thời bằng 0. Chứng minh rằng nếu n_1, n_2,\ldots, n_k là các số nguyên dương đôi một khác nhau và không có ước chính phương lớn hơn 1 thì \sum a_i\sqrt{n_i}\not=0. 

Lời giải. Ta sẽ chứng minh bằng quy nạp theo N, số ước nguyên tố của \prod n_i, khẳng định: Tồn tại tổng S'=\sum b_i\sqrt{m_i} sao cho SS' là số nguyên khác 0, ở đây m_i là các số nguyên dương đôi một khác nhau và không có ước chính phương khác 1, tập các ước nguyên tố của \prod m_i là tập con của tập các ước nguyên tố của \prod n_i, b_i là các số nguyên, và S=\sum a_i\sqrt{n_i}. Từ đó suy ra S\not=0.

Với N=0 ta chọn S'=1.

Với N=1 ta chọn S'=\sqrt{p_1} khi S=a_1\sqrt{p_1}, chọn S'=-a_1\sqrt{p_1}+a_2 nếu S=a_1\sqrt{p_1}+a_2.

Continue reading “Các căn bậc hai là độc lập nguyên”

Popoviciu’s theorem


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

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.