USA TSTST 2026

USA TSTST (Team Selection Test Selection Test) là một trong những kỳ thi cốt lõi trong quy trình tuyển chọn đội tuyển Olympic Toán học Quốc tế (IMO) của Hoa Kỳ.

Dưới đây là một số thông tin tổng quan về kỳ thi này:

Thời điểm và đối tượng: Kỳ thi được tổ chức vào cuối chương trình Trại hè Toán học (MOP – Mathematical Olympiad Program). Tất cả học sinh tham gia MOP chưa tốt nghiệp trung học đều đủ điều kiện dự thi.
Cấu trúc đề thi: TSTST mô phỏng chính xác định dạng của kỳ thi IMO. Kỳ thi diễn ra trong 3 ngày, mỗi ngày học sinh phải giải quyết 3 bài toán trong thời gian 4,5 giờ.
Mục tiêu tuyển chọn: Kết quả của TSTST được dùng để chọn ra một nhóm học sinh xuất sắc (thường rơi vào khoảng 25–35 em, tùy chất lượng từng năm) để tham dự chuỗi USA Team Selection Tests (TST) trải dài trong năm học kế tiếp.
Chốt danh sách đội tuyển: Thành tích đạt được ở kỳ thi USAMO cùng với tổng điểm từ các kỳ TST sẽ quyết định 6 thành viên chính thức đại diện Hoa Kỳ tham dự IMO.

Một lưu ý lịch sử thú vị: Trước năm 2011, quy trình tuyển chọn của Hoa Kỳ không có vòng TSTST (chỉ đi thẳng từ MOP → TST → IMO). Việc bổ sung kỳ thi này từ năm 2011 đã giúp mở rộng cơ hội cạnh tranh và chuẩn hóa chuyên nghiệp hơn quy trình tuyển chọn đội tuyển của cường quốc Toán học này.

Dưới đây là đề năm 2026.

usatstst2026 Download

A Proof of Brill’s Theorem via Directional Derivatives

Let $K$ be the field of real numbers $\mathbb{R}$ or the field of complex numbers $\mathbb{C}$ . Given a vector $v = (v_1, \ldots, v_n) \in K^n$ . The directional derivative operator with respect to the vector $v$ , denoted by $D_v$ , is a map from the ring $K[x_1, \ldots, x_n]$ to itself, defined by

$\displaystyle D_v(P) = \sum_{i=1}^n v_i \frac{\partial P}{\partial x_i},$

where $\frac{\partial P}{\partial x_i}$ is the formal partial derivative of the polynomial $P$ with respect to the variable $x_i$ .

Theorem 1. Let $P, Q \in K[x_1, \ldots, x_n]$ , constants $a, b \in K$ , and a linear form $L(x) = c_1x_1 + \ldots + c_nx_n$ . The operator $D_v$ has the following properties.

(1) $D_v(aP + bQ) = aD_v(P) + bD_v(Q)$ .

(2) $D_v(PQ) = D_v(P)Q + P D_v(Q)$ .

(3) For any positive integer $k$ , $D_v(P^k) = k P^{k-1} D_v(P)$ .

(4) $D_v(L) = L(v)$ .

Proof. (1) By the definition of the partial derivative of a polynomial, we have

$\displaystyle \frac{\partial (aP + bQ)}{\partial x_i} = a\frac{\partial P}{\partial x_i} + b\frac{\partial Q}{\partial x_i},$

thus we immediately obtain $\displaystyle D_v(aP + bQ) = aD_v(P) + bD_v(Q).$

(2) Since the formal partial derivative obeys the product rule

$\displaystyle \frac{\partial (PQ)}{\partial x_i} = \frac{\partial P}{\partial x_i}Q + P\frac{\partial Q}{\partial x_i}$ we have

$\displaystyle D_v(PQ) = \sum_{i=1}^n v_i \left( \frac{\partial P}{\partial x_i}Q + P\frac{\partial Q}{\partial x_i} \right)$

$\displaystyle = \left( \sum_{i=1}^n v_i \frac{\partial P}{\partial x_i} \right) Q + P \left( \sum_{i=1}^n v_i \frac{\partial Q}{\partial x_i} \right) = D_v(P)Q + P D_v(Q).$

(3) We prove this by mathematical induction on $k$ .

For $k=1$ , the formula becomes $D_v(P^1) = 1 \cdot P^0 \cdot D_v(P)$ , which is trivially true.

Suppose the property holds for $k-1$ , that is

$\displaystyle D_v(P^{k-1}) = (k-1)P^{k-2}D_v(P).$

Applying (2), we obtain

$\displaystyle D_v(P^k) = D_v(P)P^{k-1} + P D_v(P^{k-1})$

$=D_v(P)P^{k-1} + P \big( (k-1)P^{k-2}D_v(P) \big)=k P^{k-1} D_v(P).$

By the principle of mathematical induction, the property holds for all positive integers $k$ .

(4) For a linear form $L(x) = c_1x_1 + \ldots + c_nx_n$ , we have

$\displaystyle D_v(L) = \sum_{i=1}^n v_i \frac{\partial L}{\partial x_i} = \sum_{i=1}^n v_i c_i = L(v).$

The theorem is completely proved. $\Box$

Theorem 2 (Brill). Suppose $K$ is the field of real numbers $\mathbb{R}$ or the field of complex numbers $\mathbb{C}$ . Let $L_1, L_2, \ldots, L_m$ be $m$ non-zero linear forms in $n$ $(n>1)$ variables that are pairwise non-proportional over $K$ . Then, for any integer $k \ge m-1$ , the set of powers $\{L_1^k, L_2^k, \ldots, L_m^k\}$ is linearly independent over $K$ .

Proof. We prove the theorem by mathematical induction on the number of linear forms $m$ . For $m=1$ , we have 1 non-zero linear form $L_1$ . For any integer $k \ge 0$ , the polynomial $L_1^k$ is not the zero polynomial, so the set consisting of only one element $\{L_1^k\}$ is trivially linearly independent. Thus, the assertion holds for $m=1$ .

Now suppose the assertion holds for $m-1$ linear forms, for some integer $m > 1$ . Consider $m$ non-zero pairwise non-proportional linear forms $L_1, \ldots, L_m$ and an exponent $k \ge m-1$ .

Consider the linear relation

$\displaystyle \sum_{i=1}^m c_i L_i^k = 0$ (1)

where $c_i \in K$ . We need to show that $c_i = 0$ for all $i = 1, \ldots, m$ .

Since $L_m$ is not identically $0$ , the set of points $x \in K^n$ such that $L_m(x) = 0$ is an $(n-1)$ -dimensional vector subspace of the space $K^n$ . At the same time, since $L_i$ is not proportional to $L_m$ for all $i < m$ , the intersection of the two spaces $L_i(x) = 0$ and $L_m(x) = 0$ is an $(n-2)$ -dimensional subspace.

The field $K$ has characteristic $0$ and is therefore an infinite field. A vector space over an infinite field cannot be the union of finitely many proper subspaces (see [1]). Therefore, there exists a vector $v = (v_1, \ldots, v_n) \in K^n$ such that $L_m(v) = 0$ and $\displaystyle L_i(v) \neq 0, \quad \forall i = 1, \ldots, m-1.$

Consider the directional derivative operator with respect to the vector $v$ defined as follows

$\displaystyle D_v = \sum_{j=1}^n v_j \frac{\partial}{\partial x_j}.$

When applying $D_v$ to a linear form $\displaystyle L(x) = a_1x_1 + \ldots + a_nx_n,$

we have $\displaystyle D_v(L) = a_1v_1 + \ldots + a_nv_n = L(v).$

When applying this operator to the $k$ -th power of $L$ , we obtain

$\displaystyle D_v(L^k) = k \cdot L^{k-1} \cdot D_v(L) = k \cdot L(v) \cdot L^{k-1}.$

Applying the operator $D_v$ to both sides of equation (1), we have

$\displaystyle \sum_{i=1}^m c_i k L_i(v) L_i^{k-1} = 0.$

Since $L_m(v) = 0$ , the $m$ -th term vanishes completely. Since $m \ge 2$ , we have $k \ge m-1 \ge 1$ , so we can divide both sides by $k$ (which is valid since $K$ has characteristic $0$ ) to obtain

$\displaystyle \sum_{i=1}^{m-1} \big(c_i L_i(v)\big) L_i^{k-1} = 0.$

Since $k \ge m-1$ , we deduce that $k-1 \ge m-2$ . Applying the inductive hypothesis to $m-1$ linear forms with the exponent $k-1$ , the set of polynomials $\{L_1^{k-1}, \ldots, L_{m-1}^{k-1}\}$ is linearly independent. Therefore, all coefficients in the sum above must be zero. That is,

$\displaystyle c_i L_i(v) = 0, \quad \forall i = 1, \ldots, m-1.$ But by the choice of the vector $v$ , we already have $L_i(v) \neq 0$ , so we must have $\displaystyle c_i = 0, \quad \forall i = 1, \ldots, m-1.$ Substituting $c_1 = \ldots = c_{m-1} = 0$ back into (1), we have $c_m L_m^k = 0$ . Since $L_m$ is not zero, $c_m = 0$ .

Thus $c_1 = c_2 = \ldots = c_m = 0$ , and $\{L_1^k, L_2^k, \ldots, L_m^k\}$ is linearly independent. By the principle of mathematical induction, the theorem is proved. $\Box$

References

[1] https://nttuan.org/2010/02/04/finite-unions-of-proper-subspaces-over-an-infinite-field/

Korea MO 2026 (Final Round)

NGÀY 1: Thứ Bảy, ngày 28 tháng 3 năm 2026

Thời gian làm bài: 14:00 – 18:30 (270 phút)

1. Cho tam giác nhọn $\displaystyle ABC$ có trực tâm $\displaystyle H$ . Gọi $\displaystyle D$ và $\displaystyle E$ lần lượt là chân các đường cao hạ từ các đỉnh $\displaystyle A$ và $\displaystyle C$ xuống các cạnh đối diện. Lấy một điểm $\displaystyle P$ ( $\displaystyle P \neq B, E$ ) nằm trên đoạn thẳng $\displaystyle BE$ , và gọi $\displaystyle Q$ là giao điểm của đường thẳng $\displaystyle PH$ với cạnh $\displaystyle AC$ . Gọi $\displaystyle \ell$ là đường phân giác trong của góc $\displaystyle \angle BAC$ . Đường thẳng đi qua $\displaystyle H$ và song song với $\displaystyle \ell$ cắt đường tròn ngoại tiếp tam giác $\displaystyle BDH$ và đường tròn ngoại tiếp tam giác $\displaystyle HDC$ lần lượt tại $\displaystyle X$ ( $\displaystyle X \neq H$ ) và $\displaystyle Y$ ( $\displaystyle Y \neq H$ ).

Chứng minh rằng ba đường thẳng $\displaystyle PX$ , $\displaystyle QY$ và $\displaystyle \ell$ đồng quy.

2. Một dãy số $\displaystyle \{a_{n}\} (n \ge 1)$ thỏa mãn các điều kiện sau:

$\displaystyle a_{1} = a_{2} = 1$ .
Với mọi số nguyên dương $\displaystyle n$ , ta có $\displaystyle a_{n+2} = a_{n} + \frac{1}{a_{n+1}^{2} + a_{n}^{2}}.$

Hãy xác định xem có tồn tại vô số số nguyên dương $\displaystyle n$ sao cho điều kiện sau đây được thỏa mãn hay không:

$\displaystyle a_{2n}^{3} > \frac{3n}{2} - 2026\sqrt{n}.$

3. Chứng minh rằng tồn tại một số nguyên dương $\displaystyle M$ ( $\displaystyle M \ge 3$ ) sao cho: Với mọi số nguyên $\displaystyle n \ge M$ và với bất kỳ các số nguyên dương $\displaystyle a, b, c$ thỏa mãn $\displaystyle 1 \le a < b < c \le n$ , ta luôn có

$\displaystyle \gcd(a+b+c, ab+bc+ca, abc) < 3n - \sqrt{3n} - 2^{2026}.$

NGÀY 2: Chủ Nhật, ngày 29 tháng 3 năm 2026

Thời gian làm bài: 09:00 – 13:30 (270 phút)

4. Chứng minh rằng không tồn tại bộ số nguyên dương $\displaystyle (p, q, r, n)$ nào thỏa mãn đồng thời cả hai điều kiện sau:

$\displaystyle p, q, r$ là các số nguyên tố.
$\displaystyle p^{n} + q^{n} + r^{n} = 2026(p+q)(q+r)(r+p).$

5. Minsu tham gia một chương trình truyền hình giải đố. Người dẫn chương trình chọn một số nguyên dương nhỏ hơn hoặc bằng $\displaystyle 5$ để làm “Mật mã của ngày”, và Minsu phải tìm ra số này bằng cách đặt câu hỏi. Các câu hỏi và câu trả lời tuân theo quy tắc như sau:

Trong mỗi câu hỏi, Minsu chọn một số nguyên dương $\displaystyle m$ và hỏi người dẫn chương trình xem số mật mã đó có lớn hơn hoặc bằng $\displaystyle m$ hay không.
Với mỗi câu hỏi, người dẫn chương trình chỉ trả lời “có” hoặc “không”. Trong suốt cả cuộc chơi, người dẫn chương trình được phép nói dối tối đa một lần.

Hãy tìm số câu hỏi ít nhất mà Minsu cần phải chuẩn bị để chắc chắn xác định được “Mật mã của ngày”, bất kể người dẫn chương trình có chọn số nào đi chăng nữa.

6. Ký hiệu $\displaystyle \mathbb{R}^{+}$ là tập hợp tất cả các số thực dương. Hãy tìm tất cả các giá trị có thể có của $\displaystyle f(2026)$ đối với hàm số $\displaystyle f:\mathbb{R}^{+} \rightarrow \mathbb{R}^{+}$ thỏa mãn điều kiện: với mọi số thực $\displaystyle x > 0$ và $\displaystyle y > 1$ , ta luôn có

$\displaystyle f(f(x)) + \frac{1}{y} = (f(f(xy)) + 1)f(y).$

Bốn Hệ Tư Tưởng Của Bitcoin

Tác giả: Michael Saylor

Bản dịch tiếng Việt của Gemini

Bitcoin không còn là một thử nghiệm kỹ thuật hẹp hay một cuộc phản kháng tiền tệ của một nhóm nhỏ. Nó đã trở thành mạng lưới tiền tệ kỹ thuật số thống trị và là một tài sản toàn cầu với những tác động sâu sắc đối với các cá nhân, tổ chức, tập đoàn, ngân hàng, thị trường vốn và các quốc gia.

Khi Bitcoin phát triển, cộng đồng xung quanh nó tự nhiên phân hóa thành các trường phái tư tưởng khác nhau. Những nhóm này chia sẻ niềm tin chung về tầm quan trọng của Bitcoin, nhưng lại khác nhau ở cách họ tin rằng Bitcoin nên tiến hóa, hội nhập, mở rộng quy mô và được bảo vệ.

Bài viết này mô tả bốn hệ tư tưởng chính của Bitcoin:

Người theo chủ nghĩa tối đa hóa Bitcoin (Bitcoin Maximalists)
Nhà tư bản Bitcoin (Bitcoin Capitalists)
Nhà công nghệ Bitcoin (Bitcoin Technologists)
Người theo chủ nghĩa cơ bản Bitcoin (Bitcoin Fundamentalists)

Mỗi hệ tư tưởng phản ánh một trọng tâm khác nhau. Người theo chủ nghĩa tối đa hóa coi Bitcoin là mạng lưới tiền tệ thống trị. Nhà tư bản coi Bitcoin là một nền tảng kinh tế mở cần được tích hợp vào thị trường toàn cầu. Nhà công nghệ coi Bitcoin là một giao thức phải tiếp tục được cải thiện. Người theo chủ nghĩa cơ bản coi Bitcoin là một bước đột phá tiền tệ thiêng liêng phải được bảo vệ khỏi sự tha hóa, thâu tóm và thỏa hiệp.

Các nhóm này không nhất thiết phải loại trừ lẫn nhau. Nhiều người ủng hộ Bitcoin (Bitcoiner) mang trong mình các yếu tố của nhiều hơn một góc nhìn. Nhưng những sự phân định này rất hữu ích vì chúng làm rõ các cuộc tranh luận đang định hình tương lai của Bitcoin.

1. Người theo chủ nghĩa tối đa hóa Bitcoin (Bitcoin Maximalist)

Niềm tin cốt lõi:
Bitcoin là mạng lưới tiền tệ kỹ thuật số thống trị: một bước đột phá về đạo đức, kỹ thuật và kinh tế, đồng thời là một công cụ trao quyền kinh tế. Nó cung cấp quyền tài sản vượt trội, tính toàn vẹn tiền tệ và niềm hy vọng cho những người đang đối mặt với sự khốn cùng về kinh tế.

Thế giới quan:
Người theo chủ nghĩa tối đa hóa Bitcoin tin rằng Bitcoin không chỉ đơn giản là một tài sản tiền mã hóa trong vô số các tài sản khác. Nó là một sự đột phá. Nó là mạng lưới đã giải quyết được vấn đề khan hiếm kỹ thuật số, thiết lập một nguồn cung tiền tệ cố định đáng tin cậy và tạo ra một giao thức phi tập trung để lưu trữ và chuyển giao giá trị mà không phụ thuộc vào bất kỳ chính phủ, ngân hàng, tập đoàn hay trung gian nào.

Đối với Người theo chủ nghĩa tối đa hóa, Bitcoin quan trọng vì nó cung cấp một thứ mà thế giới đang rất cần: một loại tiền tệ không thể bị tha hóa. Nó mang lại sự bảo vệ chống lại lạm phát, tịch thu, giảm giá trị, kiểm soát vốn, sự sụp đổ của các thể chế và sự hỗn loạn tiền tệ.

Những người theo chủ nghĩa tối đa hóa có xu hướng coi Bitcoin là một bước tiến về đạo đức và văn minh, chứ không đơn thuần là một giao dịch thương mại. Họ tin rằng loại tiền tệ ưu việt này sẽ cải thiện hành vi của con người, tưởng thưởng cho ưu tiên thời gian thấp (low time preference), bảo vệ tiền tiết kiệm và mang lại cho các cá nhân một lối thoát khỏi sự áp bức kinh tế.

Những điều Người theo chủ nghĩa tối đa hóa nhấn mạnh:

Bitcoin là mạng lưới tiền tệ kỹ thuật số thống trị.
Bitcoin là tài sản tiền mã hóa phi tập trung thực sự duy nhất.
Bitcoin là quyền tài sản ưu việt.
Bitcoin là giải pháp cho sự mất giá tiền tệ.
Bitcoin là niềm hy vọng cho những người đối mặt với khó khăn kinh tế.
Bitcoin là kho lưu trữ giá trị dài hạn.
Bitcoin là nền tảng của một hệ thống tiền tệ tốt hơn.

Điểm mạnh tự nhiên:
Lập trường của Chủ nghĩa tối đa hóa rất mạnh mẽ vì nó mang lại sự rõ ràng về mặt đạo đức. Nó xác định mục đích cao nhất của Bitcoin: mang lại sự trao quyền kinh tế thông qua nền tiền tệ vững chắc (sound money). Nó chống lại sự xao nhãng, sự pha loãng và sự đánh đồng sai lệch với các token hoặc dự án cạnh tranh. Chủ nghĩa tối đa hóa mang lại cho Bitcoin bản sắc mạnh mẽ nhất: không có vị trí thứ hai (there is no second best).

Rủi ro tự nhiên:
Rủi ro là Chủ nghĩa tối đa hóa có thể trở nên thiếu chính xác nếu nó không phân biệt được giữa Bitcoin – với tư cách là mạng lưới tiền tệ chiến thắng – và những cách thức khác nhau mà thế giới có thể áp dụng nó. Một Người theo chủ nghĩa tối đa hóa có thể tin rằng Bitcoin đã chiến thắng, nhưng vẫn cần phải trả lời câu hỏi làm thế nào Bitcoin tích hợp với các ngân hàng, công ty, thị trường vốn, chính phủ và hàng tỷ cá nhân. Chủ nghĩa tối đa hóa xác định đích đến. Các hệ tư tưởng khác tranh luận về lộ trình.

Continue reading →

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).