Category: Algebra

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

Bài đọc thêm

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

Làm thế nào để cải thiện trực giác Toán học?


Trực giác Toán học có thể được hiểu là khả năng nhận ra các mẫu hình, mối liên hệ, hoặc cách tiếp cận một bài toán mà không cần dựa hoàn toàn vào các bước suy luận logic chi tiết. Trực giác này giống như một “cảm giác” về Toán học, cho phép người học dự đoán, hình dung, và đưa ra giả thuyết một cách tự nhiên. Trực giác Toán học không phải là một “phép màu” hay sự đoán mò. Nó được xây dựng dựa trên kinh nghiệm, sự quen thuộc với các khái niệm Toán học, và khả năng liên kết các ý tưởng. Nhà Toán học nổi tiếng Henri Poincaré từng mô tả trực giác như một công cụ giúp ông khám phá các ý tưởng mới, nhưng chỉ khi kết hợp với tư duy logic thì trực giác mới trở thành nền tảng cho những khám phá lớn.

Để cải thiện trực giác Toán học, bạn cần rèn luyện khả năng nhận diện các cấu hình, hiểu sâu các khái niệm và áp dụng chúng một cách linh hoạt. Dưới đây là một số kinh nghiệm hữu ích:

1. Thay vì chỉ học thuộc khái niệm hay định lý, hãy tìm hiểu tại sao chúng hoạt động. Đọc các chứng minh khác nhau khi học định lý, cố gắng nắm rõ ý tưởng chứng minh. Ngoài ra, có thể tự hỏi: Khái niệm này đến từ đâu? Ý nghĩa của kết quả này là gì? Nếu thay đổi hay bỏ bớt điều kiện, kết quả sẽ ra sao? Nó còn đúng không? Việc tìm câu trả lời sẽ kích thích tư duy trực giác và khả năng liên kết.

2. Giải nhiều bài toán ở các mức độ khác nhau, kể cả các bài toán mở. Các bài toán hình học, đại số, hay tổ hợp thường giúp phát triển trực giác nhờ tính trực quan. Những bài toán mở khuyến khích bạn suy nghĩ sáng tạo và hình dung cách giải quyết vấn đề.

3. Vẽ hình, biểu đồ, hoặc sơ đồ để minh họa bài toán. Chúng giúp bạn “thấy” được các mối liên hệ. Sử dụng các công cụ như GeoGebra hoặc giấy và bút để thử nghiệm các ý tưởng.

4. Thử giải bài toán theo nhiều cách khác nhau. Ví dụ, một bài toán hình học có thể được giải bằng đại số, lượng giác, hoặc hình học thuần túy. Điều này giúp bạn phát triển sự linh hoạt và nhận ra các mẫu ẩn. Khi gặp bài toán khó, hãy cố gắng chia nhỏ hoặc giải các bài toán đơn giản hơn.

5. Khi giải sai hay không giải được một bài toán, hãy dừng lại và phân tích lý do. Hỏi bản thân: “Mình đã bỏ qua điều gì?” hoặc “Có tính chất nào mình chưa nhận ra không?” Đây là cơ hội để phát triển trực giác, vì chúng chỉ ra những điểm mù trong tư duy.

6. Đọc và học từ các nguồn chất lượng. Đọc sách, xem video bài giảng hoặc bài viết của các nhà Toán học nổi tiếng để hiểu cách họ tiếp cận vấn đề. Các cuốn sách như “How to Solve It” của George Polya hoặc “The Art and Craft of Problem Solving” của Paul Zeitz rất hữu ích.

7. Hãy học hỏi từ những người khác ngoài thầy trực tiếp dạy bạn. Tham gia các nhóm học Toán hoặc diễn đàn như Art of Problem Solving. Thảo luận với người khác giúp tiếp cận các cách suy nghĩ mới và củng cố trực giác của mình. Dạy lại khái niệm cho người khác. Khi bạn giải thích một ý tưởng Toán học, bạn buộc phải hiểu nó sâu hơn, từ đó cải thiện trực giác.

Trực giác Toán học cần phải được rèn luyện thường xuyên, bạn nên dành thời gian mỗi ngày để giải một bài toán nhỏ hoặc suy nghĩ về một khái niệm mới. Trực giác Toán học không phát triển ngay lập tức, nó đòi hỏi thời gian và sự kiên trì. Hãy coi mỗi bài toán là một cơ hội để học hỏi, ngay cả khi bạn chưa tìm ra lời giải.