Пару многочленов $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$ нечётно, то в последней партии играли девочка и мальчик с нечётными номерами.
Ответ:
Решение:
В вершины правильного 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$?
Ответ:
Решение:
Пусть $n\gt 1$ — натуральное число. Выпишем дроби $\frac{1}{n}$, $\frac{2}{n}$, $\ldots$, $\frac{n-1}{n}$ и приведём каждую к несократимому виду; сумму числителей полученных дробей обозначим через $f(n)$. При каких натуральных $n\gt 1$ числа $f(n)$ и $f(2015n)$ имеют разную чётность?
Ответ:
Решение:
В электронную таблицу, где две строки и $n$ столбцов, в произвольном порядке записаны все натуральные числа от 1 до $2n$ (в каждой клетке — одно число). В полдень каждого дня компьютер случайным образом выбирает столбец, где число из верхней строки больше числа из нижней, и меняет эти два числа местами, а затем случайным образом переставляет числа в верхней строке. В момент, когда в каждом столбце верхнее число оказывается меньше нижнего, процесс заканчивается. Докажите, что такой процесс не может происходить дольше, чем $n^2$ дней.
Ответ:
Решение:
На экране калькулятора горит число 41. За одну операцию можно увеличить или уменьшить число на экране на 33 или 34. При этом запрещается получать числа, меньшие 1, и числа, большие 99. Через 2025 операций на экране оказалось число 50. Докажите, что в некоторый момент на экране было число 67.
Ответ:
Решение:
На доске написаны натуральные числа от 1 до 1000, по одному разу каждое. Вася может стереть любые два числа и записать вместо них одно: их наибольший общий делитель или их наименьшее общее кратное. Через 999 таких операций на доске осталось одно число, равное натуральной степени десятки. Какое наибольшее значение она может принимать?
Ответ:
Решение:
На доске написаны числа 1, 2, $\ldots$, 1000. Разрешается стереть любые два числа $a$ и $b$ и записать вместо них числа $ab$ и $a^2+b^2$. Можно ли такими операциями добиться, чтобы среди чисел, написанных на доске, было хотя бы 700 одинаковых?
Ответ:
Решение:
В полдень Вася положил на стол 10 вырезанных из бумаги выпуклых десятиугольников. Затем он время от времени брал ножницы, разрезал по прямой один из лежащих на столе многоугольников на два и клал оба получившихся куска назад на стол. К полуночи Вася проделал такую операцию 51 раз. Докажите, что в полночь среди лежащих на столе многоугольников был треугольник или четырёхугольник.
Ответ:
Решение:
Делитель натурального числа называется собственным, если он меньше этого числа, но больше 1. У натурального числа $n$ нашли все собственные делители (их оказалось не меньше трёх) и записали всевозможные их попарные суммы (повторно одинаковые суммы не записывали). Докажите, что полученный набор не мог оказаться набором всех собственных делителей никакого натурального числа.
Ответ:
Решение:
40 разбойников переправились с помощью двухместной лодки с левого берега реки на правый (некоторые рейсы, возможно, выполнялись в одиночку). Могло ли случиться, что каждая пара разбойников пересекла реку вместе ровно один раз (с левого берега на правый или с правого на левый)?
Ответ:
Решение:
У Кати есть $2n$ катушек с лентами ($n$ — натуральное число). Изначально на катушках намотано $1^2, 2^2, \ldots, (2n)^2$ дециметров ленты соответственно. Каждый час Катя выбирает натуральное число $i$ и отрезает по $i$ дециметров ленты от всех катушек, на которых осталось не менее $i$ дециметров ленты. Через некоторое время все катушки, на которых изначально было нечётное количество дециметров ленты, оказались пустыми. Докажите, что в этот момент длина оставшейся ленты на каждой из остальных катушек меньше $4n$ дециметров.
Ответ:
Решение: