19.01 Задачи №19 из ЕГЭ прошлых лет

а) Пусть пара получена из пары Тогда имеем:

Поэтому пару можно получить из пары за одну операцию.

б) Пусть пара получена из некоторой пары Тогда

В случае, если предполагается, что эта пара может получиться из некоторой пары целых чисел то верна следующая система:

Тогда пара получена следующим образом:

При этом пара получена следующим образом:

в) Пусть пара, расстояние до которой нужно минимизировать, получена из пары Тогда нужно найти наименьшее из расстояний между парами и которые будут иметь вид:

Заметим, что числа и имеют одну четность:

Значит, числа и имеют разную чётность, поэтому расстояние между и нечётно, то есть не меньше 1.

Предположим, что минимальное расстояние равно 1, тогда

• Решим первую систему:

  

  Из первого уравнения получаем, что

  

  Тогда

  

  Заметим, что делится на 5, а 1 — нет. Значит, первая система уравнений не имеет решений.

• Решим вторую систему:

  

  Из второго уравнения получаем, что

  

  Тогда

  

  Заметим, что делится на 5, а 1 — нет. Значит, вторая система уравнений тоже не имеет решений.

Таким образом, расстояние 1 между парами и недостижимо.

Для следующего нечётного числа в качестве расстояния есть пример. Если то Тогда расстояние между парой и парой полученной из пары будет равно

а) Посмотрим сколько всего рублей у нас есть:

Тогда 154 рубля набрать очень просто — нужно взять все монеты, кроме одной монеты в 2 рубля.

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

Возьмём 27 монеток по 2 рубля и 20 монеток по 5 рублей. Тогда сумма взятых монет равна

б) Так как нам нужна нечётная сумма монет, то мы можем взять только нечётное число монеток по 5 рублей, то есть не более 19 таких монеток. Тогда оценим максимальную сумму, которую можно взять:

Значит, 155 рублей набрать нельзя.

в) Сумма монеток в изначальном наборе равна

Значит, чтобы получить 160 рублей, необходимо добавить хотя бы 4 монетки по 1 рублю.

Покажем, что 4 монеток по 1 рублю достаточно. Сначала научимся собирать любую сумму от 1 до 60 рублей монетками по 1 и 2 рубля:

• Если нужно набрать четное число до 56 включительно, то можно получить его монетками по 2 рубля.
• Если нужно набрать 58, то его можно получить из 28 монеток по 2 рубля и двух монеток по 1 рублю.
• Если нужно набрать 60, то его можно получить из 28 монеток по 2 рубля и четырех монеток по 1 рублю.
• Если нужно набрать нечетное число, то сначала возьмём монетку в 1 рубль. Тогда останется добрать четную сумму от 0 до 58 включительно. Её мы умеем собирать, используя только монетки по 2 рубля и не более 2 монеток по 1 рублю.

Теперь научимся собирать любое число от 61 до 160.

Для любого числа из этого промежутка будем сначала брать монетки по 5 рублей, пока не останется необходимая сумма в пределах от 0 до 60 рублей, которую мы умеем собирать из монеток по 1 и 2 рубля.

Заметим, что монетами по 5 рублей мы можем собрать любое кратное 5 число от 5 до Тогда любую сумму от 61 до 160 можно уменьшить хотя бы до 60 рублей, так как

Таким образом, мы сможем собрать любую целую сумму от 1 до 160 рублей включительно.

а) Возьмём 27 монеток по 2 рубля и 20 монеток по 5 рублей. Тогда сумма взятых монет равна

б) Так как нам нужна нечётная сумма монет, то мы можем взять только нечётное число монеток по 5 рублей, то есть не более 19 таких монеток. Тогда оценим максимальную сумму, которую можно взять:

Значит, 155 рублей набрать нельзя.

в) Сумма монеток в изначальном наборе равна

Значит, чтобы получить 160 рублей, необходимо добавить хотя бы 4 монетки по 1 рублю.

