М1768. Аэробус

Задача из журнала «Квант» (2001 год, 5 выпуск)

Условие

а) Расположите первые [latex]100[/latex] натуральных чисел в таком порядке, чтобы для любых нескольких (но не всех) из этих чисел сумма номеров занятых ими мест не равнялась сумме самих этих чисел.

б*) При посадке в аэробус пассажиры сели куда попало. В итоге все места оказались заняты, а для любого множества, в котором не более [latex]100[/latex] пассажиров, среднее арифметическое номеров занятых ими мест не менее чем на [latex]1[/latex] отличается от среднего арифметического номеров мест, указанных в билетах. Каково наименьшее возможное число мест в таком аэробусе?

Решение

а) Укажем два способа: [latex]100, 1, 2, \ldots, 97, 98, 99[/latex] и [latex]2, 3,4, \ldots, 99, 100, 1[/latex]. Каждый из них дает требуемое расположение чисел, в чем легко непосредственно убедиться.

б) Ответ: [latex]301[/latex] место.
Каждый пассажир включен в один из циклов вида [latex]P_{1}, P_{2}, \ldots , P_{m}[/latex], где [latex]P_{1}, P_{2}, \ldots , P_{m}[/latex] – некоторые пассажиры, причем [latex]P_{i}[/latex]-й пассажир ([latex]i =  1, 2, \ldots , m — 1[/latex]) имеет билет на место, которое занимает [latex]P_{i+1}[/latex]-й пассажир, а [latex]P_{m}[/latex]-й пассажир – на место, которое занимает [latex]P_{1}[/latex]-й пассажир. Если в таком цикле [latex]100[/latex] пассажиров или менее, то все они могли составить одну рассматриваемую группу, для которой среднее арифметическое номеров занимаемых ими мест равно среднему арифметическому номеров мест, указанных в их билетах, что противоречит условию. Поэтому [latex]m \geq 101 + r \geq 202[/latex]. Значит, если число циклов не меньше [latex]3[/latex], то в аэробусе размещаются [latex]303[/latex] или более пассажиров. Заметим далее, что если [latex]P_{k}, P_{k+1}, \ldots , P_{k+r} [/latex]– цепочка пассажиров, последовательно включенных в некоторый цикл, причем номера билетов [latex]P_{k}[/latex]-го и [latex]P_{k+r}[/latex]-го отличаются на [latex]1[/latex], то [latex]r \geq 101[/latex]. Рассматривая цепочку [latex]P_{k+r}, P_{k+r+1} , \ldots , P_{m}, P_{1}, \ldots , P_{k}[/latex], получим неравенство [latex]m — (k + r) + k \geq 101[/latex]. Следовательно, [latex]m \geq 101 + r \geq 202[/latex] , и поэтому число мест в аэробусе может быть меньшим, чем [latex]303[/latex], только если выполняется одно из следующих условий:

  1. Все пассажиры включены в один цикл;
  2. Число циклов равно [latex]2[/latex], причем любые два билета на соседние (по номерам) места принадлежат пассажирам из разных циклов.

Пусть выполнено первое условие. Рассмотрим пассажиров [latex]A_{n}, A_{n+1}[/latex] и [latex]A_{n+2}[/latex] с билетами на [latex]n[/latex]-е, [latex](n + 1)[/latex]-е и [latex](n + 2)[/latex]-е места соответственно. Между [latex]A_{n}[/latex]-м и [latex]A_{n+1}[/latex]-м пассажирами в кратчайшей из цепочек, их соединяющих, имеется не менее [latex]100[/latex] пассажиров, между [latex]A_{n+1}[/latex]-м и [latex]A_{n+2}[/latex]-м также не менее [latex]100[/latex] пассажиров, а между [latex]A_{n+2}[/latex]-м и [latex]A_{n}[/latex]-м либо нет ни одного пассажира, либо имеется не менее [latex]100[/latex]. Значит, если общее число мест меньше [latex]303[/latex], то либо [latex]A_{n}[/latex] сидит на [latex](n + 2)[/latex]-м месте, либо [latex]A_{n+2}[/latex] сидит на [latex]n[/latex]-м месте. Ввиду произвольности номера [latex]n[/latex] имеем (с точностью до направления) цикл [latex]A_{1} A_{3} A_{5} \ldots A_{N}A_{2}A_{4} \ldots A_{N’}[/latex], где [latex]N[/latex] и [latex]N'[/latex] – наибольший нечетный и наибольший четный номера соответственно, а [latex]A_{i}[/latex]–пассажир, занимающий [latex]i[/latex]-е место, [latex]i = 1, 2, \ldots, max ( N, N’)[/latex].Пассажиры, сидящие на местах [latex]N, 2, 4, \ldots , 198[/latex], имеют билеты на места [latex]2, 4, 6, \ldots , 200[/latex], а разность соответствующих средних равна [latex](N — 200) : 100[/latex]. Так как эта разность больше [latex]1[/latex], получаем [latex]N \geq 301[/latex]. Нетрудно убедиться, что цикл [latex] A_{1}A_{3}A_{5} \ldots A_{301}A_{2}A_{4} \ldots A_{300}[/latex] удовлетворяет условиям задачи. Пусть теперь выполнено второе условие, т.е. имеются два цикла, каждый из которых включает всех пассажиров с билетами на места одной четности. Если в каком-нибудь из этих циклов пассажир [latex]A_{n}[/latex] сидит не на [latex](n + 2)[/latex]-м месте, а [latex]A_{n+2}[/latex]– не на [latex]n[/latex]-м месте, то в цикле не менее [latex]202[/latex] пассажиров, а в аэробусе – не менее [latex]403[/latex] мест. В противном же случае имеем (с точностью до направления) цикл [latex]A_{1}A_{3}A_{5} \ldots A_{N}[/latex] , где пассажиры с билетами на места [latex]1,3, 5, \ldots , 199[/latex] сидят на местах [latex]N, 1, 3, \ldots , 197[/latex]; разность соответствующих средних арифметических [latex] (N — 199) :100[/latex] больше [latex]1[/latex], откуда [latex]N \geq 301[/latex].

С.Токарев

М1762. Две тысячи делителей

Задача из журнала «Квант» (2001 год, 4 выпуск)

Условие

Существует ли натуральное число $n$ такое, что $n$ имеет ровно $2000$ различных простых делителей и $2^n+1$ делится на $n$?

Решение

Докажем по индукции, что для любого натурального $k$ существует натуральное $n_k$, имеющее $k$ различных простых делителей, делящееся на $3$ и такое, что $2^{n_k}+1$ делится на $n_k$.

Для $k=1$ можно взять $n=3$. Пусть число $n_k=n$, кратное $3$, имеет $k$ различных простых делителей, причём $2^n+1$ делится на $n$.

Число $2^{3n}+1=\left(2^n+1\right)\left(2^{2n}-2n+1\right)$ делится на $3n$. Это следует из того, что $2^n+1$ делится на $n$, а
$$2^{2n}-2^n+1=\left(2^n-2\right)\left(2^n+1\right)+3\;\;\;(*)$$ делится на $3$ (поскольку при нечётном $n$ числа $2^n+1$ и $2^n-2$ делятся на $3$).

Далее, число $2^{2n}-2^n+1$ не делится на $9$, поскольку на $9$ делится произведение $\left(2^n-2\right)\left(2^n+1\right)$. Значит, поскольку $2^{2n}-2^n+1>3$ при $n>1$, то это число имеет при $n>1$ простой делитель $p>3$. Так как НОД $\left(2^n+1, 2^{2n}-2^n+1\right)=3$ (это тоже ясно из равенства $(*)$), то $p$ — не делитель $n$.

Из сказанного следует, что число $3pn$ имеет $k+1$ простой делитель, причём $2^{3pn}+1$ делится на $3pn$. Последнее следует, например из равенства
$$\left(2^{3n}\right)^p+1=\left(2^{3n}+1\right)\left(\left(2^{3n}\right)^{p-1}-\left(2^{3n}\right)^{p-2}+\cdots+1\right)$$

Для завершения решения достаточно положить $n_{k+1}=3pn=3pn_k$.

А.Егоров, В.Сендеров

М1759. Остроугольный прямоугольник

Задача из журнала «Квант» (2001 год, 4 выпуск)

Условие

Имеется остроугольный треугольник с меньшей стороной $c$ и противолежащим ей углом $\gamma$ . Известно, что треугольник можно раскрасить в два цвета так, что расстояние между любыми двумя точками одного цвета будет не больше $с$. Докажите, что $\gamma \geqslant 36^\circ$.

Решение

Рисунок к задачеРассмотрим треугольник $ABC$ с длинами сторон $AB=c$, $BC=a$, $CA=b$, причём $a \geqslant b \geqslant c$; углы при вершинах $A$, $B$ и $C$ обозначим соответственно через $\alpha$, $\beta$ и $\gamma$.

Пусть точка $K$ — середина стороны $BC$, точка $A_1$ — пересечение серединного перпендикуляра к $BC$ и стороны $AC$ (см. рисунок).

Из условия задачи следует, что в указанной раскраске вершины $B$ и $C$ должны быть разного цвета, поскольку расстояние между ними больше $c$ (если оно равно $c$, то треугольник равносторонний, и для него утверждение задачи выполняется). Значит, точка $A_1$ должна иметь одинаковый цвет с одной из точек $B$ или $C$.

В любом случае должно выполняться неравенство $AB \geqslant A_1C$, которое равносильно следующим неравенствам:
$$c \geqslant \frac{a}{2\cos\gamma}\;;\;\frac{\sin\gamma}{\sin\alpha}\geqslant\frac{1}{2\cos\gamma};$$
$$\sin2\gamma \geqslant \sin\alpha\;;\;\alpha \leqslant 2\gamma \leqslant \pi-\alpha$$
Учитывая, что $2\gamma \leqslant \beta+\gamma=\pi-\alpha$, имеем: $AB \geqslant A_1C \Leftrightarrow \alpha \leqslant 2\gamma .$

Завершаем доказательство:
$$180^\circ = \alpha+\beta+\gamma \leqslant 2\gamma+2\gamma+\gamma=5\gamma \Rightarrow \gamma \geqslant 36^\circ .$$

А.Эвнин

М1730. Выпуклый четырехугольник

Задача из журнала «Квант» (2000 год, 6 выпуск)

Условие задачи

Продолжения противоположных сторон произвольного выпуклого четырехугольника [latex]ABCD[/latex] пересекаются в точках [latex]M[/latex] и [latex]K[/latex]  $(рис.1)$. Через точку [latex]O[/latex] пересечения его диагоналей проводится прямая, параллельная [latex]MK[/latex]. Докажите, что отрезок этой прямой, заключенный внутри четырехугольника, делится точкой  [latex]O[/latex] пополам.

Решение

Проведем  через точку [latex]D[/latex] прямую [latex]l[/latex] (сделайте чертеж самостоятельно), параллельную [latex]KM[/latex]; пусть  [latex]E[/latex] и [latex]F[/latex] — точки пересечения [latex]l[/latex] с прямыми [latex]BC[/latex] и [latex]BA[/latex] соответственно.  Пусть для определенности прямая, проходящая через [latex]O[/latex] параллельно [latex]KM[/latex] и [latex]l[/latex] пересекает стороны [latex]AB[/latex] и [latex]CD[/latex] четырехугольника. В этом случае для решения задачи надо доказать, что точка [latex]O[/latex] лежит на медиане [latex]KL[/latex] треугольника [latex]DKF[/latex]. Мы докажем, что [latex]O[/latex] — точка пересечения медиан [latex]KL[/latex] и [latex]MN[/latex] треугольников [latex]DKF[/latex] и [latex]DME[/latex] соответственно. Обозначим точку пересечения медиан [latex]KL[/latex] и [latex]MN[/latex] через [latex]X[/latex].

Докажем вначале, что [latex]X[/latex] лежит на [latex]BD[/latex], т. е. что прямые [latex]DX[/latex] и [latex]BD[/latex] совпадают. Для этого докажем, что они делят отрезок [latex]KM[/latex] в одном и том же соотношении.

Пусть  [latex]Y[/latex] — точка пересечения [latex]DX[/latex] и [latex]KM[/latex]. Имеем [latex]\frac {\displaystyle KY}{ \displaystyle LD} = \frac{\displaystyle XY}{\displaystyle DX}[/latex] (поскольку треугольники [latex]XYK[/latex] и [latex]XDL[/latex] подобны), [latex]\frac{ \displaystyle MY}{\displaystyle DN}\ = \frac{\displaystyle XY}{\displaystyle DX}\[/latex]. Поэтому [latex]\frac{\displaystyle KY}{\displaystyle MY}\ = \frac{\displaystyle LD}{\displaystyle DN}\[/latex]. Аналогично доказывается, что [latex]BD[/latex] делит [latex]KM[/latex] в отношении [latex]\frac{\displaystyle FD}{\displaystyle DE}\[/latex]. Но [latex]FD = 2LD[/latex], [latex]DE = 2DN[/latex].

Осталось доказать, что [latex]X[/latex] лежит на отрезке [latex]AC[/latex]. Другими словами, что [latex]KL[/latex] и [latex]MN[/latex] делят отрезок [latex]AC[/latex] в одном и том же отношении.

Лемма 1.
[latex]\frac{\displaystyle VS}{\displaystyle BV}\ = \frac{\displaystyle AS}{\displaystyle AC}\[/latex], где [latex]S[/latex] — точка на стороне [latex]AC[/latex] треугольника [latex]ABC[/latex], [latex]V[/latex] — точка пересечения прямой [latex]BS[/latex] с медианой [latex]AN[/latex] этого треугольника.

Рассмотрим точку [latex]T[/latex] отрезка [latex]BC[/latex] такую, что [latex]ST[/latex] [latex]||[/latex] [latex]AN[/latex]. Из теоремы Фалеса следует, что [latex]\frac{\displaystyle VS}{\displaystyle BV}\ = \frac{\displaystyle NT}{\displaystyle BN}\ = \frac{\displaystyle NT}{\displaystyle NC}\ = \frac{\displaystyle AS}{\displaystyle AC}\ [/latex].

Лемма 2.
[latex]\frac{\displaystyle VS}{\displaystyle UV} = \left(\frac{\displaystyle AS}{\displaystyle AU}\right) \cdot \left (\frac{\displaystyle AB}{\displaystyle AC} \right )[/latex], где [latex]U[/latex] и [latex]S[/latex] — точки на сторонах [latex]AB[/latex] и [latex]AC[/latex] треугольника [latex]ABC[/latex] соответственно, а [latex]V[/latex] — точка пересечения прямой [latex]US[/latex] с медианой [latex]AN[/latex] этого треугольника.

На стороне [latex]AC[/latex] возьмем точку [latex]Z[/latex] такую, что [latex]UZ[/latex] [latex]||[/latex] [latex]BC[/latex].  По лемме 1 имеем [latex]\frac{\displaystyle VS}{\displaystyle UV}\ = \frac{\displaystyle AS}{\displaystyle AZ}\[/latex], а по теореме Фалеса [latex]\frac{\displaystyle AC}{\displaystyle AB}\ = \frac{\displaystyle AZ}{\displaystyle AU}\[/latex]. Осталось перемножить эти равенства.

Доказанные утверждения позволяют завершить решение задачи. Именно, по лемме 2 медиана [latex]KL[/latex] делит отрезок [latex]AC[/latex] (считая от [latex]C[/latex])  в отношении [latex]m = \left(\frac{\displaystyle CK}{\displaystyle KD}\right) \cdot \left (\frac{\displaystyle KF}{\displaystyle AK} \right )[/latex], а медиана [latex]MN[/latex] — в отношении [latex]n = \left(\frac{\displaystyle MC}{\displaystyle ME}\right) \cdot \left (\frac{\displaystyle MD}{\displaystyle MA} \right )[/latex]. Но [latex]\frac{\displaystyle MC}{\displaystyle ME}\ = \frac{\displaystyle KC}{\displaystyle KD}\[/latex],  [latex]\frac{\displaystyle KF}{\displaystyle AK}\ = \frac{\displaystyle MD}{\displaystyle MA}\[/latex]. Следовательно, [latex]m = n[/latex].
Утверждение задачи доказано.

Замечание. Вот ещё одно, более естественное, хотя и несколько более сложное, доказательство леммы 2.

Проведем через [latex]V[/latex] параллельные [latex]AS[/latex] и [latex]AU[/latex] прямые $(рис. 2)$.

Имеем: [latex]\frac{\displaystyle x}{\displaystyle y} = \frac{\displaystyle AC}{\displaystyle AB}[/latex] (это характеристическое свойство точек медианы!). Теорема Фалеса дает: [latex]\frac{\displaystyle VS}{\displaystyle y} = \frac{\displaystyle US}{\displaystyle AU}[/latex], [latex]\frac{\displaystyle x}{\displaystyle UV} = \frac{\displaystyle AS}{\displaystyle US}[/latex]. Перемножая эти два равенства, получаем
[latex]\frac{\displaystyle VS}{\displaystyle UV} = \left(\frac{\displaystyle AS}{\displaystyle AU}\right) \cdot \left (\frac{\displaystyle y}{\displaystyle x} \right ) = \left (\frac{\displaystyle AS}{\displaystyle AU} \right ) \cdot \left (\frac{\displaystyle AB}{\displaystyle AC} \right )[/latex].
Лемма доказана.

М. Волкевич, В. Сендеров

М1752. Восемь шахматных ладей

Задача из журнала «Квант» (2000 год, 6 выпуск)

Условие

Сколькими способами можно расставить восемь ладей на черных полях шахматной доски так, чтобы они не били друг друга?

Решение

Если не выдвигать ограничений на цвет полей, то $8$ ладей допустимым образом можно расставить $8!$ различными способами; вообще для доски размером $n\times{n}$ число способов расстановки n ладей равно числу перестановок из n элементов, т.е. $n!$.

Но нам нужно учесть ограничение на цвет полей: ладьи расставляются только на черных полях доски. Перекрасим черные поля доски в красный и синий цвета. При этом всякое черное поле, расположенное на нечетной вертикали (но на четной горизонтали), сделаем красным, а всякое черное поле, расположенное на четной вертикали (но на нечетной горизонтали), сделаем синим (см. рисунок). Из $8$ ладей, стоящих допустимым образом на черных полях, $4$ ладьи окажутся на красных полях, а остальные $4$ ладьи – на синих.

Красные поля образуют как бы отдельную шахматную доску размером $4\times4$, поэтому число способов расстановки $4$ ладей на красных полях равно $4! = 24$. То же можно сказать о синих полях.

В результате число способов для допустимых расстановок $8$ ладей равно $24^2.$

Ответ: $24^2$.

В. Произволов