An Upper Bound for the Divisor Function

Bổ đề. Với mỗi số nguyên dương $n$ , ta có $\tau (n)\leq \sqrt{3n}$ .

Lời giải. Với $n=1$ ta có ngay bất đẳng thức cần chứng minh. Giả sử $n>1$ và phân tích tiêu chuẩn ra thừa số nguyên tố của nó là $\displaystyle n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ , trong đó $p_i$ là các số nguyên tố ( $p_1 < p_2 < \dots < p_k$ ) và $\alpha_i \ge 1$ là các số nguyên dương.

Bất đẳng thức cần chứng minh $\tau(n) \le \sqrt{3n}$ có thể được viết lại dưới dạng

$\displaystyle\prod_{i=1}^k \frac{\alpha_i + 1}{p_i^{\alpha_i / 2}} \le \sqrt{3}.$

Để tiện đánh giá, ta xét hàm số $f(p, \alpha) = \frac{\alpha + 1}{p^{\alpha / 2}}$ với $p$ là số nguyên tố và $\alpha \ge 1$ . Ta sẽ tìm giá trị lớn nhất của hàm $f(p, \alpha)$ đối với từng số nguyên tố $p$ .

Với $p = 2$ , giá trị lớn nhất của của $f(2, \alpha)$ là $\frac{3}{2}$ , đạt được khi và chỉ khi $\alpha = 2$ . Với $p = 3$ , giá trị lớn nhất của $f(3, \alpha)$ là $\frac{2}{\sqrt{3}}$ , đạt được khi và chỉ khi $\alpha = 1$ . Với $p\geq 5$ , ta có
$\displaystyle f(p, \alpha) \le \frac{2}{\sqrt{5}} < 1$
với mọi số nguyên dương $\alpha$ .

Từ các đánh giá trên, ta quay lại tích ban đầu $\displaystyle\frac{\tau(n)}{\sqrt{n}} = \prod_{p_i \mid n} f(p_i, \alpha_i).$

Nếu trong phân tích của $n$ có chứa các thừa số nguyên tố $p \ge 5$ , các thành phần này sẽ kéo giá trị của tích xuống (vì chúng nhỏ hơn 1). Do đó để biểu thức đạt giá trị lớn nhất, $n$ chỉ có thể chứa các ước nguyên tố là 2 và 3. Với các $n$ này ta có

$\displaystyle \frac{\tau(n)}{\sqrt{n}} \le f(2, \alpha_2) \cdot f(3, \alpha_3) \le \frac{3}{2} \cdot \frac{2}{\sqrt{3}} = \sqrt{3}.$

Bất đẳng thức $\tau(n) \le \sqrt{3n}$ đã được chứng minh hoàn toàn. $\Box$

Chú ý. Dấu đẳng thức xảy ra khi và chỉ khi các điều kiện sau phải được thỏa mãn đồng thời:

$f(2, \alpha_2) = \frac{3}{2}$ .
$f(3, \alpha_3) = \frac{2}{\sqrt{3}}$ .
$n$ không có bất kỳ ước nguyên tố nào khác ngoài 2 và 3.

Vậy dấu đẳng thức xảy ra khi và chỉ khi $n = 2^2 \cdot 3^1 = 12$ .

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.

Combinatorial Nullstellensatz

Trong bài này chúng tôi giới thiệu một chứng minh ngắn của định lý không điểm tổ hợp của Noga Alon, và sử dụng nó chứng minh định lý Cauchy – Davenport (xem [1]). Từ bây giờ, khi nói đến trường thì các bạn hiểu là nói đến $\displaystyle \mathbb{C}$ , $\displaystyle \mathbb{R}$ , $\displaystyle \mathbb{Q}$ , hay $\displaystyle \mathbb{Z}/p\mathbb{Z}$ .

Định lý 1 (N. Alon, 1999). Cho $\displaystyle \mathbb{F}$ là một trường bất kỳ, và cho $\displaystyle P\left(x_{1}, \ldots, x_{n}\right)$ là một đa thức trong $\displaystyle \mathbb{F}\left[x_{1}, \ldots, x_{n}\right]$ . Giả sử bậc của $\displaystyle P$ là $\displaystyle \sum_{i=1}^{n} k_{i}$ , trong đó $\displaystyle k_{i}$ là một số nguyên không âm, và hệ số của đơn thức $\displaystyle x_{1}^{k_{1}} x_{2}^{k_{2}} \cdots x_{n}^{k_{n}}$ trong $\displaystyle P$ khác không. Khi đó với mỗi tập con $\displaystyle A_{1}, \ldots, A_{n}$ của $\displaystyle \mathbb{F}$ thỏa mãn $\displaystyle \left|A_{i}\right| \geq k_{i}+1$ với mỗi $\displaystyle i=1,2, \ldots, n$ , tồn tại $\displaystyle a_{1} \in A_{1}, \ldots, a_{n} \in A_{n}$ để $\displaystyle P\left(a_{1}, \ldots, a_{n}\right) \neq 0$ .

Định lý trên được gọi là định lý không điểm tổ hợp, nó là một tổng quát của kết quả: Với mỗi đa thức khác không $\displaystyle f(x)$ với hệ số thuộc một trường $\displaystyle \mathbb F$ , số nghiệm của $\displaystyle f$ trong $\displaystyle \mathbb F$ không vượt quá $\displaystyle \deg f$ .

Chứng minh (Mateusz Michalek). Khẳng định là đúng một cách hiển nhiên khi $\displaystyle P$ là đa thức hằng, bây giờ ta xét trường hợp còn lại.

Quy nạp theo $\displaystyle \deg P$ . Nếu $\displaystyle \deg(P)=1$ thì định lý là đúng. Giả sử $\displaystyle \deg(P)>1$ và $\displaystyle P$ thỏa mãn các giả thiết của định lý nhưng kết luận là sai. Nghĩa là $\displaystyle P(x)=0$ với mọi $\displaystyle x \in A_{1} \times \ldots \times A_{n}$ . Không mất tính tổng quát, giả sử $\displaystyle k_{1}>0$ . Xét một $\displaystyle a \in A_{1}$ và viết

$\displaystyle P=\left(x_{1}-a\right) Q+R\quad \quad (1)$

bằng cách sử dụng thuật toán chia. Xem (1) là một đẳng thức của các đa thức một biến $\displaystyle x_{1}$ với hệ số thuộc $\displaystyle \mathbb{F}\left[x_{2}, \ldots, x_{n}\right]$ . Vì bậc của $\displaystyle R$ theo biến $\displaystyle x_{1}$ là bé hơn $\displaystyle \deg\left(x_{1}-a\right)$ , đa thức $\displaystyle R$ không chứa $\displaystyle x_{1}$ . Từ giả thiết về $\displaystyle P$ ta có $\displaystyle Q$ phải có một đơn thức không bị triệt tiêu có dạng $\displaystyle x_{1}^{k_{1}-1} x_{2}^{k_{2}} \cdots x_{n}^{k_{n}}$ và

$\displaystyle \deg(Q)=\sum_{i=1}^{n} k_{i}-1=\deg(P)-1.$

Lấy mỗi $\displaystyle x \in\{a\} \times A_{2} \times \ldots \times A_{n}$ và thay vào (1). Vì $\displaystyle P(x)=0$ ta có $\displaystyle R(x)=0$ . Nhưng $\displaystyle R$ không chứa $\displaystyle x_{1}$ , suy ra $\displaystyle R$ cũng bằng không trên $\displaystyle \left(A_{1}-\{a\}\right) \times A_{2} \times \ldots \times A_{n}$ .

Bây giờ thay mỗi $\displaystyle x \in\left(A_{1}-\{a\}\right) \times A_{2} \times \ldots \times A_{n}$ vào (1). Vì $\displaystyle x_{1}-a$ khác không, ta có $\displaystyle Q(x)=0$ . Vậy là $\displaystyle Q$ bằng không trên $\displaystyle \left(A_{1}-\{a\}\right) \times A_{2} \times \ldots \times A_{n}$ , trái với giả thiết quy nạp. $\Box$

