Convex set

Trong bài này, $\mathbb{R}^1,$ $\mathbb{R}^2$ và $\mathbb{R}^3$ lần lượt là tập các điểm thuộc đường thẳng, mặt phẳng và không gian.

Cho số nguyên dương $d\leq 3.$ Một tập hợp $C\subset \mathbb{R}^d$ được gọi là tập hợp lồi nếu với mỗi hai điểm $A$ và $B$ thuộc $C,$ cả đoạn thẳng $AB$ cũng nằm trong $C.$

Dễ thấy giao của một họ bất kỳ các tập hợp lồi là một tập hợp lồi. Vì thế ta có thể định nghĩa bao lồi của một tập hợp $X\subset \mathbb{R}^d$ là giao của tất cả các tập hợp lồi trong $\mathbb{R}^d$ chứa $X.$ Như vậy bao lồi của một tập hợp là tập hợp lồi nhỏ nhất chứa nó.

Nếu $A$ và $B$ là hai điểm khác nhau thì bao lồi của tập hợp $\{A,B\}$ là đoạn thẳng $AB.$ Nếu $A,B$ và $C$ là ba điểm không thẳng hàng thì bao lồi của tập $\{A,B,C\}$ là tam giác $ABC$ (phần trong và biên).

Dùng tổ hợp lồi ta có một mô tả khác của bao lồi.

Định lí 1. Cho $X$ là một tập hợp con khác rỗng của $\mathbb{R}^2.$ Khi đó điểm $x$ thuộc bao lồi của $X$ khi và chỉ khi tồn tại các điểm $x_1,x_2,\ldots,x_n\in X$ và các số thực không âm $t_1,t_2,\ldots,t_n$ thỏa mãn $\sum t_i=1$ và $x=\sum t_ix_i.$

Biểu diễn $\sum t_ix_i$ như trong định lí trên được gọi là tổ hợp lồi của các điểm $x_1,$ $x_2,$ $\ldots,$ $x_n.$

Với tập hợp hữu hạn trong mặt phẳng ta có kết quả sau, kết quả này được dùng nhiều trong các bài toán thi chọn học sinh giỏi.

Định lí 2. Cho số nguyên $n>2$ và $n$ điểm $A_1,A_2,\ldots,A_n$ trong $\mathbb{R}^2.$ Khi đó bao lồi của tập $\{A_i\}$ là đa giác lồi có tập đỉnh là tập con của tập $\{A_i\}.$

Trong định lí trên một đoạn thẳng được xem là một đa giác lồi với hai đỉnh là các đầu mút.

Định lí Helly là một kết quả cơ bản trong hình học tổ hợp về giao của các tập hợp lồi. Nó được Eduard Helly phát hiện vào năm 1913, nhưng mãi đến năm 1923 ông mới công bố, lúc đó các chứng minh của Radon (1921) và Konig (1922) đã xuất hiện.

Định lí 3 (Helly). Cho số nguyên $n>3$ và $n$ tập hợp lồi $X_1,X_2,\ldots,X_n$ trong $\mathbb{R}^2.$ Khi đó nếu mỗi ba tập trong chúng có giao khác rỗng thì cả $n$ tập có giao khác rỗng.

Chứng minh. Ta chứng minh bằng quy nạp theo $n.$ Đầu tiên ta xét $n=4.$ Giả sử bốn tập hợp lồi $X_1,$ $X_2,$ $X_3$ và $X_4$ trong $\mathbb{R}^2$ có tính chất: mỗi ba tập trong chúng có giao khác rỗng. Lấy bốn điểm $A_1,$ $A_2,$ $A_3$ và $A_4$ sao cho $A_i$ thuộc $\displaystyle \bigcap_{j\not=i}A_j$ với mỗi $i.$

Nếu bốn điểm $A_1,$ $A_2,$ $A_3$ và $A_4$ thẳng hàng theo thứ tự đó thì $A_2$ thuộc cả bốn tập lồi. Nếu bao lồi của $\{A_i\}$ là một tam giác thì điểm còn lại không phải là đỉnh của bao lồi sẽ thuộc cả bốn tập lồi. Nếu bao lồi của $\{A_i\}$ là một tứ giác thì giao điểm của hai đường chéo tứ giác sẽ thuộc cả bốn tập lồi.

