International Mathematical Olympiad: Shortlisted Problems

Hình tạo bởi một đường gấp khúc đóng và không tự cắt được gọi là đa giác đơn. Một tam giác cơ bản là một tam giác trong mặt phẳng tọa độ có các đỉnh là các điểm nguyên đồng thời trên biên và phần trong của nó không còn điểm nguyên nào khác. Định lí Pick cho một cách đơn giản tính diện tích đa giác đơn có các đỉnh nguyên.

Trong chứng minh định lí Pick ta cần dùng công thức tích diện tích của tam giác trong mặt phẳng tọa độ.

Định lí 1. Trong mặt phẳng tọa độ $Oxy$ , cho tam giác $ABC.$ Khi đó diện tích của tam giác $ABC$ bằng $\displaystyle \frac{1}{2}\left|(x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A)\right|.$ Nói riêng, với mỗi hai điểm $M$ và $N$ ta có diện tích của tam giác $OMN$ bằng $\dfrac{1}{2}\mid x_My_N-y_Mx_N\mid.$

Định lí 2. Mọi tam giác cơ bản đều có diện tích bằng $\dfrac{1}{2}.$

Chứng minh. Giả sử $TAB$ là một tam giác cơ bản bất kỳ. Không mất tính tổng quát, xem $T$ trùng với gốc tọa độ $O.$ Ta cần chứng minh $\mid x_1y_2-x_2y_1\mid =1,$ với $(x_1;y_1)$ và $(x_2;y_2)$ lần lượt là tọa độ của $A$ và $B.$

Gọi $K$ là điểm sao cho $OAKB$ là hình bình hành. Giả sử $M$ là một điểm nguyên nằm trong hoặc trên biên hình bình hành sao cho $M$ khác các đỉnh. Khi đó $M$ thuộc tam giác $ABK$ và điểm $N$ đối xứng với $M$ qua tâm hình bình hành là điểm nguyên thuộc tam giác $OAB$ nhưng khác các đỉnh, không thể xảy ra điều này do $OAB$ là một tam giác cơ bản. Như vậy hình bình hành $OAKB$ không chứa điểm nguyên nào khác bốn đỉnh của nó.

Giả sử $P$ là một điểm nguyên bất kỳ. Vì $\overrightarrow{OA}$ và $\overrightarrow{OB}$ là hai vector không cùng phương nên tồn tại cặp số thực $(\alpha,\beta)$ để $\overrightarrow{OP}=\alpha \overrightarrow{OA}+\beta \overrightarrow{OB}.$ Gọi $P'$ là điểm xác định bởi $\overrightarrow{OP'}=\{\alpha\} \overrightarrow{OA}+\{\beta\} \overrightarrow{OB}.$ Vì $\{\alpha\}$ và $\{\beta\}$ thuộc $[0;1)$ nên $P'$ thuộc hình bình hành $OAKB$ , nhưng $P'$ lại là một điểm nguyên, suy ra $P'$ phải là một trong bốn đỉnh của hình bình hành. Dễ thấy $P'\equiv O$ và do đó $\alpha$ và $\beta$ là hai số nguyên.

Gọi $\overrightarrow{i}$ và $\overrightarrow{j}$ lần lượt là các vector đơn vị đặt trên $Ox$ và $Oy$ . Khi đó theo lập luận trên, tồn tại các cặp số nguyên $(u,v)$ và $(u',v')$ để $\overrightarrow{i}=u \overrightarrow{OA}+v \overrightarrow{OB}$ và $\overrightarrow{j}=u' \overrightarrow{OA}+v' \overrightarrow{OB}.$ Từ hai đẳng thức này ta có $\begin{cases} 1=ux_1+vx_2\\ 0=uy_1+vy_2\end{cases}$ và $\begin{cases}0=u'x_1+v'x_2\\ 1=u'y_1+v'y_2,\end{cases}$ suy ra $\displaystyle u=\frac{y_2}{D},v=-\frac{y_1}{D},u'=-\frac{x_2}{D}$ và $\displaystyle v'=\frac{x_1}{D},$ trong đó $D=x_1y_2-x_2y_1\not =0$ do $O,A$ và $B$ không thẳng hàng. Vì $u,$ $v,$ $u'$ và $v'$ là các số nguyên nên $x_1,x_2,y_1$ và $y_2$ đều là bội của $D$ , do đó $D^2\mid D$ và bởi thế, $D=\pm 1.$

Định lí Pick. Cho $P$ là một đa giác đơn có các đỉnh là các điểm nguyên, $I$ là số điểm nguyên nằm trong và $B$ là số điểm nguyên nằm trên biên của $P$ . Khi đó ta có đẳng thức $\displaystyle S_P=I+\frac{1}{2}B-1.$

Chứng minh. Chia $P$ thành $N$ tam giác cơ bản. Gọi $S$ là tổng các góc trong của tất cả các tam giác cơ bản đó. Ta sẽ tính $S$ theo hai cách. Vì số tam giác là $N$ nên $S=N\pi.$

Tổng tất cả các góc có đỉnh là một điểm nguyên nằm trong $P$ bằng $2\pi$ , tổng tất cả các góc có đỉnh là một điểm nguyên nằm trên biên của $P$ nhưng không phải đỉnh của $P$ bằng $\pi$ và tổng của tất cả các góc có đỉnh là đỉnh của $P$ bằng $(n-2)\pi$ , ở đây $n$ là số đỉnh của $P$ . Do đó $S=2\pi I+\pi B-2\pi$ , suy ra $N\pi=2\pi I+\pi B-2\pi\Rightarrow N=2I+B-2$ . Để ý thêm $S_P=\dfrac{1}{2}N$ , ta có điều phải chứng minh.

Divisibility theory in the integers

Trong bài này chúng tôi sẽ trình bày quan hệ chia hết trên tập các số nguyên. Bài viết là tài liệu tự học của các học sinh lớp 10 đang học tại T’s Lab, nhưng các bạn học sinh lớp 8 hoặc 9 xuất sắc có thể hiểu được toàn bài mà không gặp khó khăn nào. Nhiều chứng minh trong bài dùng tính chất sau của tập các số nguyên không âm.

Mỗi tập khác rỗng gồm các số nguyên không âm đều có phần tử nhỏ nhất.

Đầu tiên chúng ta đến với định lí nền tảng của toàn bài.

Định lí 1 (Thuật toán chia). Cho hai số nguyên $a$ và $b$ với $b>0.$ Khi đó tồn tại đúng một cặp số nguyên $(q,r)$ thỏa mãn

$a=q b+r$ và $0 \leq r<b$ . Hai số $q$ và $r$ lần lượt được gọi là thương và dư trong phép chia $a$ cho $b$ .

Chứng minh. Gọi $S$ là tập hợp tất cả các số nguyên không âm có dạng $a-xb$ , với một số nguyên $x$ . Ta thấy $S$ khác rỗng nên nó có phần tử nhỏ nhất, ký hiệu là $r$ . Từ định nghĩa của $S$ , ta có thể viết $r=a-q b,$ trong đó $q$ là một số nguyên. Nếu $r \geq b$ thì $a-(q+1)$ là một phần tử nhỏ hơn $r$ của $S$ , vô lý, do đó $r<b$ . Bây giờ giả sử $(q,r)$ và $(q^{\prime},r^{\prime})$ là hai cặp có tính chất nói đến trong định lí. Khi đó $a=q b+r=q^{\prime} b+r^{\prime}$ và $0 \leq r<b, 0 \leq r^{\prime}<b$ . Từ đây ta có $\left|r^{\prime}-r\right|=b\left|q-q^{\prime}\right|,$ để ý thêm $\left|r^{\prime}-r\right|<b$ , ta thu được $0 \leq\left|q-q^{\prime}\right|<1.$ Suy ra $q=q^{\prime}$ , và $r=r^{\prime}$ . $\Box$

Ví dụ 1. Từ định lí 1 ta thấy mọi số nguyên đều có thể viết được dưới dạng $2k$ hoặc $2k+1$ với một số nguyên $k.$ Tương tự, mọi số nguyên đều có thể viết được dưới dạng $3k$ , $3k+1$ , hoặc $3k+2$ với một số nguyên $k.$ $\Box$

Định nghĩa 1. Cho hai số nguyên $a$ và $b$ với $b$ khác $0$ . Khi đó $a$ được gọi là chia hết cho $b$ , ký hiệu $b \mid a$ , nếu tồn tại số nguyên $c$ sao cho $a=bc$ . Ta viết $b \nmid a$ khi $a$ không chia hết cho $b$ .

Khi $b \mid a$ , ta cũng nói $b$ là một ước của $a$ , hay $a$ là một bội của $b$ . Ta có ngay lập tức các tính chất sau, chứng minh của chúng là bài tập cho bạn đọc.

Định lí 2. Với các số nguyên $a$ , $b$ , và $c$ , ta có các tính chất sau:

(1) $a\mid 0,1\mid a, a \mid a$ .

(2) $a \mid 1$ khi và chỉ khi $a= \pm 1$ .

(3) Nếu $a \mid b$ và $c \mid d$ , thì $a c \mid b d$ .

(4) Nếu $a \mid b$ và $b \mid c$ , thì $a \mid c$ .

(5) $a \mid b$ và $b \mid a$ khi và chỉ khi $a= \pm b$ .

(6) Nếu $a \mid b$ và $b\neq 0$ , thì $\mid a\mid \leq \mid b\mid$ .

(7) Nếu $a \mid b$ và $a \mid c$ , thì $a \mid(b x+c y)$ với các số nguyên bất kỳ $x$ và $y$ .

Ta xét một số ví dụ có sử dụng các tính chất này.

Ví dụ 2. Cho $a$ , $b$ , $c$ , và $d$ là các số nguyên thỏa mãn $ad-bc>1$ . Chứng minh rằng ít nhất một bốn số đã cho không chia hết cho $ad-bc$ .

Lời giải. Giả sử ngược lại, khi đó cả bốn số $a$ , $b$ , $c$ , và $d$ đều chia hết cho $ad-bc$ . Suy ra $ad$ và $bc$ cùng chia hết cho $(ad-bc)^2$ , do đó $(ad-bc)^2\mid ad-bc,$ điều này không thể xảy ra vì $ad-bc>1$ . $\Box$

Ví dụ 3. Tìm tất cả bộ ba số nguyên $(a,b,c)$ sao cho $1<a<b<c$ và $(a-1)(b-1)(c-1)$ là một ước của $abc-1.$

Lời giải. Các bộ ba phải tìm là $(2,4,8)$ và $(3,5,15)$ . Giả sử $(a,b,c)$ là một bộ ba thỏa mãn các yêu cầu của đề bài. Khi đó ba số $a$ , $b$ và $c$ có cùng tính chẵn-lẻ, do đó $\displaystyle 2 < \frac{abc}{(a-1)(b-1)(c-1)}\leq \frac{a}{a-1} \cdot \frac{a+2}{a+1} \cdot \frac{a+4}{a+3},$ suy ra $a<4.$ Đến đây xét $a=2$ và $a=3$ ta có câu trả lời. $\Box$