Một áp dụng đầu tiên là chứng minh ngắn của định lý Cauchy – Davenport trong lý thuyết số cộng tính. Định lý được chứng minh đầu tiên bởi Cauchy vào năm 1813 và bởi Davenport vào năm 1935. Cho $\displaystyle A$ và $\displaystyle B$ là hai tập con khác rỗng của $\displaystyle \mathbb{Z}/{p}\mathbb{Z}$ với $\displaystyle \mid A\mid =a$ và $\displaystyle \mid B\mid =b$ . Hỏi tập

$\displaystyle A+B:=\{a+b\mid (a,b)\in A\times B\}$

có thể có ít nhất bao nhiêu phần tử?

Định lý 2 (Cauchy – Davenport). Cho số nguyên tố $\displaystyle p$ và cho $\displaystyle A$ và $\displaystyle B$ là hai tập con khác rỗng của $\displaystyle \mathbb{Z}/{p}\mathbb{Z}$ với $\displaystyle \mid A\mid =a$ và $\displaystyle \mid B\mid =b$ . Khi đó

$\displaystyle |A+B|\geq\min \{p,a+b-1\}.$

Chứng minh. Nếu $\displaystyle a+b>p$ thì $\displaystyle \mid A+B\mid =p$ . Thật vậy, với mỗi $\displaystyle g\in \mathbb{Z}/{p}\mathbb{Z}$ , hai tập $\displaystyle g-A$ và $\displaystyle B$ có giao khác rỗng vì $\displaystyle a+b>p$ . Lấy $\displaystyle h\in (g-A)\cap B$ ta có ngay $\displaystyle h=b=g-a\quad (a\in A,b\in B),$ suy ra $\displaystyle g=a+b\in A+B$ . Từ đây ta có $\displaystyle |A+B|=p=\min \{p,a+b-1\}.$

Bây giờ ta xét $\displaystyle a+b\leq p$ và giả sử bất đẳng thức là sai. Gọi $\displaystyle C$ là một tập có cỡ $\displaystyle a+b-2$ trong $\displaystyle \mathbb{Z}/{p}\mathbb{Z}$ chứa $\displaystyle A+B$ . Xét đa thức

$\displaystyle f(x, y)=\prod_{c \in C}(x+y-c)$

trên $\displaystyle \mathbb{Z}/{p}\mathbb{Z}$ . Đây là một đa thức hai biến có bậc $\displaystyle a+b-2$ . Ta sẽ chứng minh

$\displaystyle \left[x^{a-1} y^{b-1}\right] f(x, y)=\left(\begin{array}{c}a+b-2 \\ a-1\end{array}\right) \not =0.$

Để hình thành hệ số này khi khai triển $\displaystyle f$ , ta chọn $\displaystyle x$ đúng $\displaystyle a-1$ lần và $\displaystyle y$ đúng $\displaystyle b-1$ lần trong $\displaystyle a+b-2$ thừa số. Như vậy ta có đẳng thức đầu. Hệ số nhị thức khác không là vì $\displaystyle a+b-2<p$ và $\displaystyle p$ là số nguyên tố.

Vì $\displaystyle |A|=a$ và $\displaystyle |B|=b$ , định lý không điểm tổ hợp cho ta $\displaystyle x \in A$ và $\displaystyle y \in B$ mà $\displaystyle f(x, y) \neq 0$ . Điều này không thể xảy ra vì $\displaystyle f$ đã được dựng để triệt tiêu trên mọi cặp $\displaystyle (x, y)$ như vậy. $\Box$

Bài đọc thêm

[1] https://nttuan.org/2014/09/29/cauchy-davenport/

Iran Team Selection Test 2009

Ngày 1

Bài 1: Cho tam giác $ABC$ và các điểm $A^{\prime}$ , $B^{\prime}$ , $C^{\prime}$ lần lượt nằm trên $BC$ , $CA$ , $AB$ sao cho tâm đường tròn nội tiếp của tam giác $A^{\prime}B^{\prime}C^{\prime}$ và tam giác $ABC$ trùng nhau, đồng thời bán kính đường tròn nội tiếp tam giác $A^{\prime}B^{\prime}C^{\prime}$ bằng một nửa bán kính đường tròn nội tiếp tam giác $ABC$ . Chứng minh rằng $ABC$ là tam giác đều.

Bài 2: Cho $a$ là một số tự nhiên cố định. Chứng minh rằng tập hợp các ước nguyên tố của $2^{2^{n}}+a$ với $n=1,2,\dots$ là vô hạn.

Bài 3: Giả sử $a, b, c$ là ba số thực dương thỏa mãn $a+b+c=3$ . Chứng minh rằng

$\displaystyle\frac{1}{2+a^{2}+b^{2}}+\frac{1}{2+b^{2}+c^{2}}+\frac{1}{2+c^{2}+a^{2}}\le\frac{3}{4}$ .

Ngày 2

Bài 4: Tìm tất cả các đa thức $f$ với hệ số nguyên sao cho, với mọi số nguyên tố $p$ và các số tự nhiên $u, v$ thỏa mãn điều kiện $p|uv-1$ , ta luôn có $p|f(u)f(v)-1$ .

Bài 5: Cho tam giác $ABC$ có $AA^{\prime}$ , $BB^{\prime}$ và $CC^{\prime}$ là ba đường cao. Gọi $P$ là chân đường vuông góc hạ từ $C^{\prime}$ xuống $A^{\prime}B^{\prime}$ , và $Q$ là một điểm trên $A^{\prime}B^{\prime}$ sao cho $QA=QB$ . Chứng minh rằng:
$\angle PBQ=\angle PAQ=\angle PC^{\prime}C$

Bài 6: Cho một đường đi khép kín trên các đỉnh của một lưới hình vuông $n \times n$ đi qua mỗi đỉnh đúng một lần. Chứng minh rằng tồn tại hai đỉnh kề nhau sao cho nếu ta cắt đường đi tại hai điểm này thì độ dài của mỗi phần nhận được không nhỏ hơn một phần tư tổng chiều dài đường đi.

Continue reading →

Canadian Mathematical Olympiad 2008

Bài 1. Cho $ABCD$ là một tứ giác lồi có $AB$ là cạnh dài nhất. Các điểm $M$ và $N$ lần lượt nằm trên các cạnh $AB$ và $BC$ , sao cho mỗi đoạn thẳng $AN$ và $CM$ chia tứ giác thành hai phần có diện tích bằng nhau. Chứng minh rằng đoạn thẳng $MN$ chia đôi đường chéo $BD$ .

Bài 2. Tìm tất cả các hàm số $f$ xác định trên tập hợp các số hữu tỉ và nhận giá trị hữu tỉ sao cho $f(2f(x)+f(y))=2x+y$ , với mỗi $x$ và $y$ .

Bài 3. Cho $a, b, c$ là các số thực dương thỏa mãn $a+b+c=1$ . Chứng minh rằng

$\displaystyle\frac{a-bc}{a+bc}+\frac{b-ca}{b+ca}+\frac{c-ab}{c+ab}\le\frac{3}{2}$ .

Bài 4. Tìm tất cả các hàm số $f$ xác định trên tập hợp các số tự nhiên và nhận giá trị là các số tự nhiên sao cho $(f(n))^{p}\equiv n \pmod{f(p)}$ với mọi $n\in \mathbb{N}$ và mọi số nguyên tố $p$ .

Bài 5. Một đường đi của quân xe không tự cắt trên một bàn cờ (một lưới chữ nhật gồm các ô vuông đơn vị) là một đường đi được tạo ra bởi một chuỗi các nước đi song song với một cạnh của bàn cờ từ một ô vuông đơn vị này sang một ô vuông đơn vị khác, sao cho mỗi nước đi bắt đầu từ nơi nước đi trước đó kết thúc và không có nước đi nào đi qua một ô vuông đã được đi qua trước đó, tức là đường đi của quân xe không tự cắt. Gọi $R(m,n)$ là số các đường đi của quân xe không tự cắt trên một bàn cờ kích thước $m\times n$ ( $m$ hàng, $n$ cột) bắt đầu tại góc dưới bên trái và kết thúc tại góc trên bên trái. Ví dụ, $R(m,1)=1$ với mọi số tự nhiên $m$ ; $R(2,2)=2$ ; $R(3,2)=4$ ; $R(3,3)=11$ . Tìm một công thức cho $R(3,n)$ với mỗi số tự nhiên $n$ .