Поиск задач
Ищите по условию, ответу и решению. Можно сузить поиск темой, сложностью и источником, а ввод одного числа — это поиск задачи по её номеру.
Найдено задач: 383
В стране лингвистов существует $n$ языков. Там живет $m$ людей, каждый из которых знает ровно три языка, причём для разных людей эти наборы различны. Известно, что максимальное число людей, любые два из которых могут поговорить без посредников, равно $k$. Оказалось, что $11n\leqslant k\leqslant m/2$. Докажите, что тогда в стране найдутся хотя бы $mn$ пар людей, которые не смогут поговорить без посредников.
Ответ:
Решение:
В Чикаго орудует $36$ преступных банд, некоторые из которых враждуют между собой. Каждый гангстер состоит в нескольких бандах, причём любые два гангстера состоят в разных наборах банд. Известно, что ни один гангстер не состоит в двух бандах, враждующих между собой. Кроме того, оказалось, что каждая банда, в которой не состоит некоторый гангстер, враждует с какой-то бандой, в которой данный гангстер состоит. Какое наибольшее количество гангстеров может быть в Чикаго?
Ответ:
Решение:
На олимпиаду пришло 2018 участников, некоторые из них знакомы между собой. Будем говорить, что несколько попарно знакомых участников образуют «кружок», если любой другой участник олимпиады не знаком с кем-то из них. Докажите, что можно рассадить всех участников олимпиады по 90 аудиториям так, что ни в какой аудитории не будут сидеть все представители какого-либо «кружка».
Ответ:
Решение:
Андрей Михайлович выписал на доску все возможные последовательности длины $2022$, состоящие из $1011$ нулей и $1011$ единиц. Назовём две последовательности совместимыми, если они совпадают ровно в $4$ позициях. Докажите, что Андрей Михайлович может разбить все последовательности на $20$ групп так, чтобы никакие две совместимые последовательности не попали в одну группу.
Ответ:
Решение:
В выпуклом многограннике обозначим через В, Р и Т соответственно число вершин, рёбер и максимальное число треугольных граней, которые имеют общую вершину. Докажите, что $\text{В}\sqrt{\text{Р}+\text{Т}}\geqslant 2\text{Р}$.
Например, для тетраэдра ($\text{В}=4$, $\text{Р}=6$, $\text{Т}=3$) выполняется равенство, а для треугольной призмы ($\text{В}=6$, $\text{Р}=9$, $\text{Т}=1$) или куба ($\text{В}=8$, $\text{Р}=12$, $\text{Т}=0$) имеет место строгое неравенство.
Например, для тетраэдра ($\text{В}=4$, $\text{Р}=6$, $\text{Т}=3$) выполняется равенство, а для треугольной призмы ($\text{В}=6$, $\text{Р}=9$, $\text{Т}=1$) или куба ($\text{В}=8$, $\text{Р}=12$, $\text{Т}=0$) имеет место строгое неравенство.
Ответ:
Решение:
Петя и Вася независимо друг от друга разбивают белую клетчатую доску $100\times 100$ на произвольные группы клеток, каждая из чётного (но не обязательно все из одинакового) числа клеток, каждый — на свой набор групп. Верно ли, что после этого всегда можно покрасить по половине клеток в каждой группе из разбиения Пети в чёрный цвет так, чтобы в каждой группе из разбиения Васи было поровну чёрных и белых клеток?
Ответ:
Решение:
Среди зрителей кинофестиваля было поровну мужчин и женщин. Всем зрителям понравилось одинаковое количество фильмов. Каждый фильм понравился восьми зрителям. Докажите, что не менее $3/7$ фильмов обладают следующим свойством: среди зрителей, которым фильм понравился, не менее двух мужчин.
Ответ:
Решение:
Можно ли расставить в вершинах и в серединах рёбер правильного октаэдра по одному натуральному числу от 1 до 18 так, чтобы все числа были различны, а в каждой вершине стояло число, равное сумме четырёх чисел, стоящих в серединах исходящих из этой вершины рёбер?
Ответ:
Решение:
В каждой клетке квадратной таблицы написано по действительному числу. Известно, что в каждой строке таблицы сумма $k$ наибольших чисел равна $a$, а в каждом столбце таблицы сумма $k$ наибольших чисел равна $b$.
1) Докажите, что если $k=2$, то $a=b$.
2) В случае $k=3$ приведите пример такой таблицы, для которой $a\neq b$.
1) Докажите, что если $k=2$, то $a=b$.
2) В случае $k=3$ приведите пример такой таблицы, для которой $a\neq b$.
Ответ:
Решение:
В клетках таблицы $n\times n$ стоят плюсы и минусы. За один ход разрешается в произвольной строке или в произвольном столбце поменять все знаки на противоположные. Известно, что из начальной расстановки можно получить такую, при которой во всех ячейках стоят плюсы. Докажите, что этого можно добиться не более чем за $n$ ходов.
Ответ:
Решение:
На длинной скамейке сидели мальчик и девочка. К ним по одному подошли ещё $20$ детей, и каждый из них садился между какими-то двумя уже сидящими. Назовём девочку отважной, если она садилась между двумя соседними мальчиками, а мальчика — отважным, если он садился между двумя соседними девочками. Когда все сели, оказалось, что мальчики и девочки сидят на скамейке, чередуясь. Сколько из них были отважными?
Ответ:
Решение:
В строку выписано 81 ненулевое число. Сумма любых двух соседних чисел положительна, а сумма всех чисел отрицательна. Каким может быть знак произведения всех чисел?
Ответ:
Решение:
Назовём расстановку $n$ единиц и $m$ нулей по кругу хорошей, если в ней можно поменять местами соседние нуль и единицу так, что получится расстановка, отличающаяся от исходной поворотом. При каких натуральных $n$, $m$ существует хорошая расстановка?
Ответ:
Решение:
На доске написаны $1000$ последовательных целых чисел. За ход можно разбить написанные числа на пары произвольным образом и каждую пару чисел заменить на их сумму и разность (не обязательно вычитать из большего меньшее, все замены происходят одновременно). Докажите, что на доске больше никогда не появятся $1000$ последовательных целых чисел.
Ответ:
Решение:
На экране суперкомпьютера напечатано число $11\ldots1$ ($900$ единиц). Каждую секунду суперкомпьютер заменяет его по следующему правилу. Число записывается в виде $\overline{AB}$, где $B$ состоит из двух его последних цифр, и заменяется на $2\cdot A+8\cdot B$ (если $B$ начинается на нуль, то он при вычислении опускается). Например, $305$ заменяется на $2\cdot 3+8\cdot 5=46$. Если на экране остаётся число, меньшее $100$, то процесс останавливается. Правда ли, что он остановится?
Ответ:
Решение:
На кольцо свободно нанизано $2009$ бусинок. За один ход любую бусинку можно передвинуть так, чтобы она оказалась ровно посередине между двумя соседними. Существуют ли такие изначальная расстановка бусинок и последовательность ходов, при которых какая-то бусинка пройдёт хотя бы один полный круг?
Ответ:
Решение:
По рёбрам треугольной пирамиды ползают четыре жука, при этом каждый жук всё время остаётся только в одной грани (в каждой грани — свой жук). Каждый жук обходит границу своей грани в определённом направлении, причём так, что любые два жука по общему для них ребру ползут в противоположных направлениях. Докажите, что если скорости (возможно, непостоянные) каждого из жуков всегда больше $1$ см/с, то когда-нибудь какие-то два жука обязательно встретятся независимо от пирамиды, начального положения и скорости жуков.
Ответ:
Решение:
На окружности отмечены 10 точек, занумерованные по часовой стрелке: $A_1$, $A_2$, $\ldots$, $A_{10}$, причём известно, что их можно разбить на пары симметричных относительно центра окружности. Изначально в каждой отмеченной точке сидит по кузнечику. Каждую минуту один из кузнечиков прыгает вдоль окружности через своего соседа так, чтобы расстояние между ними не изменилось. При этом нельзя пролетать над другими кузнечиками и попадать в точку, где уже сидит кузнечик. Через некоторое время оказалось, что какие-то 9 кузнечиков сидят в точках $A_1$, $A_2$, $\ldots$, $A_9$, а десятый кузнечик сидит на дуге $A_9A_{10}A_1$. Можно ли утверждать, что он сидит именно в точке $A_{10}$?
Ответ:
Решение:
Назовем расстановку $n$ единиц и $m$ нулей по кругу хорошей, если в ней можно поменять местами соседние нуль и единицу так, что получится расстановка, отличающаяся от исходной поворотом. При каких натуральных $n$, $m$ существует хорошая расстановка?
Ответ:
Решение:
На доске написано несколько чисел. Разрешается стереть любые два числа $a$ и $b$, а затем вместо одного из них написать число $\dfrac{a+b}{4}$. Какое наименьшее число может остаться на доске после 2018 таких операций, если изначально на ней написано 2019 единиц?
Ответ:
Решение: