Competition problem — Combinatorics

Library / /9 of 11

Combinatorics Difficulty 6.8 National olympiad Prove it Romania

Let $n \ge 3$ be a positive integer, set $M = \{1, 2, \dots, n\}$ and let $k > 0$ be a real number. Let's associate each non-empty subset of $M$ with a point in the plane, such that any two distinct subsets correspond to different points. If the absolute value of the difference between the arithmetic means of the elements of two distinct non-empty subsets of $M$ is at most $k$ , we connect the points associated with these subsets with a segment. Determine the minimum value of $k$ such that the points associated with any two distinct non-empty subsets of $M$ are connected by a segment or a broken line.

Solution

To show that $\frac{1}{2}$ is the required minimum, notice that:

* $1 \le m_A \le n$ , for every nonempty subset $A \subset M$ , (1);
* any two one-element subsets are connected with a sequence of subsets, (2).

Indeed, for $k < p$ , consider the sequence $\{k\}, \{k, k+1\}, \{k+1\}, \{k+1, k+2\}, \dots, \{p-1, p\}, \{p\}$ . The absolute value of the difference between the arithmetic means of any two consecutive subsets from this sequence is $\frac{1}{2}$ .

Let $A$ and $B$ be two different subsets and $m_A, m_B$ be the arithmetic means of their elements, respectively. Denote by $n_A, n_B$ the closest integers to $m_A$ and $m_B$ , respectively. From (1) we have $n_A, n_B \in [1, n]$ and it is enough to consider the sequence $A, s_{n_A, n_B}, B$ , where $s_{n_A, n_B}$ is the sequence described for the subsets $\{n_A\}$ and $\{n_B\}$ .

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 and solution reproduced as published; topic and difficulty added by this site.