У фокусника и помощника есть колода с картами; одна сторона («рубашка») у всех карт одинакова, а другая окрашена в один из 2017 цветов (в колоде по 1000000 карт каждого цвета). Фокусник и помощник собираются показать следующий фокус. Фокусник выходит из зала, а зрители выкладывают на стол в ряд $n\gt 1$ карт рубашками вниз. Помощник смотрит на эти карты, а затем все, кроме одной, переворачивает рубашкой вверх, не меняя их порядка. Затем входит фокусник, смотрит на стол, указывает на одну из закрытых карт и называет её цвет. При каком наименьшем $n$ фокусник может заранее договориться с помощником так, чтобы фокус гарантированно удался?
Ответ:
Решение:
В белой таблице $2016\times2016$ некоторые клетки окрасили чёрным. Назовём натуральное число $k$ удачным, если $k\leqslant2016$, и в каждом из клетчатых квадратов со стороной $k$, расположенных в таблице, окрашено ровно $k$ клеток. (Например, если все клетки чёрные, то удачным является только число 1.) Какое наибольшее количество чисел могут быть удачными?
Ответ:
Решение:
Есть клетчатая доска $2015\times2015$. Дима ставит в $k$ клеток по детектору. Затем Коля располагает на доске клетчатый корабль в форме квадрата $1500\times1500$. Детектор в клетке сообщает Диме, накрыта эта клетка кораблём или нет. При каком наименьшем $k$ Дима может расположить детекторы так, чтобы гарантированно восстановить расположение корабля?
Ответ:
Решение:
На клетчатый лист бумаги размера $100\times100$ положили несколько попарно неперекрывающихся картонных равнобедренных прямоугольных треугольничков с катетом 1; каждый треугольничек занимает ровно половину одной из клеток. Оказалось, что каждый единичный отрезок сетки (включая граничные) накрыт ровно одним катетом треугольничка. Найдите наибольшее возможное число клеток, не содержащих ни одного треугольничка.
Ответ:
Решение:
Дана клетчатая таблица $100\times100$, клетки которой покрашены в чёрный и белый цвета. При этом во всех столбцах поровну чёрных клеток, в то время как во всех строках разные количества чёрных клеток. Каково максимальное возможное количество пар соседних по стороне разноцветных клеток?
Ответ:
Решение:
Поле представляет собой клетчатый квадрат $41\times41$, в одной из клеток которого замаскирован танк. Истребитель за один выстрел обстреливает одну клетку. Если произошло попадание, танк переползает на соседнюю по стороне клетку поля, если нет — остаётся на месте. При этом после выстрела пилот истребителя не знает, произошло ли попадание. Для уничтожения танка надо попасть в него два раза. Каким наименьшим числом выстрелов можно обойтись для того, чтобы гарантировать, что танк уничтожен?
Ответ:
Решение:
Даны натуральные числа $a$ и $b$, причём $a\lt b\lt 2a$. На клетчатой плоскости отмечены некоторые клетки так, что в каждом клетчатом прямоугольнике $a\times b$ или $b\times a$ есть хотя бы одна отмеченная клетка. При каком наибольшем $\alpha$ можно утверждать, что для любого натурального $N$ найдётся клетчатый квадрат $N\times N$, в котором отмечено хотя бы $\alpha N^2$ клеток?
Ответ:
Решение:
Дано натуральное число $n\geqslant 2$. Рассмотрим все покраски клеток доски $n\times n$ в $k$ цветов такие, что каждая клетка покрашена ровно в один цвет, и все $k$ цветов встречаются. При каком наименьшем $k$ в любой такой покраске найдутся четыре окрашенных в четыре разных цвета клетки, расположенные в пересечении двух строк и двух столбцов?
Ответ:
Решение:
У нумизмата есть 100 одинаковых по внешнему виду монет. Он знает, что среди них 30 настоящих и 70 фальшивых монет. Кроме того, он знает, что массы всех настоящих монет одинаковы, а массы всех фальшивых — разные, причём любая фальшивая монета тяжелее настоящей; однако точные массы монет неизвестны. Имеются двухчашечные весы без гирь, на которых можно за одно взвешивание сравнить массы двух групп, состоящих из одинакового числа монет. За какое наименьшее количество взвешиваний на этих весах нумизмат сможет гарантированно найти хотя бы одну настоящую монету?
Ответ:
Решение:
На рисунке изображён автодром; точки — это перекрёстки, отрезки — дороги. Каждый отрезок между соседними точками машина проезжает ровно за минуту. Приехав на перекрёсток, машина немедленно уезжает с него по любой дороге, кроме той, по которой она приехала. Сначала несколько машин расположены на перекрёстках, затем они одновременно начинают двигаться по указанным правилам. При каком наибольшем количестве машин может случиться, что они смогут неограниченно долго ездить, никогда не встречаясь (ни на перекрёстках, ни на дорогах)?
Ответ:
Решение:
У Андрея на огороде выросли кабачки, среди которых нет двух одинаковой массы. Андрей решил некоторое число самых маленьких взять себе, некоторое число самых маленьких из оставшихся отдать другу, а остальные — в рагу. При таком распределении себе он бы взял 10% от общей массы, а другу досталось бы 50%. Только друг сказал, что ему не нужно столько кабачков. Тогда Андрей распределил кабачки по-другому, но по тому же принципу: некоторое число самых маленьких себе, из оставшихся некоторое число самых маленьких другу, остальное — в рагу. После этого у Андрея и у друга оказалось по 20% общей массы кабачков. Какое наименьшее количество кабачков могло вырасти на огороде у Андрея?
Ответ:
Решение:
По окружности расставили 2023 числа, наименьшее из которых равно 0, а наибольшее равно $N$. Для каждых двух чисел, стоящих на окружности рядом, на доску выписали их сумму. Оказалось, что любые два числа на доске отличаются не более чем на 1. Каково наибольшее возможное значение $N$?
Ответ:
Решение:
В белом клетчатом квадрате размером $10\times10$ клеток закрасили черным 84 клетки. Какое наименьшее количество «уголков» из трех черных клеток могло при этом образоваться?
Ответ:
Решение:
На клетчатую доску размером $100\times100$ поставили 1975 ладей (каждая ладья занимает одну клетку, разные ладьи стоят на разных клетках). Какое наибольшее количество пар ладей, бьющих друг друга, могло при этом получиться? Напомним, что ладья может бить на любое число клеток по горизонтали и вертикали, но не бьёт ладью, загороженную другой ладьёй.
Ответ:
Решение:
Из нечётных натуральных чисел от 1 до 47 составили 12 дробей, меньших 1, использовав каждое число по одному разу. Получившиеся дроби разбили на группы равных между собой. Какое наименьшее количество групп могло получиться?
Ответ:
Решение:
Стороны 100 одинаковых равносторонних треугольников покрашены в 150 цветов так, что в каждый цвет покрашены ровно две стороны. Если приложить два треугольника одноцветными сторонами, то полученный ромб будем называть хорошим. Петя хочет сложить из этих треугольников как можно больше хороших ромбов, причем каждый треугольник должен входить не более, чем в один ромб. Какое наибольшее количество хороших ромбов может гарантировать себе Петя независимо от способа раскраски треугольников?
Ответ:
Решение:
Петя отмечает на плоскости четыре точки так, чтобы их все нельзя было зачеркнуть двумя параллельными прямыми. Из прямых, проходящих через пары точек, Вася выбирает две, измеряет угол между ними и платит Пете сумму, равную градусной мере угла. Какую наибольшую сумму может гарантировать себе Петя?
Ответ:
Решение:
Разрешается вырезать из шахматной доски размером $20\times20$ любые 18 клеток, а потом выставить на оставшиеся клетки несколько ладей, не бьющих друг друга. Какое наибольшее число ладей можно выставить таким образом? Ладьи бьют друг друга, если они стоят на одной горизонтали или вертикали доски и между ними нет вырезанных клеток.
Ответ:
Решение:
а) Клетки таблицы $11\times 10$ раскрасили в 3 цвета так, что в каждом квадрате $2\times 2$ есть клетки всех трёх цветов. Какое наибольшее количество клеток первого цвета может быть?
б) Клетки таблицы $11\times 10$ раскрасили в 3 цвета так, что в каждом прямоугольнике $1\times 4$ и $4\times 1$ есть клетки всех трёх цветов. Какое наибольшее количество клеток первого цвета может быть?
б) Клетки таблицы $11\times 10$ раскрасили в 3 цвета так, что в каждом прямоугольнике $1\times 4$ и $4\times 1$ есть клетки всех трёх цветов. Какое наибольшее количество клеток первого цвета может быть?
Ответ:
Решение:
В стране ровно 1000 городов, некоторые пары городов соединены двусторонними авиалиниями. Известно, что для любого натурального $k\leqslant500$ выполнено следующее утверждение: «Если выбрать любое множество $A$ из $k$ городов, то найдётся хотя бы $k$ городов, не принадлежащих $A$, каждый из которых соединён авиалинией хотя бы с одним городом из $A$». Какое наименьшее количество авиалиний может быть в этой стране?
Ответ:
Решение: