Для каких натуральных $n$ найдутся такие целые числа $a$, $b$, $c$, $d$, большие, чем $10^{2026}$, что \[ a^2+b^2=c^2+d^2\quad\text{и}\quad a+b-c-d=n? \]
Ответ:
Решение:
В кружке 42 человека, любые двое из которых имеют среди кружковцев не менее десяти общих друзей. Докажите, что найдутся двое, имеющие среди кружковцев не менее двенадцати общих друзей.
Ответ:
Решение:
Сначала Саша прямолинейными разрезами, каждый из которых соединяет две точки на сторонах квадрата, делит квадрат со стороной 2 на 2020 частей. Затем Дима вырезает из каждой части по кругу. Докажите, что Дима всегда может добиться того, чтобы сумма радиусов этих кругов была не меньше 1.
Ответ:
Решение:
Замкнутая ломаная состоит из 1001 звена и такова, что никакие три её вершины не лежат на одной прямой. Известно, что каждое её звено, кроме, может быть, двух, пересекает все 998 звеньев, не имеющих с ним общих концов. Верно ли, что каждое из двух оставшихся звеньев тоже пересекает все 998 звеньев, не имеющих с ним общих концов?
Ответ:
Решение:
На доске написано 100 натуральных чисел, среди которых ровно 33 нечётных. Каждую минуту на доску дописывается сумма всех попарных произведений всех чисел, уже находящихся на ней (например, если на доске были записаны числа 1, 2, 3, 3, то следующим ходом было дописано число $1\cdot2+1\cdot3+1\cdot3+2\cdot3+2\cdot3+3\cdot3$). Можно ли утверждать, что рано или поздно на доске появится число, делящееся на $2^{10000000}$?
Ответ:
Решение:
Дана окружность длины 90. Можно ли отметить на ней 10 точек так, чтобы среди дуг с концами в этих точках имелись дуги со всеми целочисленными длинами от 1 до 89?
Ответ:
Решение:
Некоторые рёбра выпуклого многогранника удалось покрасить в красный цвет так, что в каждую вершину входит ровно два красных ребра, причём эти ребра лежат в одной грани. Кроме того, в каждой грани оказалось не более двух красных ребер. Сколько вершин может быть в таком многограннике?
Ответ:
Решение:
Петя выбрал 100 попарно различных положительных чисел, меньших 1, и расставил их по кругу. Затем он проделывает с ними операции. За одну операцию можно взять три стоящих подряд (именно в таком порядке) числа $a$, $b$, $c$ и заменить число $b$ на $a-b+c$. При каком наибольшем $k$ Петя мог выбрать исходные числа и сделать несколько операций так, чтобы после них среди чисел оказалось $k$ целых?
Ответ:
Решение:
Пару многочленов $F(x,y)$ и $G(x,y)$ с целыми коэффициентами назовём важной, если из делимости на 100 обеих разностей $F(a,b)-F(c,d)$ и $G(a,b)-G(c,d)$, где $a$, $b$, $c$, $d$ — целые, следует, что числа $a-c$ и $b-d$ делятся на 100. Существует ли такая важная пара многочленов $P(x,y)$, $Q(x,y)$, что пара многочленов $P(x,y)-xy$ и $Q(x,y)+xy$ также является важной?
Ответ:
Решение:
Изначально в строку выписывают 250 букв — 125 букв А и 125 букв Б в некотором порядке. Затем за одну операцию можно взять любой кусок из нескольких подряд стоящих букв, среди которых поровну букв А и Б, и переставить буквы в этом куске в обратном порядке, поменяв в этом куске все буквы А на буквы Б и буквы Б на буквы А. (Например, из строки А$\underbrace{\text{БАББАА}}$Б можно одной операцией получить строку А$\underbrace{\text{ББААБА}}$Б.) Можно ли выписать исходную строку и совершить несколько операций так, чтобы в результате на доске оказалась та же строка, буквы которой записаны в обратном порядке?
Ответ:
Решение:
В каждой строке таблицы $100\times n$ в некотором порядке стоят числа от 1 до 100, числа в строке не повторяются (в таблице $n$ строк и 100 столбцов). Разрешается поменять местами в строке два числа, отличающиеся на 1, если они не стоят рядом. Оказалось, что с помощью таких операций нельзя получить двух одинаковых строк. При каком наибольшем $n$ это возможно?
Ответ:
Решение:
Квадрат $100\times100$ разбит на квадраты $2\times2$. Потом его разбивают на доминошки (прямоугольники $1\times2$ и $2\times1$). Какое наименьшее количество доминошек могло оказаться внутри квадратов разбиения?
Ответ:
Решение:
С одной стороны теннисного стола выстроилась очередь из $n$ девочек, а с другой — из $n$ мальчиков. И девочки, и мальчики пронумерованы числами от 1 до $n$ в том порядке, как они стоят. Первую партию играют девочка и мальчик с номерами 1, а далее после каждой партии проигравший встаёт в конец своей очереди, а победивший играет со следующим. Через некоторое время оказалось, что каждая девочка сыграла ровно одну партию с каждым мальчиком. Докажите, что если $n$ нечётно, то в последней партии играли девочка и мальчик с нечётными номерами.
Ответ:
Решение:
В компании некоторые пары людей дружат (если $A$ дружит с $B$, то и $B$ дружит с $A$). Оказалось, что среди каждых 100 человек в компании количество пар дружащих людей нечётно. Найдите наибольшее возможное количество человек в такой компании.
Ответ:
Решение:
В вершины правильного 100-угольника поставили 100 фишек, на которых написаны номера $1, 2, \ldots, 100$, именно в таком порядке по часовой стрелке. За ход разрешается обменять местами некоторые две фишки, стоящие в соседних вершинах, если номера этих фишек отличаются не более чем на $k$. При каком наименьшем $k$ серией таких ходов можно добиться расположения, в котором каждая фишка сдвинута на одну позицию по часовой стрелке (по отношению к своему начальному положению)?
Ответ:
Решение:
В компании некоторые пары людей дружат (если $A$ дружит с $B$, то и $B$ дружит с $A$). Оказалось, что при любом выборе 101 человека из этой компании количество пар дружащих людей среди них нечётно. Найдите наибольшее возможное количество человек в такой компании.
Ответ:
Решение:
Изначально на доске написана пара чисел $(1,1)$. Если для некоторых $x$ и $y$ на доске написана одна из пар $(x,y-1)$ и $(x+y,y+1)$, то можно дописать другую. Аналогично, если на доске написана одна из пар $(x,xy)$ и $\left(\frac{1}{x},y\right)$, то можно дописать другую. Докажите, что в каждой выписанной паре первое число будет положительным.
Ответ:
Решение:
Изначально на доску выписали числа $1-\sqrt{2}$, $\sqrt{2}$ и $1+\sqrt{2}$. Каждую минуту с доски стираются все три написанных на ней числа $x$, $y$ и $z$, а вместо них на доску записываются числа $x^2+xy+y^2$, $y^2+yz+z^2$ и $z^2+zx+x^2$. Могут ли в некоторый момент все три числа на доске оказаться рациональными?
Ответ:
Решение:
Изначально на стол положили 100 карточек, на каждой из которых записано по натуральному числу; при этом было ровно 43 карточки с нечётными числами. Затем каждую минуту проводилась следующая процедура. Для каждых трёх карточек, лежащих на столе, вычислялось произведение записанных на них чисел, все эти произведения складывались, и полученное число записывалось на новую карточку, которая добавлялась к лежащим на столе. Через год после начала процесса выяснилось, что на столе есть карточка с числом, кратным $2^{10000}$. Докажите, что число, кратное $2^{10000}$, было на одной из карточек уже через день после начала.
Ответ:
Решение:
Изначально на стол кладут 100 карточек, на каждой из которых записано по натуральному числу; при этом среди них ровно 28 карточек с нечётными числами. Затем каждую минуту проводится следующая процедура. Для каждых 12 карточек, лежащих на столе, вычисляется произведение записанных на них чисел, все эти произведения складываются, и полученное число записывается на новую карточку, которая добавляется к лежащим на столе. Можно ли выбрать исходные 100 чисел так, что для любого натурального $d$ на столе рано или поздно появится карточка с числом, кратным $2^d$?
Ответ:
Решение: