IMO Shortlist 2024: Algebra

Trong bài này tôi sẽ giới thiệu các bài toán đại số trong cuốn IMO Shortlist 2024, các bài toán từ IMO SL năm trước các bạn có thể tìm ở https://nttuan.org/category/contests/imo-shortlist/ .

Phần hình học của bộ 2024 tôi đã đăng ở đây https://nttuan.org/2025/08/07/isl2024g/

A1. https://artofproblemsolving.com/community/c6h3358923p31205921

Tìm tất cả các số thực $\alpha$ sao cho với mỗi số nguyên dương $n$ , số

$[\alpha]+[2\alpha]+\cdots+[n\alpha]$

chia hết cho $n$ . (IMO2024/1)

A2. https://artofproblemsolving.com/community/c6h3610446p35340919

Cho $n$ là một số nguyên dương. Tìm giá trị nhỏ nhất có thể của

$S = 2^0 x_0^2 + 2^1 x_1^2 + \dots + 2^n x_n^2,$

trong đó $x_0, x_1, \dots, x_n$ là các số nguyên không âm sao cho $x_0 + x_1 + \dots + x_n = n$ .

A3. https://artofproblemsolving.com/community/c6h3610463p35340954

Hãy xác định xem với mọi dãy số thực dương $(a_n)$ ,

$\displaystyle\frac{3^{a_1}+3^{a_2}+\cdots+3^{a_n}}{(2^{a_1}+2^{a_2}+\cdots+2^{a_n})^2} < \frac{1}{2024}$

có đúng với ít nhất một số nguyên dương $n$ hay không.

A4. https://artofproblemsolving.com/community/c6h3610435p35340902

Tìm tất cả các tập con $\mathcal{S}$ của $\{2^{0},2^{1},2^{2},\ldots\}$ sao cho tồn tại một hàm $f\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ với

$\mathcal{S}=\{f(a+b)-f(a)-f(b)\mid a,b\in\mathbb{Z}_{>0}\}.$

A5. https://artofproblemsolving.com/community/c6h3610458p35340939

Tìm tất cả các dãy số tuần hoàn $a_1,a_2,\dots$ gồm các số thực sao cho với mỗi số nguyên dương $n$ ,

$a_{n+2}+a_{n}^2=a_n+a_{n+1}^2$

và $|a_{n+1}-a_n|\leqslant 1.$

A6. https://artofproblemsolving.com/community/c6h3610454p35340929

Cho $a_0, a_1, a_2, \ldots$ là một dãy tăng ngặt các số nguyên dương sao cho với mỗi $n \ge 1$ , ta có

$\displaystyle a_n \in \left\{ \frac{a_{n-1} + a_{n+1}}{2}, \sqrt{a_{n-1} \cdot a_{n+1}} \right\}.$

Cho $b_1, b_2, \ldots$ là một dãy vô hạn các chữ cái được xác định bởi

$b_n = A$ nếu $a_n = \frac{1}{2}(a_{n-1} + a_{n+1})$ , $=G$ trong trường hợp còn lại. Chứng minh rằng tồn tại các số nguyên dương $n_0$ và $d$ sao cho với mọi $n \ge n_0$ ta có $b_{n+d} = b_n$ .

A7. https://artofproblemsolving.com/community/c6h3359771p31218720

Một hàm số $f:\mathbb{Q}\to\mathbb{Q}$ được gọi là đẹp nếu với mỗi số hữu tỷ $x$ và $y$ , $f(x+f(y))=f(x)+y$ hoặc $f(f(x)+y)=x+f(y)$ . Chứng minh rằng tồn tại số nguyên $c$ sao cho với mọi hàm số đẹp $f$ , có không quá $c$ số hữu tỷ có dạng $f(r)+f(-r)$ , với số hữu tỷ $r$ nào đó. Tìm giá trị nhỏ nhất của các số $c$ có tính chất này. (IMO2024/6)

A8. https://artofproblemsolving.com/community/c6h3610460p35340944

Cho $p \ne q$ là các số nguyên dương nguyên tố cùng nhau. Xác định tất cả các dãy vô hạn $a_1$ , $a_2$ , $\dots$ các số nguyên dương sao cho với mỗi số nguyên dương $n$ ,

$\max(a_n, a_{n+1}, \dots, a_{n+p}) - \min(a_n, a_{n+1}, \dots, a_{n+p}) = p$

và $\max(a_n, a_{n+1}, \dots, a_{n+q}) - \min(a_n, a_{n+1}, \dots, a_{n+q}) = q$ .

IMO Shortlist 2024: Geometry

Trong bài này tôi sẽ giới thiệu các bài toán hình học trong cuốn IMO Shortlist 2024, các bài toán từ IMO SL năm trước các bạn có thể tìm ở https://nttuan.org/category/contests/imo-shortlist/

G1. https://artofproblemsolving.com/community/c6h3610481p35341119

Cho $ABCD$ là tứ giác nội tiếp sao cho $AC<BD<AD$ và $\angle DBA<90^\circ$ . Điểm $E$ nằm trên đường thẳng đi qua $D$ song song với $AB$ sao cho $E$ và $C$ nằm khác phía đối với $AD$ và $AC=DE$ . Điểm $F$ nằm trên đường thẳng đi qua $A$ song song với $CD$ sao cho $F$ và $C$ nằm khác phía đối với $AD$ và $BD=AF$ . Chứng minh rằng các đường trung trực của $BC$ và $EF$ cắt nhau trên đường tròn ngoại tiếp của $ABCD$ .

G2. https://artofproblemsolving.com/community/c6h3359767p31218657

Cho $ABC$ là một tam giác với $AB < AC < BC$ . Gọi tâm đường tròn nội tiếp và đường tròn nội tiếp của tam giác $ABC$ lần lượt là $I$ và $\omega$ . Gọi $X$ là điểm trên đường thẳng $BC$ , khác $C$ , sao cho đường thẳng qua $X$ song song với $AC$ tiếp xúc với $\omega$ . Tương tự, gọi $Y$ là điểm trên đường thẳng $BC$ , khác $B$ , sao cho đường thẳng qua $Y$ song song với $AB$ tiếp xúc với $\omega$ . Đường thẳng $AI$ cắt lại đường tròn ngoại tiếp tam giác $ABC$ tại $P$ . Gọi $K$ và $L$ lần lượt là trung điểm của $AC$ và $AB$ . Chứng minh rằng $\angle KIL + \angle YPX = 180^{\circ}$ . (IMO2024/4)

G3. https://artofproblemsolving.com/community/c6h3610478p35341061

Cho $ABCDE$ là một ngũ giác lồi và $M$ là trung điểm của $AB$ . Giả sử $AB$ tiếp tuyến với đường tròn ngoại tiếp tam giác $CME$ tại $M$ và $D$ nằm trên các đường tròn ngoại tiếp của $AME$ và $BMC$ . Các đường thẳng $AD$ và $ME$ cắt nhau tại $K$ , và các đường thẳng $BD$ và $MC$ cắt nhau tại $L$ . Các điểm $P$ và $Q$ nằm trên đường thẳng $EC$ sao cho $\angle PDC = \angle EDQ = \angle ADB$ . Chứng minh rằng các đường thẳng $KP, LQ,$ và $MD$ đồng quy.

G4. https://artofproblemsolving.com/community/c6h3610440p35340910

Cho $ABCD$ là tứ giác có $AB$ song song với $CD$ và $AB<CD$ . Hai đường thẳng $AD$ và $BC$ cắt nhau tại $P$ . Điểm $X$ khác $C$ nằm trên đường tròn ngoại tiếp tam giác $ABC$ sao cho $PC=PX$ . Điểm $Y$ khác $D$ nằm trên đường tròn ngoại tiếp tam giác $ABD$ sao cho $PD=PY$ . Hai đường thẳng $AX$ và $BY$ cắt nhau tại $Q$ . Chứng minh rằng $PQ$ song song với $AB$ .

G5. https://artofproblemsolving.com/community/c6h3610468p35340974

Cho tam giác $ABC$ có tâm nội tiếp $I$ , và $\Omega$ là đường tròn ngoại tiếp tam giác $BIC$ . Cho $K$ là một điểm nằm trong đoạn thẳng $BC$ sao cho $\angle BAK < \angle KAC$ . Đường phân giác của $\angle BKA$ cắt $\Omega$ tại các điểm $W$ và $X$ sao cho $A$ và $W$ nằm cùng một phía đối với $BC$ , và đường phân giác của $\angle CKA$ cắt $\Omega$ tại các điểm $Y$ và $Z$ sao cho $A$ và $Y$ nằm cùng một phía đối với $BC$ . Chứng minh rằng $\angle WAY = \angle ZAX$ .

G6. https://artofproblemsolving.com/community/c6h3610439p35340907

Cho $ABC$ là tam giác nhọn với $AB < AC$ , và $\Gamma$ là đường tròn ngoại tiếp $ABC$ . Các điểm $X$ và $Y$ nằm trên $\Gamma$ sao cho $XY$ và $BC$ cắt nhau trên đường phân giác ngoài của $\angle BAC$ . Giả sử các tiếp tuyến của $\Gamma$ tại $X$ và $Y$ cắt nhau tại điểm $T$ nằm cùng phía với $A$ đối với $BC$ , và $TX$ và $TY$ cắt $BC$ tại $U$ và $V$ , tương ứng. Gọi $J$ là tâm của đường tròn bàng tiếp đối diện đỉnh $T$ của tam giác $TUV$ . Chứng minh rằng $AJ$ là phân giác của $\angle BAC$ .

G7. https://artofproblemsolving.com/community/c6h3610452p35340925

Cho $ABC$ là tam giác có tâm nội tiếp $I$ sao cho $AB<AC<BC$ . Giao điểm thứ hai của $AI, BI$ , và $CI$ với đường tròn ngoại tiếp tam giác $ABC$ lần lượt là $M_{A}$ , $M_{B}$ , và $M_{C}$ . Các đường thẳng $AI$ và $BC$ cắt nhau tại $D$ và các đường thẳng $BM_{C}$ và $CM_{B}$ cắt nhau tại $X$ . Giả sử đường tròn ngoại tiếp tam giác $XM_{B}M_{C}$ và $XBC$ cắt nhau tại $S\neq X$ . Các đường thẳng $BX$ và $CX$ cắt lại đường tròn ngoại tiếp tam giác $SXM_{A}$ tại $P\neq X$ và $Q\neq X$ , tương ứng. Chứng minh rằng tâm đường tròn ngoại tiếp tam giác $SID$ nằm trên $PQ$ .

G8. https://artofproblemsolving.com/community/c6h3610449p35340922

Cho tam giác $ABC$ có $AB<AC<BC$ , và $D$ là một điểm nằm trong đoạn thẳng $BC$ . Cho $E$ là một điểm trên đường tròn ngoại tiếp tam giác $ABC$ sao cho $A$ và $E$ nằm khác phía đối với $BC$ và $\angle{BAD}=\angle{EAC}$ . Gọi $I,I_B,I_C,J_B$ và $J_C$ lần lượt là tâm nội tiếp của các tam giác $ABC,ABD,ADC,ABE$ và $AEC$ . Chứng minh rằng $I_B,I_C,J_B$ và $J_C$ đồng viên khi và chỉ khi $AI,I_BJ_C$ và $J_BI_C$ đồng quy.

China National Olympiad 2025

2025China Download

Discrete random variables

Ta thường không quan tâm đến thí nghiệm mà chỉ quan tâm đến một số hệ quả từ thí nghiệm đó. Chẳng hạn, những tay cờ bạc chỉ quan tâm đến số tiền họ được hay mất, không quan tâm mấy đến trò chơi. Nhiều hệ quả từ thí nghiệm có thể được biểu diễn bằng một hàm trên không gian mẫu của thí nghiệm.

Định nghĩa 1. Cho một không gian xác suất $(\Omega,\mathcal{F},\mathbb{P})$ . Một biến ngẫu nhiên là một hàm $X:\Omega\to\mathbb{R}$ sao cho với mỗi $x\in\mathbb{R}$ , $\{\omega\in\Omega\mid X(\omega)\leq x\}\in\mathcal{F}.$

Một biến ngẫu nhiên được gọi là rời rạc nếu nó chỉ nhận giá trị trong một tập hợp đếm được.

Không khó khăn lắm để thấy rằng nếu $X$ và $Y$ là các biến ngẫu nhiên (biến ngẫu nhiên rời rạc) thì $X+Y$ , $XY$ , và $\alpha X$ ( $\alpha\in\mathbb{R}$ ) cũng là các biến ngẫu nhiên (biến ngẫu nhiên rời rạc).

Định nghĩa 2. Cho một không gian xác suất $(\Omega,\mathcal{F},\mathbb{P})$ và một biến ngẫu nhiên $X:\Omega\to\mathbb{R}$ . Hàm phân bố của biến ngẫu nhiên $X$ là hàm $F_X:\mathbb{R}\to [0;1]$ xác định bởi

$F_X(x)=\mathbb{P}(\{\omega\in\Omega\mid X(\omega)\leq x\}),\quad\forall x\in\mathbb{R}.$

Để cho gọn, ta viết sự kiện $\{\omega\in\Omega\mid X(\omega)\leq x\}$ bởi $\{ X\leq x\}$ . Khi đó xác suất $\mathbb{P}(\{\omega\in\Omega\mid X(\omega)\leq x\})$ sẽ được viết là $\mathbb{P}( X\leq x)$ .

Ví dụ 1. Tung một đồng xu hai lần. Không gian mẫu của phép thử là $\Omega =\{NN,SS,SN,NS\}$ . Xét biến ngẫu nhiên $X$ , số mặt ngửa, xác định bởi

$X(NN)=2, X(SS)=0, X(SN)=1, X(NS)=1.$

Hàm phân bố của $F_X:\mathbb{R}\to [0;1]$ của $X$ xác định bởi

$F_X(x)=\begin{cases}0,\quad x<0\\ 1/4,\quad 0\leq x<1\\ 3/4,\quad 1\leq x<2\\ 1,\quad x\geq 2.\end{cases}$

Ví dụ 2. Xét không gian xác suất $(\Omega,\mathcal{F},\mathbb{P})$ và một biến cố $A$ . Hàm chỉ báo của $A$ là hàm $I_A: \Omega\to \mathbb{R}$ xác định bởi

$I_A(\omega)=\begin{cases}1,\quad \omega\in A\\ 0,\quad \omega\not\in A.\end{cases}$

Ta thấy $I_A$ là một biến ngẫu nhiên rời rạc với hàm phân bố $F:\mathbb{R}\to [0;1]$ xác định bởi

$F(x)=\begin{cases}0,\quad x<0\\ 1-\mathbb{P}(A),\quad 0\leq x<1\\ 1,\quad x\geq 1. \end{cases}$

Nếu $\{A_i\}_{i\in I}$ là một họ các biến cố đôi một rời nhau sao cho $\displaystyle A\subset \bigcup_{i\in I} A_i$ thì

$I_A(\omega)=\sum_{i\in I}I_{A\cap A_i}(\omega),\quad \forall \omega\in \Omega.$ $\Box$

Định lý 1. Hàm phân bố $F_X$ của biến ngẫu nhiên $X$ có các tính chất sau

(a) với mỗi số thực $x_1$ và $x_2$ , nếu $x_1<x_2$ thì $F_X(x_1)\leq F_X(x_2)$ .

(b) $\displaystyle \lim_{x\to -\infty}F_X(x)=0$ và $\displaystyle \lim_{x\to +\infty}F_X(x)=1$ .

(c) $F_X$ liên tục phải tại mọi điểm.

Chứng minh. Xét hai số thực $x_1$ và $x_2$ với $x_1<x_2$ . Biến cố $\{X\leq x_2\}$ là hợp của hai biến cố rời nhau $\{X\leq x_1\}$ và $\{x_1<X\leq x_2\}$ nên

$F_X(x_2)=\mathbb{P}(X\leq x_2)=\mathbb{P}(X\leq x_1)+\mathbb{P}(x_1<X\leq x_2)\geq \mathbb{P}(X\leq x_1)=F_X(x_1).$

Ta có $\{X\leq n\}_{n\geq 1}$ là một dãy tăng các sự kiện có hợp bằng $\Omega$ , theo định lý 1 trong [1], ta có

$1=\mathbb{P}(\Omega)=\mathbb{P}\left(\bigcup_{n=1}^{+\infty}\{X\leq n\}\right)=\lim_{n\to +\infty}\mathbb{P}(X\leq n),$

kết hợp với tính đơn điệu của $F_X$ ta được $\displaystyle \lim_{x\to +\infty}F_X(x)=1$ . Tính chất $\displaystyle \lim_{x\to -\infty}F_X(x)=0$ được chứng minh theo cách tương tự.

Bây giờ xét một số thực $x_0$ . Ta thấy $\{x_0<X\leq x_0+\frac{1}{n}\}_{n\geq 1}$ là một dãy giảm các sự kiện có giao bằng rỗng, theo định lý 2 trong [1], ta có

$0=\mathbb{P}\left(\bigcap_{n=1}^{+\infty}\left\{x_0<X\leq x_0+\frac{1}{n}\right\}\right)=\lim_{n\to +\infty}\left(F_X\left(x_0+\frac{1}{n}\right)-F_X(x_0)\right),$

kết hợp với tính đơn điệu của $F_X$ ta có $F_X$ liên tục phải tại $x_0$ . $\Box$

Continue reading →

Tree

Một đồ thị không chứa chu trình được gọi là một rừng. Một rừng liên thông được gọi là một cây.

Ví dụ 1. Cho $G$ là một cây trên $n>1$ đỉnh. Chứng minh rằng $G$ có ít nhất hai lá, và nếu $v$ là một lá thì $G\setminus\{v\}$ là một cây.

Hướng dẫn. Trong các đường đi của $G$ , quan tâm đến một đường đi dài nhất. Chứng minh hai đầu của nó là lá. Chỉ ra $G\setminus\{v\}$ là một rừng liên thông. $\Box$

Định lý 1. Với một đồ thị $G$ , các khẳng định sau là tương đương:

(1) $G$ là một cây;

(2) Mỗi hai đỉnh của $G$ được nối với nhau bởi một đường đi duy nhất trong $G$ ;

(3) $G$ là đồ thị liên thông và với mỗi cạnh $e$ , đồ thị có được từ $G$ bằng cách bỏ đi cạnh $e$ không phải là đồ thị liên thông;

(4) $G$ không chứa chu trình và với mỗi hai đỉnh không kề nhau $x$ và $y$ , đồ thị có được từ $G$ bằng cách thêm vào cạnh $xy$ chứa một chu trình.

Chứng minh. Giả sử $G$ là một cây và $x$ , $y$ là hai đỉnh của $G$ . Vì $G$ là đồ thị liên thông nên có một đường đi nối $x$ và $y$ , ký hiệu là $\alpha$ . Nếu có một đường đi khác đường đi này nối $x$ và $y$ , ký hiệu là $\beta$ , gọi $z$ là đỉnh chung gần $x$ nhất của hai đường đi. Đường đi từ $x$ đến $z$ dọc theo $\alpha$ hợp với đường đi từ $z$ đến $x$ dọc theo $\beta$ tạo thành một chu trình, vô lý. Vậy ta đã chứng minh $(1)\Rightarrow (2)$ .

Xét một cạnh $e=xy$ của $G$ . Nếu đồ thị có được từ $G$ bằng cách bỏ đi cạnh $e$ là đồ thị liên thông, thì trong $G$ có một đường đi nối $x$ và $y$ mà không chứa $e$ . Đường đi này cùng với $e$ là hai đường đi nối $x$ và $y$ . Vậy ta đã chứng minh $(2)\Rightarrow (3)$ , vì nếu có $(2)$ thì đồ thị phải là đồ thị liên thông.

Bây giờ giả sử có $(3)$ . Trước tiên ta thấy $G$ không chứa chu trình, vì nếu không ta bỏ đi một cạnh của chu trình thì đồ thị mới vẫn liên thông, vô lý. Xét hai đỉnh không kề nhau $x$ và $y$ . Vì $G$ là đồ thị liên thông nên có đường đi nối $x$ và $y$ . Thêm cạnh $xy$ vào đường đi này ta có một chu trình trong đồ thị có được từ $G$ bằng cách thêm vào cạnh $xy$ . Vậy ta có $(4)$ .

Cuối cùng, ta giả sử có $(4)$ . Xét hai đỉnh phân biệt $x$ và $y$ . Nếu $x$ và $y$ kề nhau thì có đường đi nối $x$ và $y$ , là $xy$ chẳng hạn. Nếu $x$ và $y$ không kề nhau thì đồ thị có được từ $G$ bằng cách thêm vào cạnh $xy$ chứa một chu trình. Vì $G$ không chứa chu trình nên chu trình này chứa $xy$ , bỏ $xy$ ra khỏi nó ta có đường đi trong $G$ nối $x$ và $y$ . Vậy ta có $(1)$ . $\Box$

Hệ quả. Một đồ thị liên thông trên $n$ đỉnh là một cây khi và chỉ khi nó có $n-1$ cạnh.

Chứng minh. Giả sử $G$ là một cây trên $n$ đỉnh. Vì $G$ là đồ thị liên thông nên theo định lý 1 trong [4], ta có thể đánh số các đỉnh của $G$ là $v_1$ , $v_2$ , $\ldots$ , $v_n$ sao cho $G_i:=G[v_1,v_2,\ldots,v_i]$ là đồ thị liên thông với mọi $i$ . Do $G$ là một cây nên mỗi $G_i$ là một cây. Giả sử $G_i$ có $i-1$ cạnh với mọi chỉ số $i<k$ ( $k$ là một số nguyên dương sao cho $k\leq n$ ). Vì $G_k$ là liên thông nên với mỗi $i<k$ , có đường đi trong $G_k$ nối $v_i$ và $v_k$ . Trong tất cả các đường đi như thế, xét đường đi ngắn nhất và giả sử nó nối $v_1$ và $v_k$ . Đường đi này phải có độ dài bằng $1$ , hay $v_k$ và $v_1$ kề nhau trong $G$ . Vì $G$ không có chu trình nên trong $G_{k-1}$ , chỉ có đúng một đỉnh kề với $v_k$ , suy ra $G_k$ có $k-2+1=k-1$ cạnh. Theo nguyên lý quy nạp toán học, $G=G_n$ có $n-1$ cạnh.

Ngược lại, giả sử $G$ là một đồ thị liên thông trên $n$ đỉnh và có $n-1$ cạnh. Gọi $T$ là một đồ thị con bao trùm liên thông cực tiểu của $G$ . Do tính cực tiểu, khi bỏ mỗi cạnh ra khỏi $T$ thì đồ thị thu được không liên thông, suy ra theo định lý 1 thì $T$ là một cây. Cây này có số cạnh bằng $n-1$ theo phần đầu của chứng minh, do đó $T=G$ . $\Box$

Trong một số vấn đề, việc xét một cây với gốc sẽ rất thuận tiện. Giả sử có một cây $T$ và một đỉnh cố định $r$ , gọi là gốc của cây. Với hai đỉnh $x$ và $y$ của $T$ , có đúng một đường đi nối $x$ và $y$ , ta ký hiệu nó là $xTy$ . Với $a,b\in T$ , ta viết $a\leq_T b$ (hoặc $a\leq b$ khi không sợ nhầm lẫn) nếu $a\in rTb$ . Ta thấy $\leq_T$ là một quan hệ thứ tự bộ phận trên $T$ , gọi là thứ tự cây. Khi $a<b$ ta nói $b$ nằm trên $a$ , hay $a$ nằm dưới $b$ . Theo quan hệ thứ tự này thì $r$ là phần tử nhỏ nhất của $T$ , mỗi lá là phần tử cực đại. Hai đầu mút của mỗi cạnh của $T$ là so sánh được.

Ví dụ 2. Cho số nguyên $n$ lớn hơn $1$ và một cây trên $n$ đỉnh. Các đỉnh của cây được viết các số thực $x_1$ , $x_2$ , $\ldots$ , $x_n$ . Mỗi cạnh của cây được viết tích của hai số được viết trên các đầu mút của cạnh, gọi $S$ là tổng tất cả các số này. Chứng minh rằng

$\displaystyle\sqrt{n-1}\left(x_1^2+x_2^2+\dots+x_n^2\right)\geq 2S.$

Lời giải. Giả sử tập các đỉnh của cây là $V=\{v_1, v_2, \ldots, v_n\}$ sao cho với mỗi $i$ , số được viết trên $v_i$ là $x_i$ . Với hai đỉnh kề nhau $v_i$ và $v_j$ , gọi $P(i,j)$ là tập các đỉnh của cây không nối được đến $v_i$ bởi một đường đi sau khi xóa khỏi cây cạnh $v_iv_j$ . Ta có ngay $1\leq \mid P(i,j)\mid \leq n-1$ mỗi khi $v_i$ và $v_j$ kề nhau.

Nhận xét 1. Nếu $v_i$ và $v_j$ kề nhau thì $\mid P(i,j)\mid +\mid P(j,i)\mid=n$ .

Chứng minh. Gọi $v$ là một đỉnh của cây, và xem nó là gốc. Ta có $v_i$ và $v_j$ là so sánh được theo thứ tự cây. Nếu $v_i<v_j$ thì $v\in P(j,i)$ , nếu $v_j<v_i$ thì $v\in P(i,j)$ , nhưng không thể có cả hai. Như vậy $V$ được phân hoạch thành $P(i,j)$ và $P(j,i)$ , từ đây ta có điều cần chứng minh. $\Box$

Nhận xét 2. Với mỗi $i$ ,

$\displaystyle \sum_{v_j\in N(v_i)}\mid P(i,j)\mid =n-1$ .

Chứng minh. Cố định một chỉ số $i$ . Do mỗi đỉnh đều nối đến $v_i$ bởi một đường đi duy nhất và cây không có chu trình nên các $P(i,j)$ với $v_j\in N(v_i)$ làm thành một phân hoạch của $V\setminus\{v_i\}$ , từ đây ta có điều cần chứng minh. $\Box$

Bây giờ với mỗi cạnh $v_iv_j$ , theo nhận xét 1 ta có

$\displaystyle \mid P(i,j)\mid .\mid P(j,i)\mid=\frac{n^2-(\mid P(i,j)\mid -\mid P(j,i)\mid)^2}{4}\geq n-1,$

suy ra

$\displaystyle\frac{\mid P(i,j)\mid}{\sqrt{n-1}}x_i^2+\frac{\mid P(j,i)\mid}{\sqrt{n-1}}x_j^2\geq 2\sqrt{\frac{\mid P(i,j)\mid .\mid P(j,i)\mid}{n-1}}|x_ix_j|\geq 2x_ix_j.$