Question

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

Answer 1

Рассмотрим пару человек с возрастами k,n.

Из условия:

k-9>n/2

2k-18>n

2k>n+18

k>9+n/2

n-9>k/2

2n-18>k>9+n/2

4n-36>18+n

3n>54

n>18

k>9+n/2>9+9=18

Значит нельзя составить такие пары, где хотя бы 1 человек будт с возрастом n<=18.

Рассмотрим человека с возрастом 19:

Пусть возраст его пары m.

Тогда из условия:

19-9>m/2

20>m

Но m>18, значит m=19, что невозможно, так как есть только один человек с возрастом 19.

Тогда сгрупируем людей таким образом: 20 и 21, 22и 23, ... , 94 и 95.

Человек с возрастом 96 не попадет ни в какую пару.

Докажем, что так можно сгрупировать:

Пусть есть люди с возрастами p и p+1.

Из условия:

2p-18>p+1

p>19

2(p+1)-18>p

p>16

Значит при p>=20 такое выполняется.

Докажем, что это и есть максимальное количество пар:

Уже доказано, что люди с возрастами 1,2,...19 не могут войти ни в одну из пар.

Значит осталось людей (с возрастами 20,21...96) 96-20+1=77 непарное число.

Значит один человек никуда не войдет. И максимальное количество пар 76/2=38.

В нашем случае (20 и 21,...94 и 95) пар тоже 38.

Ответ: 38