У Даши и Саши есть по доске $9\times9$. Даша укладывает на свою доску 40 не перекрывающихся плиток $1\times2$ (так, что плитки занимают 80 клеток, а одна клетка остается не покрытой). Пусть у неё есть $D$ способов сделать это. Саша красит на своей доске 41 единичных отрезков-границ между соседними клетками, так, чтобы для каждой клетки доски хотя бы одна её сторона была покрашена. Пусть у Саши $S$ способов сделать это. Докажите, что $S\leqslant 2D$.
Ответ:
Решение:
В группе из 79 школьников у каждого не более 39 знакомых, причем у любого мальчика есть знакомая девочка, а у любой девочки — знакомый мальчик. Может ли оказаться, что все девочки из этой группы имеют в ней поровну знакомых мальчиков, а все мальчики — поровну знакомых девочек? Все знакомства — взаимные.
Ответ:
Решение:
Можно ли пронумеровать вершины, рёбра и грани куба различными целыми числами от $-12$ до 13 так, чтобы номер каждой вершины равнялся сумме номеров сходящихся в ней рёбер, а номер каждой грани равнялся сумме номеров ограничивающих её рёбер?
Ответ:
Решение:
В классе учится больше 6, но меньше 60 учеников, и в нём организовано семь кружков. Каждый ученик класса посещает одинаковое количество кружков. Известно, что для любых двух кружков найдутся ровно три ученика, которые посещают их оба. Сколько учеников может быть в таком классе?
Ответ:
Решение:
По кругу стоят $n$ мальчиков и $n$ девочек. Назовём пару из мальчика и девочки хорошей, если на одной из дуг между ними стоит поровну мальчиков и девочек (в частности, стоящие рядом мальчик и девочка образуют хорошую пару). Оказалось, что есть девочка, которая участвует ровно в 10 хороших парах. Докажите, что есть и мальчик, который участвует ровно в 10 хороших парах.
Ответ:
Решение:
Каждая клетка доски $100\times100$ окрашена либо в чёрный, либо в белый цвет, причём все клетки, примыкающие к границе доски — чёрные. Оказалось, что нигде на доске нет одноцветного клетчатого квадрата $2\times2$. Докажите, что на доске найдётся клетчатый квадрат $2\times2$, клетки которого окрашены в шахматном порядке.
Ответ:
Решение:
Сто гномов, веса которых равны 1, 2, 3, $\ldots$, 100 фунтов, собрались на левом берегу реки. Плавать они не умеют, но на этом же берегу находится гребная лодка грузоподъёмностью 100 фунтов. Из-за течения плыть обратно трудно, поэтому у каждого гнома хватит сил грести с правого берега на левый не более одного раза (грести в лодке достаточно любому из гномов; гребец в течение одного рейса не меняется). Могут ли все гномы переправиться на правый берег?
Ответ:
Решение:
Дано натуральное число $n\gt 5$. На кольцевой полоске бумаги написана последовательность из нулей и единиц. Для каждой последовательности $w$ из $n$ нулей и единиц посчитали количество способов вырезать из полоски фрагмент, на котором написана $w$. Оказалось, что наибольшее количество $M$ достигается на последовательности $11\underbrace{00\ldots0}_{n-2}$, а наименьшее (возможно, нулевое) — на последовательности $\underbrace{00\ldots0}_{n-2}11$. Докажите, что есть и другая последовательность из $n$ нулей и единиц, встречающаяся ровно $M$ раз.
Ответ:
Решение:
Куб $100\times100\times100$ разбит на миллион единичных кубиков; в каждом кубике расположена лампочка. Три грани большого куба, имеющие общую вершину, окрашены: одна красным, другая синим, а третья зеленым. Назовем столбцом набор из 100 кубиков, образующих блок $1\times1\times100$. У каждого из 30 000 столбцов есть одна окрашенная торцевая клетка; в этой клетке стоит переключатель — нажатие на этот переключатель меняет состояние всех 100 лампочек в столбце (выключенная лампочка включается, а включенная выключается). Изначально все лампочки были выключены. Петя нажал на несколько переключателей, получив ситуацию, в которой ровно $k$ лампочек горят. Докажите, что после этого Вася может нажать на несколько переключателей так, чтобы ни одна лампочка не горела, использовав не более $k/100$ переключателей с красной грани.
Ответ:
Решение:
Пусть даны натуральные числа $x_1$ и $x_2$. На прямой даны $y_1$ белых отрезков и $y_2$ чёрных отрезков, при этом $y_1\geqslant x_1$ и $y_2\geqslant x_2$. Известно, что никакие два отрезка одного цвета не пересекаются (даже не имеют общих концов). Также известно, что при любом выборе $x_1$ белых отрезков и $x_2$ чёрных отрезков обязательно какая-то пара выбранных отрезков будет пересекаться. Докажите, что \[(y_1-x_1)(y_2-x_2)\lt x_1x_2.\]
Ответ:
Решение:
В ряд выписаны по одному разу все натуральные числа от 1 до 1000 в каком-то порядке. Докажите, что можно выбрать несколько стоящих подряд выписанных чисел, сумма которых больше 100000, но не превосходит 100500.
Ответ:
Решение:
Саша выбрал 199 многочленов с вещественными коэффициентами так, что сумма любых ста из них имеет вещественный корень. Докажите, что сумма каких-то девяти из них также имеет вещественный корень.
Ответ:
Решение:
В стране Эйлерии 101 город. Каждые два города соединены двусторонним беспосадочным рейсом одной из 99 авиакомпаний. Известно, что из каждого города выходят рейсы всех 99 компаний. Назовём треугольником три города, попарно соединённых рейсами одной и той же компании. Докажите, что в Эйлерии не больше одного треугольника.
Ответ:
Решение:
Имеется 70 переключателей и 15 ламп. Каждая лампа соединена с 35 переключателями. Никакие два переключателя не соединены с одним и тем же набором ламп. Нажатие на переключатель меняет состояние всех ламп, с которыми он соединён (включённые выключает и наоборот). Изначально все лампы выключены. Докажите, что можно нажать на какие-то 19 переключателей таким образом, чтобы включилось не менее восьми ламп.
Ответ:
Решение:
В лагерь приехали 99 школьников, причём все приехавшие имеют одно и то же ненулевое количество знакомых среди остальных. Группу ребят, обладающую тем свойством, что любой из приехавших, не входящий в эту группу, знаком с кем-то из этой группы, будем называть популярной. Докажите, что из любой популярной группы, содержащей более 49 ребят, можно выбрать популярную группу, содержащую ровно 49 ребят.
Ответ:
Решение:
Числа $1, 2, \ldots, 1000$ разбили на два множества по 500 чисел: красные $k_1$, $k_2$, $\ldots$, $k_{500}$ и синие $s_1$, $s_2$, $\ldots$, $s_{500}$. Докажите, что количество таких пар $m$ и $n$, у которых разность $k_m-s_n$ дает остаток 7 при делении на 100, равно количеству таких пар $m$ и $n$, у которых разность $s_n-k_m$ дает остаток 7 при делении на 100. Здесь рассматриваются все возможные разности, в том числе и отрицательные.
Напомним, что остатком от деления целого числа $a$ на 100 называется разность между числом $a$ и ближайшим числом, не большим $a$ и делящимся на 100. Например, остаток от деления числа 2022 на 100 равен $2022-2000=22$, а остаток от деления числа $-11$ на 100 равен $-11-(-100)=89$.
Напомним, что остатком от деления целого числа $a$ на 100 называется разность между числом $a$ и ближайшим числом, не большим $a$ и делящимся на 100. Например, остаток от деления числа 2022 на 100 равен $2022-2000=22$, а остаток от деления числа $-11$ на 100 равен $-11-(-100)=89$.
Ответ:
Решение:
Впишите в каждый квадратик одну и ту же цифру, чтобы получилось верное равенство: \[\square+\square+\square+\square=\square\times\square\]
Ответ:
Решение:
В примере на сложение \[\square+\triangle+\square=\square\square\] впишите одну и ту же цифру в каждый квадратик и другую цифру в треугольник так, чтобы пример получился верным.
Ответ:
Решение:
Замените звёздочки цифрами так, чтобы равенство стало верным и все семь цифр были различными: \[\ast\ast+\ast\ast=175.\]
Ответ:
Решение: