Разложим по полочкам! Решения задач части 3.

Описание и условия задач

Решения задач части 1

Решения задач части 2

Решения задач части 3

Решения задач части 4

3.1Сколько следует взять различных чисел, чтобы разность квадратов двух из них делилась на $n$?

Из равенства $a^2-b^2=(a-b)(a+b)$ следует, что разность квадратов делится на $n$, когда либо числа дают одинаковые остатки при делении на $n$, либо сумма остатков равна $n$. Это означает, что числа, дающие остатки $r$ и $n-r$ попадают в один «ящик».

Заметим, что «ящик» для нулевого остатка имеет только числа кратные $n$. Остается $n-1$ остатков и $\left\lceil\frac{n-1}{2}\right\rceil$ ящиков. (Если $n$ — четно, то последний ящик также «непарный» так как соответствует только остатку $\frac{n}{2}$). Таким образом всего $\left\lceil\frac{n-1}{2}\right\rceil+1=\left\lceil\frac{n+1}{2}\right\rceil$ «ящиков», поэтому следует взять $\left\lceil\frac{n+1}{2}\right\rceil+1=\left\lceil\frac{n+3}{2}\right\rceil$ (или $\left\lfloor\frac{n+4}{2}\right\rfloor$) чисел.

В действительности, для некоторых $n$ выборок должно быть меньше. Так, при делении $a^2$ на 4 возможно лишь два остатка: 0 (для четного $a$) и 1 (для нечетного $a$), поэтому достаточно выбрать лишь 3 числа, тогда как применяя полученную формулу для $n=4$ получаем 4. Зато для последующих чисел 5 и 6 формула верна. При делении полного квадрата на 5 возможны три остатка: 0 ($5^2$), 1($1^2$), 4($2^2$), так что действительно требуется 4 числа. В случае $n=6$ возможны 4 остатка: 0 ($6^2$), 1 ($1^2$), 3 ($3^2$), 4($2^2$), так что необходимо выбрать 5 чисел, что снова согласуется с формулой.

3.2Десять друзей послали друг другу праздничные открытки. Каждый послал 5 открыток. Докажите, что какие-то двое послали открытки друг другу.

Источник: E.Ю.Иванова. «Олимпиадные задачи» МГУ Мехмат М 2008. Задача 21 (без решения)

Для каждой пары друзей $(a,b)$ соорудим ящик, в который попадают открытки, посланные от $a$ к $b$ или наоборот. Количество открыток равно 50, а количество ящиков $\frac{10 \cdot 9}{2}=45$. Таким образом в каком-то ящике $(p, q)$ окажутся две открытки. Это значит, что $p$  и  $q$ послали открытки друг другу.

3.3Доказать, что равносторонний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками.

Источник: E.Ю.Иванова. «Олимпиадные задачи» МГУ Мехмат М 2008. Задача 7

Вначале докажем вспомогательное утверждение (которое многие сочтут очевидным, но мы люди въедливые): Расстояние между двумя точками, лежащими внутри или на сторонах равностороннего треугольника не больше длины его стороны, причем равенство имеет место тогда и только тогда, когда обе точки совпадают с вершинами. (Более общий факт, который доказывается аналогично: «расстояние между двумя точками внутри или на сторонах треугольника не превышает длину его наибольшей стороны, причем равенство достигается тогда и только тогда, когда обе точки совпадают с концами одной из наибольших сторон».)

Докажем, что $|MN|$ (здесь вертикальные линии используются для обозначения длины отрезка) меньше длины стороны $a$   треугольника $ABC$. Пусть $E$ и $F$ — точки пересечения прямой $MN$ со сторонами $\triangle ABC$ (в частности одна или обе точки могут совпадать с $M$  или  $N$). Так как $|MN| \leqslant |EF|$, достаточно доказать, что $|EF| \leqslant a$.

Пусть ни одна из точек $E$ и $F$ не совпадает с вершинами $\triangle ABC$. Тогда существует сторона $\triangle ABC$, для определенности $AC$, не содержащая ни $E$, ни $F$.

Если $EF \nparallel AC$, из точек $A$ и $C$ проведем прямые, параллельные $EF$ до пересечения со сторонами треугольника. При этом один из отсекаемых отрезков, для определенности $AD$, окажется внутри $\triangle ABC$. В случае $EF \parallel AC$ примем вершину $C$ в качестве точки $D$. Из подобия треугольников $EBF$ и $ABD$ следует $\frac{|EF|}{|AD|}$ = $\frac{|EB|}{|AB|} \lt 1$, то есть $|EF| \lt |AD|$.

Таким образом, всё сводится к случаю, когда одна из выбранных точек совпадает с вершиной, а другая лежит на контуре $\triangle ABC$. Докажем что $|AD| \leqslant a$. Если $D$ совпадает с $B$   или  $C$, то очевидно $|AD|=a$. Покажем, что в остальных случаях $|AD| \lt a$. Пусть $H$ – проекция $A$ на $BC$. Если $D$  и  $H$ совпадают, то $|AD| \lt |AC|$, как катет прямоугольного треугольника $ADC$. В противном случае, один из отрезков $BH$, $CH$ содержит точку $D$. Если для определенности $D \in CH$, то $|DH| \lt |CH|$, откуда $|AD| \lt |AC|$, как отрезок с меньшей длиной проекции.

Обратимся, наконец, к задаче. Если треугольник покрывается двумя равносторонними треугольниками меньшей длины, то, согласно принципу Дирихле, один из малых треугольников должен содержать (внутри или на своем контуре) две вершины исходного треугольника, При этом расстояние между этими вершинами (равное длине стороны исходного треугольника) превышает длину стороны малого треугольника. Как следует из доказанного вспомогательного утверждения, это невозможно.

3.4Доказать, что среди пяти точек внутри равностороннего треугольника с длиной стороны 1 найдутся две точки, расстояние между которыми меньше $\dfrac{1}{2}$.

В равностороннем треугольнике $ABC$ длиной стороны 1 проведем средние линии. При этом $\triangle ABC$ разбивается его на четыре малых равносторонних треугольника, длина стороны каждого из которых равна $\frac{1}{2}$.

Каждой из отмеченных пяти точек поставим в соответствие малый треугольник, которому она принадлежит (один из двух малых треугольников, если точка оказалась на средней линии $\triangle ABC$). Согласно принципу Дирихле найдутся две точки $P$ и $Q$, расположенные внутри или на контуре одного и того же малого треугольника. (Как видно из чертежа, выбор точек не всегда однозначен, но это не существенно.)

Заметим, что ни одна из отмеченных точек не может совпадать с вершиной малого треугольника, так как в этом случае точка оказалась бы в вершине или на контуре треугольника $ABC$, тогда как по условию все отмеченные точки находятся внутри $\triangle ABC$. Вследствие вспомогательного утверждения, доказанного при решении предыдущей задачи расстояние между точками $P$ и $Q$ меньше длины стороны малого треугольника $\frac{1}{2}$.

3.5В квадратной клетке со стороной 1м находится анаконда длиной 10м. Барон Мюнхаузен утверждает, что он в любой момент одним выстрелом может прострелить анаконду сразу в шести местах. Не преувеличивает ли барон? (Анаконду можно считать ломаной линией.)

Источник: «Квант» №7, 1985 год, задача М932. Умышленно или нет, в оригинальном решении («Квант» №11, 1985 год) допущена неточность, которая здесь исправлена.

Переведем формулировку задачи на привычный язык: Внутри квадрата длиной стороны 1 помещена ломаная линия длиной 10. Всегда ли удается провести прямую, пересекающую ломаную линию не менее чем в 6 точках?

Выберем в качестве осей координат две пересекающиеся стороны квадрата. Заметим, что длина каждого отрезка ломаной не больше суммы длин ее проекций на оси координат, по той простой причине, что длина гипотенузы меньше суммы длин катетов. При этом равенство достигается тогда и только тогда, когда отрезок параллелен одной из координатных осей (так что прямоугольный треугольник вырождается в отрезок). Так как длина ломаной равна 10, сумма длин ее проекций не меньше 10. В этом случае найдется координатная ось, сумма длин проекций на которую не меньше 5.

Заметим, что поскольку ломаная находится внутри квадрата, между ломаной и сторонами квадрата находится небольшой зазор, позволяющий уменьшить длину квадрата на достаточно малую величину, чтобы суженный квадрат по-прежнему вмещал всю линию. Если $p$ – наибольшая сумма проекций, а $a$ — длина стороны суженного квадрата, то $p \geqslant 5$,  и  $a \lt 1$, поэтому $\dfrac{p}{a} \gt 5$  откуда $\left\lceil\dfrac{p}{a}\right\rceil \geqslant 6$. Это означает, что на одной из сторон квадрата найдется точка, принадлежащая не менее 6 проекциям. Перпендикуляр к стороне квадрата, восстановленный в этой точке пересечет ломаную не менее чем в 6 точках.

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

Заметим, что прострелить анаконду в 7 точках не всегда удается. На предлагаемом рисунке анаконда находится внутри полосы шириной в $\frac{1}{12}$ метра, причем все ее 12 звеньев расположены параллельно сторонам квадрата. Если все этим звеньям дать максимально возможную длину, то длина каждого звена будет не меньше $1-2\cdot\frac{1}{12}=\frac{5}{6}$, так что общая длина будет не меньше $\frac{5}{6} \cdot 12 = 10$. Остается при необходимости сократить анаконду до 10м, при этом она останется неуязвимой для попадания в 7 точках. Впрочем, от уменьшения количества точек попадания анаконде станет ничуть не легче.

3.6В квадрате со стороной 1 проведено несколько окружностей, сумма длин которых равна 10. Доказать, что можно провести прямую так, что она пересечет не менее четырех окружностей.

Проекция окружности на сторону квадрата представляет собой отрезок, длина которого равна диаметру окружности. Так как диаметр окружности в π раз меньше ее длины, сумма длин диаметров (и следовательно сумма длин проекций) равна $\dfrac{10}{\pi}$. Таким образом на стороне квадрата длиной 1 найдется точка принадлежащая не менее $\left\lceil\dfrac{10}{\pi}\right\rceil = 4$ проекциям. Перпендикуляр, восстановленный к стороне квадрата в этой точке, пересечет не менее чтырех окружностей.

Заметим, что число 4 нельзя заменить бо́льшим числом, поскольку в квадрат можно поместить 4 окружности, диаметр каждой из которых равен $\frac{5}{2\pi}$. В этом случае сумма длин окружностей равна 10, однако пересечь 5 окружностей просто невозможно.

3.7В окружности радиуса 1 проведено несколько хорд. Доказать, если каждый диаметр пересекает не более $k$ хорд, сумма длин хорд меньше $\pi k$.

Предположим, что сумма длин хорд не меньше $\pi k$.

Для каждой хорды рассмотрим множество точек окружности, таких что проходящий через них диаметр пересекает данную хорду. Такими точками являются внутренние точки наименьшей из дуг, стягиваемых данной хордой, а также внутренние точки дуги, симметричной относительно центра окружности. (Если хорда является диаметром, ей соответствует вся окружность, кроме концов хорды.)

Так как длина дуги больше длины стягивающей хорды и каждой хорде соответствуют две дуги, сумма длин дуг более чем в два раза превышает сумму длин хорд. Следовательно сумма длин дуг $s \gt 2 \pi k$, причем эти дуги расположены на окружности длины $2\pi$.

Согласно принципу Дирихле существует точка, принадлежащая не менее $n = \left\lceil \dfrac{s}{2\pi} \right\rceil$ дугам. Так как $\dfrac{s}{2\pi} \gt \dfrac{2 \pi k}{2\pi} = k$, то $n \geqslant k+1$.Таким образом на окружности существует точка, принадлежащая не менее $k+1$ дугам, так что диаметр, проведенный через эту точку пресекает не менее $k+1$ хорд. Это противоречит условию задачи.

3.8Доказать, что в любом семизначном числе, не кратном 7, можно вычеркнуть несколько цифр слева и несколько цифр справа, чтобы получившееся после вычеркивания число было кратно 7.

Пусть $\overline{a_1a_2a_3a_4a_5a_6a_7}$ — заданное число. Рассмотрим 7 чисел: $m_1=\overline{a_1000000}$, $m_2=\overline{a_1a_200000}$, … $m_7=\overline{a_1a_2a_3a_4a_5a_6a_7}$. Каждое из $m_i$ ($i=1\dots 7$) можно записать, как $m_i=\overline{a_{1}\dots a_{i}\underbrace{0...0}_{7-i\;\text{нулей}}} = c_i \cdot 10^{7-i}$, где $c_i$ — число составленное левыми $i$ цифрами.

