Назовём расстоянием между двумя клетками клетчатой доски наименьшее количество ходов, за которое шахматный король может добраться от одной из них до другой. Найдите наибольшее количество клеток, которое можно отметить на доске $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$ вы можете гарантированно найти дом Знайки?
Ответ:
Решение:
В алфавите $n\gt 1$ букв; словом является каждая конечная последовательность букв, в которой любые две соседние буквы различны. Слово называется хорошим, если из него нельзя вычеркнуть все буквы, кроме четырёх, так, чтобы осталась последовательность вида $aabb$, где $a$ и $b$ — различные буквы. Найдите наибольшее возможное количество букв в хорошем слове.
Ответ:
Решение:
На плоскости отмечены $N$ точек. Любые три из них образуют треугольник, величины углов которого в градусах выражаются натуральными числами. При каком наибольшем $N$ это возможно?
Ответ:
Решение:
Дано натуральное число $n\gt 4$. На плоскости отмечены $n$ точек, никакие три из которых не лежат на одной прямой. Василий проводит по одному все отрезки, соединяющие пары отмеченных точек. На каждом шаге, проводя очередной отрезок $S$, Василий помечает его наименьшим натуральным числом, которым ещё не помечен ни один отрезок, имеющий с $S$ общий конец. Для какого наибольшего $k$ Василий может действовать так, чтобы пометить какой-то отрезок числом $k$?
Ответ:
Решение:
Дано натуральное число $n$. Саша утверждает, что для любых $n$ лучей в пространстве, никакие два из которых не имеют общих точек, он сможет отметить на этих лучах $k$ точек, лежащих на одной сфере. При каком наибольшем $k$ его утверждение верно?
Ответ:
Решение:
Пусть $S$ — 100-элементное множество, состоящее из натуральных чисел, не превосходящих 10 000. Отметим в пространстве все точки, каждая из координат которых принадлежит множеству $S$. К каждой из 1 000 000 отмеченных точек $(x,y,z)$ прикрепим шарик с написанным на нём числом $\dfrac{x^2+y^2+z^2}{xy+yz+zx}$. На каком наибольшем количестве шариков может быть написано число, равное 2?
Ответ:
Решение:
В классе 18 детей. Родители решили подарить детям из этого класса торт. Для этого они сначала узнали у каждого ребёнка площадь куска, который он хочет получить. После этого они заказали торт квадратной формы, площадь которого в точности равна сумме 18 названных чисел. Однако, увидев торт, дети захотели, чтобы их куски тоже были квадратными. Родители могут резать торт разрезами, параллельными сторонам торта (разрезы не обязаны начинаться или оканчиваться на стороне торта). Для какого наибольшего $k$ родители гарантированно могут вырезать из заказанного торта $k$ квадратных кусков, которые можно выдать $k$ детям, чтобы каждый из них получил желаемое?
Ответ:
Решение:
Дано натуральное число $k$. Вдоль дороги стоят $n$ столбов через равные промежутки. Миша покрасил их в $k$ цветов и для каждой пары одноцветных столбов, между которыми нет других столбов того же цвета, вычислил расстояние между ними. Все эти расстояния оказались различны. При каком наибольшем $n$ так могло оказаться?
Ответ:
Решение:
Дано нечётное число $n\geqslant 3$. В клетчатом квадрате $2n\times2n$ закрашивают $2(n-1)^2$ клеток. Какое наибольшее количество трёхклеточных уголков можно гарантированно вырезать из незакрашенной клетчатой фигуры?
Ответ:
Решение:
Каждый из 2024 людей является рыцарем или лжецом. Некоторые из них дружат друг с другом, причем дружба взаимна. Каждого из них спросили про количество друзей, и все ответы оказались различными целыми числами от 0 до 2023. Известно, что
- все рыцари отвечали на вопрос верно,
- все лжецы изменяли истинный ответ ровно на 1.
Ответ:
Решение:
Двум мальчикам выдали по мешку картошки, в каждом мешке по 150 клубней. Ребята по очереди перекладывают картошку, каждый своим очередным ходом перекладывает ненулевое количество клубней из своего мешка в чужой. При этом они должны соблюдать условие новой возможности: на каждом ходе мальчик должен переложить больше клубней, чем у него было в мешке перед любым из его предыдущих ходов (если такие ходы были). Так, первым своим ходом мальчик может переложить любое ненулевое количество, а своим пятым ходом мальчик может переложить 200 клубней, если перед его первым, вторым, третьим и четвёртым ходами количества клубней в его мешке были меньше 200. Какое максимальное суммарное количество ходов могут совершить ребята?
Ответ:
Решение:
1000 детей, среди которых нет двух одинакового роста, выстроились в шеренгу. Назовём пару различных детей $(a,b)$ хорошей, если между ними не стоит ребёнка, рост которого больше роста одного из $a$ и $b$, но меньше роста другого. Какое наибольшее количество хороших пар могло образоваться? (Пары $(a,b)$ и $(b,a)$ считаются одной и той же парой.)
Ответ:
Решение:
На плоскости отмечены 106 точек, никакие три из которых не лежат на одной прямой, и проведены все отрезки между ними. Гриша поставил на каждом проведённом отрезке вещественное число, по модулю не превосходящее 1, и для каждой шестёрки отмеченных точек посчитал сумму чисел на всех 15 отрезках, соединяющих их. Оказалось, что каждая такая сумма по модулю не меньше числа $C$, при этом среди таких сумм есть как положительная, так и отрицательная. При каком наибольшем $C$ это возможно?
Ответ:
Решение:
В программу соревнования входит 25 видов спорта, в каждом из которых определяется один победитель, получающий золотую медаль. В соревновании участвуют 25 спортсменов, каждый — во всех 25 видах спорта. Имеется 25 экспертов, каждый из которых должен сделать прогноз, сколько золотых медалей получит каждый спортсмен, при этом в его прогнозе количества медалей должны являться целыми неотрицательными числами с суммой 25. Эксперта признают компетентным, если он верно угадает количество золотых медалей хотя бы у одного спортсмена. При каком наибольшем $k$ эксперты могут сделать такие прогнозы, что хотя бы $k$ из них будут признаны компетентными независимо от исхода соревнования?
Ответ:
Решение: