В деревне живут 94 человек в возрасте 1 , 2 , . . . , 94 лет (для каждого возраста - ровно один человек). Два человека могут образовать счастливую пару, если возраст каждого из них хотя бы на 9 лет больше половины возраста другого. Какое наибольшее количество (непересекающихся) счастливых пар можно составить из жителей селения?
Ответы
Ответ:
36 пар
Пошаговое объяснение:
Покажем, что люди в возрасте от 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. Всего счастливых пар будет 94/2 - 18/2 = 47 - 9 = 36.