Числа и их свойства

Решение:

Поскольку $A+2+B-1=A+B+1$, с каждым ходом сумма чисел будет возрастать на $1$.

а) После $20$ ходов сумма станет

$$7+11+20=38<50,$$ значит, второе число пары не будет натуральным. Это запрещено.

б) Понадобится

$$600-(7+11)=582$$ хода. Такая ситуация возможна, если каждый раз на роль уменьшаемого выбирать большее из двух чисел — если оно равно $1$, то оба числа должны быть единицами, что невозможно, поскольку сумма чисел постоянно растёт и в самом начале равна

$$7+11>1+1.$$

в) Заметим, что разность между числами всегда меняется на $3$:

$$(A+2)-(B+1)=(A-B)-3.$$

Изначально эта разность равна

$$11-7=4$$ и не кратна трём, поэтому она никогда не станет равна нулю. Значит, сделать числа $50$ и $50$ не получится.

Поэтому сумма двух этих чисел будет не больше

$$49+50=99$$ и будет сделано не более

$$99-18=81$$ хода. Сделать столько ходов можно, например, так:

$$(7,11)\mapsto(9,10).$$ Затем $40$ раз повторить пару ходов

$$(x,x+1)\mapsto(x+2,x)\mapsto(x+1,x+2),$$ увеличивающую оба числа на $1$, если наибольшее не превосходило $49$.

Ответ: а) нет; б) $582$; в) $81$.

Решение

а) Да, возможно

Возьмём набор из 16 монет:

● одна монета номиналом 1 рубль;

● две монеты по 2 рубля;

● одна монета 5 рублей;

● двенадцать монет по 10 рублей.

Покажем, что с помощью этого набора можно составить любую целую сумму от 1 до 100 рублей.
Любое число $S \in [1; 100]$ представим в виде $$S = 10a + b, \quad 0 \le a \le 10,\; 0 \le b \le 9,$$ причём если $S = 100$, то берём все 10 десяток (хотя их 12). Для $S < 100$ используем $a$ монет по 10 рублей (где $a \le 9$). Остаток $b$ набираем монетами 1, 2, 2 и 5: они позволяют получить любое число от 0 до 9 (достаточно заметить, что $5, 2, 2, 1$ дают все остатки). Следовательно, набор из 16 монет подходит.

б) Нет, пяти монет недостаточно.

Предположим противное: выбрано 5 монет, позволяющих оплатить любую цену от 1 до 25 рублей.

Для того чтобы заплатить 3 рубля, необходимы как минимум две монеты (1 и 2). Для оплаты всех сумм от 1 до 4 рублей требуется не менее трёх монет (например, комбинации $1,1,2$ или $1,2,2$). Значит, среди пяти монет как минимум три заняты достоинствами 1 и 2.

Остаются две монеты. Рассмотрим два случая.

1. Если среди оставшихся двух монет нет двух десяток (то есть не более одной монеты 10 рублей), то максимальная сумма, которую можно набрать, не превосходит $$1 + 2 + 2 + 5 + 10 = 20$$ (или меньше, если нет пятёрки). Тогда нельзя оплатить 21 рубль — противоречие.

2. Если же обе оставшиеся монеты — десятки, то возможные наборы имеют вид либо $1,1,2,10,10$, либо $1,2,2,10,10$.
   В первом случае доступны суммы: без десяток — 1, 2, 3, 4; с одной десяткой — 11–14; с двумя — 21–24. Число 19 не получается.
   Во втором случае: без десяток — 1–5; с одной — 11–15; с двумя — 21–25. Число 19 также недостижимо.
   Значит, и в этом случае нельзя гарантировать оплату всех сумм до 25.

Следовательно, 5 монет недостаточно.

в) Минимальное количество монет — 13

Сначала докажем, что 12 монет не хватит.
Рассуждая аналогично пункту б), для оплаты всех сумм от 1 до 4 рублей необходимо минимум три монеты достоинством 1 или 2. Оставшиеся монеты (их не более 9) могут быть самого крупного номинала — 10 рублей, но если взять 10 десяток, то общее число монет станет 13, что больше 12. При 12 монетах максимум можно взять 9 десяток, две двойки и одну единицу, тогда общая максимальная сумма равна $$9 \cdot 10 + 2 + 2 + 1 = 95.$$ Значит, нельзя оплатить цены 96–100 рублей. Итак, 12 монет недостаточно.

Теперь покажем, что 13 монет достаточно. Возьмём набор: $$\underbrace{10, 10, \ldots, 10}_{9\text{ штук}},\; 5,\; 2,\; 2,\; 1.$$ Всего $9 + 1 + 2 + 1 = 13$ монет.

Для любой цены $S \le 100$ представим её в виде $S = 10a + b$, где $0 \le a \le 10$, $0 \le b \le 9$. Если $S = 100$, отдаём все 13 монет (сумма как раз 100). Если $S < 100$, то $a \le 9$ — берём $a$ монет по 10 рублей. Остаток $b$ набираем монетами $5, 2, 2, 1$:

● если $b \ge 5$, берём одну монету 5 рублей и добираем $b-5$ с помощью двух двоек и единицы (это возможно, так как эти три монеты дают все числа от 0 до 5);

● если $b < 5$, набираем его непосредственно из двоек и единицы. Таким образом, любая цена до 100 рублей будет оплачена без сдачи.

Следовательно, минимальное необходимое число монет равно 13.

Ответ:

а) да, может;

б) нет, не может;

в) 13 монет.

Решение

а)

Да, может. Покажем последовательность действий:

1. Отрезаем от единственной линейки $8$ см — получаем две линейки по $8$ см.
2. От каждой линейки отрезаем $4$ см — получаем четыре линейки по $4$ см.
3. От каждой линейки отрезаем $2$ см — получаем восемь линеек по $2$ см.
4. От каждой линейки отрезаем $1$ см — получаем шестнадцать линеек по $1$ см.

Таким образом, за $4$ хода линейка длиной $16$ см полностью разделена на части по $1$ см.

Ответ: да, может.

б)

За один ход Егор может разделить каждую имеющуюся линейку на две части, следовательно, общее количество линеек за один ход увеличивается не более чем вдвое. Изначально есть одна линейка. После $5$ ходов максимальное число линеек не превосходит $$2^5 = 32.$$ Чтобы получить $100$ частей по $1$ см, необходимо иметь $100$ линеек. $100 > 32$, значит, за $5$ ходов это невозможно.

Ответ: нет, не может.

в)}

Оценим снизу: после $7$ ходов максимальное число линеек равно $2^7 = 128$, что меньше $200$. Следовательно, семи ходов недостаточно.

Покажем, что $8$ ходов достаточно. Будем действовать по следующей схеме:

После $8$-го хода все линейки имеют длину $1$ см, то есть задача выполнена. Следовательно, минимальное количество ходов равно $8$.

Ответ: $8$ ходов.

Окончательные ответы:

а) да;

б) нет;

в) $8$.