РЕШУ ОЛИМП, математика: задания, ответы, решения

Поиск
?

в условии в решении в тексте к заданию в атрибутах
Скопировать ссылку на результаты поиска
Класс: 10 11 7 8 9
Атрибут

Всего: 51 1–20 | 21–40 | 41–51

Добавить в вариант

Тип 0 № 7484 Добавить в вариант

Султан собрал 300 придворных мудрецов и предложил им испытание. Имеются колпаки 25 различных цветов, заранее известных мудрецам. Султан сообщил, что на каждого из мудрецов наденут один из этих колпаков, причём если для каждого цвета написать количество надетых колпаков, то все числа будут различны. Каждый мудрец будет видеть колпаки остальных мудрецов, а свой колпак нет. Затем все мудрецы одновременно огласят предполагаемый цвет своего колпака. Могут ли мудрецы заранее договориться действовать так, чтобы гарантированно хотя бы 150 из них назвали цвет верно?

(А. В. Грибалко)

Решение.

Поскольку $0 плюс 1 плюс 2 плюс \ldots плюс 24=300,$ количества колпаков различных цветов принимают все значения от 0 до 24.

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

Договориться (заранеe!) о том, как каждому мудрецу делать этот выбор, можно различными способами. Например, можно воспользоваться обобщением леммы Холла (см. по этому поводу статью М. Шевцовой «Многократная лемма Холла в задачах про мудрецов» в Кванте №7 за 2019 год). Стратегия, приведённая ниже, основана на понятии чётности перестановки.

Пусть мудрецы заранее занумеровали цвета числами от 0 до 24. Тогда истинному распределению колпаков соответствует перестановка

$\left \beginalign номер цвета кол минус во колпаков \endalign . левая круглая скобка \beginarrayccccccccc 0 1 2 \ldots i \ldots j \ldots 24 a_0 a_1 a_2 \ldots a_i \ldots a_j \ldots a_24 \endarray правая круглая скобка \text .$

Если мудрец видит равное количество колпаков цвета i и цвета j (по k штук каждого из этих двух цветов), то ему нужно принять решение, к какому из этих двух цветов отнести свой колпак, то есть выбрать между двумя перестановками

$левая круглая скобка \beginarrayccccccccc 0 1 2 \ldots i \ldots j \ldots 24 a_0 a_1 a_2 \ldots k \ldots k плюс 1 \ldots a_24 \endarray правая круглая скобка ,$

$левая круглая скобка \beginarrayccccccccc 0 1 2 \ldots i \ldots j \ldots 24 a_0 a_1 a_2 \ldots k плюс 1 \ldots k \ldots a_24 \endarray правая круглая скобка .$

Одна из этих перестановок соответствует истинному распределению цветов, при этом указанные перестановки отличаются расположением ровно двух элементов, поэтому имеют разную чётность.

Мудрецы могут заранее договориться, чтобы ровно 150 из них сделали свой выбор в пользу чётной перестановки, а остальные 150  — в пользу нечётной перестановки.

Тогда ровно 150 мудрецов верно назовут цвет своего колпака.

Замечание. Стратегия, согласно которой мудрецы заранее договариваются так, что 150 из них выбирают цвет с большим номером (из двух, между которыми нужно сделать выбор), а остальные 150 выбирают цвет с меньшим номером, не гарантирует 150 верных ответов.

Действительно, пусть истинному распределению колпаков соответствует перестановка номер цвета кол-во колпаков

$\left \beginalign номер цвета кол минус во колпаков \endalign . левая круглая скобка \beginarraycccccccccccccc0 1 2 \ldots 15 16 17 18 19 20 21 22 23 24 0 1 2 \ldots 15 16 17 24 23 22 21 20 19 18\endarray правая круглая скобка$

и пусть мудрецы, которым достались колпаки цветов 3−17 (их ровно 150 человек), должны выбрать цвет с меньшим номером, а остальные 150 мудрецов  — с большим номером. Тогда все мудрецы, кроме мудрецов с колпаками цветов 1, 2 и 24, назовут цвет ошибочно.

Ответ: да, могут.

Решение · Помощь

Тип 21 № 7630 Добавить в вариант

В каждую клетку доски 4 × 4 Аня положила по нескольку зерен и передала доску Боре (см. рис.). Трансверсалью доски называется набор из 4 клеток, любые две из которых расположены в разных строках и разных столбцах (см. примеры). Боря за один ход может снять одинаковое количество зерен с каждой клетки какой-либо одной трансверсали. За какое минимальное число ходов Боря может снять все зерна с доски?

Доска с зернами

Пример (серые клетки

образуют трансверсаль)

Пример (серые клетки

не образуют трансверсаль)

Аналоги к заданию № 7630: 7636 Все

Решение · Помощь

Тип 21 № 7636 Добавить в вариант

Доска с зернами

Пример (серые клетки

образуют трансверсаль)

Пример (серые клетки

не образуют трансверсаль)

Аналоги к заданию № 7630: 7636 Все

Решение · Прототип задания · Помощь

Тип 21 № 7644 Добавить в вариант

4	5	6	0
5	0	4	6
5	5	3	2
1	5	2	7

В некоторые клетки доски 4 × 4 Аня положила по нескольку зерен и передала доску Боре (см. рис.). Трансверсалью доски называется набор из 4 клеток, любые две из которых расположены в разных строках и разных столбцах. Боря за один ход может снять одинаковое количество зерен с каждой клетки какой-либо одной трансверсали. За какое минимальное число ходов Боря может снять все зерна с доски?

Решение · Помощь

Тип 0 № 7915 Добавить в вариант

В каждой клетке полоски 1 × 61 стоит либо плюс, либо минус. Таня выбирает любые три клетки и меняет три знака в них на противоположные. А Саша выбирает любые три последовательных клетки и меняет три знака в них на противоположные. Изначально во всех клетках стояли минусы. Таня и Саша делают ходы по очереди, начинает Таня. Какого наибольшего количества плюсов может добиться Таня после какого-нибудь своего хода?

Решение.

Сначала покажем, что Таня после некоторого своего хода может добиться 43 плюсов. Пронумеруем клетки в полоске по порядку числами от 1 до 61. Пусть Таня своим ходом изменяет 3 минуса в клетках с номерами, не кратными 3 (если там все плюсы, то она меняет любые другие знаки). Заметим, что своим ходом Саша может поменять только 2 знака в этих клетках (ведь среди любых трёх подряд идущих клеток обязательно есть клетка с номером, кратным 3). Получаем, что своим ходом Таня увеличивает количество плюсов в этих клетках на 3 (либо же после её хода там окажутся все плюсы), а Саша уменьшает максимум на 2, поэтому после некоторого хода Тани на всех этих клетках окажутся плюсы. Следующим ходом Саша опять меняет не более двух плюсов на этих клетках, а Таня в свою очередь меняет минусы в этих клетках и ещё хотя бы в одной другой (с номером, кратным 3). Таким образом, плюсов окажется хотя бы 41 + 1  =  42. Осталось заметить, что после каждого хода любого игрока меняется чётность количества плюсов в полоске, и после хода Тани оно всегда нечётное, поэтому всего плюсов будет хотя бы 43. Теперь покажем, что Саша может играть так, чтобы после любого хода Тани было не более 43 плюсов. Рассмотрим три случая:

1)  Пусть перед ходом Саши есть три плюса подряд. В этом случае Саша просто меняет их на минусы. Количество плюсов уменьшается на 3.

2)  Пусть перед ходом Саши нет трёх плюсов подряд, но есть два плюса подряд. В этом случае Саша меняет их на минусы, а в следующей за ними клетке минус меняет на плюс. Количество плюсов уменьшается на 1.

3)  Пусть перед ходом Саши нет двух плюсов подряд. В этом случае всего плюсов не более 21. Действительно, разбив всю полоску на 20 групп по 3 последовательных клетки и ещё 1 группу из 1 клетки, получаем, что в каждой группе не более одного плюса. Саша делает любой ход, после чего количество плюсов становится не более 24.

Докажем, что Саша, придерживаясь такой стратегии, после каждого своего хода будет оставлять не более 40 плюсов. Отсюда будет следовать, что Таня не сможет добиться более 43 плюсов. Если перед ходом Саши всего не более 41 плюса, то после его хода плюсов будет не более 40 (либо он уменьшит их количество, либо их станет не более 24). Рассмотрим момент, когда перед его ходом 42 или 43 плюса (больше быть не может, т. к. до этого момента он всегда оставлял Тане не более 40). В этом случае обязательно найдётся 3 плюса подряд (иначе, если нет трёх плюсов подряд, разбив всю полоску на 20 групп по 3 последовательных клетки и ещё 1 группу из 1 клетки, получаем, что в каждой группе не более двух плюсов и ещё в отдельной клетке не более одного, поэтому всего плюсов было бы не более 20 · 2 + 1  =  41, что неверно). После смены этих последовательных плюсов на минусы количество плюсов будет не более 40.

Ответ: 40.

Решение · Помощь

Тип 0 № 8226 Добавить в вариант

Петя задумал некоторое натуральное число. За один ход он может домножить его на любое рациональное число от $дробь: числитель: 1, знаменатель: 3 конец дроби$ до 2. Докажите, что за несколько таких операций Петя сможет получить число 1001.

Решение · Помощь

Тип 0 № 8482 Добавить в вариант

Штирлиц хочет послать в Центр шифровку, представляющую собой код из 100 символов «точка» или «тире». Полученная им накануне из Центра Инструкция о конспирации гласит:

— при передаче шифровки по радио ровно 49 символов следует заменить на противоположные;

— расположение «неверных» символов возлагается на передающую сторону и с Центром не обсуждается.

Докажите, что Штирлиц может послать свою шифровку 10 раз, подбирая при каждой передаче 49 символов так, чтобы Центр, получив эти 10 шифровок, имел возможность однозначно восстановить исходный код.

Решение.

Пусть шифровки представляют собой последовательности из нулей и единиц. Ясно, что можно считать, что Штирлиц шифрует строку, состоящую из одних нулей.

Штирлиц разобьёт двоичную строку на два блока по 49 бит в каждом и оставшиеся два бита. В шифровке C₁ единицы будут стоять в первом блоке, в строка C₂  — во втором блоке. Центр, увидев эти шифровки, обнаружит, что они различаются в 98 битах, а, значит, последние два бита верное в обеих шифровках. Если на $k минус 1$ шаге Центр уже вычислил а бит в первом блоке и b бит во втором блоке, то всего ему уже известно $a плюс b плюс 2$ бита. Пусть для определенности $a меньше или равно b$ (если $a больше b,$ то первый и второй блоки меняются местами). Тогда Штирлиц передаст шифровку C_k, 6 которой единицы будут стоять на этих $a плюс b плюс 2$ позициях, а такое каких-то $47 минус a минус b$ позициях первого блока. Центр сравнит C₂ и C_k и обнаружит, что в них есть одинаковые неверные b бит, а также различающиеся $98 минус 2 b$ позиций (47 – b в первом блоке и 49 – b во втором). Но такое возможно только, если на оставшихся позициях переданы верные биты. Следовательно, Центр теперь в дополнении к известным ранее а битам знает еще b + 2 бита из первого блока и всего ему известно $a плюс b плюс 2$ бита из первого блока. Выпишем далее пары чисел a u, которые будут возникать после получения Центром очередной шифровки. После второй шифровки $a=b=0,$ после третей $a=2$ и $b=0,$ после четвертой $a=2$ и $b=4,$ после пятой $a=8$ и $b=4,$ после шестой $a=8$ и $b=14,$ после седьмой $a=24$ и $b=14,$ наконец, после восьмой шифровки $a=24$ и $b=40.$ Следовательно, в этот момент Центр уже знает 66 бит из послания Штирлица. Тогда в девятой шифровке Штирлиц передаст 49 единиц в каких-то 49 позициях из уже известных Центру и тогда центр поймет, что остальные позиции правильные и узнает оставшуюся часть сообщения. Десятая шифровка Штирлицу даже и не пригодилась.

