Рубрика: Задачи «Квант»

Математические задачи из детского физико-математического журнала «Квант»

M610. Об «интересных» наборах чисел

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

Условие

Фиксируем $k \in \mathbb N$.
$а)$ Рассмотрим множество всех наборов целых чисел $a_1, \ldots , a_k$ таких, что $0 \le a_1 \le a_2 \le \ldots \le a_k \le k$; обозначим число таких наборов через $N.$ Рассмотрим среди них те, для которых $a_k = k$; пусть их число равно $M$. Докажите, что $N=2M$.
$б)$ Наложим на рассматриваемые наборы дополнительное ограничение: сумма $a_1 + \ldots + a_k$ делится на $k$. Пусть соответствующие числа равны $N’$ и $M’$. Докажите, что $N’ = 2M’$ (Из рисунка 1 видно, что при $k=3$ эти числа равны $M=10$, $N=20$; $M’=4$, $N’=8$.)

Рис. 1.

Решение

Как известно, если два множества имеют одинаковое число элементов, между ними можно установить взаимно однозначное соответствие. Собственно говоря, это и есть определение того, что в множествах элементов поровну, но этот факт иногда забывается. А между тем довольно часто равенство двух чисел устанавливается именно через взаимно однозначное соответствие подходящих множеств.

Нам нужно доказать, что наборов, в которых $a_k = k$ ровно половина. Поэтому попробуем установить взаимно однозначное соответствие между этими наборами и оставшимися, теми, у которых $a_k < k$.

Сопоставить набору $(a_1, a_2, \ldots, a_k)$ набор $(a_k, a_{k-1}, \ldots, a_1)$ нельзя, так как новый набор — невозрастающий. Можно попробовать сопоставить набору $(a_1, \ldots, a_k)$ набор $k-a_k, k-a_{k-1}, \ldots, k-a_1)$: он уже — неубывающий, но… $k-a_1$ не обязательно быть меньше $k$. Поэтому это соответствие не решает задачу.

Значит, необходимо более сложное соответствие. Для его построения нам понадобится понятие диаграммы Юнга данного набора.

Рис. 2

Что это такое, проще всего объяснить на примере: набору $(0, 0, 2, 3, 5)$ соответствует диаграмма, изображенная на рисунке 2 — в каждой строке столько соответствующее число.

Дополним диаграмму Юнга до квадрата (рис. 3). Тогда становится ясно, что наша первоначальная идея заключалась в том, что отсчитывать диаграмму не из красных, а из белых квадратиков (и, соответственно, не слева-снизу, а справа-сверху).

Рис. 3

Попытаемся теперь дополнить рисунок 3 вертикальной диаграммой — как на рисунке 4. Отсчитывая эту диаграмму снизу-слева, получим набор $(2, 2, 3, 4, 4)$. Назовем этот набор дополнительным к набору $(0, 0 , 2, 3, 5)$. Еще один пример изображен на рисунке 5.

Ясно, что если исходный набор $(a_1, \ldots, a_k),$ а дополнительный — $(b_1, \ldots, b_k)$, то $(a_k = k)$ тогда и только тогда, когда $b_k < k$. В самом деле, $a_k = k$, если верхняя правая клетка входит в основную диаграмму Юнга, и $a_k < k,$ если она входит в дополнительную.

Рис. 4

Установленное нами соответствие между наборами, у которых $a_k = k$, и наборами, у которых $a_k < k$, очевидно, взаимно однозначно. Тем самым мы решили $a)$. Кроме того, сумма чисел исходного и дополнительного наборов равна $k^2$ (в наших примерах — 25). Поэтому сумма чисел дополнительного набора делится на $k$ тогда и только тогда, когда делится на $k$ сумма чисел исходного набора. Это решает $б)$.

Рис. 5

Замечание. Задача $a)$ имеет и другое решение: можно непосредственно посчитать числа $N$ и $M$.

Лемма. Число наборов целых чисел $a_1, \ldots, a_m$ таких, что $0 \le a_1 \le \ldots \le a_m \le k$ равно $C^m_{k+m}$.

Доказательство. Рассмотрим набор $(b_1, \ldots, b_m)$ где $b_i = a_i + i : b_1 = a_1 +1, b_2 = a_2 +2 $ и т. д. Тогда, очевидно, $1 < b_1 < b_2 < \ldots < b_m \le k+m$, то есть $(b_1, \ldots, b_m)$ — произвольный возрастающий набор $m$ целых чисел их первых $k+m$ чисел. Число таких наборов равно $C^m_{k-m}$.

Поэтому число наборов, в которых $a_k \le k$, по лемме равно $C^k_{2k}$. Если же $a_k = k$, то нам остается выбрать числа $a_1, \ldots, a_{k-1}$ так, что $0 \le a_1 \le \ldots \le a_{k-1} \le k$; их число равно $C^{k-1}_{2k-1}$. Остается посчитать, что $2C^{k-1}_{2k-1}$ равно $C^k_{2k}$.

А. Толпыго

M699. О полукруге, разрезанном на два криволинейных треугольника, в которые вписаны окружности

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

Условие

Полукруг с диаметром $AB$ разрезан отрезком $CD$, перпендикулярным $AB,$ на два криволинейных треугольника $ACD$ и $BCD$, в которые вписаны окружности, касающиеся $AB$ в точках $E$ и $F$. Докажите, что а) $|AD| = |AF|$, б) $|DF|$ — биссектриса угла $BDC$, в) величина угла $EDF$ не зависит от выбора точки $C$ на $AB$.

Решение

а) Пусть $O$ — центр данного полукруга. Будем считать, что $|AO| = 1$. Пусть, для определенности, точка $C$ лежит между $B$ и $O$ и $|OC| = a$ (см. рисунок).

Применяя теорему Пифагора к треугольникам $ADC$ и $ODC$, получаем $|AD|^2 — |AC|^2 = |OD|^2 — |OC|^2$, то есть $|AD|^2 =$ $= |AC|^2 + |OD|^2 — |OC|^2$, или $|AD|^2 = (1 + a)^2 + 1 — a^2 =$ $= 2 + 2a$.

Пусть $O_1$ — центр окружности, вписанной в криволинейный треугольник $BDC$, $r$ — её радиус. Из прямоугольного треугольника $OO_1F$ находим $(1 — r)^2 = r^2 + (a + r)^2$, или $(a + r)^2 + 2r = 1$. Поскольку $|AF|^2 = (1 + a + r)^2 = 1 + 2a + 2r + (a + r)^2 = 2 + 2a$, получаем $|AF| = |AD|$. (Аналогично доказывается $|BD| = |BE|$.)

б) Треугольник $ADF$ — равнобедренный, так что $\widehat{AFD} = \widehat{ADF}$. Далее, $\widehat{AFD} = \widehat{BDF} + \widehat{DBF}$, $\widehat{ADF} = \widehat{ADC} + \widehat{CDF}$ и $\widehat{ADC} = $ $= \widehat{DBF}$; поэтому $\widehat{CDF} = \widehat{BDF}.$

в) из решения пункта б) следует, что $\widehat{EDF} = \widehat{EDC} + \widehat{CDF} = $ $ = \displaystyle{1\over 2}\widehat{ADB} = \displaystyle{\pi\over 4}$.

В.Сендеров

М623. Задача об осях симметрии куба, правильной треугольной пирамиды и нечетности осей симметрии многогранника.

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

Условие

а) Сколько осей симметрии имеет куб? Правильная треугольная пирамида?

б)* Докажите, что если некоторый многогранник имеет $k$ осей симметрии $(k \geq 1)$, то $k$ нечетно.

Решение

а) Нетрудно указать девять осей симметрии куба. Это — прямые, соединяющие центр куба $O$ с центрами граней (их три: $Ox$, $Oy$, $Oz$ на рисунке $1$) и с серединами ребер (их шесть).