Vậy khẳng định đúng với $n=4.$ Bây giờ ta giả sử khẳng định đúng với $n\, (n\geq 4),$ và đi chứng minh nó đúng với $n+1.$ Xét $n+1$ tập hợp lồi $X_1,X_2,\ldots,X_{n+1}$ trong $\mathbb{R}^2$ có tính chất: mỗi ba tập trong chúng có giao khác rỗng. Dùng giả thiết quy nạp cho $n$ tập hợp lồi $X_1\cap X_{n+1},X_2\cap X_{n+1},\ldots,X_n\cap X_{n+1}$ ta có điều cần chứng minh. $\Box$

Một cách tổng quát ta có kết quả sau, chứng minh được thực hiện tương tự như trên.

Cho số nguyên $n>d+1$ và $n$ tập hợp lồi $X_1,X_2,\ldots,X_n$ trong $\mathbb{R}^d.$ Khi đó nếu mỗi $d+1$ tập trong chúng có giao khác rỗng thì cả $n$ tập có giao khác rỗng.

Polynomials in one variable: Basic definitions

Trong bài này $K$ là một trong các tập hợp $\mathbb{F}_p$ (tập các số nguyên modulo một số nguyên tố $p$ ), $\mathbb{Q}$ , $\mathbb{R},$ hoặc $\mathbb{C}$ .

Định nghĩa 1. Cho $n$ là một số tự nhiên và $a_0,a_1,...,a_n \in K$ . Mỗi tổng hình thức có dạng

$a_n x^n+a_{n-1} x^{n-1}+\ldots+a_1 x+a_0$

được gọi là một đa thức trên $K$ theo biến $x$ với hệ số $a_0,a_1,...,a_n$ . Nếu $k$ là chỉ số lớn nhất sao cho $a_k \neq 0$ , thì ta nói đa thức $f(x)=a_k x^k+\ldots+a_1x+a_0$ có bậc $k$ , viết $\text{deg}(f(x))=k$ , $a_k$ được gọi là hệ số đầu của đa thức $f(x)$ , và $a_0$ được gọi là hệ số tự do của $f(x)$ . Nếu $a_0$ là hệ số đầu của $f(x)$ , thì $f(x)$ được gọi là đa thức hằng.

Nếu hệ số đầu của $f(x)$ là $1$ , thì $f(x)$ được gọi là đa thức monic. Tập tất cả đa thức với hệ số trong $K$ được ký hiệu bởi $K[x]$ .

Theo định nghĩa này thì đa thức không, đa thức mà mọi hệ số là không, không có bậc. Để thuận tiện, ta qui ước nó là đa thức hằng và có bậc bằng $-\infty$ . Một đa thức hằng $f(x)=a_0$ có bậc $0$ nếu $a_0 \neq 0$ . Hai đa thức bằng nhau nếu chúng có cùng bậc và tất cả các hệ số tương ứng bằng nhau. Cần phân biệt giữa đa thức $f(x)$ và hàm đa thức tương ứng từ $K$ đến $K$ xác định bởi thay một phần tử của $K$ vào vị trí của $x$ . Nếu $f(x)=a_m x^m+\ldots+a_1x+a_0$ và $c \in K$ , thì $f(c)=a_m c^m+\ldots+a_1c+a_0$ được gọi là giá trị của $f(x)$ tại $c$ . Nếu $K$ là $\mathbb{F}_p$ thì có thể có hai đa thức khác nhau xác định cùng một hàm đa thức.

Ví dụ 1. Cho $K$ là $\mathbb{F}_3$ và xét các đa thức $x^3$ và $x$ . Với mỗi $c \in \mathbb{F}_3$ , ta có $c^3 \equiv c\pmod{3},$ do đó các hàm đa thức $f(x)=x^3$ và $g(x)=x$ là bằng nhau như các hàm từ $\mathbb{F}_3$ tới $\mathbb{F}_3$ .

Continue reading →

Siegel’s lemma

Trong bài này tôi sẽ giới thiệu một chứng minh của bổ đề Siegel, một bổ đề có nhiều áp dụng trong số học (xem trong [1], trang 316).

Bổ đề Siegel. Cho hai số nguyên dương $N>M$ và một bảng các số nguyên không đồng thời bằng không $(a_{i,j})$ có cỡ $M\times N$ . Khi đó hệ phương trình

