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

Поиск
?

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

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

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

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

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

В произвольной клетке прямоугольной доски размером 2 × 2016 клеток стоит шахматный конь. Перемещаясь по описанному правилу (и не выходя при этом за края доски), он может из этой клетки попасть в некоторые другие клетки доски, но не во все. Какое наименьшее количество клеток нужно добавить к доске, чтобы конь мог из любой клетки доски попасть во все остальные? (Добавление клетки происходит так, чтобы она имела общую сторону с одной из уже имеющихся. Добавлять можно любое количество клеток, получившаяся при этом доска не обязательно должна иметь прямоугольную форму).

Решение.

Занумеруем клетки как показано на рисунке 1. Конь может из любой клетки попасть в любую клетку с таким же номером, и не может попасть в другие.

Таким образом, все клетки разбились на 4 множества, так что конь не может перескочить из одного множества в другое, но может свободно перемещаться внутри одного множества.

Добавим две клетки как на рисунке 2. Докажем, что теперь конь может попасть из любой клетки в любую другую. Клетка А соединяет клетки, отмеченные розовым цветом, т. е. через ней можно из множества 1 перескочить в множество 4. (Находясь в любой клетке с номером 1, можно прийти в розовую клетку с номером 1, затем через A попасть в розовую клетку с номером 4, и из ней в любую клетку с номером 4. В итоге из любой клетки с номером 1 можно с помощью А попасть в любую клетку с номером 4.)

Клетка В соединяет клетки, отмеченные зелёным, т. е. через ней можно из любого из множеств 2, 3, 4 перескочить так же в любое из этих множеств.

В итоге, сочетая клетки A, B, можно из любого множества попасть в любое другое. Например чтобы попасть из множества 1 в множество 2, вначале с помощью А попадаем из 1 в 4, затем с помощью В попадаем из 4 в 2.

Осталось убедиться, что одной клетки не хватит. Из рисунка 3 видно, что все добавляемые клетки разбиваются на два вида: в клетки А можно попасть не больше чем из 3 клеток доски, в клетки В можно попасть из 4-х клеток, но среди них всегда есть две из одного множества (отмеченные одинаковой цифрой). Т. е. клетки, в которую можно попасть из всех 4-х множеств, не существует.

Ответ: 2.

Критерии оценивания выполнения задания	Баллы
Присутствует а), б), в).	4
Присутствует а), в), отсутствует или ошибочно б).	3
Присутствует а), б), отсутствует или ошибочно в).	2
В решении присутствует только а).	1
Решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	4

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

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

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

Решение.

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

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

Строки и столбцы, содержащие чётное число красных клеток назовём чётными, а содержащие нечётное число красных клеток  — нечётными. Допустим, можно поменять все знаки в таблице меньше чем за 100 операций, тогда рассмотрим некоторую синюю клетку А в строке Х и столбце Y. Чтобы знак в А поменялся, нужно, чтобы, чтобы Х и Y вместе содержали нечётное количество красных клеток, можно считать строку Х чётной, а столбец Y  — нечётным. Заметим, что на пересечении строки и столбца одинаковой чётности должна стоять красная клетка, а на пересечении строки и столбца разной чётности  — синяя, иначе знак в этой клетке после всех операций не изменится. Следовательно, количество красных клеток в каждой чётной строке равно числу чётных столбцов, а количество синих  — числу нечётных столбцов таблицы. Есть хотя бы одна чётная строка Х, значит, всего в таблице чётное число нечётных столбцов. Но количество красных клеток в каждой нечётной строке (нечётное!) равно числу нечётных столбцов, то есть чётному числу  — противоречие с тем, что есть хотя бы один нечётный столбец. Следовательно, нельзя обойтись меньше, чем 100 операциями.

Ответ: За 100 операций.

Критерии оценивания выполнения задания	Баллы
Верное решение.	7
Верный пример для 100 операций с пояснениями.	2
Доказательство минимальности 100	5
Решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	7

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

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

По координатной плоскости, стартуя в начале координат, прыгает кузнечик. Первый прыжок длины один сантиметр направлен вдоль оси ОХ, каждый следующий прыжок на 1 см длиннее предыдущего, и направлен перпендикулярно предыдущему в одну из двух сторон по его выбору. Сможет ли кузнечик после 31-ого прыжка оказаться в начале координат?

Критерии оценивания выполнения задания	Баллы
Верный ответ.	7
Присутствует идея раздельной стратегии прыжков по горизонтали и вертикали.	1
Есть идея разбиения прыжков на четвёрки, за которые он возвращается на исходное положение в данном направление.	2
Решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	7

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

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

По координатной плоскости, стартуя в начале координат, прыгает кузнечик. Первый прыжок длины один см направлен вдоль оси ОХ, каждый следующий прыжок на 1 см длиннее предыдущего, и направлен перпендикулярно предыдущему в одну из двух сторон по его выбору. Сможет ли кузнечик после сотого прыжка оказаться в начале координат?

Критерии оценивания выполнения задания	Баллы
Верный ответ.	7
Присутствует идея раздельного рассмотрения прыжков по горизонтали и вертикали.	1
Отсутствие доказательства того, что при любой расстановке плюсов и минусов между ними сумма длин вертикальных прыжков никогда не будет равна 0.	4
Решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	7

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

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

Имеются таблицы А и В, в ячейки которых вписаны целые числа. С таблицей А можно проделывать следующие действия:

1)  прибавлять к строке другую строку, умноженную на произвольное целое число;

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

Например, если к первой строке таблицы A прибавить вторую строку, умноженную на 4, то получится таблица, изображенная на рисунке справа после слова пример. Можно ли, проделав некоторое количество указанных действий с таблицей А, получить таблицу B? Ответ обоснуйте.

Таблица A

1	0
0	2

Таблица B

0	2
3	0

Таблица C

1	8
0	2

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

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

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

 ·  вверх (робот перемещается на соседнюю клетку сверху);

 ·  вниз (робот перемещается на соседнюю клетку снизу);

 ·  влево (робот перемещается на соседнюю клетку слева);

 ·  вправо (робот перемещается на соседнюю клетку справа).

Если, например, робот выполнит последовательность из четырех команд (вверх, вправо, вниз, влево), то он, очевидно, вернется в исходное положение, т. е. окажется в той же клетке, из которой начал движение. Сколько существует всего различных последовательностей из 4 команд, возвращающих робота в исходное положение?

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

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

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

 ·  вверх (робот перемещается на соседнюю клетку сверху);

 ·  вниз (робот перемещается на соседнюю клетку снизу);

 ·  влево (робот перемещается на соседнюю клетку слева);

 ·  вправо (робот перемещается на соседнюю клетку справа).

Если, например, робот выполнит последовательность из четырех команд (вверх, вправо, вниз, влево), то он, очевидно, вернется в исходное положение, т. е. окажется в той же клетке, из которой начал движение. Сколько существует всего различных последовательностей из 8 команд, возвращающих робота в исходное положение?

Решение.

Для краткости команду влево будем обозначать Л, вправо – П, вверх – В, вниз – Н. Чтобы робот вернулся в исходное положение, необходимо и достаточно, чтобы ему было отдано команд Л столько же, сколько и команд П, а команд В – столько же, сколько и Н. Пусть k – количество команд Л в последовательности. Подсчитаем количество N_k искомых последовательностей для k от 0 до 4.

 ·  $k=0.$ Последовательность состоит только из команд В и Н. Так как их поровну, то на 4 местах из 8 должна быть команда В, а на оставшихся двух – Н. Выбрать 4 места из 8 можно $C_8 в степени 4$ способами. Следовательно, $N_0=C_8 в степени 4 =70;$

 ·  $k=1.$ Последовательность состоит из одной команды Л, одной П, а также трех В и трех Н. Разместить две команды Л и П на 8 позициях можно $C_8 в квадрате умножить на C_2 в степени 1$ способами: $C_8 в квадрате$ – число способов вообще выбрать 2 позиции из 8, $C_2 в степени 1 =2$ – число способов разместить на этих двух позициях команды Л и П. На оставшихся 6 позициях следует разместить 3 команды В, что можно сделать $C_6 в кубе$ способами. Поэтому $N_1=C_8 в квадрате умножить на C_2 в степени 1 умножить на C_6 в кубе =1120;$

 ·  $k=2.$ Здесь две Л, две П а также по 2 команды В и Н. Для Л и П имеем $C_8 в степени 4 умножить на C_4 в квадрате$ вариантов размещения. На оставшихся 4 позициях разместить 2 команды В можно $C_4 в квадрате$ способами. Значит, $N_2=C_8 в степени 4 умножить на C_4 в квадрате умножить на C_4 в квадрате =2520.$

Рассуждая аналогичным образом, можно показать, что $N_3=N_1$ и $N_4=N_0.$ Таким образом, искомое число последовательностей равно $2 умножить на левая круглая скобка N_0 плюс N_1 правая круглая скобка плюс N_2=4900.$

Ответ: 4900.

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

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

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

В алфавите языка альфов три буквы A, Л и Ф. Все слова этого языка можно построить, применяя последовательно следующие правила к любому слову из этого языка:

(1)поменять порядок букв в слове на противоположный;

(2)заменить две последовательные буквы так: ЛA → ФФ, AФ → ЛЛ, ФЛ → AA, ЛЛ → AФ, ФФ → ЛA или AA → ФЛ.

Известно, что ЛЛAФAЛAФФAЛAФФФAЛAФФФФAЛЛ  — это слово из языка альфов. Есть ли в языке альфов слово ЛФAЛФAЛФAЛФAЛAФЛAФЛAФЛAФЛ?

Критерии оценивания выполнения задания	Оценка	Баллы
Полное решение.	+	16
Найдена идея решения. Решение не доведено до конца или содержит ошибки. При этом имеется существенное продвижение в верном направлении.	+/2	8
Решение в целом неверное или незаконченное, но содержит определенное продвижение в верном направлении.	∓	4
Решение не соответствует ни одному критерию, описанному выше.	−/0	0
Максимальный балл	16

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

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

С числом, записанным на доске, разрешается делать следующую операцию: стирать две соседние цифры, сумма которых не превосходит 9, и записывать эту сумму на их место. Изначально было написано 200-значное число 12341234 ... 1234. С числом на доске проделывали указанную операцию до тех пор, пока это не стало невозможно. Какое наибольшее число могло оказаться на доске в результате?

Решение.

Сумма цифр исходного числа

$левая круглая скобка 1 плюс 2 плюс 3 плюс 4 правая круглая скобка умножить на 50=500 .$

Сумма цифр конечного числа такая же.

Разобьём цифры конечного числа на пары: первую со второй, третью с четвёртой, и т. д. Последняя цифра может остаться без пары. В каждой паре сумма цифр не меньше десяти, откуда в числе не может быть больше 100 цифр. Поскольку 100-значные числа превосходят все числа с меньшим количеством знаков, ответ в первую очередь стоит искать среди них.

Если в числе ровно 100 цифр, и сумма цифр в какой-то паре больше 10, то общая сумма цифр больше 500. Значит, в каждом 100-значном числе, которое может у нас получиться, сумма цифр в каждой паре ровно 10.

Обратите внимание: утверждение о том, что в каждом таком числе сумма соседних цифр равна 10 вообще говоря, неверно: может получиться, например, число $376464 \ldots 64,$ в котором это условие нарушается.

В каждой паре нам необходимо максимизировать первую цифру и минимизировать вторую. Поскольку каждая пара цифр получается указанными в условии операциями из 1234, вторая цифра не меньше 4 и наибольший вари ант для каждой пары это 64, откуда мы полу чаем ответ.

Ответ: 64...64  — 100-значное число.

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

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

С числом, записанным на доске, разрешается делать следующую операцию: стирать две соседние цифры, сумма которых не превосходит 9, и записывать эту сумму на их место. Изначально было написано 300-значное число 12 251 225 ... 1225. С числом на доске проделывали указанную операцию до тех пор, пока это не стало невозможно. Какое наибольшее число могло оказаться на доске в результате?

Решение.

Сумма цифр исходного числа

$левая круглая скобка 1 плюс 2 плюс 2 плюс 5 правая круглая скобка умножить на 75=750 .$

Сумма цифр конечного числа такая же.

Разобьём цифры конечного числа на пары: первую со второй, третью с четвёртой, и т. д. Последняя цифра может остаться без пары. В каждой паре сумма цифр не меньше десяти, откуда в числе не может быть больше 150 цифр. Поскольку 150-значные числа превосходят все числа с менышим количеством знаков, ответ в первую очередь стоит искать среди них.

Если в числе ровно 150 цифр, и сумма цифр в какой-то паре больше 10, то общая сумма цифр больше 750. Значит, в каждом 150-значном числе, которое может у нас получиться, сумма цифр в каждой паре ровно 10.

Обратите внимание: утверждение о том, что в каждом таком числе сумма соседних цифр равна 10 вообще говоря, неверно: может получиться, например, число $375 555 \ldots 55,$ в котором это условие нарушается.

В каждой паре нам необходимо максимизировать первую цифру и минимизировать вторую. Поскольку каждая пара цифр полу чается указанными в условии операциями из 1225, вторая цифра не менышее 5 и наибольший вариант для каждой пары это 55, откуда мы полу чаем ответ.

Ответ: 55...55  — 100-значное число.

Аналоги к заданию № 744: 742 743 Все

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

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

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

Решение.

Назовём n-ой фазой несколько подряд идущих операций, который при меняются к числам, равным n. Если таких операций не было, будем говорить, что данная фаза состоит из нуля операций. Начинается всё с нулевой фазы.

В течение одной фазы никакое число не может увеличится больше, чем на 4. Действительно, если мы увеличили само число, то ни к нему, ни к его соседям не может быть применена наша операция в течение этой фазы ни до, не после, поскольку число, увеличенное на один в некоторой фазе, не может оказаться минимальным в течение той же самой фазы. Среди соседей числа можно выбрать не больше 4 не соседних между собой, значит, действительно мы можем увеличить число не больше, чем на 4 за одну фазу.

Рассмотрим первые, четвёртые, седьмые и десятые клетки в первой, четвёртой, седьмой и десятой строках таблицы, всего 16 штук. Заметим, что никакая операция не затрагивает две из них. Значит, чтобы сменилось n фаз, надо совершить хотя бы 16n операций. Важно! Мы не можем утверждать, что одна фаза длится хотя бы 16 операций, так как некоторые из наших чисел могли быть увеличены на предыдущих фазах.

Значит, у нас прошло не более 5 фаз и в каждой никакое число не могло увеличится более, чем на 4. Следовательно, за 80 операций никакое число не могло стать больше, чем 20.

Пример строится следующим образом: рассмотрим вторые, четвёртые, седьмые и десятые клетки во второй, четвёртой, седьмой и десятой строках таблицы, всего 16 штук. Будем применять операции только к ним. Операции, применённые к одной из этих клеток, не затрагивают остальные 15, и при этом после применения операций ко в сем 16 клеткам все числа в таблице увеличиваются хотя бы на 1. При этом число в третьей клетке третьей строки будет каждую фазу увеличиваться на 4.

Разумеется, пример не единственный.

Ответ: 20.

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

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

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

Решение.

В течение одной фазы никакое число не может увеличится больше, чем на 4. Действительно, если мы увеличили само число, то ни к нему, ни к его соседя м не может быть применена наша операция в течение этой фазы ни до, не после, поскольку число, увеличенное на один в некоторой фазе, не может оказаться минимальным в течение той же самой фазы. Среди соседей числа можно выбрать не больше 4 не соседних между собой, значит, действительно мы можем увеличить число не больше, чем на 4 за одну фазу.

Рассмотрим первые, четвёртые и седьмые клетки в первой, четвёртой и седьмой строках таблицы, всего 9 штук. Заметим, что никакая операция не затрагивает две из них. Значит, чтобы сменилось n фаз, надо совершить хотя бы 9n операций. Важно! Мы не можем утверждать, что одна фаза длится хотя бы 9 операций, так как некоторые из наших чисел могли быть увеличены на предыдущих фазах.

Значит, у нас прошло не более 10 фаз и в каждой никакое число не могло увеличится более, чем на 4. Следовательно, за 90 операций никакое число не могло стать больше, чем 40.

Пример строится следующим образом: рассмотрим вторые, четвёртые и шестые клетки во второй, четвёртой и шестой строках таблицы, всего 9 штук. Будем применять операции только к ним. Операции, применённые к одной из этих клеток, не затрагивают остальные 8, и при этом после применения операций ко в см 9 клеткам все числа в таблице увеличиваются хотя бы на 1. При этом число в третьей клетке третьей строки будет каждую фазу увеличиваться на 4.

Разумеется, пример не единственный.

Ответ: 40.

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

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

На доске написано три числа. За один ход разрешается стереть любые два числа a и b и вместо них написать числа $дробь: числитель: a, знаменатель: b конец дроби$ и b². Можно ли с помощью таких операций из тройки $левая круглая скобка дробь: числитель: 1, знаменатель: корень из: начало аргумента: 3 конец аргумента конец дроби ,1,1 плюс корень из: начало аргумента: 3 конец аргумента правая круглая скобка$ получить тройку $левая круглая скобка корень из: начало аргумента: 3 конец аргумента ,3, дробь: числитель: 1, знаменатель: 3 плюс корень из: начало аргумента: 3 конец аргумента конец дроби правая круглая скобка$ ?

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

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

Вдоль окружности расположено n монет, каждая лежит орлом или решкой вверх. Если две соседние монеты лежат одинаково (обе орлом или обе решкой), разрешается обе перевернуть. Сколько имеется вариантов расположения монет, которые нельзя получить друг из друга, применяя такие операции?

Решение.

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

Перейдем теперь к случаю чётного n. Научимся переводить расположения монет в конфигурацию как можно более простого вида, а затем посчитаем количество таких простых конфигураций, которые нельзя получить друг из друга. Отметим на окружности точку возле любой из монет. Разобьём монеты на группы подряд идущих монет, имеющих одинаковую ориентацию. Будем переворачивать группы, в которых чётное число монет, до тех пор, пока такие группы не исчезнут или не останется ровно одна группа. Если осталось несколько групп, то они все нечётны. Отметим, что если в какой-то группе есть хотя бы три монеты, то две из них можно перекинуть в соседнюю группу. Действительно, это можно сделать заменами

$\mathrmOP левая квадратная скобка \mathrmOO правая квадратная скобка \mathrmO arrow \mathrmOPPPO. \qquad левая круглая скобка * правая круглая скобка$

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

Покажем, что все остальные конфигурации нельзя получить друг из друга. Действительно, наша операция не меняет разность количества орлов на чётных местах и количества орлов на нечётных местах. Когда большая группа состоит из одного орла, т. е. когда все орлы стоят на нечётных местах, а решки на чётных, эта разность равна $дробь: числитель: n, знаменатель: 2 конец дроби .$ Увеличение количества орлов в большой группе уменьшает эту разность на 1, поэтому все разности от 0 до $дробь: числитель: n, знаменатель: 2 конец дроби .$ возможны. Аналогично, когда большая группа состоит из решек получатся разности от −1 до $минус дробь: числитель: n, знаменатель: 2 конец дроби .$ Итого получаем $n плюс 1$ различную конфигурацию.

Ответ: 2 варианта для нечётных n и $n плюс 1$ вариант для чётных n.

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

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

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

а)  если он увеличивает на 2 количество пятерок, то при этом количество двоек уменьшится на 1;

б)  если он увеличивает на 1 количество пятерок, то количество двоек увеличивается на 2;

в)  если он уменьшает на 2 количество пятерок, то количество двоек увеличивается на 1;

г)  если он уменьшает на 1 количество пятерок, то количество двоек уменьшается на 2.

Может ли он, совершая такие операции, превратить свои 3 пятерки и 30 двоек в 30 пятерок и 3 двойки?

Критерии проверки:

Вид погрешности или ошибки	Отметка в работе	Баллы
Каждая задача оценивается по 10-балльной шкале и снабжается отметкой в работе 0, −, ∓, ±, + в соответствии с критериями.
Решение задачи верное, выбран рациональный путь решения	+	10
Решение верное, но путь не рационален или имеются один  — три недочета или негрубая ошибка	+	9
Решение верное, но путь не рационален и имеются один  — три недочета или негрубая ошибка	±	7−8
Ход решения верный, но есть несколько негрубых ошибок или решение не завершено	∓	5−6
Допущены грубые ошибки, но ответ получен (неверный)	∓	3−4
Допущены грубые ошибки и ответ не получен либо решение лишь начато, то что начато  — без ошибок	−	2
Решение начато, но продвижение ничего не дает для результата	−	1
Задача не решилась	0	0
Недочеты: незначительные (непринципиальные) арифметические ошибки. Негрубые ошибки: технические ошибки в применении формул и теорем, не влияющие на смысл решения; необоснованность логических (верных) выводов. Грубые ошибки:    I.  Логические, приводящие к неверному заключению.   II.  Арифметические ошибки, искажающие смысл ответа. III.  Неверный чертеж в геометрических задачах. IV.  Принципиальные ошибки в применении элементарных формул и теорем.

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

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

Назовем «уголком» квадрат 2 × 2, из которого вырезана одна клетка. В каждой клетке таблицы 100 × 100 стоит натуральное число. За одну операцию разрешается взять три клетки, расположенные в виде «уголка» и прибавить к каждому из чисел в этих клетках по единице. Всегда ли с помощью таких операций можно сделать все числа в таблице равными?

Решение.

Разобьем таблицу на 2500 квадратиков 2 × 2. Несложно видеть, что в каждом квадратике можно сделать числа равными (в квадратике 2 × 2. прибавление единиц к числам из уголка соответствует вычитанию единицы из одного числа с последующим увеличением всех чисел квадрата на один, а такими вычитаниями легко сделать числа равными). Кроме того, четырьмя операциями все числа в квадратике можно увеличить на три. Поэтому достаточно добиться того, чтобы числа из разных квадратиков давали одинаковый остаток от деления на три.

Дальше будем смотреть только на остатки. Возьмем два соседних квадратика. С помощью четырех операций можно увеличить все числа в одном квадратике на единицу, a все числа в другом квадратике  — на двойку. Поэтому можно остаток чисел в одном квадратике увеличить на 1, а в другом  — уменьшить на 1. Пусть остаток суммы чисел во всей таблице равен r. Покажем, как добиться того, чтобы все числа в таблице имели остаток r. Последовательно слева направо пройдем по парам квадратиков сначала в верхней строке и получим во всех квадратиках, кроме самого правого, остаток r. Проделаем те же действия с остальными строками. Наконец, двигаясь сверху вниз, последовательно обработаем правый столбец. В результате всех квадратиках, кроме правого нижнего, будут числа, дающие остаток r, а в правом нижнем  — числа, дающие остаток x. Тогда сумма чисел во всей таблице дает остаток

$левая круглая скобка 50 в квадрате минус 1 правая круглая скобка умножить на 4 r плюс 4 x \equiv x левая круглая скобка \bmod 3 правая круглая скобка ,$

поэтому $x=r.$

Ответ: всегда.

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

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

На доске вначале было записано n чисел: 1, 2, ..., n. Разрешается стереть любые два числа на доске, а вместо них записать модуль их разности. Какое наименьшее число может оказаться на доске после $левая круглая скобка n минус 1 правая круглая скобка$ таких операций а) при $n = 111;$ б) при $n = 110?$

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

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

Есть бесконечная в одну сторону клетчатая полоска, клетки которой пронумерованы натуральными числами, и мешок с десятью камнями. В клетках полоски камней изначально нет. Можно делать следующее:

— перемещать камень из мешка в первую клетку полоски или обратно;

— если в клетке с номером i лежит камень, то можно переложить камень из мешка в клетку с номером $i плюс 1$ или обратно.

Можно ли, действуя по этим правилам, положить камень в клетку с номером 1000?

Решение.

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

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

База индукции: $n=1 .$ Очевидно.

Переход индукции. Допустим, мы доказали, что при помощи запаса в n камней можно положить камень во все клетки до $левая круглая скобка 2 в степени левая круглая скобка n правая круглая скобка минус 1 правая круглая скобка$ -й. Пусть теперь есть n черных камней и один красный камень. Будем действовать следующим образом:

1)  не вынимая красный камень из мешка, добьемся того, чтобы в $левая круглая скобка 2 в степени левая круглая скобка n правая круглая скобка минус 1 правая круглая скобка$ -й клетке оказался черный камень. Это можно сделать по предположению индукции;

2)  положим красный камень в 2ⁿ-ю клетку;

3)  проведем операции как в пункте 1), но противоположные и в обратном порядке. Понятно, что красный камень не помешает это сделать. В конце окажется, что все черные камни снова лежат в мешке, а на полоске ровно один камень  — красный камень в клетке 2ⁿ. Договоримся, что далее мы красный камень убирать не будем;

4)  клетки с номерами от $2 в степени левая круглая скобка n правая круглая скобка плюс 1$ до $2 в степени левая круглая скобка n плюс 1 правая круглая скобка минус 1$ образуют полоску длиной $2 в степени левая круглая скобка n правая круглая скобка минус 1.$ К ней применимо предположение индукции для n камней, так как красный камень позволяет совершать операции с самой левой клеткой этой полоски. Поэтому можно положить камень в последнюю клетку.

Таким образом, имея запас в 10 камней, можно положить камень во все клетки с номерами от 1 до $1023=2 в степени левая круглая скобка 10 правая круглая скобка минус 1.$

Ответ: да.

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

На самом деле достаточно полоски длиной 1000. Действительно, заметим, что среди клеток с номерами от 1000 до 1023 самый первый камень будет положен в клетку с номером 1000. То есть, чтобы положить камень в 1000-ю клетку, клетки с номерами от 1001 до 1023 использовать не обязательно, а значит, при запасе в 10 камней можно положить камень в последнюю клетку полоски длиной 1000.

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

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

На доске записаны 10 чисел: 1, 2, 3, 4, 4, 5, 5, 11, 12, 13. С ними можно производить операции двух типов: либо из любых девяти из них вычесть 1, а к оставшемуся прибавить 9, либо наоборот, из одного вычесть 9, а к остальным прибавить по 1. При этом отрицательные числа получать нельзя. Можно ли, применив несколько таких операций, сделать все десять чисел разными?

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

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

По кругу записаны 32 числа a₁, a₂, ..., a₃₂, каждое из которых равно −1 или 1. За одну операцию каждое число a_n, n  =  1, 2, ..., 32 заменяют на произведение a_na_n+1 его и следующего за ним по циклу числа, при этом индексы рассматриваются циклически, a₃₃  =  a₁, a₃₄  =  a₂ и так далее. Докажите, что для любого начального набора чисел a₁, a₂, ..., a₃₂ после некоторого конечного числа операций всегда получится набор из 32 единиц. Найдите наименьшее число N операций такое, что после применения N операций из любого начального набора чисел всегда получится набор из 32 единиц.

Решение.

Покажем индукцией по n, что, если по кругу записаны 2ⁿ чисел, то ответ задачи равен 2ⁿ. База индукции $n=1$ рассматривается несложно: либо $левая фигурная скобка 1, минус 1 правая фигурная скобка arrow левая фигурная скобка минус 1, минус 1 правая фигурная скобка arrow левая фигурная скобка 1, 1 правая фигурная скобка ,$ либо $левая фигурная скобка минус 1, минус 1 правая фигурная скобка arrow левая фигурная скобка 1, 1 правая фигурная скобка ,$ в любом случае двух операций всегда достаточно, а меньше  — не всегда.

Шаг индукции. Пусть по кругу записаны $2 в степени левая круглая скобка n плюс 1 правая круглая скобка$ чисел и утверждение верно для любых 2ⁿ плюс-минус единиц по кругу. Рассмотрим отдельно множества А, из 2ⁿ чисел, стоящих на местах с нечётными индексами и B  — из 2ⁿ чисел стоящих на местах с чётными индексами, Заметим, что после выполнения двух операций каждое число a_k, $k=1, 2, \ldots, 32$ заменится на произведение

$левая круглая скобка a_k a_k плюс 1 правая круглая скобка левая круглая скобка a_k плюс 1 a_k плюс 2 правая круглая скобка =a_k a_k плюс 2,$

так как $a_k плюс 1 в квадрате =1.$ Отсюда следует, что, в результате выполнения двух операций на исходном множестве из $2 в степени левая круглая скобка n плюс 1 правая круглая скобка$ чисел множества А и В меняются так, как если бы на каждом из них было выполнено по одной операции. По предположению индукции, для того, чтобы получить вместо множеств А и В множества из одних единиц, достаточно 2ⁿ операций, следовательно, чтобы получить все единицы из исходного множества, достаточно вдвое большего числа операций, то есть $2 умножить на 2 в степени левая круглая скобка n правая круглая скобка =2 в степени левая круглая скобка n плюс 1 правая круглая скобка$ операций. Примером множества чисел, для которого необходимо ровно $2 в степени левая круглая скобка n плюс 1 правая круглая скобка$ операций, является множество из 31 единицы и одной минус единицы. После двух операций оно даст аналогичные множества чисел А и В, для которых, по индукции, нужно ровно 2ⁿ операций, значит, для исходного множества их нужно ровно $2 умножить на 2 в степени левая круглая скобка n правая круглая скобка =2 в степени левая круглая скобка n плюс 1 правая круглая скобка .$ При количестве чисел $32=2 в степени левая круглая скобка 5 правая круглая скобка$ число необходимых операций рано 32.

Ответ: 32.

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

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

$a_1$	$b_1$
$c_1$	$d_1$

$a_2$	$b_2$
$c_2$	$d_2$