Покажем, что 4 монеток по 1 рублю достаточно. Сначала научимся собирать любую сумму от 1 до 60 рублей монетками по 1 и 2 рубля:

• Если нужно набрать четное число до 56 включительно, то можно получить его монетками по 2 рубля.
• Если нужно набрать 58, то его можно получить из 28 монеток по 2 рубля и двух монеток по 1 рублю.
• Если нужно набрать 60, то его можно получить из 28 монеток по 2 рубля и четырех монеток по 1 рублю.
• Если нужно набрать нечетное число, то сначала возьмём монетку в 1 рубль. Тогда останется добрать четную сумму от 0 до 58 включительно. Её мы умеем собирать, используя только монетки по 2 рубля и не более 2 монеток по 1 рублю.

Теперь научимся собирать любое число от 61 до 160.

Для любого числа из этого промежутка будем сначала брать монетки по 5 рублей, пока не останется необходимая сумма в пределах от 0 до 60 рублей, которую мы умеем собирать из монеток по 1 и 2 рубля.

Заметим, что монетами по 5 рублей мы можем собрать любое кратное 5 число от 5 до Тогда любую сумму от 61 до 160 можно уменьшить хотя бы до 60 рублей, так как

Таким образом, мы сможем собрать любую целую сумму от 1 до 160 рублей включительно.

а) Возьмем набор из пяти гирь по 1, 2, 4, 8 и 16 кг. Тогда

Значит, существует набор из пяти гирь, которым можно отвесить любое целое число килограммов от 1 до 25.

б) Заметим, что существует ровно наборов из этих четырех гирь, включая пустой, потому что для каждой из 4 гирь есть два варианта: мы либо берем ее в набор, либо нет. Тогда всего существует не более 16 различных весов, которые можно отвесить этими гирями. Но от 1 до 25 есть 25 различных весов, поэтому набором из четырех гирь отвесить любое целое число килограммов от 1 до 25 нельзя.

в) Заметим, что существует ровно наборов из этих пяти гирь, включая пустой, потому что для каждой из 5 гирь есть два варианта: мы либо берем ее в набор, либо нет. Тогда всего существует не более 32 различных весов, которые можно отвесить этими гирями. Но пустой набор весит 0 кг, значит, положительных различных весов не более 31.

Приведем пример на 31 (для набора из пяти гирь по 1, 2, 4, 8 и 16 кг):

а) По условию оба числа должны делиться на 45, значит, каждое число делится и на 5, и на 9, так как 5 и 9 взаимнопросты.

По признаку делимости на 5, она числа должны заканчиваться на 0 или 5. Так как в наборе цифр у нас один 0 и одна 5, можно сказать, что первое число оканчивается на 5, а второе — на 0.

Остались цифры 1, 2, 3, 7, 9. По признаку делимости на 9, сумма цифр каждого из чисел должна делиться на 9. Тогда посмотрим какие цифры могут быть в одном числе с 0. Заметим, что их две или три. Сумму 9 двумя цифрами можно набрать так:

Пусть первое число состоит из цифр 2, 7 и 0. Тогда второе состоит из цифр 1, 3, 9 и 5, то есть сумма его цифр равна 18. Тогда как бы мы не расположили цифры в числах, они оба будут делится на 45. Значит, осталось подобрать правильный порядок цифр в числах.

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

Например, если трёхзначным будет число 270, а четырёхзначным — число 1935, то их сумма будет равна

Заметим, что а

б) Если оба числа кратны 45, то и их сумма будет кратна 45. В частности, она также будет кратна 9. Но число 3435 не делится на 9:

Значит, эта сумма не может быть равна 3435.

в) По признаку делимости на 5, если число делится на 5, то оно оканчивается на 0 или на 5. Оба числа из условия должны делиться на 5, так как они делятся на 45. Тогда в одном из них на конце стоит 0, а в другом — 5.

По признаку делимости на 9, если число делится на 9, то и его сумма цифр делится на 9. Сумма всех цифр равна

Тогда у одного числа сумма цифр будет равна 18, а у другого — 9, потому что обе эти суммы должны быть больше 0.

Заметим, что если в числе есть 9, то в нем еще есть хотя бы одна ненулевая цифра, то есть сумма его цифр больше 9, а значит равна 18.

Если цифра 9 входит в трёхзначное число, то вторая цифра (не по счёту) у него либо 0, либо 5, но в таком случае третья должна быть либо 9, либо 4. Таких цифр нет, поэтому 9 содержится в четырёхзначном числе.

Тогда есть два варианта: либо в четырёхзначном числе есть 9 и 0, либо — 9 и 5.

1)

Если есть 9 и 0, то сумму 18 можно набрать только с цифрами 7 и 2. Тогда четырёхзначное число состоит из цифр 9, 7, 2, 0 и наибольшее число, которое из них можно составить, чтобы оно делилось на 45, равно 9720.

Тогда трёхзначное число состоит из цифр 5, 3, 1 и наибольшее число, которое из них можно составить, чтобы оно делилось на 45, равно 315.

Тогда сумма этих чисел равна

2)

Если есть 9 и 5, то сумму 18 можно набрать только с цифрами 3 и 1. Тогда четырёхзначное число состоит из цифр 9, 5, 3, 1 и наибольшее число, которое из них можно составить, чтобы оно делилось на 45, равно 9315.

Тогда трёхзначное число состоит из цифр 7, 2, 0 и наибольшее число, которое из них можно составить, чтобы оно делилось на 45, равно 720.

Тогда сумма этих чисел равна

Значит, максимально возможная сумма чисел равна 10035.

Пусть исходные чисел равны …, Тогда их сумму можно вычислить так:

Меняем в их записи первую и вторую цифру местами, тогда сумма новых чисел равна

Пусть

а) Пусть сумма после операции увеличилась в 4 раза, тогда

Вычтем из второго уравнения первое:

Из этих данных уже достаточно просто можно получить пример.

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

Пусть всего 16 чисел, в них Пусть

Тогда

Таким образом,

Итого изначально на доске написали 8 чисел 16 и 8 чисел 17.

б) Аналогично пункту а) составим систему и решим её:

Полученная система не имеет целых решений, так как 2112 не делится на 99, поэтому условие пункта б) невозможно.

в) Пусть сумма увеличилась в раз. Тогда

Заметим, что каждое из написанных чисел увеличилось не более чем в раза, значит,

Преобразуем второе уравнение:

Тогда оценим снизу:

Так как — целое, то

Заметим при этом, что

Приведем пример изначальных чисел, при которых сумма увеличилась в раза, то есть стала равна

Мы выяснили, что Тогда пусть изначально на доске было 14 чисел, при этом

Тогда имеем:

Если взять то действительно

Значит, если изначально на доске были написаны два числа 18 и двенадцать чисел 19, то после операции из условия сумма чисел на доске изменилась с 264 на 1254.

Пусть исходные чисел равны …, Тогда их сумму можно вычислить так:

Меняем в их записи первую и вторую цифру местами, тогда сумма новых чисел равна

Пусть

а) Пусть сумма после операции увеличилась в 4 раза, тогда

Вычтем из второго уравнения первое:

Из этих данных уже достаточно просто можно получить пример.

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

Пусть всего 20 чисел, в них Пусть

Тогда

Таким образом,

Итого изначально на доске написали 10 чисел 16 и 10 чисел 17.

б) Аналогично пункту а) составим систему и решим её:

Полученная система не имеет целых решений, так как 2310 не делится на 99, поэтому условие пункта б) невозможно.

в) Пусть сумма увеличилась в раз. Тогда

Заметим, что каждое из написанных чисел увеличилось не более чем в раза, значит,

Преобразуем второе уравнение:

Тогда оценим снизу:

Так как — целое, то

Заметим при этом, что

Приведем пример изначальных чисел, при которых сумма увеличилась в раза, то есть стала равна

Мы выяснили, что Тогда пусть изначально на доске было 18 чисел, при этом

Тогда

Если взять то действительно

Значит, если изначально на доске были написаны двенадцать чисел 18 и шесть чисел 19, то после операции из условия сумма чисел на доске изменилась с 330 на 1518.

Пусть исходные чисел равны …, Тогда их сумму можно вычислить так:

Меняем в их записи первую и вторую цифру местами, тогда сумма новых чисел равна

Пусть

а) Пусть сумма после операции увеличилась в 3 раза, тогда

Вычтем из второго уравнения первое:

Из этих данных уже достаточно просто можно получить пример.

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

Пусть всего было 168 чисел, в них Пусть

Тогда

Таким образом,

Итого изначально на доске написали 162 числа 14 и 6 чисел 18.

б) Аналогично пункту а) составим систему и решим её:

Тогда , Отсюда получаем, что чисел не более 96, так как иначе Следовательно, . То есть полученные значения и недостижимы.

в) Пусть сумма увеличилась в раз. Тогда

Заметим, что каждое из написанных чисел увеличилось не более чем в раза, значит,

Преобразуем второе уравнение:

Тогда оценим снизу:

Так как — целое, то

Заметим при этом, что

Приведем пример изначальных чисел, при которых сумма увеличилась в раза, то есть стала равна

Мы выяснили, что Тогда пусть изначально на доске было 126 чисел, при этом

Тогда

Если взять то действительно

Значит, если изначально на доске было написано 123 числа 19 и 3 числа 13, то после операции из условия сумма чисел на доске изменилась с 2376 на 11286.

Пусть исходные чисел равны …, Тогда их сумму можно вычислить так:

Меняем в их записи первую и вторую цифру местами, тогда сумма новых чисел равна

Пусть

а) Пусть сумма после операции уменьшилась в 3 раза, тогда

Вычтем из второго уравнения первое:

Из этих данных уже достаточно просто можно получить пример.

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

Пусть всего было 42 числа, в них Пусть Тогда

Таким образом,

Итого изначально на доске написали 33 числа 51 и 9 чисел 11.

б) Аналогично пункту а) составим систему и решим её:

Вычтем из второго уравнения первое:

Данная система не имеет целых решений, поскольку 1944 не делится нацело на 11. Тогда требуемое условие пункта б) невозможно.

в) Пусть

Заметим, что каждое из написанных чисел уменьшилось не более чем в раза, значит,

Тогда оценим снизу:

Так как — целое, то

Заметим при этом, что

Тогда из второго уравнения системы:

Так как — целое число, то Тогда

Следовательно,

Приведем пример изначальных чисел, при которых сумма уменьшилась в 4,5 раза. Пусть изначально на доске было 22 числа, при этом

Тогда

Значит,

Значит, если изначально на доске было написано 22 числа 81, то после операции из условия сумма чисел на доске изменилась с 1782 на 396.

а) Пусть выбрали числа 1, 3, 5, 7, 9, 11, 13, 15, 19. Тогда и

Значит,

б) Пусть — сумма первых четырех по величине выбранных чисел, а — сумма последних четырех. Тогда

Значит,

Заметим, что — сумма восьми нечетных чисел, поэтому число — четно. Значит, число тоже четно. Поэтому

в) Оценим число Если — пятое по величине число, то первые четыре числа не более и Тогда

Значит,

При этом то есть Следовательно,

Оценим число Заметим, что

Тогда

Таким образом,

Это значение достигается, если выбрали числа 1, 3, 5, 7, 9, 41, 43, 45, 47:

Пусть исходные чисел равны …, Тогда их сумму можно вычислить так:

Меняем в их записи первую и вторую цифру местами, тогда сумма новых чисел равна

Пусть

а) Пусть сумма после операции уменьшилась в 3 раза, тогда

Вычтем из второго уравнения первое:

Из этих данных уже достаточно просто можно получить пример.

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

Пусть всего было 56 чисел, в них Пусть Тогда

Таким образом,

Итого изначально на доске написали 54 числа 41 и 2 числа 81.

б) Аналогично пункту а) составим систему и решим её:

Вычтем из второго уравнения первое:

Такая ситуация невозможна, поскольку так как , то чисел не более 16 и

в) Пусть

Заметим, что каждое из написанных чисел уменьшилось не более чем в раза, значит,

Тогда оценим сверху:

Так как — целое, то

Заметим при этом, что

Тогда из первого уравнения системы при получаем

Приведем пример чисел, при которых сумма уменьшилась в 4 раза. Пусть изначально было 36 чисел.

Тогда

Значит,

Значит, если изначально на доске было написано 27 чисел 61 и 9 чисел 81, то после операции из условия сумма чисел на доске изменилась с 2376 на 594.

а) Пусть за этого футболиста проголосовало человек. Тогда известно, что

Таким образом, после голоса Васи у футболиста будет 5 голосов из 14, то есть

голосов, дающих рейтинг 36.

б) Да, приведём пример. Пусть всего было 200 участников, из которых 199 проголосовали за первого футболиста и 1 проголосовал за второго футболиста. Тогда у первого футболиста процент голосов равен значит, рейтинг равен 100. У второго же футболиста процент голосов равен а значит, рейтинг равен 1. Таким образом, их суммарный рейтинг составит

в) Обозначим количество участников, проголосовавших за данного футболиста до голоса Васи, за а общее количество посетителей сайта до участия Васи за Тогда известно, что

Заметим, что

Тогда имеем:

Это означает, что

Следовательно, Подставим это во второе неравенство системы:

Таким образом, получаем, что наибольшее число отданных голосов, включая Васин, не больше

Приведём пример на 82 голоса. Пусть изначально за футболиста проголосовало 6 посетителей сайта из 81 общего голоса, а потом за него же проголосовал Вася.

Тогда у данного футболиста был процент голосов, равный

При этом процент голосов стал равен

Это соответствует рейтингу 7 до голоса Васи и рейтингу 9 после его голоса.

а) Да, может. Например, если то получаем равенство:

Или, например, если то получаем равенство:

б) Заметим, что если то первая цифра числа равна 4. Также заметим, что вторая цифра числа не меньше 4. Таким образом, и и не меньше 40. Значит,

Тогда указанное равенство не может быть верным.

в) Сначала приведем пример: тогда

Так как есть пример на 810, то поэтому можем считать, что и и — двузначные числа.

Пусть Тогда заметим, что если оба мальчика зачеркнули или то Такое нам не подходит. Значит, один из мальчиков вычеркнул первую цифру, пусть это был Серёжа.

Если то Тогда

Тогда значит,

Оценим

Тогда если Коля не вычеркнул первую цифру, то

Значит, Тогда может равняться только 0. Получили наш пример.

Пусть оба мальчика вычеркнули первую цифру. Тогда Значит, Если то Нам надо найти Тогда так как Значит, Но тогда что невозможно, так как 841 не оканчивается на 29.

Таким образом, 810 — наибольшее возможное

а) Заметим, что при каждом действии сумма чисел увеличивается ровно на 1. Действительно:

• Если было и стало то сумма стала

  

• Если было и стало то сумма стала

  

Значит, за 20 ходов сумма увеличится на 20, то есть будет равна

Так как числа всегда остаются натуральными, то при такой сумме ни одно из чисел не может равняться 50.

б) Как было показано в пункте а), сумма чисел увеличивается на 1 после каждого хода. Начальная сумма чисел равна 18. Тогда понадобится ровно хода для достижения искомой суммы, которую можно получить путём проведения следующего алгоритма 291 раз:

в) Рассмотрим разность вида «второе число — первое число». Изначально она равна Далее возможны два варианта.

Первый вариант:

Второй вариант:

Далее, при делении на 3 имеют одинаковый остаток числа

То есть разность второго и первого чисел (именно в этом порядке) всегда даёт один и тот же остаток при делении на 3. Изначально эта разность равна и даёт остаток 1 при делении на 3.

Ответом будет 81 ход, когда из чисел (7, 11) сделаем пару чисел (49, 50) следующим образом:

Предположим, что ходов было хотя бы 82. Тогда сумма чисел равна хотя бы 100. С учётом требуемого условия это возможно, только если оба числа равны 50 и ходов было 82. Однако это невозможно, поскольку в таком случае разность чисел не дает остаток 1 при делении на 3. Противоречие.

а) Да, существуют, например, сумма для чисел 992 и 555 равна

б) Найдем наибольшую возможную сумму для пятизначных чисел. Для этого нужно взять числа 99999 и 99999. Тогда

Значит, хотя бы одна цифра чисел и меньше 9. Тогда сумма не больше

Таким образом, не существуют такие пятизначные числа и для которых

в) Покажем, как можно получить числа от 1 до 9 в виде суммы двузначных чисел:

Теперь покажем, как можно получить числа от 10 до 18 в виде суммы двузначных чисел:

Покажем, как можно получить числа от до в виде суммы двузначных чисел, где

Таким образом, мы показали, как получить все числа от 1 до где то есть до 90, двузначными числами. Тогда четырехзначными числами мы тоже можем получить числа от 1 до 90, просто приписав два нуля в конце каждого из двузначных чисел.

Заметим, что этим же способом мы можем получить числа от 91 до 180, приписав к соответствующим двузначным числам не два нуля в конце, а 99 и 91.

Таким образом, мы можем получить числа от 1 до 180.

Покажем, как получить числа от 163 до 252. Для этого к нашим двузначным числам, дающим числа от 1 до 90, допишем в конце по две девятки. Тогда сумма получившихся чисел будет находиться от до

Осталось получить числа 253, 254, 255, 256, 257, 258, 259 и 260:

• Сумма для чисел 9992 и 9995 равна 253:

  

• Сумма для чисел 9987 и 9984 равна 254:

  

• Сумма для чисел 8889 и 8887 равна 255:

  

• Сумма для чисел 8888 и 8888 равна 256:

  

• Сумма для чисел 9888 и 9886 равна 257:

  

• Сумма для чисел 9887 и 9887 равна 258:

  

• Сумма для чисел 9995 и 9985 равна 259:

  

• Сумма для чисел 9997 и 9885 равна 260:

  

Таким образом, все числа от 1 до 260 можно получить в виде суммы для двух некоторых четырехзначных чисел.

а) Да, могло. Если в классе учились 5 девочек и 20 мальчиков, то процентная доля девочек была равна

При этом условие на общее количество детей в классе выполняется, так как

б) Пусть изначально в классе учились детей, при этом из них — девочки. В этом случае процентная доля девочек составляла

Мы знаем, что изначальная процентная доля девочек была не более 21%, значит,

После перевода еще одной девочки в класс количество девочек в классе стало равно а количество детей — Тогда в этом случае процентная доля девочек составила

Тогда нам нужно сравнить

Заметим, что Тогда сравним

Заметим, что по условию Тогда значит,

Таким образом,

Следовательно, меньше 30%, то есть после перевода в класс еще одной девочки их процентная доля не могла стать равной 30%.

в) Аналогично пункту б) оценим Но в этот раз будем пользоваться тем, что так как — натуральное.

Тогда

Значит, наибольшее целое значение, которое могла принимать процентная доля девочек, равно 27%. Заметим, что — несократимая дробь, тогда если

то не меньше 100. Это не так, потому что

Значит, наибольшее целое значение, которое могла принимать процентная доля девочек, равно 26%. Заметим, что — несократимая дробь, тогда если

то не меньше 50. Это не так, потому что

Значит, наибольшее целое значение, которое могла принимать процентная доля девочек, равно 25%. Если изначально было 2 девочки и 9 мальчиков, то исходная процентная доля девочек была равна

Тогда после перевода еще одной девочки в класс она стала равняться

а) Да, можно:

б) Предположим, что это можно сделать. Если изначально была дробь то спустя два хода дробь стала:

Заметим, что при данных действиях несократимая дробь остается несократимой, так как по алгоритму Евклида

Значит, если дробь стала равна то это в точности дробь Тогда Поскольку и — натуральные числа, то второе равенство может быть верно, только если Однако, в таком случае Получим противоречие. Значит, дробь через 2 хода получиться не могла.

в) Из пункта б) известно, что если была дробь то спустя два хода дробь станет равна Тогда

Выразим через и

Заметим, что Тогда

Выразим через и

Заметим, что Тогда

Изначальная дробь должна быть правильной, поэтому

Тогда

Значит, если — правильная дробь, то значение получить нельзя.

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

Осталось проверить, что такая дробь правильная и несократимая. Она правильная, так как мы накладывали условия и ранее. Тогда осталось проверить то, что она несократима. Дробь мы будем восстанавливать по несократимой дроби поэтому

Тогда по алгоритму Евклида

Значит, если — несократимая, то и — несократимая.

Таким образом, наименьшее значение, которое нельзя получить из правильной несократимой дроби за 2 хода, равно

а) Да, можно:

б) Предположим, что это можно сделать. Если изначально была дробь то спустя 3 хода дробь стала:

Заметим, что при данных действиях несократимая дробь остается несократимой, так как по алгоритму Евклида

Значит, если дробь стала равна то это в точности дробь Тогда Поскольку и — натуральные числа, то второе равенство может быть верно, только если Однако, в таком случае Получим противоречие. Значит, дробь через 3 хода получиться не могла.

в) Из пункта б) известно, что если была дробь то спустя два хода дробь станет равна Тогда

Выразим через и

Заметим, что Тогда

Выразим через и

Заметим, что Тогда

Изначальная дробь должна быть правильной, поэтому

Тогда

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

Осталось проверить, что такая дробь правильная и несократимая. Она правильная, так как мы накладывали условия и ранее. Тогда осталось проверить то, что она несократима. Дробь мы будем восстанавливать по несократимой дроби поэтому

Тогда по алгоритму Евклида

Значит, если — несократимая, то и — несократимая.

Таким образом, наибольшее значение, которое нельзя получить из правильной несократимой дроби за 2 хода, равно

а) Да, можно, например так:

б) Рассмотрим пару где и совершим с ней два хода:

Таким образом, за ходов из пары мы можем получить только пары вида

После одного хода из мы получим Тогда за ход из пары мы можем получить только пары вида

Число 806 не равно ни ни Следовательно, пару невозможно получить за несколько ходов из пары

в) Заметим, что числа любой пары, которую мы можем получить, одной четности: если изначально и разной четности, то и — нечетные; если и одной четности, то и — четные.

Теперь поймем, из какой пары можно было получить пару Пусть Тогда

Таким образом, пару можно было получить только из пары Ее в свою очередь можно было получить только из пары

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

а) Да, можно, например так:

б) Рассмотрим пару где и совершим с ней два хода:

Таким образом, за ходов из пары мы можем получить только пары вида

После одного хода из мы получим Тогда за ход из пары мы можем получить только пары вида

Число 408 не равно ни ни Следовательно, пару невозможно получить за несколько ходов из пары

в) Заметим, что числа любой пары, которую мы можем получить, одной четности: если изначально и разной четности, то и — нечетные; если и одной четности, то и — четные.

Теперь поймем, из какой пары можно было получить пару Пусть Тогда

Таким образом, пару можно было получить только из пары Ее в свою очередь можно было получить только из пары

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