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

Asian Pacific Mathematics Olympiad 2009

Bài 1. Xét phép toán sau trên các số thực dương được viết trên bảng: Chọn một số $r$ được viết trên bảng, xóa số đó, và sau đó viết một cặp số thực dương $a$ và $b$ thỏa mãn điều kiện $2r^2=ab$ lên bảng. Giả sử ban đầu bạn chỉ có một số thực dương trên bảng, và thực hiện phép toán này $k^2-1$ lần để cuối cùng thu được $k^2$ số thực dương, không nhất thiết phân biệt. Chứng minh rằng tồn tại một số trên bảng không vượt quá $kr$ .

Bài 2. Cho $a_1, a_2, a_3, a_4, a_5$ là các số thực thỏa mãn $\frac{a_1}{k^2+1} + \frac{a_2}{k^2+2} + \frac{a_3}{k^2+3} + \frac{a_4}{k^2+4} + \frac{a_5}{k^2+5} = \frac{1}{k^2}$ với $k=1,2,3,4,5$ . Tìm giá trị của $\frac{a_1}{37} + \frac{a_2}{38} + \frac{a_3}{39} + \frac{a_4}{40} + \frac{a_5}{41}$ (Biểu diễn giá trị dưới dạng một phân số duy nhất.)

Bài 3. Cho ba đường tròn $\Gamma_1, \Gamma_2, \Gamma_3$ không giao nhau và rời nhau từng đôi một trên mặt phẳng. Với mỗi điểm $P$ trên mặt phẳng, nằm ngoài ba đường tròn, dựng sáu điểm $A_1, B_1, A_2, B_2, A_3, B_3$ như sau: Với mỗi $i=1,2,3$ , $A_i, B_i$ là các điểm phân biệt trên đường tròn $\Gamma_i$ sao cho các đường thẳng $PA_i$ và $PB_i$ đều là tiếp tuyến của $\Gamma_i$ . Gọi điểm $P$ là điểm ngoại lệ nếu, từ cách dựng trên, ba đường thẳng $A_1B_1, A_2B_2, A_3B_3$ đồng quy. Chứng minh rằng mọi điểm ngoại lệ trên mặt phẳng, nếu tồn tại, đều nằm trên cùng một đường tròn.

Bài 4. Chứng minh rằng với mọi số nguyên dương $k$ , tồn tại một cấp số cộng $\frac{a_1}{b_1}$ , $\frac{a_2}{b_2}$ , $\dots$ , $\frac{a_k}{b_k}$ gồm các số hữu tỉ, trong đó $a_i, b_i$ là các số nguyên dương nguyên tố cùng nhau với mỗi $i=1,2,\dots,k$ , sao cho các số nguyên dương $a_1, b_1, a_2, b_2, \dots, a_k, b_k$ đều phân biệt.

Bài 5. Larry và Rob là hai robot đi cùng một chiếc xe từ Argovia đến Zillis. Cả hai robot đều có quyền điều khiển vô lăng và rẽ theo thuật toán sau: Larry rẽ trái $90^\circ$ sau mỗi $l$ kilômét lái xe tính từ điểm xuất phát; Rob rẽ phải $90^\circ$ sau mỗi $r$ kilômét lái xe tính từ điểm xuất phát, trong đó $l$ và $r$ là các số nguyên dương nguyên tố cùng nhau. Trong trường hợp cả hai lượt rẽ xảy ra đồng thời, xe sẽ tiếp tục đi thẳng mà không chuyển hướng. Giả sử mặt đất bằng phẳng và xe có thể di chuyển theo bất kỳ hướng nào. Giả sử xe xuất phát từ Argovia và hướng về phía Zillis. Với những lựa chọn nào của cặp $(l, r)$ thì xe được đảm bảo sẽ đến Zillis, bất kể khoảng cách từ Argovia là bao xa?

Japan Mathematical Olympiad 2008 (Finals)

Bài 1. Cho $P(x)$ là một đa thức với hệ số nguyên sao cho $P(n^{2})=0$ với một số nguyên khác không $n$ nào đó. Chứng minh rằng $P(a^{2})\ne1$ với mọi số hữu tỉ $a\ne0$ .

Bài 2. Có 2008 thẻ đỏ và 2008 thẻ trắng. 2008 người chơi ngồi thành một vòng tròn hướng mặt vào trong, với tình trạng ban đầu là mỗi người được chia 2 thẻ. Mỗi người thực hiện quy trình sau trong cùng một lượt:
(*) Nếu bạn có nhiều hơn một thẻ đỏ, bạn sẽ chuyển một thẻ đỏ cho người ngồi liền kề bên trái.

Nếu bạn không có thẻ đỏ nào, bạn sẽ chuyển một thẻ trắng cho người ngồi liền kề bên trái.
Tìm giá trị lớn nhất của số lượt cần thiết để đạt được trạng thái mà tất cả mọi người đều có một thẻ đỏ và một thẻ trắng lần đầu tiên.

Bài 3. Cho tam giác nhọn $ABC$ có tâm đường tròn ngoại tiếp $O$ . Đường tròn đi qua hai điểm $A, O$ cắt các đường thẳng $AB$ và $AC$ lần lượt tại $P, Q$ (khác $A$ ). Nếu độ dài các đoạn thẳng $PQ$ và $BC$ bằng nhau, hãy tìm góc $\le90^{\circ}$ tạo bởi hai đường thẳng $PQ$ và $BC$ .

Bài 4. Tìm tất cả các hàm số $f:\mathbb{R}\rightarrow\mathbb{R}$ thỏa mãn $f(x+y)f(f(x)-y)=xf(x)-yf(y)$ với mọi $x,y\in\mathbb{R}$ .

Bài 5. Có tồn tại hay không một số nguyên dương $n$ sao cho với mọi số hữu tỉ $r$ , tồn tại một số nguyên $b$ và các số nguyên khác không $a_{i}$ ( $i=1,2,\dots, n$ ) thỏa mãn $r=b+\sum_{i=1}^{n}\frac{1}{a_{i}}$ ?