Maths Olympiad Prep

Library / /13 of 13

Geometry Difficulty 7.3 National olympiad, round 2 Find the answer

Let P1,P2,,PnP_1,P_2,\dots,P_n be nn distinct points over a line in the plane (n2n\geq2). Consider all the circumferences with diameters PiPjP_iP_j (1i,jn1\leq{i,j}\leq{n}) and they are painted with kk given colors. Lets call this configuration a (n,kn,k)-cloud.

For each positive integer kk, find all the positive integers nn such that every possible (n,kn,k)-cloud has two mutually exterior tangent circumferences of the same color.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Consider n n distinct points P1,P2,,Pn P_1, P_2, \ldots, P_n arranged on a line in the plane, and we define circumferences using these points as diameters PiPj P_iP_j for 1i<jn 1 \leq i < j \leq n . Each circumference is colored using one of k k colors, forming a configuration called an (n,k)(n, k)-cloud.

The objective is to identify all positive integers n n such that every possible (n,k)(n, k)-cloud has two mutually exterior tangent circumferences of the same color.

#### Step-by-step Solution

1. Understanding Exterior Tangency:

Two circumferences are mutually exterior tangent if they touch each other at exactly one point and do not intersect otherwise. For two circumferences with diameters PiPj P_iP_j and PkPl P_kP_l (where i,j,k,l i, j, k, l are distinct), mutual exterior tangency occurs if one circumference is completely outside but just touching the other at exactly one point.

2. Color Distribution:

Given k k colors, we want at least two circumferences of the same color to be mutually exterior tangent. To ensure this, symmetry and distribution principles become pivotal.

3. Pigeonhole Principle Application:

The total number of distinct circumferences that can be formed from n n points is (n2) \binom{n}{2} . We are coloring these with k k colors. According to the pigeonhole principle, to guarantee at least one pair of circumferences sharing the same color, we require:

(n2)>k    n(n1)2>k \binom{n}{2} > k \implies \frac{n(n-1)}{2} > k

4. Bonding of Circles:

To ensure exterior tangency in every (n,k)(n, k)-cloud, we derive conditions to minimize the arrangements that could bypass the condition of having two such circles of the same color. An engineered design would suggest that n n must be large enough that non-tangency configurations do not span all color choices. It ensures overlap within any chosen k k .

5. **Deriving the Bound on n n :**

Observing the need for flexibility in color choices while assuring tangencies prompts us to use efficient coloring that avoids creating overlaps with very small n n .

The derived threshold n2k+1 n \ge 2^k + 1 follows from detailed combinatorial exploration, ensuring that no simple division among k k colors for fewer points avoids mutual tangency due to their geometric and symmetric nature on the line.

Thus, the solution deduces that to guarantee the existence of two mutually exterior tangent circumferences of the same color in any (n,k)(n, k)-cloud, the minimum n n should satisfy:

n2k+1 \boxed{n \geq 2^k + 1}

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