Согласно задаче 1.5 из семи чисел можно либо выбрать число, кратное 7, либо два числа, разность которых кратна 7. Рассмотрим каждый из этих случаев.

а) Пусть некоторое $m_i$ кратно 7. Тогда, согласно условию задачи, $i \lt 7$. Так как $10^i$ и $7$ — взаимно простые числа, то число $c_i$, получаемое вычеркиванием правых $7-i$ цифр кратно 7.

б) Допустим есть два числа $m_i$  и  $m_j$ ($i \lt j$), такие что число  $m_j-m_i=$ $\overline{a_{i+1}\dots a_{j}\underbrace{0...0}_{7-j\;\text{нулей}}}$  кратно 7. Рассуждая аналогично случаю а), заключаем, что число $\overline{a_{i+1}\dots a_{j}}$ также кратно семи. Оно получается вычеркиванием $i$ левых и $7-j$ правых цифр.

3.9К простому числу каждый раз дописывается справа произвольная цифра, отличная от 9. Докажите, что в некоторый момент число станет составным.

Если дописать четную цифру, или пять, число сразу станет составным, так как разделится на 2 или 5. Поэтому не будем это делать.

Дописать цифру 1 или 7 ($7=2 \cdot 3+1$) — значит увеличить на 1 остаток от деления суммы цифр на 3, дописать 3 — значит не изменить остаток. Вспомним, что остаток от деления суммы цифр на 3 совпадает с остатком от деления самого числа на 3. Если первоначальное число дает остаток 2 при делении на 3, достаточно однажды дописать одну из цифр 1 или 7 (возможно после троек) чтобы число стало кратно 3. Если остаток равен единице, то цифры 1 и/или 7 следует дописать дважды (одинаковую или различные, возможно чередуясь с тройками, например ...373331 или ...7337 или ...11), чтобы число стало кратным трем.

Всё? Нет не всё! Осталось рассмотреть случай, когда (возможно после одной единицы или семерки) дописываются только тройки и никакие другие цифры. В этом случае остаток на 3 сохраняется, так что ожидать, что число разделится на 3 бессмысленно.…

Пусть $p$ число стоящее перед вереницей из одних троек. Это либо первоначальное число, либо число, образованное после дописывания единственной единицы или семерки. В любом случае $p$ обязано быть простым, иначе цель достигнута и в дописывании троек нет смысла. Покажем, результате дописывания мы когда-нибудь получим число, кратное ... $p$.

Для этого заметим, что после дописывания $i$ троек число станет равным $m = p\cdot10^i+a_i$, где $a_i$ — число составленное из $i$ троек. Поэтому достаточно сделать $a_i$ кратным $p$, чтобы $m$ разделилось на $p$. Для кого-то это может показаться сложным, но ведь у нас есть опыт решения предыдущих задач!

Итак, рассмотрим $p+1$ чисел, составленных из одних троек: $\{a_i\}_{i=1}^{p+1}$. Среди них конечно же найдутся два числа $a_j$ и $a_k$ ($j<k$), разность которых делится на $p$. Заметим, что $$ a_k - a_j = \underbrace{3...3}_{k-j\;\text{троек}}\underbrace{0...0}_{j\;\text{нулей}}=a_{k-j}\cdot 10^j, $$ поэтому число $a_{k-j}$ ... нет, не получается! Необходимо, чтобы $p$ и $10^j$ были взаимно простыми, а это не дано...

Есть выход! Так как $p$ – простое число, числа $p$ и $10^j$ могут иметь общий делитель, отличный от единицы, лишь тогда, когда $p$ равно 2 или 5. Отложим эти случаи в сторону и продолжим прерванное рассуждение. Итак, $a_{k-j}\cdot 10^j$ делится на $p$, причем $p$ и $10^j$ предполагаются взаимно простыми, поэтому число $a_{k-j}$ обязано делиться на $p$. Таким образом, дописав $k-j$ троек, получим составное число.

Если $p=2$ или $p=5$, будем считать, что тройки дописываются к числам 23 и 53 соответственно. Или можно не мудрить, а просто заметить, что чи́сла   $233333 = 353 \cdot 661$  и  $533 = 13 \cdot 41$   являются составными. Для нахождения таких чисел использовался Divisors calculator.

Описание и условия задач

Решения задач части 1

Решения задач части 2

Решения задач части 3

Решения задач части 4