Разборов А. А. / Авторы задач / Задачи // Архив журнала «Квант»

Ведущий специалист по теории сложности. Член-корреспондент РАН, единственный российский лауреат премии Неванлинны Международного математического союза (1990), лауреат премии Гёделя (2007, совместно со Стивеном Рудичем). Золотой медалист Международной математической олимпиады (1979).

Персональная страница.‍

См. также

Math-Net.Ru‍

Задачи по математике‍‍

Задача М574
Конечная последовательность $a_1$‍,‍ $a_2$‍,‍ $\ldots$‍,‍ $a_n$‍‍ из чисел 0 и 1 должна удовлетворять следующему условию: для любого целого $k$‍‍ от 0 до $n-1$‍‍ сумма $$ a_1a_{k+1}+a_2a_{k+2}+\ldots+a_{n-k}a_n $$ является нечётным числом.
Задача М650
Существует ли последовательность
$$a_1,\ a_2,\ a_3,\ \ldots,\ a_n, ...$$
1. натуральных чисел такая, что любое натуральное число единственным образом записывается в виде суммы нескольких её членов: $$ a_{i_1}+a_{i_k}\quad(i_1 \lt \ldots \lt i_k,\ k\ge 0); \tag{*} $$
2. натуральных чисел такая, что 1 нe представляется в…
Задача М666
Докажите, что наименьшее общее кратное $n$‍‍ натуральных чисел $a_1 \lt a_2 \lt \ldots \lt a_n$‍‍ не меньше $na_1$‍.‍
Задача М673
На плоскости в вершинах треугольника лежат три шайбы $A$‍,‍ $B$‍,‍ $C$‍.‍ Хоккеист выбирает одну из них и бьёт по ней так, что она проходит между двумя другими и останавливается в какой-то точке.
1. Покажите, как после…
Задача М680
Два связиста играют в такую игру. Имеются $n$‍‍ телефонных узлов, и связисты по очереди соединяют кабелем два из них по своему выбору. Выигрывает тот, после хода которого с любого узла можно будет дозвониться до любого другого (быть может, через несколько промежуточных; начало игры…
Задача М722
В точках $A_1$‍,‍ $A_2$‍,‍ $\dots$‍,‍ $A_n$‍,‍ расположенных по окружности, расставляются в некотором порядке числа $1$‍,‍ $2$‍,‍ $\dots$‍,‍ $n$‍.‍
1. Докажите, что сумма…
Задача М756
В стране, кроме столицы, больше 100 roродов. Столица страны соединена авиалиниями со 100 городами; каждый из остальных городов соединён авиалиниями ровно с 10 городами. Известно, что из любого города можно (быть может, с пересадками) перелететь в любой другой. Докажите, что можно закрыть…
Задача М815
На окружности расставлены $4k$‍‍ точек, занумерованных в произвольном порядке числами 1, 2, $\ldots$‍,‍ $4k$‍.‍
1. Докажите, что эти точки можно соединить $2k$‍‍ попарно непересекающимися отрезками так, что разность…
Задача М959
В стране между некоторыми парами городов установлено авиационное сообщение. Докажите, что можно закрыть не более $\dfrac1{k-1}$‍‍ часть авиалиний таким образом, что среди любых $k$‍‍ городов найдутся два, не соединённые между собой авиалинией, если
Задача М1168
В стране 1989 городов и 4000 дорог (каждая дорога соединяет два города). Докажите, что можно выбрать кольцевой маршрут, проходящий не более чем через 20 городов.
Задача М1214
В некоторых клетках прямоугольной таблицы из $n$‍‍ строк и $m\gt n$‍‍ столбцов расставлены звёздочки так, что в каждом столбце стоит хотя бы одна звёздочка. Докажите, что найдётся такая звёздочка, что в её строке звёздочек больше, чем в её столбце.
Задача М1223
На квадратный лист бумаги со стороной $a$‍‍ посадили несколько клякс, площадь каждой из которых не больше 1. Докажите, что если каждая прямая, параллельная сторонам листа, пересекает не более одной кляксы, то суммарная площадь клякс не больше $a$‍.‍

Разборов А. А.‍12

Задачи по математике‍‍