$\displaystyle \sum_{j=1}^Na_{i,j}x_j=0,\quad i=1,2,\ldots,M$

có nghiệm nguyên $(y_1,y_2,\ldots,y_N)$ thỏa mãn $\max \mid y_i\mid \leq \left(N\max \mid a_{i,j}\mid \right)^{\frac{M}{N-M}}$ và các số $y_1,y_2,\ldots,y_N$ không đồng thời bằng không.

Hệ phương trình thuần nhất trên có số ẩn nhiều hơn số phương trình và có hệ số hữu tỷ nên nó có nghiệm hữu tỷ khác không, do đó nó có nghiệm nguyên khác không (xem trong [2], trang 49). Bổ đề nói rằng ta có thể tìm nghiệm nguyên không tầm thường đủ nhỏ của hệ.

Chứng minh. Đặt $a=\max \mid a_{i,j}\mid$ , $\displaystyle L_i(x_1,x_2,\ldots,x_N)=\sum_{j=1}^Na_{i,j}x_j,$
$\displaystyle a_i^{+}=\sum_{j=1}^N\max\{a_{i,j};0\},$ và $\displaystyle a_i^{-}=\sum_{j=1}^N\min \{a_{i,j};0\},$ với $i=1,2,\ldots,M$ .

Xét một số tự nhiên $b$ . Gọi $S$ là tập các bộ số tự nhiên $(x_1,x_2,\ldots,x_{N})$ thỏa mãn $x_i\leq b$ với mọi $i$ . Khi đó $\mid S\mid =(b+1)^N$ và với mỗi $(x_i)\in S$ , bộ

$(L_1(x_1,x_2,\ldots,x_N),L_2(x_1,x_2,\ldots,x_N),\ldots,L_M(x_1,x_2,\ldots,x_N))$

thuộc tập hợp tích $\displaystyle T=\prod_{i=1}^M\{a_i^{-}b,a_i^{-}b+1,\ldots,a_i^{+}b\}$ . Ta có

$\displaystyle \mid T\mid = \prod_{i=1}^M\mid \{a_i^{-}b,a_i^{-}b+1,\ldots,a_i^{+}b\}\mid = \prod_{i=1}^M(b(a_i^+-a_i^-)+1)\leq (bNa+1)^M.$

Giả sử chọn được $b$ thỏa mãn bất đẳng thức

$\displaystyle (bNa+1)^M<(b+1)^N.\quad (*)$

Khi đó tồn tại hai phần tử khác nhau $(x_i)$ và $(x_i^{\prime})$ của $S$ để hai phần tử tương ứng trong $T$ là một. Ta thấy $(y_i)$ , với $y_i=x_i-x_i^{\prime}$ , là một nghiệm nguyên khác không của hệ phương trình thỏa mãn $\mid y_i\mid\leq b$ với mọi $i$ . Bây giờ kiểm tra thấy khi $b= \left[\left(Na\right)^{\frac{M}{N-M}}\right]$ thì có $(*)$ , từ đó có nghiệm $(y_i)$ thỏa mãn bổ đề.

Tài liệu tham khảo

[1] Hindry, M., Silverman, J.H.: Diophantine Geometry. Springer, New York (2000)
[2] Jacobson, N.: Lectures in Abstract Algebra: II. Linear Algebra. Springer, New
York (1975)

ISL1988/4 và một số bài toán liên quan

Gần đây bài toán sau lại tìm đến tôi: Cho số nguyên $n$ lớn hơn $1$ và một bảng ô vuông cỡ $n \times n.$ Viết vào các ô vuông của bảng các số $1, 2, \ldots, n^2$ sao cho hai ô khác nhau được viết hai số khác nhau. Chứng minh rằng tồn tại hai ô vuông có chung cạnh mà hiệu hai số được viết trên đó không bé hơn $n.$

Đây là bài toán số $4$ trong cuốn IMO 1988 Shortlist, mà tôi ký hiệu là ISL1988/4. Để làm tài liệu tham khảo cho các bạn đồng nghiệp và học sinh, tôi giới thiệu nhiều lời giải của bài toán và một số bài toán liên quan. Không có kiến thức đặc biệt nào được sử dụng trong bài, các bạn học sinh lớp $8$ hay $9$ định hướng thi vào các lớp chuyên Toán có thể hiểu được tất cả các lời giải.