Bài 10 HMMT tháng 11/2026 – Đồ thị và tuyến tính của kỳ vọng
HMMT tháng 11/2026 diễn ra ngày 7 tháng 11 tại Đại học Harvard. Hai vòng cá nhân General và Theme kéo dài 50 phút mỗi vòng. Kỳ thi còn có hai phần thi đồng đội là Team và Guts. Thông tin kỳ thi · Thể thức thi.
Bài 10 vòng General hỏi về số thành phần liên thông kỳ vọng của một mạng đường hầm ngẫu nhiên. Cùng Học Toán dùng đồ thị có hướng để nối các quyết định riêng lẻ của từng thành phố với cấu trúc của cả mạng. Từ đó, ta có thể tính đáp số bằng tính tuyến tính của kỳ vọng và mở rộng bài toán từ 100 thành phố lên $n$ thành phố.
- Đề General gốc của HMMT, Bài 10 (PDF)
- Lời giải tiếng Việt của Cùng Học Toán (PDF)
- English solution (PDF)
- Read the English commentary
Mỗi thành phần có đúng một cặp chọn nhau
Xét $n\ge 2$ thành phố. Để phân tích quy tắc chọn đường hầm trong đề gốc, ta vẽ mũi tên $u\to v$ khi $u$ chọn đường hầm $uv$. Ta bỏ hướng khi xét liên thông, và hai mũi tên ngược chiều trên cùng một cạnh chỉ biểu thị một đường hầm đã xây.
Giả sử ta vừa đi theo mũi tên từ $u$ đến $v$. Cạnh $uv$ cũng là một lựa chọn của $v$. Nếu $v$ chọn đi tiếp đến $w\ne u$ thì cạnh $vw$ rẻ hơn $uv$. Chi phí giảm nghiêm ngặt ở mỗi bước cho đến khi một mũi tên đưa ta trở lại ngay thành phố vừa rời. Có hữu hạn cạnh, nên ta sẽ đến một cặp thành phố chọn nhau và từ đó đi qua lại giữa hai thành phố ấy.
$$D\longrightarrow A\longleftrightarrow B\longleftarrow C.$$
Trong sơ đồ này, cả bốn thành phố dẫn đến cặp $A,B$. Nói chung, hai đầu của mỗi đường hầm đã xây dẫn đến cùng một cặp, vì có ít nhất một mũi tên từ đầu này sang đầu kia. Do đó, mọi thành phố trong cùng một thành phần liên thông dẫn đến cùng một cặp. Ngược lại, những thành phố dẫn đến cùng một cặp nối được với nhau qua cặp ấy. Vậy mỗi thành phần liên thông chứa đúng một cặp chọn nhau.
Tính kỳ vọng bằng biến chỉ báo
Gọi $C_n$ là số thành phần liên thông. Với mỗi thành phố $u$, đặt $J_u=1$ nếu $u$ thuộc một cặp chọn nhau và $J_u=0$ trong trường hợp còn lại. Mỗi thành phần có đúng hai thành phố với $J_u=1$, nên
$$2C_n=\sum_u J_u.$$
Cố định hai thành phố $u,v$ phân biệt. Chúng chọn nhau đúng khi $uv$ rẻ nhất trong các cạnh kề $u$ hoặc $v$. Tập này có $2(n-1)-1=2n-3$ cạnh vì $uv$ xuất hiện trong cả hai danh sách. Thứ tự chi phí trên tập này là ngẫu nhiên đều, nên xác suất $u$ và $v$ chọn nhau bằng $1/(2n-3)$. Với $u$ cố định, các biến cố tương ứng với $n-1$ giá trị của $v$ loại trừ lẫn nhau. Do đó
$$\mathbb E[J_u]=\mathbb P(J_u=1)=\frac{n-1}{2n-3}.$$
Tính tuyến tính của kỳ vọng áp dụng cả khi các biến $J_u$ phụ thuộc. Chẳng hạn, với ba thành phố, luôn có đúng hai biến bằng $1$. Biết hai giá trị thì xác định được giá trị còn lại. Lấy kỳ vọng trong đẳng thức đếm ở trên cho
$$\mathbb E[C_n]=\frac{n(n-1)}{2(2n-3)}\quad\text{với }n\ge 2.$$
Khi $n=100$, công thức cho $\mathbb E[C_{100}]=4950/197$. Khi $n$ lớn, tỉ số $\mathbb E[C_n]/n$ tiến tới $1/4$.
Đối chiếu với lời giải chính thức
Ban tổ chức chỉ ra rằng mạng là một rừng bằng cách xét cạnh đắt nhất của một chu trình giả định. Từ đẳng thức giữa số đỉnh, số cạnh và số thành phần của rừng, lời giải chính thức quy bài toán về việc đếm những đường hầm được chọn ở cả hai đầu. Lập luận bằng mũi tên ở trên chứng minh trực tiếp vì sao có đúng một đường hầm như vậy trong mỗi thành phần. Hai cách đều cho đáp số $4950/197$. Lời giải chính thức, trang 10–11.
English commentary
The November 2026 HMMT took place at Harvard on November 7. Problem 10 of the General Round asks for the expected number of connected components in a random tunnel network. A directed graph connects each city's local choice to the structure of the whole network. Indicator variables then let us extend the calculation from 100 cities to any $n\ge 2$.
Following the arrows
Consider $n\ge 2$ cities with one candidate tunnel for every pair. The costs are distinct and their relative order is uniform. Draw an arrow $u\to v$ when $uv$ is the cheapest candidate tunnel incident to $u$. To read the connected components of the built network, ignore the arrow directions and count two opposite arrows as one tunnel.
Suppose we follow an arrow from $u$ to $v$. The edge $uv$ was available to $v$, so if $v$ points to $w\ne u$, then $vw$ is cheaper than $uv$. The costs decrease strictly until an arrow returns to the city just left. Since only finitely many costs are available, such a return must occur. The arrows then alternate between two cities that choose each other.
For example, in the diagram
$$D\longrightarrow A\longleftrightarrow B\longleftarrow C,$$
all four cities lead to the pair $A,B$. In general, both endpoints of every built edge lead to the same pair because at least one arrow runs from one endpoint to the other. All cities in a connected component therefore lead to the same pair. Conversely, cities leading to the same pair are joined by their paths to it. Hence each component contains exactly one pair of cities that choose each other.
Counting with indicators
Let $C_n$ be the number of connected components. For each city $u$, let $J_u=1$ if it belongs to a pair whose members choose each other, and let $J_u=0$ otherwise. Each component contributes exactly two cities with $J_u=1$, so
$$2C_n=\sum_u J_u.$$
Two cities $u,v$ choose each other exactly when $uv$ is the cheapest edge among those incident to at least one of them. There are $2(n-1)-1=2n-3$ such edges, with $uv$ counted once. Their relative order is uniform, so each edge is equally likely to be cheapest. For fixed $u$, the events that it forms a pair with each of its $n-1$ possible partners are mutually exclusive. Thus
$$\mathbb E[J_u]=\mathbb P(J_u=1)=\frac{n-1}{2n-3}.$$
Linearity of expectation applies to dependent indicators as well. When there are three cities, for instance, exactly two indicators equal $1$ in every outcome. Taking expectations gives
$$\mathbb E[C_n]=\frac12\sum_u\mathbb E[J_u]=\frac{n(n-1)}{2(2n-3)}\quad\text{for }n\ge2.$$
For $n=100$, this gives $4950/197$. As $n$ grows, the ratio $\mathbb E[C_n]/n$ tends to $1/4$.
Comparison with the official solution
The official argument proves that the network is a forest and uses its edge count to determine the number of components. The directed graph identifies the particular pair within each component. Both approaches give the same expectation. Official solution, pp. 10–11.
Để lại một bình luận