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

Поиск
?

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

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

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

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

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

Решение.

Для каждой кучки назовём её показателем максимальную степень двойки, на которую делится число содержащихся в ней камней, она может быть равна $1=2 в степени левая круглая скобка 0 правая круглая скобка .$ Рассмотрим поведение показателей кучек, участвующих в перекладывании. После перекладывания камней из кучки с $2 в степени левая круглая скобка a правая круглая скобка левая круглая скобка 2 k плюс 1 правая круглая скобка$ камнями в кучку с $2 в степени левая круглая скобка b правая круглая скобка левая круглая скобка 2 l плюс 1 правая круглая скобка$ камнями в первой остаётся

камней, а во второй становится $2 в степени левая круглая скобка b плюс 1 правая круглая скобка левая круглая скобка 2 l плюс 1 правая круглая скобка$ камней. Если $a=b,$ то

$2 в степени левая круглая скобка a правая круглая скобка левая круглая скобка 2 k плюс 1 правая круглая скобка минус 2 в степени левая круглая скобка b правая круглая скобка левая круглая скобка 2 l плюс 1 правая круглая скобка =2 в степени левая круглая скобка a плюс 1 правая круглая скобка левая круглая скобка k минус l правая круглая скобка ,$

поэтому оба показателя возрастут. Если $a не равно q b,$ то

$2 в степени левая круглая скобка a правая круглая скобка левая круглая скобка 2 k плюс 1 правая круглая скобка минус 2 в степени левая круглая скобка b правая круглая скобка левая круглая скобка 2 l плюс 1 правая круглая скобка =2 в степени левая круглая скобка c правая круглая скобка левая круглая скобка 2 m плюс 1 правая круглая скобка ,$

где $c=\min левая фигурная скобка a, b правая фигурная скобка .$ При этом минимальный в данной паре кучек показатель сохраняется, а второй гарантированно становится больше минимального. Заметим, что количество кучек с минимальным среди всех показателем при произвольном перекладывании либо уменьшается на 2, либо не меняется.

Рассмотрим произвольную раскладку $N=2 в степени левая круглая скобка t правая круглая скобка$ камней по более, чем одной кучке. В ней число кучек с минимальным показателем 2^s, $s меньше t$ будет чётным. Действительно, общее число камней $N=2 в степени левая круглая скобка t правая круглая скобка$ и сумма количеств камней в не минимальных кучках делятся на $2 в степени левая круглая скобка s плюс 1 правая круглая скобка$ поэтому сумма количеств камней в минимальных кучках тоже делится на $2 в степени левая круглая скобка s плюс 1 правая круглая скобка ,$ значит, их количество делится на 2. Если в раскладке есть хотя бы две кучки, разбиваем все кучки с минимальным показателем на пары, выполняем в каждой перекладывание из большей в меньшую и получаем раскладку с большим минимальным показателем, чем рассматриваемая. Проделав эту процедуру не более, чем t раз, получим раскладку с минимальным показателем t, то есть  — с единственной кучкой из $2 в степени левая круглая скобка t правая круглая скобка =N$ камней.

Пусть теперь $N=2 в степени левая круглая скобка t правая круглая скобка левая круглая скобка 2 k плюс 1 правая круглая скобка ,$ $k больше или равно 1$ не является степенью двойки. Рассмотрим любой процесс сборки некоторой раскладки N камней по кучкам в одну и произведём его в обратном порядке, посредством процедур перекладывания, обратных к исходным, когда половина одной из кучек перекладывается в другую. При этом в обратном процессе количество камней в первой кучке (она же последняя в исходном процессе сборки) и всех получающихся на каждом шаге будет делиться на нечётное число $2 k плюс 1.$ Следовательно, любая раскладка, в которой есть кучка из числа камней, не делящегося на $2 k плюс 1,$ не может быть собрана в одной кучке. В частности, не может быть собрана в одну раскладка $левая фигурная скобка 1, N минус 1 правая фигурная скобка$ по двум кучкам.

Замечания.

1.  В случае $N=2 в степени левая круглая скобка t правая круглая скобка левая круглая скобка 2 k плюс 1 правая круглая скобка$ можно предложить другое решение того, что раскладка $левая фигурная скобка 1, N минус 1 правая фигурная скобка$ по двум кучкам не может быть собрана в одну. Этого достаточно для доказательства необходимости в условии задачи, то есть того, что любая начальная раскладка N камней по кучкам может быть собрана в одной куче только тогда, когда N является степенью двойки.

Докажем по индукции, что после k перекладываний количества камней в кучках имеют вид

$левая фигурная скобка 2 в степени левая круглая скобка k правая круглая скобка минус a_k умножить на N, левая круглая скобка a_k плюс 1 правая круглая скобка умножить на N минус 2 в степени левая круглая скобка k правая круглая скобка правая фигурная скобка$

для некоторого целого числа $a_k больше или равно 0.$ База индукции при $k=0$ очевидна:

$левая фигурная скобка 1, N минус 1 правая фигурная скобка = левая фигурная скобка 2 в степени левая круглая скобка 0 правая круглая скобка минус 0 умножить на N, 1 умножить на N минус 2 в степени левая круглая скобка 0 правая круглая скобка правая фигурная скобка ,$

то есть $a_0=0.$ Шаг индукции: либо мы перекладываем камни из правой кучки в левую, тогда в левой станет $2 в степени левая круглая скобка k плюс 1 правая круглая скобка минус 2 a_k N,$ а в правой останется $левая круглая скобка 2 a_k плюс 1 правая круглая скобка N минус 2 в степени левая круглая скобка k плюс 1 правая круглая скобка$ камней, при этом $a_k плюс 1=2 a_k,$ либо мы перекладываем камни из левой кучки в правую, тогда в левой останется $2 в степени левая круглая скобка k плюс 1 правая круглая скобка минус левая круглая скобка 2 a_k плюс 1 правая круглая скобка N,$ а в правой станет $2 левая круглая скобка a_k плюс 1 правая круглая скобка N минус 2 в степени левая круглая скобка k плюс 1 правая круглая скобка$ камней, при этом $a_k плюс 1=2 a_k плюс 1.$

Если после некоторого k-ого перекладывания раскладки $левая фигурная скобка 1, N минус 1 правая фигурная скобка$ останется всего одна кучка, то число камней в другой станет равным 0, следовательно, выполнится равенство одно из равенств $2 в степени левая круглая скобка k правая круглая скобка минус a_k умножить на N=0$ или $левая круглая скобка a_k плюс 1 правая круглая скобка умножить на N минус 2 в степени левая круглая скобка k правая круглая скобка =0 . B$ обоих случаях N будет делителем числа 2^k, то есть тоже степенью двойки противоречие с тем, что в рассматриваемом случае $N=2 в степени левая круглая скобка t правая круглая скобка левая круглая скобка 2 k плюс 1 правая круглая скобка .$ Следовательно, при любом N, отличном от степени двойки, раскладка $левая фигурная скобка 1, N минус 1 правая фигурная скобка$ не может быть собрана в одну кучку.

2.  Объединяя оба случая $N=2 в степени левая круглая скобка t правая круглая скобка$ и $N=2 в степени левая круглая скобка t правая круглая скобка левая круглая скобка 2 k плюс 1 правая круглая скобка ,$ получаем доказательство более общего утверждения: раскладка N камней может быть собрана в одной кучке тогда и только тогда, когда количество камней в каждой её кучке делится на набольший нечётный делитель N.

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

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

Пусть n  — натуральное число, не заканчивающееся на 0, и R(n)  — четырёхзначное число, получающееся из n изменением порядка следования его цифр на обратный, например R(3257)  =  7523: Найти все натуральные четырёхзначные числа n такие, что $R левая круглая скобка n правая круглая скобка =4n плюс 3.$

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

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

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

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

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

Найти все натуральные n , для которых на клетчатой доске размера n на n клеток можно отметить n клеток, стоящих в разных горизонталях и разных вертикалях, которые можно последовательно обойти ходом шахматного коня, начиная с некоторой, не вставая на одну клетку дважды, и вернуться на исходную клетку. Конь при этом может вставать только на отмеченные клетки.

Решение.

Пример для n  =  4 несложен:

Докажем, что при n  =  4, требуемого в условии набора клеток не существует. Предположим, при данном n удалось отметить n клеток в разных горизонталях и разных вертикалях доски n на n, которые можно последовательно обойти ходом шахматного коня и вернуться в исходную отмеченную клетку. Рассмотрим величины горизонтальных перемещений коня при его последовательных ходах по отмеченным клеткам вертикалей доски. Конь либо придёт в клетку на вертикали а (первой слева) из клетки на вертикали b (второй слева), а затем уйдёт в клетку на вертикали с (третьей слева), либо наоборот. В первом случае (второй случай симметричен первому), чтобы не было повторов вертикалей, прийти на вертикаль b он может только с вертикали d а уйти с вертикали с может только на вертикаль е. Все предшествующие приходу на вертикаль d и последующие за уходом с вертикали е ходы делаются с горизонтальным смещением 2, кроме одного со смещением 1, который замкнёт цепь перемещений коня и может произойти только у правого края доски. Всего конь сместится по горизонтали 2 раза на одну клетку и $n минус 2$ раза на две клетки. Ровно то же самое можно сказать и о его вертикальных перемещениях по горизонталям доски. Каждым ходом конь смещается в одном направлении на одну клетку, а в другом  — на две, поэтому в общем наборе из всех его 2n смещений в обоих направлениях число смещений на одну клетку должно совпадать с числом смещений на две клетки, откуда $2 n минус 4=4$ и $n=4.$

Ответ: n  =  4.

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

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

По кругу записаны 150 неотрицательных целых чисел, сумма которых равна n. Назовем число удачным, если оба его соседа являются натуральными. Раз в минуту выбирается удачное число, к нему прибавляется 2, а из его соседей вычитается по единице. Процесс заканчивается, если не осталось ни одного удачного числа. Найдите наибольшее значение n, при котором процесс заведомо закончится.

Решение.

Начнем с того, что если $n=150,$ то процесс необязательно закончится. Действительно, рассмотрим следующую расстановку (мы выписываем числа в строку для удобства, но следует иметь в виду, что первое и последнее число в строке являются соседними на окружности):

$\beginarrayllllllll 2 0 1 1 1 \ldots 1 1. \endarray$

Если мы выберем 0 в качестве удачного числа, то получим следующую расстановку

$\beginarrayllllllll 1 2 0 1 1 \ldots 1 1. \endarray$

Нетрудно видеть, что она получается из предыдущей сдвигом на одну позицию по часовой стрелке. Проведя такую операцию 150 раз, мы придем в исходную позицию и сможем продолжать процесс бесконечно. При $n больше 150$ легко строится аналогичный пример.

Докажем теперь, что если $n меньше или равно 149,$ то процесс обязательно застопорится. Для этого обратим внимание на нули (хотя бы один ноль обязательно есть, поскольку $n меньше 150 правая круглая скобка .$ Нули разбивают окружность на несколько дуг. Одна из них должна быть заполнена единицами, иначе сумма чисел на каждой дуге хотя бы на 1 больше количества чисел в ней, и тогда общая сумма будет не меньше 150. Выберем наименьшую из дуг, заполненных единицами (возможно, это дуга длины ноль, то есть просто два рядом стоящих нуля). Заметим, что длина такой наименьшей дуги не увеличивается при проведении операций, а если проводится операция, затрагивающая эту дугу, то длина строго уменьшается. Действительно, при проведении операции с единицей внутри, дуга разрывается на меньшие части  — одну двойку и две дуги, заполненные единицами. При проведении операции с нулем на конце, дуга, очевидно, укорачивается на одну единицу.

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

Если процесс продолжается бесконечно долго, то комбинация чисел по кругу рано или поздно повторится. Пусть повторилась позиция a₁, a₂, ..., a₁₅₀, при этом между повторениями число на первой позиции выбирали в качестве удачного $x_1$ раз, число на второй позиции  — x₂ раз, ..., число на 150-й позиции  — x₁₅₀ раз. Тогда, поскольку все числа после всех операций не изменились, имеют место соотношения

$2 x_2 минус x_1 минус x_3=0,$

$2 x_3 минус x_2 минус x_4=0,$

$умножить на s$

$2 x_149 минус x_148 минус x_150=0,$

$2 x_150 минус x_149 минус x_1=0,$

$2 x_1 минус x_150 минус x_2=0.$

Из них следует, что $x_1=x_2=\ldots=x_150$ (достаточно рассмотреть максимальное из x_j и понять, что соседние с ним совпадают).

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

Ответ: 149.

Аналоги к заданию № 5905: 5921 5922 Все

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

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

По кругу записаны 250 неотрицательных целых чисел, сумма которых равна n. Назовем число удачным, если оба его соседа являются натуральными. Раз в минуту выбирается удачное число, к нему прибавляется 2, а из его соседей вычитается по единице. Процесс заканчивается, если не осталось ни одного удачного числа. Найдите наибольшее значение n, при котором процесс заведомо закончится.

Решение.

Начнем с того, что если $n=250,$ то процесс необязательно закончится. Действительно, рассмотрим следующую расстановку (мы выписываем числа в строку для удобства, но следует иметь в виду, что первое и последнее число в строке являются соседними на окружности):

$\beginarrayllllllll 2 0 1 1 1 \ldots 1 1 . \endarray$

Если мы выберем 0 в качестве удачного числа, то получим следующую расстановку

$\beginarrayllllllll 1 2 0 1 1 \ldots 1 1 . \endarray$

Нетрудно видеть, что она получается из предыдущей сдвигом на одну позицию по часовой стрелке. Проведя такую операцию 250 раз, мы придем в исходную позицию и сможем продолжать процесс бесконечно. При $n больше 250$ легко строится аналогичный пример.

Докажем теперь, что если $n меньше или равно 249,$ то процесс обязательно застопорится. Для этого обратим внимание на нули (хотя бы один ноль обязательно есть, поскольку $n меньше 250 правая круглая скобка .$ Нули разбивают окружность на несколько дуг. Одна из них должна быть заполнена единицами, иначе сумма чисел на каждой дуге хотя бы на 1 больше количества чисел в ней, и тогда общая сумма будет не меньше 250. Выберем наименьшую из дуг, заполненных единицами (возможно, это дуга длины ноль, то есть просто два рядом стоящих нуля). Заметим, что длина такой наименьшей дуги не увеличивается при проведении операций, а если проводится операция, затрагивающая эту дугу, то длина строго уменьшается. Действительно, при проведении операции с единицей внутри, дуга разрывается на меньшие части  — одну двойку и две дуги, заполненные единицами. При проведении операции с нулем на конце, дуга, очевидно, укорачивается на одну единицу.

Если процесс продолжается бесконечно долго, то комбинация чисел по кругу рано или поздно повторится. Пусть повторилась позиция a₁, a₂ ..., a₂₅₀, при этом между повторениями число на первой позиции выбирали в качестве удачного x₁ раз, число на второй позиции  — x₂ раз, ..., число на 250-й позиции  — x₂₅₀ раз. Тогда, поскольку все числа после всех операций не изменились, имеют место соотношения

$2 x_2 минус x_1 минус x_3=0,$

$2 x_3 минус x_2 минус x_4=0 ,$

$умножить на s$

$2 x_249 минус x_248 минус x_250=0,$

$2 x_250 минус x_249 минус x_1=0,$

$2 x_1 минус x_250 минус x_2=0 .$

Из них следует, что $x_1=x_2=\ldots=x_250$ (достаточно рассмотреть максимальное из x_j и понять, что соседние с ним совпадают).

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

Ответ: 249.

Аналоги к заданию № 5905: 5921 5922 Все

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

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

По кругу записаны 350 неотрицательных целых чисел, сумма которых равна n. Назовем число удачным, если оба его соседа являются натуральными. Раз в минуту выбирается удачное число, к нему прибавляется 2, а из его соседей вычитается по единице. Процесс заканчивается, если не осталось ни одного удачного числа. Найдите наибольшее значение n, при котором процесс заведомо закончится.

Решение.

Начнем с того, что если $n=350,$ то процесс необязательно закончится. Действительно, рассмотрим следующую расстановку (мы выписываем числа в строку для удобства, но следует иметь в виду, что первое и последнее число в строке являются соседними на окружности):

$\beginarrayllllllll 2 0 1 1 1 \ldots 1 1 . \endarray$

Если мы выберем 0 в качестве удачного числа, то получим следующую расстановку

$\beginarrayllllllll 1 2 0 1 1 \ldots 1 1 . \endarray$

Нетрудно видеть, что она получается из предыдущей сдвигом на одну позицию по часовой стрелке. Проведя такую операцию 350 раз, мы придем в исходную позицию и сможем продолжать процесс бесконечно. При $n больше 350$ легко строится аналогичный пример.

Докажем теперь, что если $n меньше или равно 349,$ то процесс обязательно застопорится. Для этого обратим внимание на нули (хотя бы один ноль обязательно есть, поскольку $n меньше 350 правая круглая скобка .$ Нули разбивают окружность на несколько дуг. Одна из них должна быть заполнена единицами, иначе сумма чисел на каждой дуге хотя бы на 1 больше количества чисел в ней, и тогда общая сумма будет не меньше 350. Выберем наименьшую из дуг, заполненных единицами (возможно, это дуга длины ноль, то есть просто два рядом стоящих нуля). Заметим, что длина такой наименьшей дуги не увеличивается при проведении операций, а если проводится операция, затрагивающая эту дугу, то длина строго уменьшается. Действительно, при проведении операции с единицей внутри, дуга разрывается на меньшие части  — одну двойку и две дуги, заполненные единицами. При проведении операции с нулем на конце, дуга, очевидно, укорачивается на одну единицу.

Если процесс продолжается бесконечно долго, то комбинация чисел по кругу рано или поздно повторится. Пусть повторилась позиция a₁, a₂, ..., a₃₅₀, при этом между повторениями число на первой позиции выбирали в качестве удачного x₁ раз, число на второй позиции  — x₂ раз, ..., число на 350-й позиции  — x₃₅₀ раз. Тогда, поскольку все числа после всех операций не изменились, имеют место соотношения

$2 x_2 минус x_1 минус x_3=0,$

$2 x_3 минус x_2 минус x_4=0 ,$

$умножить на s$

$2 x_349 минус x_348 минус x_350=0 ,$

$2 x_350 минус x_349 минус x_1=0,$

$2 x_1 минус x_350 минус x_2=0.$

Из них следует, что $x_1=x_2=\ldots=x_350$ (достаточно рассмотреть максимальное из x_j и понять, что соседние с ним совпадают).

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

Ответ: 349.

Аналоги к заданию № 5905: 5921 5922 Все

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

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

По кругу записаны 450 неотрицательных целых чисел, сумма которых равна n. Назовем число удачным, если оба его соседа являются натуральными. Раз в минуту выбирается удачное число, к нему прибавляется 2, а из его соседей вычитается по единице. Процесс заканчивается, если не осталось ни одного удачного числа. Найдите наибольшее значение n, при котором процесс заведомо закончится.

Решение.

Начнем с того, что если $n=450,$ то процесс необязательно закончится. Действительно, рассмотрим следующую расстановку (мы выписываем числа в строку для удобства, но следует иметь в виду, что первое и последнее число в строке являются соседними на окружности):

$\beginarrayllllllll 2 0 1 1 1 \ldots 1 1 . \endarray$

Если мы выберем 0 в качестве удачного числа, то получим следующую расстановку

$\beginarrayllllllll 1 2 0 1 1 \ldots 1 1 . \endarray$

Нетрудно видеть, что она получается из предыдущей сдвигом на одну позицию по часовой стрелке. Проведя такую операцию 450 раз, мы придем в исходную позицию и сможем продолжать процесс бесконечно. При $n больше 450$ легко строится аналогичный пример.

Докажем теперь, что если $n меньше или равно 449,$ то процесс обязательно застопорится. Для этого обратим внимание на нули (хотя бы один ноль обязательно есть, поскольку $n меньше 450 правая круглая скобка .$ Нули разбивают окружность на несколько дуг. Одна из них должна быть заполнена единицами, иначе сумма чисел на каждой дуге хотя бы на 1 больше количества чисел в ней, и тогда общая сумма будет не меньше 450. Выберем наименьшую из дуг, заполненных единицами (возможно, это дуга длины ноль, то есть просто два рядом стоящих нуля). Заметим, что длина такой наименьшей дуги не увеличивается при проведении операций, a если проводится операция, затрагивающая эту дугу, то длина строго уменьшается. Действительно, при проведении операции с единицей внутри, дуга разрывается на меньшие части  — одну двойку и две дуги, заполненные единицами. При проведении операции с нулем на конце, дуга, очевидно, укорачивается на одну единицу.

Если процесс продолжается бесконечно долго, то комбинация чисел по кругу рано или поздно повторится. Пусть повторилась позиция a₁, a₂, ..., a₄₅₀, при этом между повторениями число на первой позиции выбирали в качестве удачного x₁ раз, число на второй позиции  — x₂ раз, ..., число на 450-й позиции  — x₄₅₀ раз. Тогда, поскольку все числа после всех операций не изменились, имеют место соотношения

$2 x_2 минус x_1 минус x_3=0,$

$2 x_3 минус x_2 минус x_4=0,$

$умножить на s$

$2 x_449 минус x_448 минус x_450=0,$

$2 x_450 минус x_449 минус x_1=0,$

$2 x_1 минус x_450 минус x_2=0.$

Из них следует, что $x_1=x_2=\ldots=x_450$ (достаточно рассмотреть максимальное из x_j и понять, что соседние с ним совпадают).

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

Ответ: 449.

Аналоги к заданию № 5904: 5918 5919 5920 ...5918 5919 5920 5923 Все

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

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

На доске написаны числа 2, 3, 5, ..., 2003, 2011, 2017, т. е. все простые числа, не превосходящие 2020. За одну операцию можно заменить два числа a, b на максимальное простое число, не превосходящее $корень из: начало аргумента: a в квадрате минус ab плюс b в квадрате конец аргумента .$ После нескольких операций на доске осталось одно число. Какое максимальное значение оно может принимать?

Решение.

Заметим, что если $a меньше b,$ то $a меньше корень из: начало аргумента: a в степени левая круглая скобка 2 конец аргумента минус a b плюс b в квадрате правая круглая скобка меньше b.$ Действительно, $a в квадрате меньше a в квадрате минус a b плюс b в квадрате ,$ так как $a b меньше b в квадрате$ и $a в квадрате минус a b плюс b в квадрате меньше b в квадрате ,$ так как $a в квадрате меньше a b.$

Таким образом, число 2017 или какое-то большее него не может появиться после какой-то операции. Но последнее число появилось после какой-то операции, поэтому оно не больше 2011.

Отложим число 2017 и будем применять операцию к двум наибольшим оставшимся числам x и y, где $x меньше y.$ Заметим, что так как x и y  — это два соседних простых числа, то наибольшее число, не превосходящее $корень из: начало аргумента: x в степени левая круглая скобка 2 конец аргумента минус x y плюс y в квадрате правая круглая скобка$   — это x. Таким образом, мы каждый раз будем откидывать самое большое из наших чисел, пока на доске не останутся числа 2 и 2017.

Теперь применим операцию к числам 2 и 2017. Заметим, что

$2017 в квадрате минус 2 умножить на 2017 плюс 2 в квадрате больше 2011 в квадрате ,$

поэтому в результате этой операции на доске окажется число 2011.

Ответ: максимальное значение равно 2011.

Замечание.

Неравенство $a меньше корень из: начало аргумента: a в степени левая круглая скобка 2 конец аргумента минус a b плюс b в квадрате правая круглая скобка меньше b$ при $a меньше b$ можно доказать геометрически. Дело в том, что в треугольнике со сторонами a и b и углом 60° между ни ми длина третьей стороны равна как раз $корень из: начало аргумента: a в степени левая круглая скобка 2 конец аргумента минус a b плюс b в квадрате правая круглая скобка .$ А так как угол 60° всегда средний по величине в своем треугольнике, то и лежащая напротив него сторона также средняя по величине.

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

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

У Поликарпа есть 2 коробки, в первой из которых лежит n монет, а вторая пустая. За один ход он может либо переложить одну монету из первой коробки во вторую, либо убрать из первой коробки ровно k монет, где k  — количество монет во второй коробке. При каких n Поликарп может сделать первую коробку пустой не более чем за 10 ходов?

Решение.

Назовём ход, при котором перекладывается одна монета из первой коробки во вторую, ходом первого типа, а ход, при котором монеты убираются из первой коробки  — ходом второго типа. Пусть в сего было сделано x ходов первого типа и y ходов второго типа. Тогда во второй коробке не больше x монет. Поэтому при выполнении ходов второго типа мы заберём из первой коробки не более xy монет, значит, в сумме заберём не более $x плюс x y$ монет. Так как $x плюс y меньше или равно 10,$ то

$x плюс x y меньше или равно x плюс x левая круглая скобка 10 минус x правая круглая скобка = минус x в квадрате плюс 11 x.$

При целочисленных значениях x максимум этого выражения достигается в точках $x=5$ и $x=6$ и равен $5 умножить на 6=30.$ Таким образом, $n меньше или равно 30.$ Докажем, что любое $n меньше или равно 30$ подходит.

Если сделать 5 ходов первого типа, а после этого 5 ходов второго типа, то мы уберём из первой коробки ровно 30 монет. Выпишем последовательность из 1 и 2, где 1 обозначает ход первого типа, а 2  — ход второго типа. Заметим, что если в этой последовательности поменять соседнюю пару 12 на пару 21, то итоговое количество монет, извлечённых из первой коробки, уменьшится на 1. Так мы можем делать, пока все 2 не окажутся слева, а все 1  — справа. Теперь будем заменять 1 на 2, и на каждом шаге количество извлечённых монет с помощью такой последовательности операций тоже будет уменьшаться на 1. Таким образом, для любого n от 0 до 30 мы можем предъявить нужную последовательность операций.

Ответ: при n от 0 до 30 включительно.

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

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

Робот умеет выполнять четыре операции с целыми числами: умножать на 2, делить на 2 (только четные числа), прибавлять 111 и вычитать 111. Может ли робот из числа 925 получить следующие числа: 295, 296, 259, 529, 592?

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

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

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

Выражение $a в кубе плюс b в кубе минус c в кубе$ легко можно вычислить используя 6 операций умножения: для возведения каждого числа в куб требуется две операции. Придумайте алгоритм вычисления этой суммы за меньшее число операций умножения. Чем меньше операций, тем выше будет оценка за задачу.

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

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

Опишите алгоритм возведения числа a в 255 степень с помощью только операции умножения:

1)  За 14 операций умножения без использования дополнительной памяти (то есть разрешается использовать только исходное число и результат последней операции).

2)  За 10 операций умножения с использованием любого количества дополнительной памяти.

3)  За 10 операций умножения с использованием одной ячейки дополнительной памяти (то есть помимо исходного числа и результата последней операции, разрешается держать в памяти ещё одно число. Это число может меняться в процессе работы алгоритма).

Замечание: верное решение для 11.3 будет засчитываться и для 11.2.

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

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

Опишите множество всех последовательностей из букв a и b таких, что в любом наборе подряд идущих символов (длины больше 1) букв a не меньше, чем букв b

Обратите внимание! В отличие от предыдущей задачи, рассматриваются не только начальные отрезки последовательности, а вообще любые!

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

Так для повторения блока из нескольких букв используйте операцию "звездочка" (итерация), например, (abb)* задает множество слов {пустое слово, abb, abbabb, abbabbabb, ...} Умножение множеств (эту операцию, как обычно в алгебре, изображают точкой или вообще опускают, что мы и будем делать), описывает склейку всех слов первого множества со словами второго (третьего и т. д.), например a*cb* обозначает множество слов: {с, ac, cb, acb, aac, ..., aaa...acb.. b, ...}. Обратите внимание что слова, в которых нет букв a или b, получаются за счет того, что результат итерации может не содержать символов, то есть быть пустым словом.

Последней операцией, которая используется в формулах, является сложение. Сложение соответствует объединению множеств. Так обозначение (a + b) c + d(ac*+) описывает множество всех последовательностей из букв a и b (обозначается (a +  b)*), к концу которых присоединена буква c, объединенного с множеством слов, начинающихся с буквы d, за которой следует буква a, а за ней любое число букв c и ещё одним однобуквенным словом (d умножить на пустое слово  — это d).

Слева приведены примеры слов, которые удовлетворяют нашему условию, справа примеры слов, которые не удовлетворяют ему. Благодаря подсветке вы можете видеть, какие из этих примеров и контрпримеров удовлетворяют построенному вами выражению, а какие  — нет.

Решение.

Обратим внимание, что слово, состоящее из одного символа b, удовлетворяет условию. Также поймём, что для последовательностей длины хотя бы 3, нам достаточно проверить выполнение условия только для наборов длины 3. Действительно, из выполнения условия для набора длины 3 (что, в случае нечётного числа означает, что количество букв а строго больше) автоматически следует выполнение условия для наборов длины 2, а набор любой другой длины можно составить из наборов длины два и три.

Выполнение условия на наборах длины 2 и 3 в свою очередь равносильно тому, что между любыми двумя буквами b есть хотя бы две буквы a. Решением задачи является формула: a* + a*b( + (aaa*b)*)a*.

Она построена следующим образом: слагаемое a* отвечает за слова, в которых нет буквы b. Если буква b есть, перед ней идёт произвольное количество букв a. Дальше для каждой следующей буквы b должно быть ещё хотя бы две буквы a, откуда мы получаем ааа*b, повторённое несколько раз. Заканчивается всё ещё несколькими буквами a.

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

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

Белая фигура «жук» стоит в угловой клетке доски 1000 × n, где n  — нечётное натуральное число, большее 2020. В двух ближайших к ней углах доски стоят два чёрных шахматных слона. При каждом ходе жук или переходит на клетку, соседнюю по стороне, или ходит как шахматный конь. Жук хочет достичь противоположного угла доски, не проходя через клетки, занятые или атакованные слоном, и побывав на каждой из остальных клеток ровно по одному разу. Покажите, что количество путей, по которым может пройти жук, не зависит от n.

(Николай Белухов)

Решение.

Сориентируем доску так, чтобы у неё было 1000 столбцов и n строк, а жук сидел в нижнем левом углу. Покрасим клетки в шахматном порядке, причём клетку жука сделаем белой. Занумеруем столбцы числами от 1 до 1000 слева направо, а строки числами от 1 до n снизу вверх.

Рассмотрим некоторый путь жука из клетки $левая круглая скобка 1, 1 правая круглая скобка$ в клетку $левая круглая скобка 1000, n правая круглая скобка .$ Из каждой клетки пути нарисуем стрелку в следующую клетку. Тогда из каждой белой клетки пути стрелка ведёт в чёрную.

Пусть i  — чётное число, причём $1000 меньше или равно i меньше или равно n минус 1003.$ Между строками i и $i плюс 1$ проведём горизонтальную прямую ℓ.

Ниже прямой ℓ количество белых клеток в пути превосходит количество чёрных не меньше чем на 1000, так как 1000 чёрных клеток в нижних строках находятся под боем слона. Поэтому не меньше 1000 стрелок идут из белых клеток ниже ℓ в чёрные клетки выше ℓ. Но так может проходить лишь стрелка из клетки в строке $i минус 1$ или i. А поскольку там всего 1000 белых клеток, в каждой из них начинается стрелка, идущая в чёрную клетку строки $i плюс 1$ или $i плюс 2.$

Стрелка из клетки $левая круглая скобка 1, i минус 1 правая круглая скобка$ может идти только в $левая круглая скобка 2, i плюс 1 правая круглая скобка .$ Тогда стрелка из $левая круглая скобка 3, i минус 1 правая круглая скобка$ может идти только в $левая круглая скобка 4, i плюс 1 правая круглая скобка .$ Последовательно рассматривая клетки

$левая круглая скобка 5, i минус 1 правая круглая скобка , левая круглая скобка 7, i минус 1 правая круглая скобка , \ldots, левая круглая скобка 999, i минус 1 правая круглая скобка , левая круглая скобка 1000, i правая круглая скобка , левая круглая скобка 998, i правая круглая скобка , \ldots, левая круглая скобка 2, i правая круглая скобка ,$

видим, что все 1000 стрелок в действительности определены однозначно (рис. 1).

Рис 1.

Аналогичное верно для $i плюс 2$ и, значит, для белых клеток в строках $i плюс 1$ и $i плюс 2.$ Поэтому если жук пришёл в белую клетку выше ℓ, то он уже никогда не вернётся в клетку ниже ℓ. Действительно, пусть жук впервые пересекает $\ell$ сверху вниз после того, как он побывал в белой клетке выше ℓ. Перед пересечением этой прямой жук находился в строке $i плюс 1$ или $i плюс 2.$ Если жук был в белой клетке, то он пошёл бы вверх. А если жук был в чёрной клетке, то он пришёл в неё из клетки ниже ℓ — значит, он уже спускался ниже ℓ, побывав в белой клетке выше ℓ. Получили противоречие.

Среди стрелок из белых клеток строк $i минус 1$ и i рассмотрим пройденную последней. Так как до этого жук не побывал в белой клетке выше ℓ, то из концов остальных таких стрелок он спускался ниже ℓ. Таким образом, лишь из одной чёрной клетки в строках $i плюс 1$ и $i плюс 2$ стрелка ведёт в белую клетку выше ℓ.

Поскольку стрелка из $левая круглая скобка 1, i плюс 2 правая круглая скобка$ не может вести в белую клетку ниже ℓ, стрелки из всех остальных чёрных клеток в строках $i плюс 1$ и $i плюс 2$ должны вести в белые клетки ниже ℓ. Последовательно рассматривая клетки

$левая круглая скобка 3, i плюс 2 правая круглая скобка , левая круглая скобка 5, i плюс 2 правая круглая скобка , \ldots, левая круглая скобка 999, i плюс 2 правая круглая скобка , левая круглая скобка 1000, i плюс 1 правая круглая скобка , левая круглая скобка 998, i плюс 1 правая круглая скобка , \ldots, левая круглая скобка 2, i плюс 1 правая круглая скобка ,$

видим, что все 999 стрелок в действительности определены однозначно (рис. 2).

Рис 2.

Аналогичное рассуждение для всех чётных значений i между 1000 и $n минус 1003$ показывает, что средняя часть пути жука определена однозначно и при росте n продолжается в виде пружины (рис. 3).

Рис 3.

Следовательно, количество возможных путей не зависит от n.

Замечание. Конструкция на рисунке 4 показывает, что рассматриваемые пути действительно существуют.

Рис 4.

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

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

На доске были выписаны 4000 различных натуральных чисел, меньших 30 000. Если на доске выписаны числа a и b, разрешается дописать на доску число НОД $левая круглая скобка a, b правая круглая скобка .$ Докажите, что такими операциями нельзя добиться того, что все числа от 1 до 10000 будут выписаны на доске.

(С. Берлов, А. Храбров)

Решение.

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

Докажем, что на доске не смогут оказаться даже все числа от 6 000 до 10 000. Предположим, что в какой-то момент все эти 4001 чисел появились.

Каким образом число a из этого промежутка могло оказаться на доске? Есть два варианта: либо оно было выписано изначально, либо появилось как НОД двух чисел, кратных a, уже выписанных к этому моменту. Во втором случае это могли быть лишь какие-то два из чисел 2a, 3a или 4a (число 5a больше или равно 30 000, как и все следующие кратные a). Однако НОД $левая круглая скобка 2a, 4a правая круглая скобка =2a,$ поэтому одно из этих двух чисел точно равно 3a. А это число уже не могло появится как НОД двух чисел, то есть оно изначально было на доске.

Итак, для любого числа a из нашего промежутка одно из чисел a и 3a было записано на доске вначале. Покрасим это число в красный цвет (если они оба были записаны вначале   покрасим любое из них). Заметим, что ни одно число не покрашено в красный цвет дважды. Это могло бы произойти, если бы в промежутке [6000, 10 000] нашлись числа a и b, для которых $a=3 b;$ но таких чисел, очевидно, не существует. Поэтому мы покрасили в красный цвет 4001 из 4000 чисел, присутствовавших на доске вначале. Противоречие!

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

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

У Васи есть калькулятор с двумя кнопками, на экране которого отображается целое число x. Нажатие на первую кнопку заменяет число x на экране на число $левая квадратная скобка дробь: числитель: x, знаменатель: 2 конец дроби правая квадратная скобка ,$ а нажатие на вторую кнопку заменяет число x на число $4 x плюс 1.$ Вначале на экране калькулятора отображается число 0. Сколько натуральных чисел, не превосходящих числа 2018, можно получить последовательным нажатием кнопок? Разрешается в процессе получать числа, большие 2018. Через [y] обозначена целая часть числа y, то есть наибольшее целое число, не превосходящее y.

Решение.

Переведем число на экране калькулятора в двоичную систему счисления. Тогда операции, выполняемые при нажатии кнопок, есть не что иное, как стирание последней цифры числа и дописывание в конец числа комбинации цифр 01. Ясно, что таким образом можно получить любую комбинацию цифр, в которой не встречаются две единицы подряд.

Обозначим через S_k количество не более чем k-значных в двоичной системе чисел, не содержащих двух единиц подряд (для удобства будем дописывать нули в старшие разряды числа, чтобы цифр стало ровно k). Легко видеть, что $S_1=2$ (числа 0 и 1), $S_2=3$ (числа 00, 01 и 10).

Убедимся, что при всех $k больше или равно 1$ выполнено рекуррентное соотношение $S_k плюс 2=S_k плюс 1 плюс S_k.$ Действительно: все не более чем $левая круглая скобка k плюс 2 правая круглая скобка$ -значные числа без двух единиц подряд либо оканчиваются на 0 (таких чисел ровно $S_k плюс 1 правая круглая скобка ,$ либо оканчиваются на 01 (таких ровно S_k), и, значит, $S_k плюс 2=S_k плюс 1 плюс S_k.$ Выясним, сколько чисел, не превосходящих 11-значного числа $2018=11 111 100 010_2,$ не содержат двух единиц подряд. Заметим, что все 11-значные числа, большие 2018, точно содержат две единицы подряд, и поэтому достаточно посчитать $S_11=233$ (что легко сделать, использовав доказанную выше рекуррентную формулу); после чего нужно откинуть комбинацию из всех нулей, которая не соответствует натуральному числу.

Ответ: 232.

Замечания.

а)  На самом деле $S_k=F_k плюс 2,$ где F_k  — последовательность Фибоначчи, определенная соотношениями $F_1=1,$ $F_2=1$ и $F_k плюс 2=F_k плюс 1 плюс F_k.$

б)  В приведенном выше решении S_k  — количество чисел, включая число 0. Если считать количество натуральных чисел, рекуррента примет вид $a_k плюс 2=a_k плюс 1 плюс a_k плюс 1.$

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

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

Дано 10 чисел: 10, 20, 30, ..., 100. С ними можно проделать следующую операцию: выбрать любые три и прибавить к выбранным числам по единице. С полученными 10 числами проделывается та же операция и т. д. Можно ли в результате нескольких операций получить:

а)  все одинаковые числа?

б)  все числа, равные 20?

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

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

На столе по кругу лежит n > 3 одинаковых монет, которые могут располагаться либо вверх орлом, либо вверх решкой. Если рядом с некоторой монетой лежат два орла или две решки, то эту монету можно перевернуть. Такую операцию разрешается проделать неограниченное число раз. При каких n можно вне зависимости от начального положения монет перевернуть их все одной стороной вверх?

Решение.

Пусть n нечётно. Разделим весь круг на группы из одинаковых подряд идущих монет. Найдётся группа из нечётного числа монет (иначе общее количество монет в круге будет чётным как сумма чётных чисел). Рассмотрим эту группу. Перевернём в ней вторую, четвёртую и т. д.  — все чётные монеты. После этого мы сможем перевернуть в ней первую, третью и т. д.  — все нечётные монеты. В итоге количество групп в круге уменьшится, и мы сможем повторить все те же самые рассуждения. В конце концов группа останется только одна, но это и будет значить, что все монеты перевёрнуты одинаково. Теперь пусть n чётно. Если n делится на 4, то в расстановке …ООРРООРР… нельзя сделать вообще ни одной операции. Если не делится, то рассмотрим расстановку …ООРРРРООРРООРР…  — одна группа из четырёх решек, а остальные группы по 2 орла или 2 решки. Если мы перевернём вторую решку из этих четырёх, то после этого мы можем перевернуть только первую, и получить аналогичную расстановку, в которой 4 орла. Если перевернём третью, то затем только четвёртую, и снова 4 орла. Для этой расстановки аналогичными рассуждениями можно показать, что мы можем получить только расстановку, которая была изначально (или сдвинуть эту группу из 4 решек). Значит, перевернуть все монеты одной стороной не выйдет.

Ответ: при нечетных n.

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

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

Тикток-хаус представляет собой квадрат $3 \times 3$ из девяти комнат, в каждой из которых живёт по блогеру. В понедельник блогеры случайным образом поменялись комнатами, после чего каждые двя человекя, оказавшиеся в соседних по стороне комнатах, сняли в честь этого совместный тикток. Во вторник блогеры снова как-то поменялись комнатами и сняли тиктоки по тому же правилу, что и в проплый день. То же самое произошло и в среду. Докажите, что какие-то два блогера совместного тиктока так не сделали.

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

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