Question

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

Answer 1

Ответ:

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.

Answer 2

Давайте рассмотрим, какие возрасты могут образовать счастливую пару для каждого жителя.

Предположим, что у первого жителя возраст составляет 1 год. Тогда возраст его партнера должен быть хотя бы 1 + 9 = 10 лет. Но у нас нет жителей с возрастами 10 и 11 лет. Значит, первый житель не может образовать счастливую пару.

Предположим, что у первого жителя возраст составляет 2 года. Тогда возраст его партнера должен быть хотя бы 2 + 9 = 11 лет. Но у нас нет жителей с возрастами 11 и 12 лет. Значит, второй житель не может образовать счастливую пару.

Мы продолжим этот процесс, исключая возможные партнеры для каждого жителя до тех пор, пока не дойдем до возраста 47 лет (половина 94). Начиная с возраста 47 лет, у каждого жителя будет хотя бы один возможный партнер.

Теперь давайте рассмотрим возраст 48 лет. Потенциальный партнер должен быть хотя бы на 48 + 9 = 57 лет. Но у нас нет жителей с возрастами 57, 58, ..., 94 лет, так как самый старший житель имеет возраст 94 лет. Значит, у жителей с возрастами 48 лет и старше также не будет счастливых пар.

Таким образом, наибольшее количество счастливых пар составит сумма всех жителей до возраста 46 лет:

1 + 2 + 3 + ... + 46 = (46 * 47) / 2 = 1081.

Таким образом, в деревне можно образовать наибольшее количество из 1081 счастливой пары.