Других осей симметрии у куба нет: это можно доказать, опираясь на такое наблюдение: при любом самосовмещении куба каждая из трех осей $Ox$, $Oy$, $Oz$ должна отображаться на одну из этих же осей, причем если это само совмещение — симметрия (поворот на $180 ^\circ$) $S_l$ относительно некоторой прямой $l$, отличной от $Ox$, $Oy$ и $ Oz$, то одна из этих трех осей должна переходить сама в себя, а две остальные — друг в друга.

У правильного тетраэдра три оси симметрии — прямые, соединяющие середины его ребер. Чтобы убедиться в этом, удобно достроить тетраэдр до куба, проведя через каждое ребро тетраэдра плоскость, параллельную противоположному ребру (рис. $2$). Ясно, что любое самосовмещение тетраэдра будет также самосовмещением этого описанного куба. Из девяти осевых симметрий, отображающих куб на себя, лишь три будут переводить в себя тетраэдр.

б) Пусть дан многогранник $M$, у которого более одной оси симметрии.

Лемма $1$ Если $l$ и $m$ — оси симметрии многогранника $M$, то $S_l (m) = m’$ — также ось симметрии $М$.

В самом деле, если точки $P$ и $P’$ многогранника $M$ симметричны относительно $m$, то $S_l (P)$ и  $S_l (P’)$ будут симметричными относительно $m’$. Короче: $S_{m’}  = S_l O S_m O S_l$.

Лемма $2$ Если $l$ и $m$ — оси симметрии многогранника $M$, пересекающиеся в точке $O$ и перпендикулярные друг к другу, то прямая $n$, перпендикулярная им обоим и проходящая через точку $O$, также служит осью симметрии $M$.

Действительно, $S_n = S_m O S_l$. Это легко проверить, приняв данные прямые за оси координат, или построив прямоугольный параллелепипед с центром в точке $O$ и осями симметрии $l$, $m$, $n$ с произвольной вершиной $P$ (рис. $3$).

Леммы $1$ и $2$ позволяют, фиксировав какую-то одну ось симметрии $l$, разбить все остальные на пары: если $m$ удовлетворяет условия леммы $2$, то пару с ней образует $n$, а если нет, то $m’ = S_l(m) \ne m$. Отсюда сразу следует утверждение задачи б).

Возникает естественный вопрос: какое вообще (конечное) множество прямых может быть множеством всех осей симметрии некоторого многогранника?

Различные примеры даются множеством осей симметрии $n$-угольной правильной призмы (здесь количество осей $p=n$ при $n$ нечетном и $p=n+1$ при $n$ четном), тетраэдра (или прямоугольного параллелепипеда с разными ребрами, $p=3$), куба (или октаэдра $p=9$) и додекаэдра (или икосаэдра, $p=15$). Попробуйте доказать, что других множеств осей симметрии (состоящих более чем из одной прямой) не бывает. Конечно, тут не обойтись без такой очень полезной леммы, которую многие читатели применили и в решении задачи б).

Лемма $3$ Оси симметрии любого многогранника пересекаются в одной точке.

Предположим, что $l$, $m$ — непересекающиеся оси симметрии многогранника $M$. Пусть $n$ — общий перпендикуляр $l$, $m$; рассмотрим прямоугольную систему координат с началом в точке $O = l \cap n$, с осью $Oz$ направленной по лучу $OA$, где $A = n \cap m$; пусть $|OA| = a$. Тогда при симметрии относительно оси $l$ координата $z$ любой точки переходит в $(-z)$, а при симметрии относительно $m$ — в $(2a-z)$. Поэтому при композиции этих двух симметрий $z$ изменяется на $2a$. Повторяя эту композицию достаточное число раз, мы «выгоним» любую точку за пределы многогранника $M$.  Противоречие!

Вот еще более короткое доказательство леммы $3$ (правда, использующее понятие, заимствованное из механики): пусть $O$ — центр масс одинаковых грузиков, помещенных в вершинах многогранника $M$; ясно, что при любом самосовмещении многогранника $M$ грузики лишь меняются местами, поэтому точка $O$ переходит в себя; в частности, все оси симметрии многогранника $M$ проходят через точку $O$.

Н. Васильев, В. Сендеров, А. Сосинский

М1. Выборы

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

Задача

В стране Анчурии, где правит президент Мирафлорес, приблизилось время новых президентских выборов. В стране ровно 20 миллионов избирателей, из которых только один процент (регулярная армия Анчурии) поддерживает Мирафлореса. Мирафлорес, естественно, хочет быть избранным, но с другой стороны, он хочет, чтобы выборы казались демократическими. «Демократическим голосованием» Мирафлорес называет вот что: все избиратели разбиваются на несколько разных групп, затем каждая из этих групп вновь разбивается на некоторое количество равных групп, затем эти последние группы вновь разбиваются на равные группы и т.д.; в самых мелких группах выбирают представителя группы — выборщика, затем выборщики выбирают представителей для голосования в еще большей группе и т.д.; наконец, представители самых больших групп выбирают президента. Мирафлорес делит избирателей на группы, как он хочет, и инструктирует своих сторонников как им голосовать. Сможет ли он так организовать «демократические выборы», чтобы его избрали президентом?(При равенстве голосов побеждает оппозиция.)

Ответ: Да, сможет.

Прежде всего разберемся, как может на «многоступенчатых» выборах победить кандидат, за которого голосует меньшинство. (Кстати, по такой системе голосуют во многих капиталистических странах.) Самый простой пример такой ситуации изображен на рисунке 1: здесь девять избирателей — четыре «черных» и пять «голубых» — разбиты на три группы потри избирателя так, что в двух группах побеждают черные, и поэтому в результате таких «двухступенчатых выборов» будет избран кандидат черных, хотя число его сторонников составляет только $\frac{4}{5}$ от общего числа избирателей. (Нетрудно сообразить,что при двухступенчатых выборах с большим числом избирателей процент голосов, достаточный для победы, может быть еще меньше, но все-таки заведомо больше $25\%.$) Ясно, что при трехступенчатой системе выборов этот процент можно сделать еще ниже. Например, если заменить на рисунке $1$ каждого избирателя группой из ста человек, причем так, что в голубой группе все сто избирателей голубые, а в черной — $51$ черный и $49$ голубых, то мы получим пример ситуации, где черные составляют только $49\%$ от общего числа избирателей и тем не менее побеждают.

После этих предварительных соображений приведем решение задачи.

Разобьем всех избирателей на 5 групп по 4 миллиона в каждой так, что две группы целиком состоят из противников Мирафлореса (назовем эти группы «голубыми», а три остальные — «черными»). Каждую из этих групп «первого ранга» снова разобьем на 5 групп второго ранга, причем из пяти групп, составляющих черную группу первого ранга, три— черных и т.д., как указано в таблице.

Ясно, что при таком разбиении для победы Мирафлореса достаточно, чтобы за него проголосовала $\frac{3^{11}}{2^8\cdot5^7} = \frac{177147}{20000000} < \frac{1}{100}$ часть всех избирателей. Тем самым, поскольку армия составляет $\frac{1}{100}$ часть избирателей и поддерживает Мирафлореса, он сможет победить.

Ранг группы $r$ 1 2 3 4 5 6 7 8 9
Общее число групп ранга $r$ $5$ $5^{2}$ $5^{3}$ $5^{4}$ $5^{5}$ $5^{6}$ $5^{7}$ $2^{4}\cdot5^{7}$ $2^{8}\cdot5^{7}$
Сколько из них черных $3$ $3^{2}$ $3^{3}$ $3^{4}$ $3^{5}$ $3^{6}$ $3^{7}$ $3^{9}$ $3^{11}$
Сколько человек в 1 группе ранга $\:r$ $4\cdot 10^{6}$ $8\cdot 10^{5}$ $16\cdot 10^{4}$ $32\cdot 10^{3}$ $64\cdot 10^{2}$ $1280$ $256$ $16$ $1$
На сколько групп ранга $r+1$ разбивается группа ранга $r$ 5 5 5 5 5 5 16 16 —
Сколько черных подгрупп ранга $r+1$ у черной группы ранга $r$ 3 3 3 3 3 3 9 9 —

Некоторые читатели пытались решить следующий, более общий вопрос: какое наименьшее число сторонников должен иметь Мирафлорес, чтобы победить на «демократических выборах», если общее количество избирателей $N$. Разумеется, ответ на этот вопрос зависит не столько от величины числа $N$ , сколько от того, как оно раскладывается на множители. Если, скажем, $N$ — число простое, то избирателей вообще никак нельзя разбить на равные группы (кроме тривиального способа: $N$ групп по одному человеку) и для победы нужно иметь простое большинство. Покажем, как ответить на этот вопрос для любого $N$ .

Рассмотрим такое разбиение $N$ человек на группы (1-го, 2-го и т. д. ранга), при котором побеждает Мирафлорес и число его сторонников — наименьшее из возможных. Очевидно, можно считать, что в группах, голосующих против него, нет ни одного его сторонника и что все черные группы одного ранга разбиты совершенно одинаково. Удобно использовать обозначение $\left[\:\right]$ — «целая часть» $\left[x\right]$ — наибольшее целое число, не превосходящее $x$; например, $\left[2\right] = 2,\left[3\frac{1}{2}\right] = 3.$ Ясно, что если некоторая черная группа состоит из $k$ групп следующего ранга, то среди них должно быть не менее $\left[\frac{k}{2}+1\right]$ черных. Пусть каждая группа $r$-го ранга $\left(r = 1,2,\ldots ,m—1\right)$ разбита на $k_{r}$, групп меньшего, ранга, а группы последнего $m$-го ранга состоят из 1 человека. Тогда для победы черных необходимо иметь по крайней мере. $B = \left(\left[\frac{k_{1}}{2}\right]+1\right)\left(\left[\frac{k_{2}}{2}\right]+1\right)\ldots \left(\left[\frac{k_{m}}{2}\right]+1\right)$ черных голосов. Наша задача свелась к такой: разложить данное $N$ в произведение таких сомножителей $k_{1},k_{2},\ldots ,k_{m},$ чтобы произведение $B$ было минимально. Пусть $N = k_{1}k_{2}\ldots k_{m}$ — такое разложение. Как показывает следующая лемма, можно предполагать, что в этом разложении нет сомножителей $k$ вида $k = pq$, где $p$ и $q$ больше 2 (если такие есть, можно провести дальнейшее разложение, не увеличивая $В$).

Лемма.
$\left(\left[\frac{p}{2}\right]+1\right)\left(\left[\frac{q}{2}\right]+1\right)\leqslant\frac{pq}{2}+1$ для всех целых $p$ и $q$ больших 2.

Доказательство. Если $p$ и $q$ оба четны, то неравенство можно переписать так $\left(\frac{p}{2}+1\right)\left(\frac{pq}{2}+1\right)\leqslant\frac{pq}{2}+1,$ $\left(p+2\right)(\left(q+2\right)\leqslant 2pq+4,$ $pq-2q-2p+4\geqslant4,$ $(p-2)(q-2)\geqslant4$ что, очевидно, верно для $p>2$ и $q>2$. В случае, когда одно из чисел $p,q,$ например $р$, четно, а другое нечетно, имеем:$\left(\frac{p}{2}+1\right)\left(\frac{q}{2}+\frac{1}{2}\right)\leqslant\frac{pq}{2}+1,$ $\left(p+2\right)\left(q+1\right)\leqslant2pq+4,$ $pq-2q-p+2\geqslant0,\left(p-2\right)\left(q-1\right)\geqslant 0$

Случай, когда $p$ и $q$ нечетны, разбирается аналогично. Лемма доказана. (отсюда сразу следует, что нечетные $N$ надо раскладывать на простые множители «до конца».) Осталось разобраться с двойками.

Можно считать, что в разложении нет сомножителей вида $2q$, где $q$ нечетно, поскольку $2\left(\left[\frac{q}{2}\right]+1\right) = \left[\frac{2q}{2}\right]+1$

Отсюда из леммы вытекает, что из четных сомножителей можно ограничиться только двойками, четверками и восьмерками. Далее ясно, что $2\cdot2$ хуже, чем $4$, поскольку $\left(\left[\frac{2}{2}\right]+1\right)^{2}=4>\left[\frac{4}{2}\right]+1=3$ Выгодно $2\cdot4$ заменить на 8, поскольку $2\cdot3 = 5>5; 4\cdot4$ лучше, чем $2\cdot8$, поскольку $3\cdot3 = 9; 2\cdot5 = 10$ и, наконец, $4\cdot4\cdot4$ менее выгодно, чем $8\cdot8$, поскольку $3\cdot3\cdot3 =27;$ $5\cdot5 = 25,$ так что больше двух четверок оставлять нельзя Итак, окончательный ответ такой: пусть $N = 2^{d}p_{1},\ldots ,p_{m}$, где $m\geqslant0,d\geqslant0$ — целые, $p_{1},\ldots,p_{m}$ — нечетные простые числа. Обозначим произведение $\frac{p_{1}+1}{2}\ldots \frac{p_{m}+1}{2}$ через $P$.

Тогда наименьшее число сторонников Мирафлореса, достаточное для победы, равно

  • $B = 2P,$ если $d = 1$(т.е. $N = 2p_{1}\ldots p_{m}$);
  • $B = 5^{n}P,$ $d = 3n\left(N=8^{n}p_{1}\ldots p_{m}\right);$
  • $B = 3\cdot5^{n}P$ $d = 3n+2\left(N=4\cdot8^{n}p_{1}\ldots p{m}\right);$
  • $B = 9\cdot5^{n}P$ $d = 3n+4\left(N=4^{2}\cdot8^{n}p_{1}\ldots p_{m}\right);$
здесь $n$-целое число,$n\geqslant0.$

Этот ответ нашли ученик 9-го класса из Томска А.Гришков и (в другой форме) еще несколько читателей в частности, для $N = 20000000 = 2^{8}\cdot5^{7}=4\cdot8^{2}\cdot5^{7}$ получаем $B=3\cdot5^{2}\cdot3^{7} = 164025$

М1653. Часы

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

Условие

На столе лежат $ 5 $ часов со стрелками. Разрешается любые из них перевести вперед. Для каждых часов время, на которое при этом их перевели, назовем временем перевода. Требуется все часы установить так, чтобы они показывали одинаковое время. За какое наименьшее суммарное время перевода это можно гарантированно сделать?

Решение

Ответ: за $ 24 $ часа.

Отметим на циферблате положения часов стрелок всех пяти часов (см. рисунок). Циферблат разобьется на пять секторов. Занумеруем их по кругу. Пусть часовая стрелка проходит секторы за $ x_1, x_2, x_3, x_4, x_5 $ часов соответственно. (Некоторые из этих чисел, нулевые; сумма $ x_1 + x_2 + x_3 + x_4 + x_5 $ равна $ 12 $ часам.)

Чтобы перевести все часы на начало первого сектора, необходимо затратить \begin{align*} & S_1 = (x_2 + x_3 + x_4 + x_5) + (x_3 + x_4 + x_5) + \\ & + (x_4 + x_5) + x_5 = x_2 + 2x_3 + 3x_4 + 4x_5 \end{align*} часов. Аналогично можно посчитать величины $ S_2, S_3, S_4 $ и $ S_5 $, где $ S_i $ — время, необходимое для установки всех часов на начало $ i $-го сектора. Следовательно, \begin{align*} & S_1 + S_2 + S_3 + S_4 + S_5 = (1 + 2 + 3 + 4) \times \\ & \times (x_1 + x_2 + x_3 + x_4 + x_5) = 10 \cdot 12 = 120 \end{align*} часов; наименьшая из величин $ S_i $ не превосходит $ 120 : 5 = 24 $ часа.

С другой стороны, если $ x_1 = x_2 = x_3 = x_4 = x_5 $ (например, если часы показывают $12$ ч, $2$ ч $24$ мин, $4$ ч $48$ мин, $7$ ч $12$ мин и $9$ ч $36$ мин), то все $ S_i $ равны $24$ часам. Менее чем $24$ часами в такой ситуацией не обойтись.

О.Подлипский