Дана клетчатая таблица $100\times100$, клетки которой покрашены в чёрный и белый цвета. При этом во всех столбцах поровну чёрных клеток, в то время как во всех строках разные количества чёрных клеток. Каково максимальное возможное количество пар соседних по стороне разноцветных клеток?
Ответ:
Решение:
На клетчатый лист бумаги размера $100\times100$ положили несколько попарно неперекрывающихся картонных равнобедренных прямоугольных треугольничков с катетом 1; каждый треугольничек занимает ровно половину одной из клеток. Оказалось, что каждый единичный отрезок сетки (включая граничные) накрыт ровно одним катетом треугольничка. Найдите наибольшее возможное число клеток, не содержащих ни одного треугольничка.
Ответ:
Решение:
Есть клетчатая доска $2015\times2015$. Дима ставит в $k$ клеток по детектору. Затем Коля располагает на доске клетчатый корабль в форме квадрата $1500\times1500$. Детектор в клетке сообщает Диме, накрыта эта клетка кораблём или нет. При каком наименьшем $k$ Дима может расположить детекторы так, чтобы гарантированно восстановить расположение корабля?
Ответ:
Решение:
В белой таблице $2016\times2016$ некоторые клетки окрасили чёрным. Назовём натуральное число $k$ удачным, если $k\leqslant2016$, и в каждом из клетчатых квадратов со стороной $k$, расположенных в таблице, окрашено ровно $k$ клеток. (Например, если все клетки чёрные, то удачным является только число 1.) Какое наибольшее количество чисел могут быть удачными?
Ответ:
Решение:
У фокусника и помощника есть колода с картами; одна сторона («рубашка») у всех карт одинакова, а другая окрашена в один из 2017 цветов (в колоде по 1000000 карт каждого цвета). Фокусник и помощник собираются показать следующий фокус. Фокусник выходит из зала, а зрители выкладывают на стол в ряд $n\gt 1$ карт рубашками вниз. Помощник смотрит на эти карты, а затем все, кроме одной, переворачивает рубашкой вверх, не меняя их порядка. Затем входит фокусник, смотрит на стол, указывает на одну из закрытых карт и называет её цвет. При каком наименьшем $n$ фокусник может заранее договориться с помощником так, чтобы фокус гарантированно удался?
Ответ:
Решение:
В некоторых клетках квадрата $200\times200$ стоит по одной фишке — красной или синей; остальные клетки пусты. Одна фишка видит другую, если они находятся в одной строке или одном столбце. Известно, что каждая фишка видит ровно пять фишек другого цвета (и, возможно, некоторое количество фишек своего цвета). Найдите наибольшее возможное количество фишек, стоящих в клетках.
Ответ:
Решение:
Дано натуральное число $k$. На клетчатой плоскости изначально отмечено $N$ клеток. Назовём крестом клетки $A$ множество всех клеток, находящихся в одной вертикали или горизонтали с $A$. Если в кресте неотмеченной клетки $A$ отмечено хотя бы $k$ других клеток, то клетку $A$ также можно отметить. Оказалось, что цепочкой таких действий можно отметить любую клетку плоскости. При каком наименьшем $N$ это могло случиться?
Ответ:
Решение:
Назовём лодочкой трапецию с основаниями 1 и 3, получающуюся приклеиванием к противоположным сторонам единичного квадратика двух треугольничков (полуклеток). В квадрате $100\times100$ расположена невидимая лодочка (её можно поворачивать, она не выходит за границы квадрата, её средняя клетка целиком лежит на одной из клеток квадрата). Одним выстрелом можно накрыть любую треугольную половинку клетки. Если выстрел пересекается с внутренностью лодочки (т. е. пересечение треугольника выстрела с лодочкой имеет ненулевую площадь), то она считается потопленной. Какого наименьшего количества выстрелов достаточно, чтобы наверняка потопить лодочку?
Ответ:
Решение:
В компании 100 детей, некоторые дети дружат (дружба всегда взаимна). Известно, что при выделении любого ребёнка оставшихся 99 детей можно разбить на 33 группы по три человека так, чтобы в каждой группе все трое попарно дружили. Найдите наименьшее возможное количество пар дружащих детей.
Ответ:
Решение:
Кондитерская фабрика выпускает $N$ сортов конфет. На Новый год фабрика подарила каждому из 1000 учеников школы подарок, содержащий по конфете нескольких сортов (составы подарков могли быть разными). Каждый ученик заметил, что для любых 11 сортов конфет он получил конфету хотя бы одного из этих сортов. Однако оказалось, что для любых двух сортов найдётся ученик, получивший конфету ровно одного из этих двух сортов. Найдите наибольшее возможное значение $N$.
Ответ:
Решение:
В межгалактической гостинице есть 100 комнат вместимостью 101, 102, $\ldots$, 200 человек. В этих комнатах суммарно живёт $n$ человек. В гостиницу приехал VIP-гость, для которого нужно освободить целую комнату. Для этого директор гостиницы выбирает одну комнату и переселяет всех её жителей в одну и ту же другую комнату. При каком наибольшем $n$ директор гостиницы всегда может таким образом освободить комнату независимо от текущего расселения?
Ответ:
Решение:
Даны $n$ монет попарно различных масс и $n$ чашечных весов, $n\gt 2$. При каждом взвешивании разрешается выбрать какие-то одни весы, положить на их чаши по одной монете, посмотреть на показания весов и затем снять монеты обратно. Какие-то одни из весов (неизвестно, какие) испорчены и могут выдавать случайным образом как правильный, так и неправильный результат. За какое наименьшее количество взвешиваний можно заведомо найти самую тяжёлую монету?
Ответ:
Решение:
Дано натуральное $n$. Из 26 единичных белых кубиков и одного чёрного кубика собирается куб $3\times3\times3$ так, что чёрный кубик находится в его центре. Из $n^3$ таких кубов с ребром 3 составили куб с ребром $3n$. Какое наименьшее количество белых кубиков можно перекрасить в красный цвет так, чтобы каждый белый кубик имел хотя бы одну общую вершину с каким-нибудь красным?
Ответ:
Решение:
Назовём расстоянием между двумя клетками клетчатой доски наименьшее количество ходов, за которое шахматный король может добраться от одной из них до другой. Найдите наибольшее количество клеток, которое можно отметить на доске $100\times100$ так, чтобы среди них не нашлось двух клеток, расстояние между которыми равно 15.
Ответ:
Решение:
В классе $m$ учеников. В течение сентября каждый из них несколько раз ходил в бассейн; никто не ходил дважды в один день. Первого октября выяснилось, что все количества посещений бассейна у учеников различны. Более того, для любых двух из них обязательно был день, когда первый из них был в бассейне, а второй — нет, и день, когда, наоборот, второй из них был в бассейне, а первый — нет. Найдите наибольшее возможное значение $m$. (В сентябре 30 дней.)
Ответ:
Решение:
Каждая грань куба $1000\times1000\times1000$ разбита на $1000^2$ квадратных клеток со стороной 1. Какое наибольшее количество этих клеток можно закрасить так, чтобы никакие две закрашенные клетки не имели общей стороны?
Ответ:
Решение:
В таблице $N\times N$ расставлены все натуральные числа от 1 до $N^2$. Число назовём большим, если оно наибольшее в своей строке, и малым, если оно наименьшее в своём столбце (таким образом, число может быть и большим, и малым одновременно, а может не быть ни тем, ни другим). Найдите наименьшую возможную разность между суммой всех больших чисел и суммой всех малых чисел.
Ответ:
Решение:
В стране $N$ городов. Некоторые пары городов связаны двусторонними авиалиниями, каждая пара не более, чем одной. Каждая авиалиния принадлежит одной из $k$ компаний. Оказалось, что из любого города можно попасть в любой другой (возможно, с пересадками), но при закрытии всех авиалиний любой из компаний это свойство нарушается. Какое наибольшее количество авиалиний (при произвольных данных $N$ и $k$) могло быть в этой стране?
Ответ:
Решение:
В языке три буквы — Ш, У и Я. Словом называется последовательность из 100 букв, ровно 40 из которых — гласные (то есть У или Я), а остальные 60 — буква Ш. Какое наибольшее количество слов можно выбрать так, чтобы у любых двух выбранных слов хотя бы в одной из ста позиций одновременно стояли гласные, причём различные?
Ответ:
Решение:
В Цветочном городе живёт $99^2$ коротышек. Некоторые из коротышек рыцари (всегда говорят правду), а остальные — лжецы (всегда лгут). Дома в городе расположены в клетках квадрата $99\times99$ (всего $99^2$ домов, расположенных в 99 вертикальных и в 99 горизонтальных улицах). В каждом доме живет ровно один коротышка. Номер дома обозначается парой чисел $(x;y)$, где $1\leqslant x\leqslant99$ — номер вертикальной улицы (номера возрастают слева направо), а $1\leqslant y\leqslant99$ — номер горизонтальной улицы (номера возрастают снизу вверх). Цветочным расстоянием между двумя домами с номерами $(x_1;y_1)$ и $(x_2;y_2)$ называется число $\rho=|x_1-x_2|+|y_1-y_2|$. Известно, что на каждой улице — вертикальной или горизонтальной — проживает не менее $k$ рыцарей. Кроме того, все коротышки знают, в каком доме живет рыцарь Знайка. Вы хотите найти его дом, но не знаете, как выглядит Знайка. Вы можете подходить к любому дому и спрашивать живущего в нем коротышку: «Каково цветочное расстояние от вашего дома до дома Знайки?». При каком наименьшем $k$ вы можете гарантированно найти дом Знайки?
Ответ:
Решение: