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

Поиск
?

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

Всего: 198 1–20 | 21–40 | 41–60 | 61–80 …

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

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

Код сейфа состоит из пяти идущих подряд цифр. Василий Петрович положил деньги в сейф, а когда захотел их забрать, выяснилось, что он забыл код. Он только помнил, что в коде были числа 21 и 16. Какое наименьшее количество пятизначных номеров необходимо перебрать, чтобы наверняка открыть сейф?

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

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

В детском саду каждому ребёнку выдали по три карточки, на каждой из которых написано либо «МА», либо «НЯ». Оказалось, что слово «МАМА» из своих карточек могут сложить 20 детей, слово «НЯНЯ»  — 30 детей, а слово «МАНЯ»  — 40 детей. У скольких детей все три карточки были одинаковы?

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

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

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

Сначала шарики были разложены по нескольким белым и чёрным коробкам так, что в каждой белой было по 31 шарику, а в каждой чёрной  — по 26 шариков. Затем принесли ещё три коробки и разложили шарики так, что в каждой белой коробке стало по 21 шарику, а в каждой чёрной  — по 16 шариков. Можно ли принести ещё несколько коробок и разложить шарики так, чтобы в каждой белой коробке стало по 15 шариков, а в каждой чёрной  — по 10 шариков?

Критерии оценивания выполнения задания	Баллы
Верное решение.	7
Замечено, что, если бы требуемое в условии было возможно, то общее число шариков делилось бы на 5.	1
Замечено, что остатки всех чисел 31, 26, 21 и 16 от деления на 5 равны 1.	1
Замечено, что количество коробок в первом и втором случаях делится на 5.	3
Замечено, что этого не может быть, потому что количества коробок в первом и втором случаях отличаются на 3.	2
Решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	7

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

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

Каждый член партии доверяет пяти однопартийцам, но никакие двое не доверяют друг другу. При каком минимальном размере партии такое возможно?

Не забудьте показать, что при указанном Вами размере партии это действительно возможно, а при меньших  — нет.

Решение.

Будем представлять партию в виде ориентированного графа: партийцев  — в виде вершин, а если партиец A доверяет партийцу B, то соединим вершину A с B ребром со стрелкой, направленной от A к B. Условие того, что никакие два партийца не доверяют друг другу, эквивалентно условию того, что никакие две вершины не соединены двумя противоположно направленными ориентированными рёбрами. Будем называть это условием одного ребра. Построим пример партии из 11 человек, удовлетворяющей условию задачи. Разместим 11 человек в вершинах правильного 11-угольника A₁ . . . A₁₁. Для каждой вершины A_i направим по ориентированному ребру из неё в каждую из пяти вершин, следующих за ней по часовой стрелке. Утверждается, что условие одного ребра выполнено. Действительно, для каждого ориентированного ребра, идущего от некоторой вершины A_i к A_j, имеется не более 4 вершин, следующих от A_i к A_j в направлении по часовой стрелке. А остальных вершин 11-угольника, отличных от A_i, A_j и вышеупомянутых последовательных вершин между ними не меньше, чем 11 − 6 = 5, и они идут последовательно от A_j к A_i по часовой стрелке «с другой стороны». Предположим противное: условие одного ребра не выполнено, то есть некоторая пара вершин A_i и A_j соединена двумя противоположно направленными рёбрами. Тогда в силу предыдущего, имеется два набора последовательных вершин, каждый из не более, чем 4 вершин: вершины одного набора идут от A_i к A_j по часовой стрелке, а вершины другого  — от A_j к A_i по часовой стрелке. Следовательно, эти наборы не пересекаются, и вместе с вершинами A_i и A_j (итого не более, чем 4 + 4 + 2 = 10 вершин) они покрывают все 11 вершин 11-угольника. Полученное противоречие доказывает, что условие одного ребра выполнено.

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

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

Тем самым,

$5n меньше или равно дробь: числитель: n левая круглая скобка n минус 1 правая круглая скобка , знаменатель: 2 конец дроби равносильно дробь: числитель: левая круглая скобка n минус 1 правая круглая скобка , знаменатель: 2 конец дроби больше или равно 5 равносильно n больше или равно 11$

что и требовалось доказать.

Ответ: 11.

Критерии оценивания выполнения задания	Баллы
Приведено построение партии из 11 человек и доказано, что меньше нельзя.	20
Приведено построение партии из 11 человек, но не доказано, что меньше нельзя.	14
Доказано, что меньше 11 сделать нельзя, но пример не построен.	12
Решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	20

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

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

В каждой клетке таблицы 5 на 5 записано по одной букве так, что в любой строке и в любом столбце не больше трёх различных букв. Какое наибольшее число различных букв может быть в такой таблице?

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

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

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

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

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

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

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

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

Критерии оценивания выполнения задания	Баллы
Приведено полное решение (в т. ч. для n-угольника).	20
Незначительные пробелы в решении (в т. ч. не доказано, что можно сопоставлять треугольники и n-угольники).	15
Серьезные пробелы в доказательстве.	10
Идея о разделении треугольников на 4 типа.	5
Решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	20

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

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

За круглым столом расселись 15 мальчиков и 20 девочек. Оказалось, что количество пар сидящих рядом мальчиков в полтора раза меньше, чем количество пар сидящих рядом девочек. Найти количество пар мальчик  — девочка, сидящих рядом.

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

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

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

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

Решение.

Запишем все числа от 1 до 100 слева направо по порядку: 1, 2, 3, 4, ..., 99, 100, разобьём на 50 пар соседних: 1 и 2, 3 и 4, …, 99 и 100, и в каждой паре числа поменяем местами: 2, 1, 4, 3, ..., 100, 99. Докажем, что полученная перестановка удовлетворяет условию задачи.

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

б)  Заметим также, что сумма чётного числа последовательных натуральных чисел не делится на их количество, а сумма нечётного числа последовательных натуральных чисел делится на их количество. Действительно, найдём сумму последовательных чисел, первое из которых равно a + 1, получим

$a плюс 1 плюс a плюс 2 плюс \ldots плюс a плюс n = na плюс дробь: числитель: n левая круглая скобка n плюс 1 правая круглая скобка , знаменатель: 2 конец дроби .$

Тут первое слагаемое всегда делится на n, а второе, только когда n + 1 чётно.

в)  Если из переставленных чисел выбрать чётное число идущих подряд, то в силу замечания а) их сумма равна сумме номеров их мест и не делится на их количество в силу б). Если же из переставленных чисел выбрать нечётное число идущих подряд, то в силу замечания а) несложно заметить, что их сумма на 1 больше или меньше суммы номеров их мест, которая делится на их количество в силу б). Значит, сумма самих чисел не может делится на их количество.

Ответ: 2, 1, 4, 3, ..., 100, 99.

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

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

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

Трое играют в настольный теннис, причем игрок, проигравший партию, уступает место игроку, не участвовавшему в ней. В итоге оказалось, что первый игрок сыграл 21 партию, а второй  — 10. Сколько партий сыграл третий игрок?

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

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

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

Назовём змейкой в выпуклом n-угольнике незамкнутую, не самопересекающуюся ломаную из n − 1 звеньев, множество вершин которой совпадает с множеством всех вершин n-угольнике. Найти число различных змеек в n-угольнике. (Змейки равны, если совпадают, как геометрические места точек n-угольника. Например, число змеек в треугольнике равно 3).

Решение.

1)   Докажем по индукции, что число змеек, одним из концов которых является фиксированная вершина А, равно $2 в степени левая круглая скобка n минус 2 правая круглая скобка .$ База при $n=3$ очевидна. Для произвольного n, имеем две возможности для звена с концом А  — это стороны АВ и АС n-угольника, где В и С  — соседние с А вершины. Если первое звено АХ отлично от АВ и АС, то диагональ АХ делит n-угольник на два невырожденных многоугольника с более, чем тремя вершинами в каждом, считая А и Х. Тогда второе звено змейки и все следующие, ввиду её несамопересекаемости, будут лежать в одном из них и не смогут содержать вершину другого, отличную от А и Х, что противоречит условию. Пусть первым звеном является АВ, тогда оставшиеся $n минус 2$ звена змейки являются змейкой с началом В в $n минус 1$ -угольнике, получающемся из исходного удалением треугольника АВС. По индукционному предположению, таких змеек будет $2 в степени левая круглая скобка n минус 3 правая круглая скобка$   — это в точности все змейки с крайним звеном АВ. Аналогично, змеек с крайним звеном АС тоже будет $2 в степени левая круглая скобка n минус 3 правая круглая скобка ,$ поэтому общее число змеек, одним из концов которых является А, будет $2 в степени левая круглая скобка n минус 2 правая круглая скобка .$

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

Ответ: $n умножить на 2 в степени левая круглая скобка n минус 3 правая круглая скобка .$

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

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

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

На доске написаны 10 натуральных чисел, среди которых могут быть равные, причём квадрат каждого из них делит сумму всех остальных. Какое наибольшее количество различных чисел может быть среди выписанных?

Решение.

Пример для четырёх различных чисел: 1, 1, 1, 2, 2, 3, 5, 5, 5, 5.

Пусть среди выписанных чисел ровно $n\geqslant2$ различных, максимальное из которых мы обозначим за x, а сумму всех чисел  — за S. Тогда сумма всех чисел, кроме максимального, не превосходит

$левая круглая скобка 9 минус n правая круглая скобка x плюс x минус 1 плюс x минус 2 плюс \ldots плюс x минус левая круглая скобка n минус 1 правая круглая скобка =9 x минус дробь: числитель: n левая круглая скобка n минус 1 правая круглая скобка , знаменатель: 2 конец дроби ,$

что не меньше $x в квадрате ,$ так как делится на него. Следовательно, неравенство $x в квадрате минус 9 x плюс дробь: числитель: n левая круглая скобка n минус 1 правая круглая скобка , знаменатель: 2 конец дроби меньше или равно 0$   — имеет решения в натуральных числах, и $дробь: числитель: 9 минус корень из: начало аргумента: 81 минус 2 n левая круглая скобка n минус 1 правая круглая скобка конец аргумента , знаменатель: 2 конец дроби меньше или равно x меньше или равно дробь: числитель: 9 плюс корень из: начало аргумента: 81 минус 2 n левая круглая скобка n минус 1 правая круглая скобка конец аргумента , знаменатель: 2 конец дроби .$ Положительность дискриминанта даёт нам $n меньше или равно 6,$ и $x меньше или равно 8,$ $S минус x меньше или равно 72 минус 1=71.$ Рассмотрим случаи каждого максимального числа отдельно.

а)  Пусть $x=8,$ тогда $S минус x меньше или равно 71$ и делится на 64, поэтому $S=72.$ Тогда $72 минус k$ делится на $k в квадрате ,k меньше или равно 7$ только при $k=1,$ поэтому в данном случае $n меньше или равно 2.$

б)  Пусть $x=7,$ тогда $S минус x меньше или равно 62$ и делится на 49, поэтому $S=56.$ Тогда $56 минус k$ делится на $k в квадрате ,k меньше или равно 6$ только при $k=1,$ поэтому и в данном случае $n меньше или равно 2.$

в)  Пусть $x=6,$ тогда $S минус x меньше или равно 53$ и делится на 36, поэтому $S=42.$ Тогда $42 минус k$ делится на $k в квадрате ,k\leqslant5$ только при $k=1,2,$ поэтому в данном случае $n меньше или равно 3.$

г)  Пусть $x=5,$ тогда $S минус x\leqslant44$ и делится на 25, поэтому $S=30.$ Тогда $30 минус k$ делится на $k в квадрате ,k меньше или равно 4$ только при $k=1,2,3,$ поэтому в данном случае $n\leqslant4.$ Искомое множество должно содержать 10 натуральных чисел с суммой 30, среди которых должны быть 1, 2, 3, 5. Теперь уже несложно построить пример для $n=4:$ 1, 1, 1, 2, 2, 3, 5, 5, 5, 5. Этот пример не единственный.

Ответ: Четыре.

Критерии оценивания выполнения задания	Баллы
Верное решение.	7
Доказано, что $n меньше или равно 4$ .	5
Пример для $n=4$ .	2
Оценка $n\le6$ .	2
Решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	7

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

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

Последовательность чисел τ (1), τ (2), ..., τ (n) называется перестановкой длины n, если каждое из чисел 1, 2, ..., n встречается в этой последовательности ровно один раз. Например, τ (1)  =  3, τ (2)  =  2, τ (3)  =  1  — перестановка длины 3. Найдите все n, для которых найдётся перестановка τ (1), τ (2), ..., τ (n), удовлетворяющая четырём условиям:

• Числа τ (i) − i для всех i от 1 до n включительно имеют попарно различные остатки от деления на n.

• Числа τ (i) − 2i для всех i от 1 до n включительно имеют попарно различные остатки от деления на n.

• Числа τ (i) − 3i для всех i от 1 до n включительно имеют попарно различные остатки от деления на n.

• Числа τ (i) − 4i для всех i от 1 до n включительно имеют попарно различные остатки от деления на n.

Решение.

Будем решать чуть обобщённую задачу, а именно: зафиксируем натуральное m и будем искать все n, для которых в любом из m множеств $левая фигурная скобка \tau левая круглая скобка i правая круглая скобка минус j i | 1 меньше или равно i меньше или равно n правая фигурная скобка$ все остатки различны. Индекс j пробегает значения $1 меньше или равно j меньше или равно m.$

Для начала докажем, что все n, не делящиеся на простые числа меньшие либо равные m + 1, подходят. Рассмотрим перестановку τ: i → (m + 1)i mod n (здесь мы позволим себе вольность считать, что остатки идут от 1 до n, а не от 0 до n – 1 как обычно). Поскольку n взаимно просто с m + 1, остатки не повторяются. Значит, по принципу Дирихле, каждый остаток встречается ровно один раз. Аналогично, каждый остаток встречается ровно один раз и в каждом из множеств

$левая фигурная скобка \tau левая круглая скобка i правая круглая скобка минус i \mid 1 меньше или равно i меньше или равно n правая фигурная скобка ,$ $левая фигурная скобка \tau левая круглая скобка i правая круглая скобка минус 2 i \mid 1 меньше или равно i меньше или равно n правая фигурная скобка ,$ $\ldots,$ $левая фигурная скобка \tau левая круглая скобка i правая круглая скобка минус m i \mid 1 меньше или равно i меньше или равно n правая фигурная скобка .$

Докажем, что перестановки с требуемыми свойствами не существует если $n \vdots p$ и $p меньше или равно m плюс 1.$ Предположим обратное, зафиксируем наименьшее такое p и обозначим через k максимальную степень p, на которую делится n.

Сперва рассмотрим случай p  =  2. Заметим что

$1 плюс 2 плюс умножить на s плюс n = дробь: числитель: n левая круглая скобка n плюс 1 правая круглая скобка , знаменатель: 2 конец дроби ,$

формула легко доказывается по индукции. Тогда сумма n чисел, дающих остатки 1, 2, ..., n, сравнима с $дробь: числитель: n левая круглая скобка n плюс 1 правая круглая скобка , знаменатель: 2 конец дроби$ по модулю n. Посчитаем двумя способами остаток суммы $\sum_i=1 в степени n \tau левая круглая скобка i правая круглая скобка минус i$ по модулю n. С одной стороны, все слагаемые дают разные остатки, значит, сумма $дробь: числитель: n левая круглая скобка n плюс 1 правая круглая скобка , знаменатель: 2 конец дроби .$ С другой стороны, по тем же соображениям у суммы отдельно $\sum_i=1 в степени n \tau левая круглая скобка i правая круглая скобка$ такой остаток, и у суммы $\sum_i=1 в степени n i$ такой же, значит, их разность имеет остаток 0. Заметим, что

$дробь: числитель: n левая круглая скобка n плюс 1 правая круглая скобка , знаменатель: 2 конец дроби \not \equiv 0 mod n,$

поскольку n + 1 нечетное а $дробь: числитель: n, знаменатель: 2 конец дроби$ не делится на 2^k. Предположение приведено к противоречию.

Попробуем получить решение в том же духе для произвольного p. Небольшой догадкой, которую нужно сделать на этом этапе решения, будет то, что считать надо сумму p  — 1-х степеней. Слабой подсказкой в эту сторону является то, что p – 1  =  1 для двойки p  =  2, и в этом же случае сработал подсчет суммы первых степеней. Гораздо более сильной  — то что p  — 1-е степени по модулю p ведут себя просто  — это 1 если число не равно нулю, 0, если равно.

Итак, далее считаем что $p больше 2,$ обозначим

$S левая круглая скобка m правая круглая скобка =\sum_i=1 в степени m i в степени левая круглая скобка p минус 1 правая круглая скобка .$

Лемма 1. Заметим, что $S левая круглая скобка n правая круглая скобка \vdots p в степени левая круглая скобка k минус 1 правая круглая скобка$ и $S левая круглая скобка n правая круглая скобка / \vdots p в степени k .$ Достаточно доказать этот факт для $n = p в степени k ,$ поскольку

$S левая круглая скобка n правая круглая скобка \equiv дробь: числитель: n, знаменатель: p в степени k конец дроби S левая круглая скобка p в степени k правая круглая скобка mod p в степени k .$

Для S(p^k) проведем индукцию по k. При k  =  1 утверждение следует из Малой теоремы Ферма: среди слагаемых p – 1 единица и один ноль. Пусть доказано для k, докажем для k + 1. Тогда

$S левая круглая скобка p в степени левая круглая скобка k плюс 1 правая круглая скобка правая круглая скобка =\sum_i=1 в степени левая круглая скобка p в степени левая круглая скобка k плюс 1 правая круглая скобка правая круглая скобка i в степени левая круглая скобка p минус 1 правая круглая скобка =\sum_i=1 в степени левая круглая скобка p в степени k правая круглая скобка \sum_j=0 в степени левая круглая скобка p минус 1 правая круглая скобка левая круглая скобка i плюс jp в степени k правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка \equiv \sum_i=1 в степени левая круглая скобка p в степени k правая круглая скобка \sum_j=0 в степени левая круглая скобка p минус 1 правая круглая скобка левая круглая скобка i в степени левая круглая скобка p минус 1 правая круглая скобка плюс левая круглая скобка p минус 1 правая круглая скобка jp в степени k i в степени левая круглая скобка p минус 2 правая круглая скобка правая круглая скобка \equiv$ $S левая круглая скобка p в степени левая круглая скобка k плюс 1 правая круглая скобка правая круглая скобка =\sum_i=1 в степени левая круглая скобка p в степени левая круглая скобка k плюс 1 правая круглая скобка правая круглая скобка i в степени левая круглая скобка p минус 1 правая круглая скобка =$
$=\sum_i=1 в степени левая круглая скобка p в степени k правая круглая скобка \sum_j=0 в степени левая круглая скобка p минус 1 правая круглая скобка левая круглая скобка i плюс jp в степени k правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка \equiv \sum_i=1 в степени левая круглая скобка p в степени k правая круглая скобка \sum_j=0 в степени левая круглая скобка p минус 1 правая круглая скобка левая круглая скобка i в степени левая круглая скобка p минус 1 правая круглая скобка плюс левая круглая скобка p минус 1 правая круглая скобка jp в степени k i в степени левая круглая скобка p минус 2 правая круглая скобка правая круглая скобка \equiv$

$\equiv \sum_i=1 в степени левая круглая скобка p в степени k правая круглая скобка левая круглая скобка i в степени левая круглая скобка p минус 1 правая круглая скобка p плюс дробь: числитель: p левая круглая скобка p минус 1 правая круглая скобка в квадрате , знаменатель: 2 конец дроби p в степени k i в степени левая круглая скобка p минус 2 правая круглая скобка правая круглая скобка \equiv pS левая круглая скобка p в степени k правая круглая скобка .$

Все сравнения по модулю p^k+1.

Теперь для каждого j: $1 меньше или равно j меньше или равно p минус 1$ рассмотрим сумму

$S_j левая круглая скобка n правая круглая скобка =\sum_1 меньше или равно i меньше или равно n левая круглая скобка \tau левая круглая скобка i правая круглая скобка минус ij правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка .$

Раскроем все степени по биному Ньютона, получим слагаемые вида

$левая круглая скобка \begin{align p минус 1s \endalign правая круглая скобка левая круглая скобка минус j правая круглая скобка в степени s \sum_1 меньше или равно i меньше или равно n\tau левая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 минус s правая круглая скобка умножить на i в степени s .$

С другой стороны, все члены в S_j(n)  — это переставленные в каком-то порядке остатки по модулю n членов суммы S(n), то есть $S_j левая круглая скобка n правая круглая скобка \equiv S левая круглая скобка n правая круглая скобка mod n.$ Итак, мы хотим найти такой набор α_j, чтобы домножив на него сравнимости $S_j левая круглая скобка n правая круглая скобка \equiv S левая круглая скобка n правая круглая скобка$ и сложив мы смогли бы прийти к противоречию. Сделать это поможет вторая лемма.

Лемма 2. Существуют такие целые числа α₁, ..., α_p – 1, что

$альфа _11 плюс альфа _22 плюс \ldots плюс альфа _p минус 1 левая круглая скобка p минус 1 правая круглая скобка \equiv 0 mod p в степени k ;$

$альфа _11 в квадрате плюс альфа _22 в квадрате плюс \ldots плюс альфа _p минус 1 левая круглая скобка p минус 1 правая круглая скобка в квадрате \equiv 0 mod p в степени k ;$

$\ldots$

$альфа _11 в степени левая круглая скобка p минус 2 правая круглая скобка плюс альфа _22 в степени левая круглая скобка p минус 2 правая круглая скобка плюс \ldots плюс альфа _p минус 1 левая круглая скобка p минус 1 правая круглая скобка в степени левая круглая скобка p минус 2 правая круглая скобка \equiv 0 mod p в степени k ;$

$альфа _11 в степени левая круглая скобка p минус 1 правая круглая скобка плюс альфа _22 в степени левая круглая скобка p минус 1 правая круглая скобка плюс \ldots плюс альфа _p минус 1 левая круглая скобка p минус 1 правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка не равно 0 mod p в степени k .$

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

$альфа _1S_1n плюс альфа _1S_1n плюс \ldots плюс альфа _p минус 1S_p минус 1n \equiv левая круглая скобка альфа _1 плюс альфа _2 плюс \ldots плюс альфа _p минус 1 правая круглая скобка S левая круглая скобка n правая круглая скобка mod p в степени k .$ $альфа _1S_1n плюс альфа _1S_1n плюс \ldots плюс$
$плюс альфа _p минус 1S_p минус 1n \equiv левая круглая скобка альфа _1 плюс альфа _2 плюс \ldots плюс альфа _p минус 1 правая круглая скобка S левая круглая скобка n правая круглая скобка mod p в степени k .$

С одной стороны, если раскрыть все S_j по биному Ньютона, и собрать вместе члены вида $\tau левая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 минус s правая круглая скобка умножить на i в степени s ,$ $1 меньше или равно s меньше или равно p минус 2,$ то по Лемме 2 перед каждым членом коэффициент, равный нулю по модулю p^k. Тогда:

$альфа _1 левая круглая скобка \sum_i=0 в степени n плюс \tau левая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка i в степени левая круглая скобка p минус 1 правая круглая скобка правая круглая скобка плюс альфа _2 левая круглая скобка \sum_i=0 в степени n \tau левая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка плюс левая круглая скобка 2i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка правая круглая скобка плюс \ldots плюс альфа _p минус 1 левая круглая скобка \sum_i=0 в степени n \tau левая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка плюс левая круглая скобка левая круглая скобка p минус 1 правая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка правая круглая скобка =$
$= левая круглая скобка альфа _1 плюс альфа _2 плюс \ldots плюс альфа _p минус 1 правая круглая скобка S левая круглая скобка n правая круглая скобка .$

Вспомнив, что $\sum_i=1 в степени n \tau левая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка =S левая круглая скобка n правая круглая скобка$ видим, что все члены вида $\tau левая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка$ сократились с правой частью, итак

$альфа _1 \sum_i=0 в степени n i в степени левая круглая скобка p минус 1 правая круглая скобка плюс альфа _2 \sum_i=0 в степени n левая круглая скобка 2i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка плюс \ldots плюс альфа _p минус 1 \sum_i=0 в степени n левая круглая скобка левая круглая скобка p минус 1 правая круглая скобка i правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка \equiv 0 равносильно$
$равносильно левая круглая скобка альфа _1 1 в степени левая круглая скобка p минус 1 правая круглая скобка плюс альфа _2 2 в степени левая круглая скобка p минус 1 правая круглая скобка плюс \ldots плюс альфа _p минус 1 левая круглая скобка p минус 1 правая круглая скобка в степени левая круглая скобка p минус 1 правая круглая скобка правая круглая скобка S левая круглая скобка n правая круглая скобка \equiv 0.$

Но первая скобка не делится на p по Лемме 2, а S(n) не делится на p^k по Лемме 1. Осталось доказать лемму 2. Сперва отметим, что если вместо набора целых чисел α_j удалось подобрать набор рациональных чисел β_j, таких что их знаменатели не делятся на p, все сравнимости из условия леммы заменились на равенства, а последнее выражение равно целому числу, не делящемуся на p  — то лемма доказана, достаточно все β_j заменить на сравнимые с ними по модулю p^k целые числа. Сравнимость определена корректно поскольку знаменатели не делятся на p.

Теперь осталось взять

$бета _j = левая круглая скобка минус 1 правая круглая скобка в степени j дробь: числитель: 1, знаменатель: j конец дроби левая круглая скобка \begin{align p минус 2j минус 1 \endalign правая круглая скобка .$

Читателю остается упражнение доказать (например, по индукции, поскольку простота p здесь уже не важна), что во всех условиях Леммы 2, кроме последнего, получается 0, а в последнем $\pm левая круглая скобка p минус 2 правая круглая скобка !.$

Ответ: все n, не делящиеся ни на 2, ни на 3, ни на 5.

Критерии оценивания выполнения задания	Баллы
Приведено полное решение	20
Найден пример, работающий для всех n, не делящихся на 2, 3 и 5	12
Доказано, что n — нечётное	8
Решение не соответствует ни одному из перечисленных выше критериев	0
Максимальный балл	20

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

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

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

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

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

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

Рассматриваются наборы из семи гирь с суммарным весом 1 (вес каждой гири неотрицателен). Назовем поднабор большим, если сумма весов гирь поднабора больше или равна 2/3. Для каждого набора найдем число больших поднаборов. Найдите минимум этого числа по всем наборам.

Решение.

Предположим, есть набор, у которого меньше 23 больших поднаборов. Тогда все наборы из 6 гирь большие. В самом деле, путь поднабор без гири A с весом a  — не большой. Тогда a > 1/3. У множества шести гирь (всех кроме A) есть 2⁶ подмножеств. Эти подмножества разбиваются на пары с пустым пересечением, дающие в объединении все гири без A. Тогда в каждой паре хотя бы одно множество весит не менее (1 − a)/2. То есть половина, 2⁶/2 = 2⁵, из этих подмножеств весит не менее (1 − a)/2. Тогда каждое множество из этой половины в объединении с A дает вес не менее (1 − a)/2 + a ≥ 2/3. Таким образом, мы нашли 25 = 32 > 23 больших набора. Противоречие.

Итого, на данный момент мы нашли уже 8 больших поднаборов: 7-элементный и все семь 6-элементных. Посмотрим, какие 5-элементные поднможества могут не давать большой поднабор.

Допустим, все гири без гирь A, B – не большой поднабор, и все без C, D – тоже не большой поднабор (разными буквами обозначены разные гири). Тогда, рассуждая аналогично предыдущему случаю, получаем, что у дополнения к A, B есть 2⁵/2 = 2⁴ подмножеств, дающих в объединении с A, B большой поднабор. То же самое с C, D: у дополнения к C, D есть 2⁵/2 = 2⁴ подмножеств, дающих в объединении с C, D большой поднабор. Рассмотрим объединение этих поднаборов и оценим его мощность. Если первое множество наборов это X, второе  — это Y, то X ∩ Y ≤ 8. Действительно, набор в пересечении X и Y включает в себя A, B, C, D, и число способов дополнить его несколькими из оставшихся трех – не более 23 = 8. Итого, больших поднаборов |X ∪ Y| = |X|+|Y| − |X ∩ Y| ≥ 16 + 16−8 = 24 > 23. Значит, не существует таких непересекающихся пар A, B и C, D, что их пятиэлементные дополнения – не большие наборы. Или же, для любых двух 5-элементных не больших наборов их 2-элементные дополнения пересекаются. Максимальное количество попарно пересекающихся 2-элементных подмножеств множества из 7 элементов – 6. (В самом деле, пусть есть несколько попарно-пересекающихся пар элементов 7-элементного множества. Если все пары содержат некоторый один и тот же элемент, то пар не больше чем остальных элементов, то есть 6. Пусть никакой элемент не принадлежит всем парам. Рассмотрим две любые пары A, B и B, C. Должна найтись пара, не содержащая A, но чтобы она пересекалась с первыми двумя она должна быть парой B, C. Тогда больше ни одной пары добавить нельзя, итого в этом случае пар не больше чем 3.) Отсюда существует хотя бы $C в степени 5 _7$ − 6 = 21 − 6 = 15 больших пятиэлементных поднабора. Складывая это количество с 8 (число уже найденных больших поднаборов мощности > 5), получаем оценку на хотя бы 23 поднабора.

Пример. Как видно из доказательства оценки, самая тяжелая гиря должна весить строго меньше $дробь: числитель: 1, знаменатель: 4 конец дроби$ строго больше $дробь: числитель: 1, знаменатель: 5 конец дроби .$ Возьмем ее вес равным $дробь: числитель: 2, знаменатель: 9 конец дроби ,$ или что то же самое $дробь: числитель: 12, знаменатель: 54 конец дроби .$ Тогда если веса остальных гирь взять равными, они получаются по $дробь: числитель: 7, знаменатель: 54 конец дроби .$ Из поднаборов без первой гири подходит только содержащий все остальные. Из поднаборов с первой гирей подходят $C в степени 4 _6$ гирь (первая и четыре оставшихся), $C в степени 5 _6$ гирь (первая и пять оставшихся) и $C_6 в степени 6$ гирь (первая и все шесть оставшихся). Итого, больших поднаборов $1 плюс C в степени 4 _6 плюс C в степени 5 _6 плюс C_6 в степени 6 = 1 плюс 15 плюс 6 плюс 1 = 23.$

Ответ: 23.

Критерии оценивания выполнения задания	Баллы
Приведено полное решение.	28
Верная оценка, но пример отсутствует (или в нем ошибка).	18
В предположении противного доказано, что все поднаборы из 6 гирь являются большими (или, что равносильно, что вес любой гири не больше 1/3); приведён пример.	14
Только пример.	9
Попытка доказывать неверный ответ.	0
Максимальный балл	28

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

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

Найти количество всех пятизначных чисел $\overlineabcde,$ все цифры которых различны и $a меньше b меньше c больше d больше e.$

Решение.

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

1)  Выбранная пятёрка не содержит нуля. Тогда её можно выбрать $C_9 в степени 5$ способами, затем выбрать из них две не максимальных и ненулевых цифры $C_4 в квадрате$ способами, и единственным способом расположить их слева от наибольшей в порядке возрастания, а обе оставшихся приписать справа от максимальной в порядке убывания. Всего имеем $C_9 в степени 5 умножить на C_4 в квадрате =126 умножить на 6=756$ таких чисел.

2)  Выбранная пятёрка содержит ноль. Тогда её ненулевые цифры можно выбрать $C_9 в степени 4$ способами, затем выбрать из них две не максимальных цифры $C_4 в квадрате$ способами, и затем единственным способом расположить их слева от наибольшей в порядке возрастания, а одну оставшуюся и ноль приписать справа от максимальной в порядке убывания. Всего имеем $C_9 в степени 4 умножить на C_3 в квадрате =126 умножить на 3=378$ таких чисел. Итого, получаем 756 + 378  =  1134 чисел.

Ответ: 1134.

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

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

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

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

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

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

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

На какое максимальное число различных прямоугольников можно разрезать шахматную доску 8 на 8 клеток? Все разрезы должны проходить только по линиям сетки. Прямоугольники различны, если они не равны как геометрические фигуры.

Решение.

Выпишем возможные размеры возможных различных целочисленных прямоугольников минимальных площадей, помещающихся по линиям сетки на доску 8 на 8 в порядке возрастания этих площадей: 1 на 1, 1 на 2, 1 на 3, 1 на 4, 2 на 2, 1 на 5, 1 на 6, 2 на 3, 1 на 7, 1 на 8, 2 на 4, 3 на 3, 2 на 5. Прямоугольников уже 13, и сумма их площадей равна 73, что больше площади доски. Значит, больше, чем на 12 прямоугольников, разрезать доску требуемым в задаче образом нельзя.

С другой стороны, сумма площадей их всех, кроме 3 на 3, равна ровно 64 и можно указать пример такого разбиения на все эти 12 прямоугольников, кроме 3 на 3: первые четыре вертикали доски разрежем на полоски ширины 1 и длин 1 и 7, 2 и 6, 3 и 5, и 8 соответственно. Оставшиеся 4 вертикали разобьём на два вертикальных прямоугольника 2 на 7, составленных из прямоугольников 2 на 5 и 2 на 2, и 2 на 4 и 2 на 3. Сверху к ним добавим горизонтальную полоску 1 на 4. Возможны и другие примеры такого разбиения.

Ответ: На 12.

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

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

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

Найти число всевозможных расстановок фишек по одной в некоторых клетках шахматной доски 8 на 8 таких, что количество фишек, стоящих в каждой строке различно и количество фишек, стоящих в каждом столбце различно.

Решение.

Строка или столбец могут содержать от 0 до 8 фишек, поэтому, если их количества по строкам и по столбцам различны, то множество значений количеств фишек в строках и множество значений количеств фишек в столбцах оба представляют из себя ряд чисел 0, 1, 2, …, 7, 8 с одним пропуском, причём пропуск этот в обоих случаях один и тот же и равен равен разности 36 и числа фишек на доске. Если этот пропуск не равен 0 или 8, то на доске одновременно будет либо пустая срока и полный столбец, либо наоборот, что невозможно.

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

Пусть нам дана произвольная расстановка первого типа, в ней найдутся заполненная строка и заполненный столбец  — всего 8 · 8  =  64 варианта для выбора их номеров. Вычеркнем их и получим расстановку 21 фишки на доске 7 на 7 с разным числом фишек в строках и разным числом фишек в столбцах. На доске 7 на 7 это соответствует расстановке с пустой строкой и пустым столбцом, для которых есть 7 · 7  =  49 способов выбора. Снова вычёркиваем их, получаем расстановку 21 фишки на доске 6 на 6 и т. д. Продолжая так, мы получим (8!)² вариантов выбора номеров соответствующих строк и столбцов (попеременно полных и пустых), которые полностью и однозначно определяют данную расстановку 36 фишек на доске 8 на 8. Добавляем к ним столько же вариантов расстановок 28 фишек на 8 на 8, получаем ответ: 2 · (8!)².

Ответ: 2 · (8!)².

Критерии оценивания выполнения задания	Баллы
Верное решение.	7
Доказано, что на доске могут стоять только 28 или 36 фишек.	2
Верно подсчитано количество расстановок только 28 (36) фишек.	6
Любой доказываемый неверный ответ, решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	7

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

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

Ася учится писать и умеет писать три буквы А, С и Я. Мама предложила ей написать семь букв подряд. В полученном «слове» три подряд идущих буквы образовали имя «АСЯ». Сколько существует таких различных семибуквенных «слов»?

Критерии оценивания выполнения задания	Оценка	Баллы
Полное решение.	+	12
Допущена незначительная вычислительная ошибка.	+.	10
Правильно представлены расчеты без учета повторения имени в «слове». Учтено, что имя может повторяться, но при этом допущены ошибки.	±	9
Правильно представлены расчеты без учета повторения имени в «слове». Не учтено, что имя может повторяться.	+/2	6
Представлены расчеты без учета повторения имени часть из которых верные. ИЛИ Указана идея, что имя может повторяться. Расчеты неверные.	∓	2
Решение не соответствует ни одному критерию, описанному выше.	−/0	0
Максимальный балл	12

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

Всего: 198 1–20 | 21–40 | 41–60 | 61–80 …