Maths Olympiad Prep

Library / /2 of 3

, 2002

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Baltic Way

Problem:

Let PP be a set of n3n \geqslant 3 points in the plane, no three of which are on a line. How many possibilities are there to choose a set TT of (n12)\left(\begin{array}{c}n-1 \\ 2\end{array}\right) triangles, whose vertices are all in PP, such that each triangle in TT has a side that is not a side of any other triangle in TT?

Solution

Solution:

For a fixed point xPx \in P, let TxT_{x} be the set of all triangles with vertices in PP which have xx as a vertex. Clearly, Tx=(n12)\left|T_{x}\right|=\left(\begin{array}{c}n-1 \\ 2\end{array}\right), and each triangle in TxT_{x} has a side which is not a side of any other triangle in TxT_{x}. For any x,yPx, y \in P such that xyx \neq y, we have TxTyT_{x} \neq T_{y} if and only if n4n \geqslant 4. We will show that any possible set TT is equal to TxT_{x} for some xPx \in P, i.e. that the answer is 1 for n=3n=3 and nn for n4n \geqslant 4.

Let
T={ti:i=1,2,,(n12)},S={si:i=1,2,,(n12)} T=\left\{t_{i}: i=1,2, \ldots,\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)\right\}, \quad S=\left\{s_{i}: i=1,2, \ldots,\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)\right\}
such that TT is a set of triangles whose vertices are all in PP, and sis_{i} is a side of tit_{i} but not of any tjt_{j}, jij \neq i. Furthermore, let CC be the collection of all the (n3)\left(\begin{array}{l}n \\ 3\end{array}\right) triangles whose vertices are in PP. Note that
C\T=(n3)(n12)=(n13) |C \backslash T|=\left(\begin{array}{c} n \\ 3 \end{array}\right)-\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)=\left(\begin{array}{c} n-1 \\ 3 \end{array}\right)
Let mm be the number of pairs (s,t)(s, t) such that sSs \in S is a side of tC\Tt \in C \backslash T. Since every sSs \in S is a side of exactly n3n-3 triangles from C\TC \backslash T, we have
m=S(n3)=(n12)(n3)=3(n13)=3C\T m=|S| \cdot(n-3)=\left(\begin{array}{c} n-1 \\ 2 \end{array}\right) \cdot(n-3)=3 \cdot\left(\begin{array}{c} n-1 \\ 3 \end{array}\right)=3 \cdot|C \backslash T|
On the other hand, every tC\Tt \in C \backslash T has at most three sides from SS. By the above equality, for every tC\Tt \in C \backslash T, all its sides must be in SS.

Assume that for pPp \in P there is a side sSs \in S such that pp is an endpoint of ss. Then pp is also a vertex of each of the n3n-3 triangles in C\TC \backslash T which have ss as a side. Consequently, pp is an endpoint of n2n-2 sides in SS. Since every side in SS has exactly 2 endpoints, the number of points pPp \in P which occur as a vertex of some sSs \in S is
2Sn2=2n2(n12)=n1 \frac{2 \cdot|S|}{n-2}=\frac{2}{n-2} \cdot\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)=n-1
Consequently, there is an xPx \in P which is not an endpoint of any sSs \in S, and hence TT must be equal to TxT_{x}.

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.