Решение задач на теорию чисел из ЕГЭ прошлых лет (страница 2)

а) Упорядочим числа по возрастанию \(a_1, a_2, \dots, a_{100}\). Пусть одно из этих чисел равно \(230\). Пусть все оставшиеся 99 чисел – это \(1, 2, 3, \dots, 99\). Тогда сумма всех ста чисел – наименьшая возможная сумма в случае, когда среди чисел есть \(230\). Вычислим ее: \[\dfrac{1+99}2\cdot 99+230=5180>5120\] Получили противоречие с условием, следовательно, ответ: нет.

б) Предположим, что на доске нет числа \(14\). Снова упорядочим числа по возрастанию и рассмотрим числа: \(1, 2, \dots, 13, 15, \dots, 101\). Мы взяли наименьшее возможное значение для первого числа, для второго и т.д. Тогда сумма всех этих чисел – наименьшая возможная сумма среди сумм произвольных ста натуральных чисел. Она равна: \[\dfrac{1+101}2\cdot 101-14=5137>5120\] Получили опять же противоречие с условием, следовательно, ответ: нет.

в) Приведем пример, когда среди чисел есть четыре числа, кратные \(14\) (это числа \(14, 28, 42, 56\)): \[1, 2, \dots, 69, \quad 71, 72, \dots, 83, \quad 85, 86, \dots, 97, \quad 100, 101, 102, 103, 115.\] Докажем, что не может быть меньше четырех чисел, кратных \(14\).
Возьмем набор чисел от \(1\) до \(100\). Сумма чисел в данном наборе равна \(5050\). Это минимально возможная сумма ста различных натуральных чисел. Назовем числа, кратные \(14\), странными. В данном наборе 7 странных чисел. Будем уменьшать количество странных чисел в нашем наборе, сохраняя минимальность суммы чисел в наборе.
Итак, для того, чтобы сумма чисел была минимальна, мы должны убрать самое большое странное число – это \(98\). Тогда взамен ему придется добавить другое число (не странное!). Самое маленькое такое число – это \(101\). После этого мы получим минимальную сумму, равную \(5053\). Она меньше, чем \(5120\), поэтому будем продолжать дальше.
Поступая аналогично, уберем странные числа \(98, 84, 70\). Вместо них добавим \(101, 102, 103\). Получим при этом минимальную сумму, равную \(5104\). Сделав данную операцию еще раз, то есть убрав \(56\) и добавив \(104\), получим минимальную сумму \(5152\), что больше, чем \(5120\). В силу минимальности суммы чисел в нашем наборе получаем противоречие.

Ответ:

а) нет

б) нет

в) 4

а) Если на доске написано поровну чисел, оканчивающихся на \(4\), и чисел, оканчивающихся на \(8\), то чисел каждого вида по 15 штук. Следовательно, если сложить все эти числа, то последняя цифра их суммы будет равна последней цифре числа \(15\cdot 4+15\cdot 8=180\), то есть последняя цифра должна быть равна \(0\), что противоречит условию.
Следовательно, ответ: нет.

б) Рассмотрим все подряд идущие 30 натуральных чисел, оканчивающихся на \(4\), начиная с самого маленького: \(4, \ 14, \ 24, \ 34, \ \dots, 284, \ 294\). Эти числа образуют арифметическую прогрессию с разностью \(10\). Следовательно, их сумма равна \[\dfrac{4+294}2\cdot 30=4470\] Заметим, что это намного больше, чем \(2786\). И заметим, что это наименьшая возможная сумма 30-ти различных чисел, оканчивающихся на \(4\). Как нам максимально уменьшить эту сумму, добавив 4 числа, оканчивающихся на \(8\) (а значит и убрав 4 числа, оканчивающихся на \(4\), ведь количество чисел должно быть всегда равно \(30\))? Нужно убрать самые большие числа, оканчивающиеся на \(4\), и добавить самые маленькие, оканчивающиеся на \(8\). То есть нужно убрать \(294, \ 284, \ 274, \ 264\) и добавить \(8, \ 18, \ 28, \ 38\). Но в этом случае сумма всех чисел будет равна \[\begin{aligned} &4470-294-284-274-264+8+18+28+38=\\ &4470-(294-8)-(284-18)-(274-28)-(264-38)=\\ & 4470-286-266-246-226=\\ &3446>2786\end{aligned}\] Следовательно, ответ: нет.

в) Назовем числа, оканчивающиеся на \(4\), “числа Ч”, а оканчивающиеся на \(8\) – “числа В”.
Из пункта б) следует, что для того, чтобы понять, какое наименьшее количество чисел В может быть на доске, нужно убирать самые большие числа Ч и добавлять самые маленькие числа В, чтобы для начала их сумма максимально приблизилась к числу \(2786\).
Уберем еще \(254\) и добавим \(48\). Тогда, аналогично алгоритму в пункте б), нужно уменьшить сумму на \(206\): \(3446-206=3240\). Уберем еще два числа Ч \(244\) и \(234\) и добавим \(58\) и \(68\), тогда сумма равна \(3240-186-166=2888\). Итак, это наименьшая возможная сумма, если среди написанных чисел будет 7 чисел В.
Заметим, что каждый раз, убирая любое число Ч и добавляя любое число В, мы уменьшаем сумму всех чисел на число \(\overline{\dots6}\). Если изначально (когда было 30 чисел Ч) последняя цифра их суммы была равна \(0\), то после 8-ми замен (убираем число Ч и добавляем число В) последняя цифра суммы будет как у числа \(\overline{\dots0}-8\cdot 6=\overline{\dots2}\). По условию сумма должна быть равна \(2786\), следовательно, 8 чисел В на доске быть не может.
А вот для 9-ти чисел В на доске последняя цифра суммы всех чисел будет равна \(6\)!
Докажем, что 9 – наименьшее количество чисел В, которое может быть написано на доске.
Сейчас мы имеем 7 чисел В: \(8, \ 18, \ 28, \ 38, \ 48, \ 58, \ 68\)
и 23 числа Ч: \(4, \ 14, \ 24, \ \dots, 214, \ 224\).
Их сумма равна \(2888\).
Нам нужно получить сумму \(2786\), то есть уменьшить имеющуюся у нас сумму на \(102\). Как говорилось ранее, “каждый раз, убирая любое число Ч и добавляя любое число В, мы уменьшаем сумму всех чисел на число \(\overline{\dots6}\)”. Представим \(102=46+56\).
Уберем первый раз число Ч и добавим число В так, чтобы сумма всех чисел уменьшилась на \(46\), а потом второй раз так, чтобы сумма уменьшилась на \(56\).
Пример: убираем \(124\) и добавляем \(78\); убираем \(144\) и добавляем \(88\).
Таким образом, мы построили пример, когда на доске написано 9 чисел В и доказали, что меньше 9-ти не может быть, чтд.

Ответ:

а) нет

б) нет

в) 9

а) Пусть 5 человек писали только первую контрольную и получили за нее по 0 баллов, еще 5 человек писали только вторую контрольную и получили за нее по 0 баллов.
Пусть оставшиеся 18 человек писали обе контрольные, причем каждый получил за обе одинаковое количество баллов: \[\begin{array}{l|c|c} \text{Номер человека} & \text{Балл за I контр.} & \text{Балл за II контр.}\\ \hline 1&0 & -\\ \hline 2&0 & -\\ \hline 3&0 & -\\ \hline 4&0 & -\\ \hline 5&0 & -\\ \hline 6&- & 0\\ \hline 7&- & 0\\ \hline 8&- & 0\\ \hline 9&- & 0\\ \hline 10&- & 0\\ \hline 11 & a_1 & a_1\\ \hline ... & ... & ...\\ \hline 28 & a_{18} & a_{18}\\ \hline\\ \end{array}\] где “\(-\)” значит, что человек не писал контрольную.
Для того, чтобы среднее арифметическое оценок за I контрольную (или за II контрольную) было равно \(15\), нужно, чтобы \[\dfrac{a_1+\dots+a_{18}+5\cdot 0}{23}=15\quad\Rightarrow\quad a_1+\dots+a_{18}=15\cdot 23\] То есть найти такие 18 чисел, сумма которых равна \(15\cdot 23\). Возьмем 15 чисел, равных \(20\), и 3 числа, равных \(15\): \(15\cdot 20+3\cdot 15=15\cdot 23\). То есть будет такая таблица: \[\begin{array}{l|c|c} \text{Номер человека} & \text{Балл за I контр.} & \text{Балл за II контр.}\\ \hline 1&0 & -\\ \hline 2&0 & -\\ \hline 3&0 & -\\ \hline 4&0 & -\\ \hline 5&0 & -\\ \hline 6&- & 0\\ \hline 7&- & 0\\ \hline 8&- & 0\\ \hline 9&- & 0\\ \hline 10&- & 0\\ \hline 11 & 20 & 20\\ \hline ... & ... & ...\\ \hline 25 & 20 & 20\\ \hline 26 & 15 & 15\\ \hline 27 & 15 & 15\\ \hline 28 & 15 & 15\\ \hline\\ \end{array}\] Видим, что среднее арифметическое лучших оценок всех учеников равно: \[\dfrac{15\cdot 20+3\cdot 15+10\cdot 0}{28}<15\] (мы получили дробь, у которой числитель такой же, как в среднем арифметическом для каждой контрольной, а вот знаменатель уже не 23, а 28!)

б) Пусть \(M\) – сумма максимальных баллов всех студентов. Предположим, что \(S=5\), то есть \[\dfrac M{28}=5\quad\Rightarrow\quad M=140\] Заметим, что либо первую, либо вторую контрольную писало не менее 14 человек (так как если каждую контрольную писало менее 14 человек, то всего студентов менее 28). Можно считать, что не менее 14 человек писало первую контрольную. Пусть \(\Sigma\) – сумма баллов по первой контрольной, \(x\geqslant 14\) – количество человек, писавших эту контрольную. Тогда \[\dfrac{\Sigma}x=15\quad\Rightarrow\quad \Sigma=15x\geqslant 15\cdot 14>140=M\] Докажем, что \(M\geqslant \Sigma\).
Действительно, возьмем произвольного студента. Если он писал только первую контрольную, то его балл будет участвовать и в \(M\), и в \(\Sigma\). Если он писал только вторую контрольную, то его балл будет участвовать в \(M\), но не будет участвовать в \(\Sigma\). Если он писал обе контрольные, то в \(\Sigma\) будет участвовать его балл за первую контрольную, а в \(M\) – его наибольший балл (то есть либо этот же балл, либо выше). Таким образом, во-первых, слагаемых в \(M\) будет больше, чем в \(\Sigma\), часть из них будет совпадать со слагаемыми из \(\Sigma\), а часть будет больше или равна. Чтд.
Ответ: нет.

в) Пусть \(a\) – сумма баллов тех, кто писал только первую контрольную, \(b\) – кто писал только вторую контрольную, \(M\) – сумма максимальных баллов среди 10-ти, писавших обе, \(m\) – сумма минимальных баллов среди этих 10-ти.
Тогда \[\dfrac{a+b+M}{28}=S\] Заметим, что среднее арифметическое всех оценок по всем контрольным также равно \(15\) (только вот количество ВСЕХ оценок уже равно \(28+10\)). Следовательно, \[\dfrac{a+b+M+m}{28+10}=15\quad\Rightarrow\quad a+b+M=15\cdot 38-m\] Тогда \[S=\dfrac{15\cdot 38-m}{28}\] Заметим, что так как максимальная оценка за контрольную – 20 баллов, то \(M\leqslant 20\cdot 10\). Следовательно, \(m\leqslant M\leqslant 20\cdot 10\). Тогда: \[S\geqslant \dfrac{15\cdot 38-20\cdot 10}{28}=\dfrac{185}{14}\] Приведем пример для \(S=\frac{185}{14}\). Из получения оценки следует, что \(m=M=10\cdot 20\), то есть 10 студентов, писавших обе контрольные, получили по 20 баллов за каждую. Тогда \(a+b=28S-M=170\). Если взять \(a=b=85\), то количество \(x\) студентов, писавших только первую контрольную, ищется: \[\dfrac{200+85}{10+x}=15\quad\Rightarrow\quad x=9\] Тогда только вторую контрольную тоже должно писать 9 человек.
То есть мы пришли к тому, что нужно показать, что есть такие 9 натуральных чисел от \(0\) до \(20\), которые в сумме дают \(85\). Есть: \(5+10+10+10+10+10+10+10+10=85\).

Ответ:

а) пример

б) нет

в) \(\frac{185}{14}\)

а) Упорядочим числа в порядке возрастания: \(a_1, \ a_2, \ a_3, \ a_4, \ a_5\). Приведем пример. Пусть \(a_1=6\), \(a_5=17\). Тогда \(a_2+a_3+a_4=24\). Следовательно, можно взять \(a_2=7, \ a_3=8, \ a_4=9\).
Ответ: да.

б) Упорядочим числа в порядке возрастания: \(a_1, \ a_2, \ a_3, ..., \ a_{10}\). Тогда \(a_i\leqslant 3a_1\), \(i=2;3;...; 10\). Предположим, что сумма может быть равна \(94\). Тогда \[a_1+a_2+a_3+...+a_{10}=94\leqslant a_1+9\cdot 3a_1=28a_1\] откуда \(a_1\geqslant 4\).
Так как все числа натуральные и различные, то при \(a_1=4\) наибольшее возможное значение \(a_{10}\) – это \(12\). Но тогда между \(4\) и \(12\) не умещается 8 различных чисел.
\((*)\) При \(a=5\) наименьшая сумма достигается, если числа равны \[5; \ 6; \ 7; \ 8; \ 9; \ 10; \ 11; \ 12; \ 13; \ 14,\] и равна \(0,5(5+14)\cdot 10=95>94\).
Заметим, что при увеличении \(a_1\) будет увеличиваться и значение наименьшей возможной суммы, следовательно, таких чисел не существует и ответ: нет.

Приведем другое доказательство пункта б):
Так как можно сказать, что \(a_{10}=3a_1-\alpha\), где \(\alpha\) – некоторое неотрицательное целое число, то количество натуральных чисел, находящихся между \(a_{10}\) и \(a_1\), будет равно \(2a_1-1-\alpha\). Так как чисел между \(a_{10}\) и \(a_1\) должно быть 8, то \(2a_1-1-\alpha\geqslant 8\), откуда \(a_1\geqslant 4,5+0,5\alpha\). Следовательно, \(a_1\geqslant 5\).
Далее можно привести то же рассуждение \((*)\).

в) Заметим, что \(8000=2^6\cdot 5^3\). Следовательно, любое число, записанное на доске, имеет вид \(2^x\cdot 5^y\) (\(x, y\geqslant 0\) – натуральные).
Начнем пробовать привести пример для двух чисел. Такой пример удается привести: \(a_1=2^6=64\) и \(a_2=5^3=125\).
Приведя пример для двух чисел, пробуем привести пример для трех чисел: \(a_1=2^4=16\), \(a_2=2^2\cdot 5=20\), \(a_3=5^2=25\).
Попробовав привести пример для четырех чисел и безуспешно потратив на это не более 10 минут, задумываемся над тем, что, вполне возможно, примера для четырех чисел не существует. Докажем, что на доске не может быть написано 4 числа и более.
Пусть \(a_1, \ a_2, \ ..., \ a_n\), \(n\geqslant 4\).
Рассмотрим два случая.

