Kvant Math Problem 1560

Consider the population as a finite set of $N$ individuals arranged along a circle.

kvantmathematicsolympiad

Verified: no
Verdicts: FAIL + PASS
Solve time: 24m56s
Source on kvant.digital

Problem

In a certain country, a person may be admitted to the guard only if he is taller than 80% (or more) of his neighbors. To prove his right to be admitted to the guard, the person himself specifies a number $R$ (a radius), after which his “neighbors” are considered to be all those who live at a distance less than $R$ from him. In the same country, a person is exempt from military service only if he is shorter than 80% (or more) of his neighbors. The definition of “neighbors” is analogous: the person himself specifies a number $r$ (a radius), and so on, where $R$ and $r$ need not coincide. Can it happen that at least 90% of the population are eligible for admission to the guard and, at the same time, at least 90% of the population are exempt from military service? (The values of $R$ and $r$ must be chosen so that the corresponding “neighbor sets” are nonempty.)

N. N. Konstantinov

59th Moscow Mathematical Olympiad, 1996, Tournament of Towns (Spring 1996)

Construction

Consider the population as a finite set of $N$ individuals arranged along a circle. Partition the circle into a sequence of alternating blocks, denoted $L_1, H_1, L_2, H_2, \dots, L_m, H_m$, such that each block contains a large, explicitly specified number of individuals. For definiteness, let each $L$-block and each $H$-block contain exactly $K$ individuals, with $K$ divisible by $10$. Assign heights to individuals so that all members of an $L$-block are shorter than all members of any $H$-block. Within each block, order the individuals in increasing height along the traversal of the circle, assigning the heights as an arithmetic progression to ensure that for any subset of consecutive individuals within the block, the relative ordering remains strictly increasing. The total number of blocks is chosen so that at least $90%$ of the population lies in the interior of blocks, leaving at most $10%$ at the boundaries between blocks. Label individuals within each block from $1$ to $K$ according to their height order.

Behavior inside an $L$-block

Fix an individual $x$ in the interior of an $L$-block at position $i$, satisfying $4 \le i \le K-3$, to avoid boundary effects. Define a small radius $R$ so that the neighborhood of $x$ contains exactly $5$ consecutive neighbors to the left and $5$ consecutive neighbors to the right, giving a total of $s = 10$ neighbors. The left and right neighbors are determined combinatorially by adjacency along the circle. Since the heights in the block increase strictly along the traversal, if $x$ is positioned as the $k$-th tallest individual within these $11$ people (including $x$), the number of neighbors shorter than $x$ is exactly $k-1$, and the number of neighbors taller than $x$ is $s-(k-1)$. Choosing $x$ to be the $9$-th tallest within this group ensures that $8$ of $10$ neighbors are shorter, yielding $80%$ of neighbors shorter than $x$. This satisfies the condition for admission to the guard. The choice of radius $R$ is combinatorially defined by the number of adjacent individuals included, ensuring the neighborhood is nonempty and contains the prescribed discrete set of neighbors.

For a larger radius $r$, define the neighborhood of $x$ to include the entire $L$-block containing $x$ together with the full adjacent $H$-blocks on both sides. Let each $H$-block contain $K$ individuals. The total neighborhood size is $s' = K + 2K = 3K$ neighbors, of which $2K$ belong to $H$-blocks and are taller than $x$. The fraction of neighbors taller than $x$ is exactly $2K/3K = 2/3$, which is slightly below $80%$. To correct this, increase the number of individuals in each $H$-block to $5K$, so that the total neighborhood size becomes $s' = K + 2\cdot5K = 11K$, of which $10K$ are taller than $x$. The fraction is $10K/11K = 10/11 > 0.8$, satisfying the exemption condition. The radius $r$ is combinatorially defined to include these blocks and is guaranteed to be nonempty.

Behavior inside an $H$-block

Fix an individual $y$ in the interior of an $H$-block at position $j$, $6 \le j \le 5K-5$, to avoid boundary effects. For a small radius $R$, select a neighborhood consisting of $5$ consecutive neighbors on either side of $y$ within the block, giving $s = 10$ neighbors. Choose $y$ to be the $3$-rd tallest among these $11$ individuals, so that $8$ of the $10$ neighbors are taller than $y$, ensuring that $80%$ of neighbors are taller. This satisfies the exemption condition for military service. The neighborhood is nonempty and defined combinatorially, avoiding continuous approximations.

For a larger radius $r$, include the entire $H$-block containing $y$ and the full adjacent $L$-blocks on both sides. Each $L$-block contains $K$ individuals. The total neighborhood size is $s' = 5K + 2\cdot K = 7K$, of which $2K$ are shorter than $y$. The fraction of neighbors shorter than $y$ is $2K/7K = 2/7 < 0.8$. Increase the size of each $L$-block to $4K$ so that $s' = 5K + 2\cdot4K = 13K$, and the number of neighbors shorter than $y$ is $8K$. Then the fraction is $8K/13K \approx 0.615$, still below $0.8$. To reach the $80%$ threshold, enlarge each $L$-block to $10K$, so $s' = 5K + 2\cdot10K = 25K$ and the number of shorter neighbors is $20K$, yielding $20K/25K = 0.8$. Now the exemption condition is satisfied. The radius $r$ is combinatorially defined to include these blocks and is nonempty.

Ensuring the 90% requirement

Only individuals within a distance of $5$ individuals from the boundary of any block may fail to satisfy one of the two conditions because their neighborhoods cannot be fully contained in the desired blocks or adjacent blocks. Each block contains at least $5K$ individuals, and only the first and last $5$ positions are excluded, so the fraction of boundary individuals per block is at most $10/5K = 2/K$. Choosing $K \ge 50$ ensures that the proportion of boundary individuals is at most $4%$. Since the blocks cover the entire population, at least $96%$ of individuals lie in interior positions and satisfy both conditions simultaneously with the appropriately defined radii $R$ and $r$. This surpasses the required $90%$ threshold.

Conclusion

By partitioning the population into discrete alternating blocks of carefully specified sizes and assigning strictly increasing heights within each block while ensuring $L$-block heights are less than $H$-block heights, it is possible to define for each interior individual a small radius $R$ and a larger radius $r$ combinatorially so that at least $80%$ of neighbors satisfy the guard and exemption conditions respectively. Explicitly computing the number of boundary individuals relative to block size guarantees that at least $90%$ of the population satisfies both properties simultaneously. Therefore, there exists a finite discrete configuration of the population and corresponding neighborhood radii realizing the desired scenario.