Question

В деревне живут 92 человек в возрасте 1, 2, . . . , 92 лет (для каждого возраста - ровно один человек). Два человека могут образовать счастливую пару, если возраст каждого из них хотя бы на 9 лет больше половины возраста другого. Какое наибольшее количество (непересекающихся) счастливых пар можно составить из жителей селения?

Answer 1

Покажем, что люди в возрасте от 1 до 18 лет в счастливую пару входить не могут. Обозначим через x возраст самого молодого человека, входящего в счастливую пару и через y возраст его партнера. Тогда имеет место неравенство x ≥ y/2 + 9 или (x-y/2) ≥ 9. Заметим, что (x-y/2) < x/2, поскольку y > x. Имеет место неравенство 2(x-y/2) ≥ 18, но так как 2(x-y/2) < x, то x > 18, то есть, возраст самого молодого человека, входящего в счастливую пару, строго больше 18 лет.

Покажем, что все пары (19, 20), (21, 22), (23, 24), ..., (93, 94) будут счастливыми. Легко проверить, что если x >= 10, то для чисел 2x-1 и 2x имеют место неравенства 2x-1 >= x + 9 и 2x >= (2x-1)/2 + 9. Всего счастливых пар будет 92/2 - 18/2 = 46 - 9 = 37.

Answer 2

Для решения этой задачи нам нужно найти наибольшее количество непересекающихся счастливых пар из жителей деревни.

Давайте рассмотрим два возможных варианта:

1. Жителю возраста 1 можно образовать пару только с жителем возраста 10 или старше (потому что возраст второго члена пары должен быть хотя бы 5 лет больше половины возраста первого члена). Таким образом, возраста 1, 2, ..., 9 не могут быть использованы для образования пар.

2. Жителю возраста 2 можно образовать пару только с жителем возраста 11 или старше.

Теперь давайте рассмотрим возраст 10: он может образовать пару с жителями возраста 1 или с жителями возраста 19 или старше.

Продолжим этот процесс:

• Возраст 10 образует пары с возрастами 1 и 19 или старше.
• Возраст 11 образует пары с возрастами 2 и 20 или старше.
• Возраст 12 образует пары с возрастами 3 и 21 или старше.
• Возраст 13 образует пары с возрастами 4 и 22 или старше.
• Возраст 14 образует пары с возрастами 5 и 23 или старше.
• Возраст 15 образует пары с возрастами 6 и 24 или старше.
• Возраст 16 образует пары с возрастами 7 и 25 или старше.
• Возраст 17 образует пары с возрастами 8 и 26 или старше.
• Возраст 18 образует пары с возрастами 9 и 27 или старше.

Таким образом, возраста 1, 2, ..., 27 нельзя использовать для образования пар. Начиная с возраста 28 и далее, каждый возраст может образовать пару с возрастами 9 лет младше и 9 лет старше.

Итак, наибольшее количество непересекающихся счастливых пар можно составить из жителей деревни возрастами от 28 до 83 включительно, т.е. всего 83 - 28 + 1 = 56 пар.