The Motzkin-Straus Theorem

To fully comprehend this topic, a basic understanding of multivariable calculus is required. A highly recommended reference is [1], specifically Theorem 2.4.15.

Let $\displaystyle G$ be a simple, undirected graph with vertices labeled as $\displaystyle 1, 2, \dots, n$ . Let $\displaystyle S$ be the set of all non-negative real vectors whose components sum to $\displaystyle 1$ :

$\displaystyle S = \left\{ x = (x_1, x_2, \dots, x_n) \in \mathbb{R}^n \;\middle|\; x_i \ge 0 \text{ for all } i=1,\dots,n, \text{ and } \sum_{i=1}^{n} x_i = 1 \right\}.$

For any vector $\displaystyle x \in S$ , we define the objective function $\displaystyle f(x)$ as the sum of the products of the weights associated with adjacent vertices in $\displaystyle G$ :

$\displaystyle f(x) = \sum_{(i,j) \in E} x_i x_j. \qquad (1)$

Here, each edge $\displaystyle (i,j) = (j,i) \in E$ is counted exactly once. The Motzkin-Straus theorem investigates the maximum value of this function over the set $\displaystyle S$ , denoted as:

$\displaystyle f(G) = \max_{x \in S} f(x) = \max_{x \in S} \sum_{(i,j) \in E} x_i x_j.$

Remark on Existence: The function $\displaystyle f(x)$ defined in (1) is a polynomial, which implies it is continuous everywhere on $\displaystyle \mathbb{R}^n$ . Furthermore, the domain $\displaystyle S$ is a closed and bounded set (a compact set) in $\displaystyle \mathbb{R}^n$ . According to the Extreme Value Theorem, any continuous real-valued function attains both a global maximum and a global minimum on a closed and bounded domain. Therefore, the maximum value $\displaystyle f(G)$ is strictly guaranteed to exist.

Theorem (Motzkin-Straus, 1965). Let $\displaystyle k$ be the clique number (the order of the largest complete subgraph) of $\displaystyle G$ . Then

$\displaystyle f(G)=\frac{1}{2}\left(1-\frac{1}{k}\right). \qquad (2)$

Proof. Suppose $\displaystyle x = (x_1, x_2, \dots, x_n)$ is a point in $\displaystyle S$ that maximizes the function

$\displaystyle f(x) = \sum_{(i,j)\in G} x_i x_j.$

Let $\displaystyle V_x = \{i \mid x_i > 0\}$ be the set of vertices with positive weights. Suppose $\displaystyle V_x$ does not induce a complete subgraph (clique). Then, there exist at least two vertices $\displaystyle u, v \in V_x$ that are not adjacent in $\displaystyle G$ .

Let $\displaystyle S_u = \sum_{j \in N(u)} x_j$ and $\displaystyle S_v = \sum_{j \in N(v)} x_j$ be the sum of the weights of the neighbors of $\displaystyle u$ and $\displaystyle v$ in $\displaystyle G$ , respectively. Without loss of generality, assume that $\displaystyle S_u \le S_v$ .

We construct a new weight distribution $\displaystyle x'$ by shifting the entire weight of $\displaystyle u$ to $\displaystyle v$ :

$\displaystyle x'_u = 0$
$\displaystyle x'_v = x_u + x_v$
$\displaystyle x'_i = x_i$ for all $\displaystyle i \neq u, v$ .

It is clear that $\displaystyle x' \in S$ because the total weight remains $\displaystyle 1$ and all weights remain non-negative. The change in the objective function is given by

$\displaystyle f(x') - f(x) = x_u (S_v - S_u).$

Since $\displaystyle x_u > 0$ and $\displaystyle S_v \ge S_u$ , we have $\displaystyle f(x') \ge f(x)$ . However, because $\displaystyle x$ is already a global maximizer, it must hold that $\displaystyle f(x') = f(x)$ .

The new point $\displaystyle x'$ still achieves the maximum value, but the number of vertices with positive weights has decreased by 1 (since $\displaystyle x'_u = 0$ ). We repeat this weight-shifting process for any remaining pair of non-adjacent vertices with positive weights. This process must terminate after a finite number of steps. Upon termination, all vertices with positive weights must be mutually adjacent, meaning they form a complete subgraph $\displaystyle C$ .

Let $\displaystyle m$ be the number of vertices in $\displaystyle C$ . Since $\displaystyle k$ is the clique number of $\displaystyle G$ , we must have $\displaystyle m \le k$ . On the complete subgraph $\displaystyle C$ , all vertices are pairwise adjacent, so

$\displaystyle f(x) = \sum_{(i,j) \in C} x_i x_j = \frac{1}{2} \left( \left( \sum_{i \in C} x_i \right)^2 - \sum_{i \in C} x_i^2 \right).$

Since the sum of the weights on $\displaystyle C$ is $\displaystyle \sum_{i \in C} x_i = 1$ , we obtain

$\displaystyle f(x) = \frac{1}{2} \left( 1 - \sum_{i \in C} x_i^2 \right).$

By the Cauchy-Schwarz inequality, we have

$\displaystyle \sum_{i \in C} x_i^2 \ge \frac{1}{m} \left( \sum_{i \in C} x_i \right)^2 = \frac{1}{m}.$

This implies $\displaystyle f(x) \le \frac{1}{2} \left( 1 - \frac{1}{m} \right).$

Since the function $\displaystyle g(m) = \frac{1}{2}\left(1 - \frac{1}{m}\right)$ is strictly increasing with respect to $\displaystyle m$ and $\displaystyle m \le k$ , we get:

$\displaystyle f(x) \le \frac{1}{2} \left( 1 - \frac{1}{k} \right). \qquad (3)$

Now, choose a maximum complete subgraph of $\displaystyle G$ with order $\displaystyle k$ . Assume the vertices of this subgraph are $\displaystyle 1, 2, \dots, k$ . By distributing the total weight equally among these $\displaystyle k$ vertices and setting the weights of all other vertices to $\displaystyle 0$ , i.e.,

$\displaystyle x_1 = x_2 = \dots = x_k = \frac{1}{k} \quad \text{and} \quad x_{k+1} = \dots = x_{n} = 0,$

we can compute the value of the objective function at this specific point as:

$\displaystyle f(x) = \binom{k}{2} \cdot \frac{1}{k^2} = \frac{k(k-1)}{2} \cdot \frac{1}{k^2} = \frac{1}{2} \left( 1 - \frac{1}{k} \right). \qquad (4)$

Combining (3) and (4), we conclude that the maximum value of the objective function on the set $\displaystyle S$ is precisely $\displaystyle f(G) = \frac{1}{2}\left(1 - \frac{1}{k}\right).$

This completes the proof. ∎

Corollary (Turán’s Theorem). Let $\displaystyle G$ be a graph with $\displaystyle n$ vertices and edge set $\displaystyle E$ . If $\displaystyle G$ contains no complete subgraph of order $\displaystyle k+1$ (meaning the clique number of $\displaystyle G$ does not exceed $\displaystyle k$ ), then the number of edges in $\displaystyle G$ satisfies

$\displaystyle |E| \le \frac{n^2}{2} \left( 1 - \frac{1}{k} \right).$

Proof. Consider the uniform weight distribution $\displaystyle x = \left(\frac{1}{n}, \frac{1}{n}, \dots, \frac{1}{n}\right)$ . Clearly, $\displaystyle x \in S$ since all coordinates are non-negative and their sum equals 1.

Evaluating the objective function $\displaystyle f(x)$ at this point, each edge $\displaystyle (i,j) \in G$ contributes exactly $\displaystyle \frac{1}{n} \cdot \frac{1}{n} = \frac{1}{n^2}$ . Since the graph $\displaystyle G$ has $\displaystyle |E|$ edges, we have:

$\displaystyle f(x) = \sum_{(i,j) \in G} x_i x_j = \sum_{(i,j) \in G} \frac{1}{n^2} = \frac{|E|}{n^2}.$

On the other hand, by the Motzkin-Straus Theorem, the value of $\displaystyle f(x)$ at any point in $\displaystyle S$ cannot exceed the global maximum $\displaystyle f(G)$ . Let $\displaystyle m$ be the clique number of $\displaystyle G$ . By hypothesis, $\displaystyle m \le k$ . Therefore:

$\displaystyle f(x) \le f(G) = \frac{1}{2} \left( 1 - \frac{1}{m} \right) \le \frac{1}{2} \left( 1 - \frac{1}{k} \right).$

Combining these two results, we obtain $\displaystyle |E| \le \frac{n^2}{2} \left( 1 - \frac{1}{k} \right).$

The inequality is thus proven. ∎

References
[1] Jerry Shurman, Calculus and Analysis in Euclidean Space (pages 23-56).

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 2022: Number theory

N1. Một số nguyên dương được gọi là số Na Uy nếu nó có ba ước dương phân biệt có tổng bằng $2022$ . Xác định số Na Uy nhỏ nhất.

N2. Tìm tất cả các số nguyên dương $n>2$ sao cho

$\displaystyle n! \mid \prod_{ p<q\le n,\quad p,q\in\mathbb{P}} (p+q).$

N3. Cho $a > 1$ là một số nguyên dương và $d > 1$ là một số nguyên dương nguyên tố cùng nhau với $a$ . Đặt $x_1=1$ và với $k\geq 1$ , $x_{k+1} = x_k + d$ nếu không chia hết $x_k$ , $=x_k/a$ nếu $a$ chia hết $x_k$ . Tìm, theo $a$ và $d$ , số nguyên dương $n$ lớn nhất mà tồn tại chỉ số $k$ sao cho $x_k$ chia hết cho $a^n$ .

N4. Tìm tất cả các bộ ba số nguyên dương $(a,b,p)$ sao cho $p$ là số nguyên tố và $a^p=b!+p.$

(IMO2022/5)

N5. Đối với mỗi $i\in [9]$ và $T\in\mathbb{N}^*$ , ký hiệu $d_i(T)$ là số lần chữ số $i$ xuất hiện khi tất cả các bội của $1829$ trong $[T]$ được viết ra theo cơ số $10$ . Chứng minh rằng có vô số $T\in\mathbb{N}^*$ sao cho có đúng hai giá trị phân biệt trong các số $d_1(T)$ , $d_2(T)$ , $\dots$ , $d_9(T)$ .

N6. Cho $Q$ là một tập hợp không nhất thiết hữu hạn các số nguyên tố. Đối với một số nguyên dương $n$ , xét phân tích ra thừa số nguyên tố của nó: gọi $p(n)$ là tổng của tất cả các số mũ và $q(n)$ là tổng của các số mũ tương ứng với các số nguyên tố trong $Q$ . Số nguyên dương $n$ được gọi là đặc biệt nếu $p(n)+p(n+1)$ và $q(n)+q(n+1)$ đều là số nguyên chẵn. Chứng minh rằng tồn tại một hằng số $c>0$ không phụ thuộc $Q$ sao cho với mọi số nguyên dương $N>100$ , số các số nguyên đặc biệt trong $[N]$ ít nhất là $cN$ .

N7. Gọi $k$ là một số nguyên dương và $S$ là một tập hữu hạn các số nguyên tố lẻ. Chứng minh rằng có nhiều nhất một cách (sai khác phép quay và đối xứng) để đặt các phần tử của $S$ xung quanh một đường tròn sao cho tích của hai số cạnh nhau bất kỳ có dạng $x^2+x+k$ với một số nguyên dương $x$ .

(IMO2022/3)

N8. Chứng minh rằng với mỗi số nguyên dương $n$ , số $5^n-3^n$ không chia hết cho số $2^n+65$ .

—

Các phần khác đã được đăng ở

Đại số: https://nttuan.org/2024/05/06/isl2022-algebra/

Hình học: https://nttuan.org/2023/09/08/isl2022-geometry/

Tổ hợp: https://nttuan.org/2023/09/29/isl2022-combinatorics/

Bản pdf của IMO SL từ 2014 đến 2021: https://nttuan.org/2023/07/02/isl/

Sau khi sửa một vài chỗ, bản pdf của IMO SL 2022 sẽ được đăng trong link trên.

IMO Shortlist 2022: Algebra

Trong bài này tôi sẽ dịch phần Đại số trong cuốn IMO Shortlist 2022. Các năm trước bạn có thể tìm ở đường dẫn https://nttuan.org/2023/07/02/isl/.

Các phần khác trong cuốn IMO Shortlist 2022 tôi đã để ở các bài dưới đây:

Hình học https://nttuan.org/2023/09/08/isl2022-geometry/

Tổ hợp https://nttuan.org/2023/09/29/isl2022-combinatorics/

A1. Cho $(a_n)_{n\geq 1}$ là một dãy số thực dương có tính chất $(a_{n+1})^2 + a_na_{n+2} \leq a_n + a_{n+2}$ với mọi số nguyên dương $n$ . Chứng minh rằng $a_{2022}\leq 1.$

A2. Cho một số nguyên $k\ge2$ . Tìm số nguyên $n \ge k+1$ nhỏ nhất sao cho tồn tại một tập $n$ số thực có tính chất: mỗi phần tử của nó có thể viết được dưới dạng tổng của $k$ phần tử phân biệt khác của tập hợp.

A3. Gọi $\mathbb{R}^+$ là tập hợp các số thực dương. Tìm tất cả các hàm $f: \mathbb{R}^+ \to \mathbb{R}^+$ sao cho với mỗi $x \in \mathbb{R}^+$ , có đúng một $y \in \mathbb {R}^+$ thỏa mãn $xf(y)+yf(x) \leq 2$ . (IMO2022/2)

A4. Gọi $n \geqslant 3$ là một số nguyên và $x_1,x_2,\ldots,x_n$ là các số thực trong đoạn $[0,1]$ . Đặt $s=x_1+x_2+\ldots+x_n$ và giả sử rằng $s \geqslant 3$ . Chứng minh rằng tồn tại các số nguyên $i$ và $j$ với $1 \leqslant i<j \leqslant n$ sao cho $2^{j-i}x_ix_j>2^{s-3}.$

A5. Tìm tất cả các số nguyên dương $n \geqslant 2$ sao cho tồn tại $n$ số thực $a_1<\cdots<a_n$ và số thực $r>0$ để $\frac{1}{2}n( n-1)$ hiệu $a_j-a_i$ với $1 \leqslant i<j \leqslant n$ bằng, theo một thứ tự nào đấy, các số $r^1,r^2,\ldots,r^{\frac{ 1}{2}n(n-1)}$ .

A6. Chúng ta nói rằng một hàm $f\colon\mathbb R\to\mathbb R$ là tốt nếu $f(x + f(y)) = f(x) + f(y)$ với mọi $x,y\in\mathbb R$ . Tìm tất cả các số hữu tỉ $q$ sao cho với mọi hàm tốt $f$ , tồn tại một số thực $z$ sao cho $f(z) = qz$ .

A7. Với số nguyên dương $m$ , ký hiệu $s(m)$ là tổng các chữ số của $m$ trong hệ thập phân. Gọi $P(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$ là một đa thức, trong đó $n \geqslant 2$ và $a_i$ là một số nguyên dương với mọi $0 \leqslant i \leqslant n-1$ . Có thể xảy ra với mỗi số nguyên dương $k$ , $s(k)$ và $s(P(k))$ có cùng tính chẵn – lẻ?

A8. Với số nguyên dương $n$ , một $n$ -dãy là một dãy $(a_0,\ldots,a_n)$ gồm các số nguyên không âm có tính chất: nếu $i$ và $j$ là các số nguyên không âm với $i+j \leqslant n$ , thì $a_i+a_j \leqslant n$ và $a_{a_i+a_j}=a_{i+j}$ . Gọi $f(n)$ là số $n$ -dãy. Chứng minh rằng tồn tại các số thực dương $c_1$ , $c_2$ và $\lambda$ sao cho $c_1\lambda^n<f(n)<c_2\lambda^n$ với mọi số nguyên dương $n$ .

Subconvex sequences

Trong bài này tôi sẽ giới thiệu một lớp dãy hay gặp trong các đề thi chọn học sinh giỏi các cấp. Chứng minh định lí chính trong bài là của Adrian Sandovichi. Để theo dõi cho dễ, các em học sinh nên đọc lại bài sau:

https://nttuan.org/2023/09/15/limit-of-a-sequence/

Định nghĩa. Cho dãy số thực không âm $(x_n)_{n\geq 1}$ và số nguyên $k>0$ . Dãy số $(x_n)_{n\geq 1}$ được gọi là một dãy lồi dưới cấp $k$ nếu có các số thực $\alpha_1,$ $\alpha_2,\ldots,$ $\alpha_k$ sao cho hai điều kiện sau được thỏa mãn đồng thời:

(1) $\alpha_i\in (0;1),\quad \forall i=\overline{1,k}$ và $\alpha_1+\alpha_2+\cdots+\alpha_k\leq 1.$

(2) $x_{n+k}\leq \alpha_1x_{n+k-1}+\alpha_2x_{n+k-2}+\cdots+\alpha_kx_n,\quad \forall n\geq 1.$

Mọi dãy lồi dưới cấp $1$ đều có giới hạn bằng $0.$ Trong định nghĩa trên, nếu dãy số $(x_n)$ có giới hạn hữu hạn và $\sum\alpha_i<1$ thì $\lim x_n=0.$

Định lí. Cho số nguyên dương $k$ . Khi đó mọi dãy lồi dưới cấp $k$ đều có giới hạn hữu hạn.

Chứng minh. Gọi $(x_n)$ là một dãy lồi dưới cấp $k$ . Khi đó tồn tại các số thực $\alpha_1,$ $\alpha_2,\ldots,$ $\alpha_k$ sao cho hai điều kiện sau được thỏa mãn đồng thời:

(1) $\alpha_i\in (0;1),\quad \forall i=\overline{1,k}$ và $\alpha_1+\alpha_2+\cdots+\alpha_k\leq 1.$

(2) $x_{n+k}\leq \alpha_1x_{n+k-1}+\alpha_2x_{n+k-2}+\cdots+\alpha_kx_n,\quad \forall n\geq 1.$

Xét dãy số $(y_n)_{n\geq 1}$ xác định bởi $\displaystyle y_n=\max_{0\leq i\leq k-1}x_{n+i}$ với mọi số nguyên $n>0.$ Ta thấy $(y_n)_{n\geq 1}$ là một dãy số không tăng và bị chặn dưới bởi $0$ nên nó có giới hạn hữu hạn không âm, đặt $L=\lim y_n$ . Ta sẽ chứng minh $(x_n)$ có giới hạn hữu hạn và $L=\lim x_n$ .

Với mọi số thực dương $\epsilon$ , cố định nó.

Đặt $\displaystyle t=\min\left\{1;\frac{\alpha_1^k}{2^k(1-\alpha_1)}\right\}.$ Vì $t>0$ và $L$ là giới hạn của dãy số không tăng $(y_n)$ nên tồn tại số nguyên dương $n_{\epsilon}$ để

$x_n\leq y_n<L+t\epsilon\leq L+\epsilon,\quad \forall n\geq n_{\epsilon}.\quad (*)$

Bây giờ ta chứng minh $x_m>L-\epsilon,\quad \forall m\geq k+n_{\epsilon}.\quad (**)$

Giả sử tồn tại số nguyên dương $m\geq k+n_{\epsilon}$ sao cho $x_m\leq L-\epsilon.$

Mệnh đề. $\displaystyle x_{m+p}\leq L-\epsilon\left(\frac{\alpha_1}{2}\right)^p,\quad \forall p=\overline{1,k-1}.$

Chứng minh. Ta chứng minh bằng quy nạp theo $p.$ Với $p=1$ , từ $(*)$ và cách chọn $t$ ta có

$x_{m+1} \leq \alpha_1x_m+\alpha_2x_{m-1}+\cdots+\alpha_kx_{m-k+1}$

$\leq\alpha_1x_m+(\alpha_2+\cdots+\alpha_k)(L+t\epsilon)$

$\leq\alpha_1(L-\epsilon)+(1-\alpha_1)(L+t\epsilon)$

$\leq L-a_1\epsilon+\left(\frac{\alpha_1}{2}\right)^k\epsilon$

$\leq L-a_1\epsilon+\left(\frac{\alpha_1}{2}\right)^1\epsilon$

$=L-\epsilon\left(\frac{\alpha_1}{2}\right).$

Suy ra khẳng định đúng với $p=1.$ Giả sử khẳng định đúng đến $p<k-1$ , ta chứng minh nó đúng với $p+1.$ Theo giả thiết quy nạp, $(*)$ và cách chọn $t$ ta có