Maths Olympiad Prep

Library / /41 of 45

Combinatorics Difficulty 9.1 IMO level Prove it United States

A communications network consisting of some terminals is called a 3-connector if among any three terminals, some two of them can directly communicate with each other. A communications network contains a windmill with nn blades if there exist nn pairs of terminals {x1,y1},,{xn,yn}\{x_1, y_1\}, \dots, \{x_n, y_n\} such that each xix_i can directly communicate with the corresponding yiy_i and there is a hub terminal that can directly communicate with each of the 2n2n terminals x1,y1,,xn,ynx_1, y_1, \dots, x_n, y_n. Determine the minimum value of f(n)f(n), in terms of nn, such that a 3-connector with f(n)f(n) terminals always contains a windmill with nn blades.

Solution

The answer is
f(n)={6if n=1;4n+1if n2. f(n) = \begin{cases} 6 & \text{if } n = 1; \\ 4n + 1 & \text{if } n \ge 2. \end{cases}
We will use connected as a synonym for directly communicating, call a set of kk terminals for which each of the (k2)\binom{k}{2} pairs of terminals is connected complete and call a set of 2k2k terminals forming kk disjoint connected pairs a k-matching.

We first show that f(n)=4n+1f(n) = 4n + 1 for n>1n > 1. The 4n4n-terminal network consisting of two disconnected complete sets of 2n2n terminals clearly does not contain an nn-bladed windmill (henceforth called an nn-mill), since such a windmill requires a set of 2n+12n+1 connected terminals. So we need only demonstrate that f(n)=4n+1f(n) = 4n + 1 is sufficient.

Note that we can inductively create a kk-matching in any subnetwork of 2k+12k + 1 elements, as there is a connected pair in any set of three or more terminals. Also, the set of terminals that are not connected to a given terminal xx must be complete, as otherwise there would be a set of three mutually disconnected terminals. We now proceed by contradiction and assume that there is a (4n+1)(4n + 1)-terminal network without an nn-mill. Any terminal xx must then be connected to at least 2n2n terminals, for otherwise there would be a complete set of size at least 2n+12n + 1, which includes an nn-mill. In addition, xx cannot be directly connected to more than 2n2n terminals, for otherwise we could construct an nn-matching among these, and therefore an nn-mill. Therefore every terminal is connected to precisely 2n2n others.

If we take two terminals uu and vv that are not connected we can then note that at least one must be connected to the 4n14n - 1 remaining terminals, and therefore there must be exactly one, ww, to which both are connected. The rest of the network now consists of two complete sets of terminals AA and BB of size 2n12n - 1, where every terminal in AA is connected to uu and not connected to vv, and every terminal in BB is not connected to uu and connected to vv. If ww were connected to any terminal in AA or BB, it would form a blade with this element and hub uu or vv respectively, and we could fill out the rest of an nn-mill with terminals in AA or BB respectively. Hence ww is only connected to two terminals, and therefore n=1n = 1.

Figure 1

Examining the preceding proof, we can find the only 5-terminal network with no 1-mill: With terminals labeled A, B, C, D, and E, the connected pairs are (A, B), (B, C), (C, D), (D, E), and (E, A). (As indicated in the figure above, a pair of terminals are connected if and only if the edge connecting them are darkened.) To show that any 6-terminal network has a 1-mill, we note that any complete set of three terminals is a 1-mill. We again work by contradiction. Any terminal a would have to be connected to at least three others, b, c, and d, or the terminals not connected to a would form a 1-mill. But then one of the pairs (b, c), (c, d), and (b, d) must be connected, and this creates a 1-mill with that pair and a.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.