Олимпиадная задача по комбинаторной геометрии для 9–11 классов Константинова Н. Н.
Задача
В некотором государстве человек может быть зачислен в полицию только в том случае, если он выше ростом чем 80% (или больше) его соседей. Чтобы доказать свое право на зачисление в полицию, человек сам называет число R (радиус), после чего его "соседями" считаются все, кто живёт на расстоянии меньше R от него (число соседей, разумеется, должно быть не нулевое). В этом же государстве человек освобождается от службы в армии только в том случае, если он ниже ростом, чем 80% (или больше) его соседей. Определение "соседей" аналогично; человек сам называет число r (радиус) и т. д., причём R и r не обязательно совпадают. Может ли случиться, что не менее 90% населения имеют право на зачисление в полицию и одновременно не менее 90% населения освобождены от армии? (Каждый человек проживает в определенной точке плоскости.)
Решение
Приведём пример такого государства. Рассмотрим точки числовой прямой: x + 1, x + 3–1, x + ·3–2, ..., x + 3–9. В эти точки поместим 10 человек. Пусть их рост (в той же последовательности) выражается числами a, a – 0,1, a – 0,2, ..., a – 0,9, где a > 1. Пусть значения R, которые называют первые девять из них (в том же порядке) – 1, 3–1, 3–2, ..., 3–8. Тогда по крайней мере 9 из них (все, кроме последнего) будут выше всех своих соседей. Конфигурацию из таких точек с какими-то значениями x и a назовём базовой конфигурацией.
Рассмотрим государство с 1000 жителей, распределённых по 100 базовым конфигурациям B0, B1, ..., B99 с параметрами xi = 399–i, a = 100 + i.
При таком расположении базовых конфигураций они не будут мешать друг другу, то есть у каждого человека "соседями" для полиции будут только те люди, которые получались, если эту базовую конфигурацию рассматривать отдельно. Таким образом, в полицию могут не попасть только некоторые из последних людей в базовых конфигурациях, а таких не больше 100 человек из 1000.
В качестве r (радиус для освобождения от армии) пусть каждый назовёт число 399–i, где i – номер его базовой конфигурации. Тогда число людей среди его "соседей" (определённых через этот радиус), которые ниже его, не больше 9 – это те, кто находится с ним в одной базовой конфигурации. Число же людей, которые выше его – это по крайней мере все люди из базовых конфигураций с бóльшими, чем у него, номерами. При i < 96 это число не меньше 40, поэтому девять более низких составляют меньше 20% всех "соседей". Таких людей 960, что больше 90% всех жителей.
Ответ
Может.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь