Задача 2. Двадцать чисел, 101 пара

Считаем все пары и ставим цель

Сколько всего пар можно составить из $20$ чисел? Каждое число образует пару с $19$ другими — получается $20 \cdot 19 = 380$ пар, но каждая пара посчитана дважды: один раз от первого числа, один раз от второго. Значит, пар всего $380 : 2 = 190$. Из них ровно $101$ должна быть хорошей, а остальные $89$ — нет.

Проверять случайные наборы из $20$ чисел бессмысленно: в каждом $190$ пар. Удобнее собрать набор из «кусочков», в которых количество хороших пар известно заранее, и следить, чтобы между кусочками хороших пар не появлялось.

Цепочка: все пары хорошие, и их легко сосчитать

Возьмём числа, в которых каждое делит следующее: $2, 4, 8, 16, \ldots$ — каждое следующее вдвое больше. Любые два таких числа образуют хорошую пару: большее получается из меньшего умножением на $2$ несколько раз, то есть делится на него. Назовём такой набор цепочкой.

Сколько пар в цепочке из $k$ чисел? Все пары хорошие, поэтому считаем все пары: первое число — с каждым из $k-1$ остальных, второе — с каждым из $k-2$ следующих, и так далее. Для пяти чисел $3, 9, 27, 81, 243$ это $4 + 3 + 2 + 1 = 10$ пар (рисунок ниже). В общем виде, как в шаге 1: $k$ чисел по $k-1$ пар на каждое, каждая пара посчитана дважды — $\dfrac{k(k-1)}{2}$ пар.

Для $14$ чисел получаем $\dfrac{14 \cdot 13}{2} = 91$ пару, а для $15$ — уже $\dfrac{15 \cdot 14}{2} = 105$ пар, это больше $101$. Значит, одна цепочка из $14$ чисел даёт $91$ пару, и до $101$ не хватает ровно $10$.

Собираем 101 = 91 + 10

$91$ пару даёт цепочка из $14$ чисел, $10$ пар — цепочка из $5$ чисел (шаг 2). Вместе это $19$ чисел; двадцатое число возьмём такое, чтобы оно не образовало хорошей пары ни с кем.

Чтобы цепочки не мешали друг другу, составим их из степеней разных простых чисел:

• первая цепочка — $14$ степеней двойки: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384;

• вторая цепочка — $5$ степеней тройки: $3, 9, 27, 81, 243$;

• двадцатое число — $5$.

Все $20$ чисел различны. Осталось самое важное: объяснить, почему между группами хороших пар нет — иначе их пришлось бы пересчитывать.

Почему между группами хороших пар нет

Сравним степень двойки $2^a$ и степень тройки $3^b$ (здесь $a \geq 1$ и $b \geq 1$).

• $3^b$ не делится на $2^a$: число $3^b = 3 \cdot 3 \cdots 3$ нечётное (произведение нечётных чисел нечётно), а $2^a$ чётное; нечётное число не делится даже на $2$.

• $2^a$ не делится на $3^b$: иначе $2^a$ делилось бы на $3$. Но остатки степеней двойки при делении на $3$ чередуются: $2$, $4 = 3 + 1$, $8 = 6 + 2$, $16 = 15 + 1$, … Умножение на $2$ переводит остаток $1$ в $2$, а остаток $2$ — в $4$, то есть снова в $1$. Остаток $0$ не появится никогда.

Теперь число $5$. Оно не делит ни $2^a$, ни $3^b$: степени двойки оканчиваются на $2, 4, 8, 6$, степени тройки — на $3, 9, 7, 1$, а делящееся на $5$ число оканчивается на $0$ или $5$. И само $5$ не делится ни на $2^a$ (оно нечётное), ни на $3^b$ ($5 = 3 \cdot 1 + 2$, а $9, 27, \ldots$ больше $5$).

Общее правило, которое здесь работает: если у двух чисел, больших $1$, нет общего простого делителя, они не делят друг друга — ведь каждый простой делитель делителя является и делителем самого числа.

Ровно 101: ни больше, ни меньше

Разложим все $190$ пар по видам и посчитаем хорошие в каждом (рисунок ниже):

• обе из степеней двойки: $91$ пара, все хорошие (шаг 2);

• обе из степеней тройки: $10$ пар, все хорошие (шаг 2);

• одно число из первой цепочки, другое из второй: $14 \cdot 5 = 70$ пар, хороших нет (шаг 4);

• число $5$ с кем-то ещё: $19$ пар, хороших нет (шаг 4).

Всего пар $91 + 10 + 70 + 19 = 190$ — учтены все. Хороших пар $91 + 10 + 0 + 0 = 101$. Набор подходит, и объяснение «не больше и не меньше» — это именно подсчёт по видам пар.