Maths Olympiad Prep

Library / /418 of 520

Combinatorics Difficulty 6.0 National olympiad Prove it

7. A spatial figure is formed by nn points and ll line segments connecting these points, where
n=q2+q+1,l12q(q+1)2+1,q2,qN. n=q^{2}+q+1, l \geqslant \frac{1}{2} q(q+1)^{2}+1, q \geqslant 2, q \in \mathbf{N} .

It is known that no four points are coplanar, each point has at least one line segment, and there exists a point with at least q+2q+2 line segments.
Prove: The figure must contain a spatial quadrilateral (i.e., a figure formed by four points A,B,C,DA, B, C, D and four line segments AB,BC,CDA B, B C, C D, DAD A).

Solution

7. Let the set of nn points V={A0,A1,A2,,An1}V=\left\{A_{0}, A_{1}, A_{2}, \cdots, A_{n-1}\right\} be the universal set, and let the set of all neighbors of AiA_{i} (points connected to AiA_{i} by a line segment) be denoted as BiB_{i}. The number of points in BiB_{i} is denoted as Bi=bi\left|B_{i}\right|=b_{i}.
Clearly, i=0n1bi=2l\sum_{i=0}^{n-1} b_{i}=2 l and bin1(i=0,1,2,,n1)b_{i} \leqslant n-1(i=0,1,2, \cdots, n-1).
If there exists bi=n1(i=0,1,2,,n1)b_{i}=n-1(i=0,1,2, \cdots, n-1), then we only need to take
ι=(n1)+[n12]+112(q+1)(n1)+1=12q(q+1)2+1. \iota=(n-1)+\left[\frac{n-1}{2}\right]+1 \leqslant \frac{1}{2}(q+1)(n-1)+1=\frac{1}{2} q(q+1)^{2}+1 .

Then the graph must contain a quadrilateral.
Therefore, we only need to discuss bi0b_{i}0.
From (2), (3), and (nb0)(q+1),(nb01)q\left(n-b_{0}\right)(q+1),\left(n-b_{0}-1\right) q being positive integers, we get
(nqq+2b0)(nqqn+3b0)>q(q+1)(nb0)(nb01). \left(n q-q+2-b_{0}\right)\left(n q-q-n+3-b_{0}\right)>q(q+1)\left(n-b_{0}\right)\left(n-b_{0}-1\right) .

This contradicts equation (1), hence the original proposition holds.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.