Решение · Помощь

Тип 0 № 8521 Добавить в вариант

Ваня, долго умножая, вычислил 2020! В числе, полученном Ваней, Ксюша слева направо расставила знаки действий: между первой и второй цифрами знак «−», между второй и третьей цифрами знак «+», между третьей и четвертой  — «−», и так далее, до конца. Затем Ваня вычислил результат этих действий. В полученном Ваней числе Ксюша опять расставила между цифрами знаки «−» и «+» по такому же правилу. После этого Ваня опять вычислил результат, и так далее. После некоторого количества таких операций было получено однозначное число. Какое?

Решение · Помощь

Тип 21 № 9322 Добавить в вариант

Дана клетчатая доска $100 \times 100.$ Каждая клетка доски покрашена в один из двух цветов: белый или чёрный. Назовём раскраску доски уравновешенной, если в каждой строке и в каждом столбце 50 белых и 50 чёрных клеток. За одну операцию разрешается выбрать две строки и дна столбца так, чтобы из 4 клеток на их пересечении две были чёрными, а две  — белыми, и перекрасить каждую из этих 4 клеток в противоположный цвет. Докажите, что из любой уравновешенной раскраски можно получить любую другую уравновешенную раскраску с помощью указанных операций.

Решение.

Докажем, что из любой уравновешенной доски можно получить доску, раскрашенную в шахматную раскраску, причём на каждом шаге доска будет оставаться уравновешенной. Из этого будет следовать, что из любой уравновешенной доски можно получить любую другую, так как операция обратима.

Будем получать шахматную раскраску следующим образом. Разобьём столбцы на пары подряд идущих. Выберем самую левую пару столбцов и в этой паре столбцов по очереди будем приводить строки (состоящие из двух клеток) к шахматной раскраске. После того как закончим с первой парой столбцов, перейдём ко второй и так далее.

Объясним, как делать следующий шаг внутри одной пары столбцов X и Y. Пусть в следующей строке A сейчас находятся чёрная и белая клетка, но в неправильном порядке. Например, слева стоит чёрная клетка, а справа белая, а должно быть наоборот. Заметим, что во всех строках выше A в первом столбце суммарно чёрных клеток не меньше, чем во втором, так как они уже покрашены шахматным образом. Значит, в какой-то строке B ниже A должна быть ситуация, когда в левом столбце чёрных клеток меньше, чем в правом, то есть должна быть строка белая-чёрная (это следует из того, что суммарно в первом столбце столько же чёрных клеток, сколько и во втором). Произведём операцию со строками A и B и текущими столбцами (см. рис. 1).

Рис. 1

Рис. 2

Пусть теперь у нас в строке A стоят две одинаковые клетки, например чёрные. Тогда в какой-то строке B должны оказаться две белые клетки (иначе суммарно чёрных клеток в этих двух столбцах будет слишком много). Понятно, что эта строка расположена ниже текущей, т. к. выше неё все строки разноцветные. Теперь заметим, что если посмотреть на эту пару строк во всей таблице, то должен быть столбец Z правее X и Y, в котором в первой строке белая клетка, а во второй  — чёрная. Тут мы пользуемся тем, что левее наших столбцов в этих строках поровну чёрных и белых клеток. Теперь осталось лишь выбрать один из столбцов X или Y (в котором неправильный цвет в строке A) и столбец Z, а также строки A и B и произвести операцию с ними (см. рис. 2).

Легко видеть, что на каждом шаге уравновешенность доски сохраняется. А так как мы всегда можем сделать шаг в нашем алгоритме, то в конце получится шахматная раскраска.

Решение · Критерии · Помощь

Тип 21 № 9386 Добавить в вариант

Даны две последовательности из букв А и Б, в каждой из которых по 100 букв. За одну операцию разрешается вставить в какое-то место последовательности (возможно, в начало или в конец) одну или несколько одинаковых букв или убрать из последовательности одну или несколько подряд идущих одинаковых букв. Докажите, что из первой последовательности можно получить вторую не более чем за 100 операций.

(В. Новиков)

Решение.

Сначала решим аналогичную задачу для последовательностей из двух букв, а именно докажем, что из одной последовательности можно получить другую не более чем за 2 операции.

Если одна из последовательностей  — это АА, а другая  — ББ, то уберём все буквы первой последовательности, а затем добавим буквы второй последовательности. В противном случае в последовательностях есть одинаковые буквы (возможно, стоящие на разных местах). Оставим в первой последовательности эту букву, а другую уберём. Затем добавим в нужное место букву, которой недостаёт для второй последовательности.

Вернёмся к первоначальной задаче. Разобьём каждую последовательность на 50 пар подряд идущих букв. За две операции каждую пару первой последовательности можно переделать в соответствующую пару второй последовательности.

Приведём другое решение.

Разобьём каждую из последовательностей на блоки подряд идущих одинаковых букв. В обеих последовательностях получится не более 50 блоков из букв А и не более 50 блоков из букв Б. Если получилось ровно по 50 блоков, то в обеих последовательностях буквы чередуются. Тогда либо последовательности совпадают, либо из первой можно получить вторую, отбросив первую букву и приписав такую же букву в конец.

Пусть в какой-то из последовательностей блоков из какой-то буквы не более 49. Понятно, что если из второй последовательности с помощью операций можно получить первую, то, проделав операции в обратном порядке, получим из первой последовательности вторую. Поэтому, не умаляя общности, можно считать, что в первой последовательности не более 49 блоков из букв А. Проделаем с первой последовательностью следующие операции.

1.  Уберём все буквы А. На это потребуется не более 49 операций.

2.  При необходимости изменим количество букв Б так, чтобы их количество совпало с количеством букв Б во второй последовательности. На это потребуется не более 1 операции.

3.  Добавим в нужные места блоки из букв А, равные по длине соответствующим блокам букв А из второй последовательности. На это потребуется не более 50 операций.

В итоге вторая последовательность получена не более чем за 100 операций.

Приведём еще одно решение.

Докажем, что на самом деле можно справиться за не более чем 51 операцию. Как и в предыдущем решении, будем пользоваться тем, что если из второй последовательности можно получить первую, то можно и наоборот.

Пусть буква А встречается в первой и второй последовательностях соответственно a₁ и a₂ раз, а буква Б  — соответственно $b_1 = 100 минус a_1$ и $b_2 = 100 минус a_2$ раз. Без ограничения общности будем считать, во-первых, что $a_1 плюс a_2 меньше или равно 100 меньше или равно b_1 плюс b_2$ (иначе можно поменять местами буквы), а во-вторых, что $a_1 больше или равно a_2$ (иначе можно поменять местами последовательности). Процесс перевода первой последовательности во вторую выполним в два этапа:

1)  удалим из первой последовательности $a_1 минус a_2$ букв А, чтобы их стало столько же, сколько во второй последовательности;

2)  в полученной последовательности изменим количества букв Б, стоящих между буквами А, чтобы она совпала со второй.

Второй этап можно выполнить за не более чем $a_2 плюс 1$ операцию. Действительно, на обе последовательности (полученную после первого этапа и требуемую) можно смотреть как на последовательности из $a_2$ букв А, в промежутках между которыми вставлены ноль или более букв Б; всего промежутков ровно $a_2 плюс 1$ (позиции до и после крайних букв А тоже считаются «промежутками»). Ясно, что мы можем за не более чем одну операцию привести количество букв Б, стоящих в каком-то одном промежутке, к требуемому. Значит, за не более чем $a_2 плюс 1$ операцию мы можем «исправить» все количества букв Б на те, что должны быть в требуемой последовательности.

Осталось доказать, что первый этап можно выполнить за $50 минус a_2$ операций.

Отметим, что $50 минус a_2 больше или равно 0,$ так как

$a_2 = дробь: числитель: 1, знаменатель: 2 конец дроби левая круглая скобка a_2 плюс a_2 правая круглая скобка меньше или равно дробь: числитель: 1, знаменатель: 2 конец дроби левая круглая скобка a_1 плюс a_2 правая круглая скобка меньше или равно 50.$

При этом если a₂  =  50, то из $a_2 меньше или равно a_1$ и $a_1 плюс a_2 меньше или равно 100$ имеем и a₁  =  50. В этом случае первая стадия процесса тривиальна  — ничего удалять не нужно. Далее разбираем случай $50 минус a_2 больше 0.$

Буквы Б в первой последовательности разделяют буквы А на $b_1 плюс 1$ непрерывных блоков из нуля или более букв (считаем, что блок из нуля букв А образуется, если две буквы Б стоят рядом, либо если буква Б стоит с краю последовательности). Достаточно доказать, что можно выбрать не более чем $50 минус a_2$ блоков так, чтобы суммарно в них было не менее $a_1 минус a_2$ букв А; в этом случае мы за не более чем $50 минус a_2$ операций можем произвольно уменьшить или удалить эти блоки и добиться требуемого количества букв А. Отметим, что если $50 минус a_2 больше или равно b_1 плюс 1,$ то можно просто выбрать все блоки, и в них окажется $a_1 больше или равно a_1 минус a_2$ букв А; далее разбираем случай $50 минус a_2 меньше b_1 плюс 1.$

Предположим противное: даже если выбрать $50 минус a_2$ наибольших (по количеству букв) блоков, в них суммарно окажется не более $a_1 минус a_2 минус 1$ букв А. Заметим, что хотя бы один из выбранных блоков содержит не более одной буквы А по принципу Дирихле, так как

$a_1 минус a_2 минус 1 меньше 2 левая круглая скобка 50 минус a_2 правая круглая скобка \Leftarrow a_1 плюс a_2 меньше 101 \Leftarrow a_1 плюс a_2 меньше или равно 100.$

Так как мы выбрали наибольшие блоки, то остальные $левая круглая скобка b_1 плюс 1 правая круглая скобка минус левая круглая скобка 50 минус a_2 правая круглая скобка$ блоков тоже содержат не более чем по одной букве А; суммарно в первой последовательности оказывается не более

$левая круглая скобка a_1 минус a_2 минус 1 правая круглая скобка плюс левая круглая скобка левая круглая скобка b_1 плюс 1 правая круглая скобка минус левая круглая скобка 50 минус a_2 правая круглая скобка правая круглая скобка = a_1 плюс b_1 минус 50 = 50$

букв А. Но мы знаем, что их a₁, откуда $a_1 меньше или равно 50.$ В этом случае $a_1 минус a_2 минус 1 меньше 50 минус a_2;$ снова применяя принцип Дирихле, получаем, что один из выбранных блоков содержит ноль букв А. Тогда все остальные блоки тоже содержат ноль букв А. Следовательно, общее количество букв А в первой последовательности не превосходит $a_1 минус a_2 минус 1;$ но мы знаем, что их ровно a₁, противоречие.

Замечание.

Можно понять, что, например, последовательность ААА ... АА нельзя перевести в АБАБ ... АБ менее чем за 51 операцию. Действительно, в первой последовательности ноль блоков из букв Б, а во второй их 50. При это каждая операция увеличивает количество блоков не более чем на 1. А ещё должна быть хотя бы одна операция, уменышающая количество букв А, и такая операция не может увеличивать количество блоков из букв Б.

Решение · Критерии · Помощь

Тип 21 № 9394 Добавить в вариант

На экране суперкомпьютера напечатано число 11 ... 1 (900 единиц). Каждую секунду суперкомпьютер заменяет его по следующему правилу. Число записывается в виде $\overlineA B,$ где B состоит из двух его последних цифр, и заменяется на $2 умножить на A плюс 8 умножить на B$ (если B начинается на нуль, то он при вычислении опускается). Например, 305 заменяется на $2 умножить на 3 плюс 8 умножить на 5 = 46.$ Если на экране остаётся число, меньшее 100, то процесс останавливается. Правда ли, что он остановится?

(2023-70, М. Евдокимов)

Решение.

Условие можно перефразировать как то, что если число на экране имеет вид $100 A плюс B,$ где $0 меньше или равно B меньше 100$ то оно заменяется на число $2 A плюс 8 B.$ Поэтому оно уменьшается на

$левая круглая скобка 100 A плюс B правая круглая скобка минус левая круглая скобка 2 A плюс 8 B правая круглая скобка = 98 A минус 7 B = 7 левая круглая скобка 14 A минус B правая круглая скобка .$

Эта величина обязательно положительна при $A больше 7,$ так что все числа, начиная с 800, обязательно уменьшаются. Естественный вопрос  — а может ли что-нибудь помешать числу уменьшиться дальше? Или можем ли мы выяснить, до какого числа, меньшего 800, «досчитает» суперкомпьютер? Во-первых, из записи выше видно, что разница между числом и его образом обязательно делится на 7. Так что остаток от деления на 7 сохраняется. А поскольку на 7 делится $1001 = 7 умножить на 11 умножить на 13,$ то делится и $111111=111 умножить на 1001,$ и, значит, и число из $900 = 6 умножить на 150$ единиц. Значит, все числа, которые будут получаться, тоже делятся на 7  — и на 14, потому что $2A плюс 8B$ это всегда число чётное.

Но этого мало. А не сохраняется ли (или не изменяется ли предсказуемым образом) делимость на ещё какое-нибудь простое число p?

Если на p делится $100 A плюс B,$ то делится и $8 левая круглая скобка 100 A плюс B правая круглая скобка = 800 A плюс 8 B$ (а если не делится, то остаток умножается ровно на 8). Разница между этим числом и $2A плюс 8B$ составляет $левая круглая скобка 800 минус 2 правая круглая скобка A = 798 A,$ так что если p  — это делитель 798, то остаток от деления на p умножится на 8. Имеем $798 = 7 умножить на 114 = 7 умножить на 2 умножить на 3 умножить на 19;$ это даёт нам два новых простых числа, 3 и 19.

Посмотрим, какой остаток даёт исходное число при делении на 3 и на 19. Оно делится на 3, потому что 900 делится на 3. Наконец, то, что $10 в степени левая круглая скобка 18 правая круглая скобка минус 1$ делится на 19  — следует из Малой Теоремы Ферма, но можно проверить и просто «делением в столбик». А значит, делится на 19 и число из $900 = 18 умножить на 50$ единиц. Поэтому все итерации, начиная со второй, будут делится на 798. И, значит, итоговое (ненулевое!) число никогда не станет меньше 100.

Ответ: нет, не остановится.

Комментарий.

Если бы нам не «повезло» с выбором исходного числа  — можно было бы «отследить» изменение остатков от деления на 3, 7 и 19 (поскольку они на каждом шаге умножаются на 8), и понять, есть ли среди получающихся вариантов числа, меньшие 100.

Решение · Критерии · Помощь

Всего: 51 1–20 | 21–40 | 41–51