1) Пусть какое-то \(a_i\) содержит в разложении на простые множители как минимум две пятерки, то есть делится на \(25\): \(a_i=25\cdot k\) (\(k\geqslant 1\)). Тогда оставшиеся числа (их не менее трех) \(\geqslant \frac{25}3\cdot k\geqslant 9\). Тогда произведение всех чисел \(\geqslant 9\cdot 9\cdot 9\cdot 25=18225\), что больше \(8000\). Получили противоречие, следовательно, такого числа среди написанных на доске быть не может.

Приведем другое объяснение невозможности существования такого числа.
Если такое число есть, то оно \(\geqslant 25\). Но тогда произведение всех оставшихся чисел \(\leqslant 320\). Но тогда среди оставшихся чисел есть число \(<7\), так как, если бы все они были \(\geqslant 7\), то их произведение было бы \(\geqslant 7\cdot 7\cdot 7=343\) (так как оставшихся чисел как минимум три). Но \(7\cdot 3<25\), что противоречит условию о том, что любые два числа отличаются не более чем в 3 раза.

2) Пусть нет числа, в разложении которого на простые множители есть две пятерки, то есть все числа в разложении имеют максимум одну пятерку. Рассмотрим три числа \(a_i\), \(a_j\) и \(a_m\), имеющие в разложении одну пятерку: \(a_i=5k, a_j=5l, a_m=5p\), где \(k,l,p\) – степени двойки. Упорядочим их по возрастанию: пусть \(a_i\) – наименьшее среди них, \(a_m\) – наибольшее. Тогда \(l\geqslant 2k\), а \(p\geqslant 2l\), следовательно, \(p\geqslant 4k\), что невозможно (тогда \(a_m\) более чем в 4 раза больше \(a_i\)). Чтд.

Ответ:

а) да

б) нет

в) 2 или 3

а) Предположим, что может быть написано 5 чисел. Расположим их в порядке возрастания: \(a_1; a_2; a_3; a_4; a_5\). Тогда произведение двух наименьших \(a_1\cdot a_2>40\). Пусть \(a_1=6\), \(a_2=7\) (тогда \(a_1\cdot a_2=42>40\)). Произведение двух наибольших \(a_4\cdot a_5<100\). Пусть \(a_4=9\), \(a_5=10\). Следовательно, осталось подобрать еще одно число \(a_3\), причем оно должно быть больше \(7\), но меньше \(9\). Возьмем, например, \(8\). Таким образом, мы получили 5 чисел: \[6; \ 7; \ 8; \ 9; \ 10.\]

б) Предположим, что может быть написано 6 чисел. Расположим их в порядке возрастания: \(a_1; a_2; a_3; a_4; a_5; a_6\). Тогда произведение двух наибольших \(a_5\cdot a_6<100\). Отсюда можно сделать вывод, что \(a_5\leqslant 9\) (так как если \(a_5\geqslant 10\), то \(a_6\geqslant 11\) и их произведение \(\geqslant 110\)).
Произведение двух наименьших \(a_1\cdot a_2>40\), следовательно, \(a_2\geqslant 7\) (так как если \(a_2\leqslant 6\), то \(a_1\leqslant 5\), следовательно, их произведение \(\leqslant 30\)). Таким образом, на отрезке \([7;9]\) должны быть расположены четыре натуральных числа \(a_2;a_3;a_4;a_5\), что невозможно, так как на этом отрезке только три натуральных числа.

в) Пусть на доске написаны 4 числа, расположим их также в порядке возрастания: \(a_1; a_2; a_3; a_4\). Аналогично предыдущему пункту, можно сделать вывод, что \(a_2\geqslant 7\), \(a_3\leqslant 9\). Следовательно, \(a_2\) и \(a_3\) могут принимать значения \(7,8\) или \(9\).

1. Пусть \(a_2=7, a_3=8\). Тогда \(a_1\) может быть равно только \(6\), потому что иначе произведение \(a_1\cdot a_2\) будет меньше \(40\). Максимальное значение для \(a_4\) – это \(12\). Следовательно, в этом случае максимально возможная сумма чисел \(6+7+8+12=33\).

2. Пусть \(a_2=7, a_3=9\). Аналогично \(a_1=6\). Максимальное значение для \(a_4\) – это \(11\). Следовательно, в этом случае максимально возможная сумма чисел \(6+7+9+11=33\).

3. Пусть \(a_2=8, a_3=9\). Тогда максимальное значение для \(a_1\) – это \(7\). Максимальное значение для \(a_4\) – это \(11\). Следовательно, в этом случае максимально возможная сумма чисел \(7+8+9+11=35\).

Так как мы рассмотрели все возможные случаи, то максимальная сумма чисел равна \(35\).

Ответ:

а) да
б) нет
в) 35

а) Покажем, что \(n = 763\) подходит: произведение цифр \(n\) равно \(7\cdot 6\cdot 3\), тогда отношение \(n\) к произведению его цифр равно \[\dfrac{763}{7\cdot 6\cdot 3} = \dfrac{109}{6\cdot 3} = \dfrac{109}{18}\]

б) Числа \(113\) и \(18\) взаимно просты, тогда для того, чтобы отношение \(n\) к произведению его цифр было равно \(\dfrac{113}{18}\), необходимо, чтобы \(n\) делилось на \(113\).

Таким образом, если какое-то \(n\) подходит, то оно имеет вид \(n = 113 k\), где \(k\in\{1, ..., 8\}\) (так как \(113\cdot 9 = 1017\) – уже не трёхзначное).

Перебором убеждаемся, что ни одно число из множества \(\{1, ..., 8\}\) не подходит на роль \(k\), следовательно, отношение \(n\) к произведению его цифр не может быть равно \(\dfrac{113}{18}\).

в) Такое отношение по крайней мере может быть равно \(\dfrac{631}{18}\) (при \(n = 631\)), но может ли оно быть ещё больше? Если при каком-то \(n\) оно оказалось ещё больше, необходимо, чтобы произведение цифр \(n\) и было равно \(18\).

В самом деле, произведение цифр \(n\) должно делиться на \(18\), раз уж отношение \(n\) к нему можно сократить до дроби вида \(\dfrac{m}{18}\), но если \(n < 1000\), то даже при сокращении числителя всего в \(2\) раза там останется \(n : 2 < 500\), а в предложенном выше примере в числителе стоит \(631 > 500\), то есть предложенный выше пример даёт заведомо большее отношение, чем любое допустимое отношение, для которого произведение цифр \(n\) было не \(18\).

Теперь разберёмся со случаем, когда произведение цифр \(n\) равно \(18 = 3\cdot 3\cdot 2\). Тогда наибольшее значение, которое может принимать число сотен в \(n\), равно \(3\cdot 3 = 9\), но чтобы произведение цифр было равно \(18\), нам придётся взять в качестве двух других цифр \(2\) и \(1\). При этом всякое трёхзначное число, записанное полученными цифрами, делится на \(3\) и дробь \(\dfrac{n}{18}\) оказывается сократимой.

Наибольшее значение, которое может принимать число сотен в \(n\), отличное от \(9\), равно \(3\cdot 2 = 6\), тогда нам придётся взять в качестве двух других цифр \(3\) и \(1\). Ну а наибольшее такое \(n\), собственно, и есть \(631\).

Ответ:

а) \(763\)

б) Нет

в) \(\dfrac{631}{18}\)

а) В качестве ответа подходит следующая последовательность ходов:
0) \(\{1; 2\}\),
1) \(\{2\cdot 1 + 2\cdot 2 - 1 = 5; 3\cdot 1 + 2 - 4 = 1\}\),
2) \(\{2\cdot 5 + 2\cdot 1 - 1 = 11; 3\cdot 1 + 5 - 4 = 4\}\),
3) \(\{2\cdot 11 + 2\cdot 4 - 1 = 29; 3\cdot 4 + 11 - 4 = 19\}\).

б) Грубо говоря, начиная с некоторого момента после каждого хода минимальное из чисел на доске вырастает примерно в \(4\) раза по сравнению с минимальным числом до этого хода. Тогда после \(100\) ходов минимальное значение должно в некотором смысле не слишком сильно отличаться от \(1\cdot 4^{100} = 2^{200} = 1024^{20}\), что намного больше, чем \(1000^{10} = 10^{30}\). Данное рассуждение не является строгим, но именно его формальный аналог и приведёт нас к строгому решению.

Итак, изложим аналогичное решение формально. Пусть в какой-то момент каждое из чисел \(m\) и \(n\), записанных на доске, не меньше \(4\), тогда

\[\begin{aligned} &2n + 2m - 1 > 2n\geqslant \min(2m, 2n)\,,\\ &3m + n - 4 > 2m\geqslant \min(2m, 2n)\,,\\ &3n + m - 4 > 2n\geqslant \min(2m, 2n)\,. \end{aligned}\]

Таким образом, в любом случае после следующего хода оба числа на доске будут больше, чем минимальное из \(2m\) и \(2n\) (и опять будут не меньше \(4\)).

Покажем, что спустя \(2\) хода минимальное из чисел на доске обязательно будет не меньше \(4\). После первого хода мы получим либо \(\{5; 1\}\), либо \(\{5; 3\}\). Тогда после второго хода мы можем получить только одну из пар \[\{11; 4\},\qquad\qquad \{11; 12\},\qquad\qquad \{15; 10\},\qquad\qquad \{15; 14\}\]

То есть в результате второго хода каждое из чисел на доске так или иначе не меньше \(4\), следовательно, и далее оба числа на доске будут не меньше \(4\).

Получается, что после второго хода минимальное из чисел на доске не меньше \(4\), а с каждым ходом после второго минимальное из чисел на доске вырастает более чем в \(2\) раза по сравнению с минимальным числом до этого хода. Тогда после \(100\) ходов минимальное из чисел на доске будет больше, чем \(4\cdot 2^{98} = 2^{100} = 1024^{10} > 1000^{10} = 10^{30}\), следовательно, после \(100\) ходов ни одно из двух чисел на доске не может быть равно \(10^{30}\).

в) По условию эта разность не может быть равна \(0\). При этом оба числа на доске – натуральные, следовательно, разность большего и меньшего из них не меньше \(1\).

Рассмотрим повнимательнее преобразование, которое мы делаем с числами за один ход. Если до этого хода ровно одно из чисел было чётным, то после этого хода обязательно оба числа будут нечётными. Если же до этого хода оба числа были нечётными, то после этого хода ровно одно из чисел будет нечётным.

Тогда после одного хода, начиная с \(\{1; 2\}\), на доске оба числа будут нечётными, как и после трёх ходов и вообще после любого нечётного количества ходов. Так как \(2017\) – нечётное, то через \(2017\) ходов оба числа на доске будут нечётными, следовательно, разность между большим и меньшим из них не может быть равна \(1\).

В итоге, мы доказали, что разность между большим и меньшим из чисел на доске после \(2017\) ходов не меньше \(2\).

Пусть в какой-то момент на доске оказались числа, разность между большим и меньшим из которых равна \(1\). Пусть это числа \(n\) и \(n + 1\), тогда следующим ходом можно получить числа \(4n + 1\) и \(3(n + 1) + n - 4 = 4n - 1\) (разность между которыми равна \(2\)).

Пусть в какой-то момент на доске оказались числа, разность между большим и меньшим из которых равна \(2\). Пусть это числа \(k\) и \(k + 2\), тогда следующим ходом можно получить числа \(4k + 3\) и \(3(k + 2) + k - 4 = 4k + 2\) (разность между которыми равна \(1\)).

Так как в начальный момент на доске написаны числа, разность между которыми равна \(1\), то можно последовательно выполнять ходы, такие что разность между числами на доске будет чередоваться: то она равна \(1\), то равна \(2\). Следовательно, через \(2017\) ходов разность чисел на доске действительно может быть равна \(2\).

Ответ:

а) \(\{1; 2\}\mapsto \{5; 1\} \mapsto \{11; 4\} \mapsto \{29; 19\}\)

б) Нет

в) \(2\)