M1479

Условие

Число 26 можно тремя способами разложить в сумму четырех натуральных чисел так, что все 12 чисел различны:

[latex]26=1+6+8+11=2+5+9+10=3+4+7+12.[/latex]

Для каждого натурального [latex]n[/latex] обозначим через [latex]K=K(n)[/latex] наибольшее число четверок натуральных чисел, дающих в сумме [latex]n[/latex] и состоящих из [latex]4K[/latex] различных чисел. Докажите, что

[latex]K(n)=\left [\frac{n-2}{8} \right ][/latex]

[latex][x][/latex]- целая чатсь числа [latex]x[/latex].

Решение

Пусть выбрано [latex]k[/latex] четверок различных натуральных чисел, в сумме дающих [latex]n[/latex]. Обозначим через [latex]s[/latex] сумму всех [latex]4k[/latex] чисел, входящих в эти четверки. Тогда, одной стороны, [latex]s=nk[/latex], а с другой стороны,

[latex]s\geqslant 1+2+\cdots +4k=2k(4k+1).[/latex]

Поэтому [latex]nk\geqslant 2k(4k+1)[/latex], откуда [latex]k\leqslant \frac{n-2}{8}[/latex].

Осталось привести набор [latex]\left [\frac{n-2}{8} \right ][/latex] четверок чисел, удовлетворяющий условиям задачи.

Обозначим число [latex]\left [\frac{n-2}{8} \right ][/latex] через [latex]a[/latex] и пусть [latex]n=8a+2+t[/latex], где [latex]t=0,1,2,\cdots,7[/latex].

Рассмотрим следующую таблицу чисел:

[latex]\begin{matrix}&1 &2 &3 &\cdots &a-1 &a \\ &2a &2a-1 &2a-2 &\cdots &a+2 &a+1 \\ &2a+1 &2a+2 &2a+3 &\cdots &3a-1 &3a \\ &4a+t &4a+t-1 &4a+t-2 &\cdots &3a+t+2 &3a+t+1 \end{matrix}[/latex]

Числа, стоящие в первом столбце, образуют первую четверку чисел, стоящие во втором — вторую четверку чисел, и так далее.

Л.Курляндчик

M2098

Задача М2098

Двое играют в игру, делая ходы по очереди: первый рисует на плоскости многоугольник, не налегающий на уже нарисованные, а второй ответным ходом раскрашивает его в один из 2008 цветов. Второй игрок хочет, чтобы любые два многоугольника, граничащие по отрезку сторны, имели разные цвета. Сможет ли первый игрок помешать ему?

Ответ: сможет

Решение

Докажем индукцией по [latex]n[/latex], что первый может играть так, что нарисованные им многоугольники будут давать в объединении некоторый многоугольник [latex]P_{n}[/latex], на границу которого выходят многоугольники не менее [latex]n[/latex] цветов. Отсюда будет следовать, что никакого конечного числа цветов недостаточно.

База индукции очевидна. Пусть утверждение верно для [latex]n=k[/latex], докажем его для [latex]n=k+1[/latex]. Из предположения индукции следует, что первый игрок может играть так, чтобы нарисованные многоугольники давали в объединении [latex]k[/latex] многоугольников [latex]P_{k}^{(1)},P_{k}^{(2)},’cdots,P_{k}^{(k)}[/latex], на границу каждого из которых выходят многоугольники не менее [latex]k[/latex] цветов. На границе многоугольника [latex]P_{k}^{(1)}[/latex] выделим отрезок [latex]Delta_{1}[/latex] некоторго цвета 1, на границе многоугольника [latex]P_{k}^{(2)}[/latex] выделим отрезок [latex]Delta_{2}[/latex] некоторго цвета 2, отличного от 1, и т.д., на границе многоугольника [latex]P_{k}^{(k)}[/latex] выделим отрезок [latex]Delta_{k}[/latex] некоторго цвета k, отличного от уже определенных цветов [latex]1,2,cdots,k-1[/latex]. Пусть теперь первый нарисует многоугольник [latex]P[/latex], пересекающийся с многоугольником [latex]P_{k}^{(i)}[/latex] по части отрезка [latex]Delta_{i}[/latex] для всех [latex]i=1,2,cdots,k[/latex] (рис.). Второй игрок должен раскрасить многоугольник [latex]P[/latex] в цвет, отличный от цветов [latex]1,2,cdots,k[/latex]. Тогда на границу многоугольника, являющего объединением многоугольников [latex]P,P_{k}^{(1)},P_{k}^{(2)},cdots,P_{k}^{(k)}[/latex], выходят не менее [latex]k+1[/latex] цветов. Переход индукции доказан.

Замечания

Строгое доказательство существования многоугольника [latex]P[/latex] из решения задачи далеко не просто (хотя интуитивно все очевидно), оно следует из известной топологической теоремы Жордана.

Отметим, что вопрос, поставленный в задаче, уже рассматривался в «Задачнике «Кванта»» для случая, когда первому игроку позволяется рисовать многоугольники лишь специального вида. Результат этой задачи интресно сопоставить также со знаменитой теоремой о четырех красках, согласно которой для раскрашивания правильным образом любой карты на плоскости достаточно лишь четырех цветов.

Е.Гик, П.Кожевников

M1538

Условие:

Прямоугольник [latex]atimes b(a>b)[/latex] разбит на прямоугольные треугольники, граничащие друг с другом только по целым сторонам, так что общая сторона двух треугольников всегда служит катетом одного и гипотенузой другого.Докажите, что [latex]frac{a}{b}geq2.[/latex]

Решение:

Пусть наш прямоугольник — [latex]ABCD[/latex]. Докажем, что вершина треугольника разбиения не может лежать внутри прямоугольника. Действительно, допустим противное, пусть хотя бы одна вершина внутри прямоугольника существует. Значит, существуют и стороны треугольников разбиения, которые обладают таким свойством: хотя бы один конец этой стороны лежит внутри прямоугольника. Рассмотрим множество [latex]M[/latex] сторон, обладающих этим свойством. По условию задачи, эта сторона для одного из примыкающих к ней треугольников разбиения служит гипотенузой. Тогда катет этого треугольника, выходящий из этой же точки, а следовательно, тоже принадлежащий множеству [latex]M[/latex], будет короче гипотенузы, т.е. короче кратчайшего отрезка множества [latex]M[/latex]. Противоречие. Итак, все вершины треугольников разбиения лежат на границе прямоугольника.

Теперь рассмотрим самую длинную из сторон треугольников разбиения: пусть это сторона [latex]m[/latex]. Она принадлежит одной из сторон прямоугольника. Действительно, иначе [latex]m[/latex] служила бы катетом для некоторого треугольника, а его гипотенуза был бы ещё длиннее. Пусть [latex]m[/latex] лежит на стороне [latex]AB[/latex] прямоугольника (см. рисунок).

Рассмотрим треугольник разбиения, гипотенузой которого служит [latex]m[/latex]. Вершина его прямого угла может лежать только на стороне [latex]CD[/latex]. Высота этого треугольника равна стороне [latex]BC[/latex]. Но высота [latex]h[/latex] прямоугольного треугольника не превышает половины гипотенузы, следовательно, [latex]mgeq 2h[/latex], откуда [latex]ABgeq 2BC[/latex], что и требуется.

А.Шаповалов, Н.Константинов

M1537

Условие:

Про [latex]n[/latex] чисел, произведение которых равно [latex]p[/latex], известно, что разность между [latex]p[/latex] и каждым из этих чисел — нечётное целое число. Докажите, что все эти числа иррациональны.

Решение:

Пусть x — одно из этих n чисел. [latex]x+b_{1} , x+b_{2}, … , x+b_{n-1}[/latex] — остальные и

[latex] p = x(x+b_{1})(x+b_{2})…(x+b_{n+1})=x+c, (1)[/latex]

где, по условию, [latex]c[/latex] нечётно, а [latex]b_{1} , b_{2}, … , b_{n-1}[/latex] должны быть чётными целыми числами. Равенство [latex](1)[/latex] можно записать, раскрыв скобки в виде

[latex] x^{n} +a_{1}x^{n-1} + a_{2}x^{n-2} +…+a_{n-2}x^{2}+x{n-1}x=c, (2)[/latex]

где [latex]a_{1},…,a_{n-2} [/latex] — чётные, а [latex]a_{n-1}=b_{1}b_{2}…b_{n-1}-1[/latex] и [latex]c[/latex] — нечётные числа.Предположив, что [latex]x[/latex] — рациональное число, мы сразу же убедимся, что [latex]x[/latex] должно быть целым:если [latex]x=k/d[/latex] — несократимая дробь, [latex]d>1[/latex], то, подставив [latex]x[/latex] в [latex](2)[/latex] и умножив обе части на [latex]d^{n-1}[/latex] , мы придём к противоречию.Но и целым [latex]x[/latex] тоже быть не может: и при чётном, и при нечётном [latex]x[/latex] левая часть — четная (в последнем случае два крайние числа нечётны, а остальные чётны), а [latex]c[/latex] — нечётно. Полученное противоречие доказывает, что [latex]x[/latex] (и любой из остальных корней уравнения (1) с чётными [latex]b[/latex], и нечётным [latex]c[/latex]) может быть только иррациональным.

Н.Васильев, Г.Гальперин

M1537. Произведение и разность чисел

Условие:

Решение:

Пусть x — одно из этих n чисел. [latex]x+b_{1} , x+b_{2}, … , x+b_{n-1}[/latex] — остальные и

[latex] p = x(x+b_{1})(x+b_{2})…(x+b_{n+1})=x+c, (1)[/latex]

[latex] x^{n} +a_{1}x^{n-1} + a_{2}x^{n-2} +…+a_{n-2}x^{2}+x{n-1}x=c, (2)[/latex]

Н.Васильев, Г.Гальперин