A Proof of Beatty’s Theorem

Cho số thực $\alpha$ . Dãy Beatty của $\alpha$ là dãy $(a_n)_{n\geq 1}$ xác định bởi $a_n=[n\alpha],\quad \forall n\geq 1.$

Định lý (Beatty). Cho hai số thực dương $\alpha$ và $\beta$ . Khi đó các dãy Beatty của $\alpha$ và $\beta$ làm thành một phân hoạch của tập các số nguyên dương khi và chỉ khi $\alpha$ và $\beta$ là các số vô tỷ và

$\displaystyle \frac{1}{\alpha}+\frac{1}{\beta}=1.$

Chứng minh. Đặt $S_{\alpha}=\{[n\alpha]|n=1,2,\ldots\}$ và $\displaystyle S_{\beta}=\{[n\beta]|n=1,2,\ldots\}.$

Giả sử $S_{\alpha}$ và $S_{\beta}$ làm thành một phân hoạch của tập các số nguyên dương. Ta thấy ngay $\alpha$ và $\beta$ lớn hơn $1$ , suy ra hai dãy Beatty của hai số này là các dãy tăng. Ta sẽ sử dụng phương pháp mật độ trong lý thuyết số giải tích.

Với mỗi số nguyên dương $k$ , cố định nó. Xét một số nguyên dương $n$ , ta có

$\displaystyle [n\alpha]\leq k\Leftrightarrow n\alpha < k+1\Leftrightarrow n < \dfrac{k+1}{\alpha}.$

Suy ra $|S_{\alpha}\cap \{1, 2, \ldots, k\}|=\left[\dfrac{k+1}{\alpha}\right]$ hoặc $\left[\dfrac{k+1}{\alpha}\right]-1$ tùy theo $\dfrac{k+1}{\alpha}$ không nằm trong hay nằm trong $\mathbb{Z}$ . Chứng minh tương tự ta có $\displaystyle |S_{\beta}\cap \{1, 2, \ldots, k\}|=\left[\dfrac{k+1}{\beta}\right]$ hoặc $\left[\dfrac{k+1}{\beta}\right]-1$ tùy theo $\dfrac{k+1}{\beta}$ không nằm trong hay nằm trong $\mathbb{Z}$ .

Mà $|S_{\alpha}\cap \{1, 2, \ldots, k\}|+|S_{\beta}\cap \{1, 2, \ldots, k\}|=k$ , suy ra

$\displaystyle -2+\left[\dfrac{k+1}{\alpha}\right]+\left[\dfrac{k+1}{\beta}\right]\leq k\leq \left[\dfrac{k+1}{\alpha}\right]+\left[\dfrac{k+1}{\beta}\right].$

Kết hợp với định nghĩa phần nguyên ta được

$\displaystyle -4+\dfrac{k+1}{\alpha}+\dfrac{k+1}{\beta} < k\leq \dfrac{k+1}{\alpha}+\dfrac{k+1}{\beta}.$

Chia các vế cho $k$ và cho $k\to+\infty$ ta có $\dfrac{1}{\alpha}+\dfrac{1}{\beta}=1.$ Nếu $\alpha$ là số hữu tỷ thì từ đẳng thức này ta có $\beta$ cũng là số hữu tỷ. Viết $\displaystyle \alpha=\dfrac{p}{q},\quad \beta=\dfrac{r}{s},$ với $p$ , $q$ , $r$ , và $s$ là các số nguyên dương. Ta thấy $S_{\alpha}\cap S_{\beta}\not=\emptyset$ , chẳng hạn $pr$ thuộc cả hai tập này, suy ra vô lý. Bởi vậy $\alpha$ là số vô tỷ, và $\beta$ cũng thế.

Bây giờ giả sử ngược lại, $\alpha$ và $\beta$ là các số vô tỷ và $\dfrac{1}{\alpha}+\dfrac{1}{\beta}=1.$ Ta thấy ngay $\alpha$ và $\beta$ lớn hơn $1$ , suy ra hai dãy Beatty của hai số này là các dãy tăng. Nếu $S_{\alpha}\cap S_{\beta}\not=\emptyset$ thì tồn tại các số nguyên dương $k,m$ và $n$ sao cho $k=[m\alpha]=[n\beta]$ . Suy ra

$\displaystyle k\leq m\alpha < k+1,\quad k\leq n\beta < k+1.$

Vì $\alpha$ và $\beta$ là các số vô tỷ nên

$\displaystyle k < m\alpha < k+1,\quad k < n\beta < k+1,$

suy ra

$\displaystyle \frac{k}{\alpha} < m < \frac{k+1}{\alpha},\quad \frac{k}{\beta} < n < \frac{k+1}{\beta},$

cộng theo vế ta có $k < m+n < k+1$ , vô lý. Như vậy $S_{\alpha}\cap S_{\beta}=\emptyset$ .

Nếu tồn tại số nguyên dương $l$ sao cho $l\not\in S_{\alpha}\cup S_{\beta}$ thì tồn tại các số nguyên không âm $p$ và $q$ sao cho

$\displaystyle [p\alpha] < l < [(p+1)\alpha], \quad [q\beta] < l < [(q+1)\beta].$

Vì $l$ là số nguyên nên từ các bất đẳng thức trên ta suy ra $p\alpha < l$ , đồng thời $[(p+1)\alpha] \geq l+1$ kéo theo $(p+1)\alpha \geq l+1$ . Lập luận tương tự cho $\beta$ , ta được

$\displaystyle p\alpha < l < l+1\leq (p+1)\alpha,\quad q\beta < l < l+1\leq (q+1)\beta.$

Vì $\alpha,\beta$ là các số vô tỷ nên

$\displaystyle p\alpha < l < l+1 < (p+1)\alpha,\quad q\beta < l < l+1 < (q+1)\beta.$

Chia các vế cho $\alpha,\beta$ và cộng lại ta có

$\displaystyle p+q < l < l+1 < p+q+2,$

điều này không thể xảy ra (do khoảng mở $(p+q, p+q+2)$ có độ dài bằng $2$ nên chỉ chứa đúng một số nguyên là $p+q+1$ ). $\blacksquare$

Min-Max Identities for the Least Common Multiple and Greatest Common Divisor

Bổ đề. Với mọi số nguyên dương $a_1, a_2, \dots, a_n$ , ta có các hệ thức

$\displaystyle [a_1, a_2, \dots, a_n] = \prod_{k=1}^n \left( \prod_{1 \le i_1 < i_2 < \dots < i_k \le n} (a_{i_1}, a_{i_2}, \dots, a_{i_k}) \right)^{(-1)^{k-1}}$

và

$\displaystyle (a_1, a_2, \dots, a_n) = \prod_{k=1}^n \left( \prod_{1 \le i_1 < i_2 < \dots < i_k \le n} [a_{i_1}, a_{i_2}, \dots, a_{i_k}] \right)^{(-1)^{k-1}}.$

Chứng minh. Gọi $\alpha_i = v_p(a_i) \ge 0$ là số mũ của $p$ trong phân tích tiêu chuẩn của $a_i$ (với $i = 1, 2, \dots, n$ ).

Ta đã biết rằng số mũ của $p$ trong bội chung nhỏ nhất $[a_{i_1}, \dots, a_{i_k}]$ là $\max(\alpha_{i_1}, \dots, \alpha_{i_k})$ , và số mũ của $p$ trong ước chung lớn nhất $(a_{i_1}, \dots, a_{i_k})$ là $\min(\alpha_{i_1}, \dots, \alpha_{i_k})$ .

Do đó, để chứng minh hai hệ thức đã cho, ta chỉ cần chứng minh hai đẳng thức về số mũ sau đây với mọi dãy số nguyên không âm $\alpha_1, \dots, \alpha_n$ :

$\displaystyle \max(\alpha_1, \dots, \alpha_n) = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \le i_1 < \dots < i_k \le n} \min(\alpha_{i_1}, \dots, \alpha_{i_k}) \qquad (1)$

và

$\displaystyle \min(\alpha_1, \dots, \alpha_n) = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \le i_1 < \dots < i_k \le n} \max(\alpha_{i_1}, \dots, \alpha_{i_k}). \qquad (2)$

Xét các tập hợp $A_i = \{1, 2, \dots, \alpha_i\}$ với mỗi $i = 1, \dots, n$ (nếu $\alpha_i = 0$ thì $A_i = \emptyset$ ). Số phần tử của tập hợp $A_i$ chính là $|A_i| = \alpha_i$ . Với mọi tập con các chỉ số $I = \{i_1, i_2, \dots, i_k\}$ , ta có

$\displaystyle \left| \bigcap_{j=1}^k A_{i_j} \right| = \min(\alpha_{i_1}, \dots, \alpha_{i_k})$

và

$\displaystyle \left| \bigcup_{j=1}^k A_{i_j} \right| = \max(\alpha_{i_1}, \dots, \alpha_{i_k}).$

Áp dụng Nguyên lý bù trừ cho số phần tử của tập hợp hợp, ta có

$\displaystyle \left| \bigcup_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \le i_1 < \dots < i_k \le n} \left| \bigcap_{j=1}^k A_{i_j} \right|.$

Thay các giá trị lực lượng tập hợp vào, ta lập tức thu được đẳng thức $(1)$ .

Tương tự, áp dụng Nguyên lý bù trừ dạng đối ngẫu cho số phần tử của tập hợp giao, ta có

$\displaystyle \left| \bigcap_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \le i_1 < \dots < i_k \le n} \left| \bigcup_{j=1}^k A_{i_j} \right|.$

Thay các giá trị tương ứng vào, ta nhận được đẳng thức $(2)$ .

Vì số mũ của mọi số nguyên tố $p$ ở cả hai vế của các hệ thức đều bằng nhau, các hệ thức về bội chung nhỏ nhất và ước chung lớn nhất ban đầu được chứng minh hoàn toàn. $\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.

Finite Unions of Proper Subspaces Over an Infinite Field

A vector space over an infinite field cannot be the union of finitely many proper subspaces.

Proof. Assume for the sake of contradiction that $V$ is a vector space over an infinite field $\mathbb{F}$ and $V = \bigcup_{i=1}^n W_i$ , where $n$ is the smallest positive integer satisfying this property and the $W_i$ are proper subspaces of $V$ .
Since $V$ cannot be a proper subspace of itself, $n$ must be greater than or equal to $2$ . Since $n$ is minimal, $W_n$ is not contained in the union of the remaining subspaces. Thus there exists a vector $u \in W_n$ such that $u \notin W_i$ for all $i < n$ . On the other hand, since $W_n$ is a proper subspace of $V$ , there exists a vector $v \notin W_n$ .
Consider the infinite set of vectors of the form $v + c u$ with $c \in \mathbb{F}$ . Since $V$ is the union of $n$ subspaces and the field $\mathbb{F}$ has infinitely many elements, by the pigeonhole principle there exists a subspace $W_k$ containing at least two distinct vectors from the considered set. Suppose $v + c_1 u \in W_k$ and $v + c_2 u \in W_k$ with $c_1, c_2 \in \mathbb{F}$ and $c_1 \neq c_2$ . Then the difference of these two vectors is $(c_1 - c_2) u \in W_k$ . Since $c_1 \neq c_2$ , the scalar $c_1 - c_2$ is non-zero, hence we have $u \in W_k$ . If $k = n$ , then from $v + c_1 u \in W_n$ and $u \in W_n$ we deduce that $v \in W_n$ , which contradicts the choice of $v$ . If $k < n$ , then $u \in W_k$ , which contradicts the choice of $u$ . All cases lead to a contradiction. Therefore, a vector space over an infinite field cannot be the union of finitely many proper subspaces. $\Box$

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$