«Друг моего друга мне не друг» или две теоремы теории графов. Решения задач.

Это страница содержит решения задач, предложенных здесь

1. В шахматном турнире принимает участие 15 шахматистов. Возможна в течении турнира ситуация, когда каждый шахматист сыграл ровно 7 партий?

Сопоставим каждому шахматисту вершину графа, а каждой сыгранной партии — ребро графа, соединяющего вершины, соответствующие игравшим в ней шахматистам. Тогда количество сыгранных шахматистом партий равно степени соответствующей вершины. Если каждый шахматист сыграл 7 партий, сумма степеней вершин равна $15 \cdot 7 =105$, что невозможно, так как, согласно лемме о рукопожатиях, сумма степеней вершин четна.

2. На плоскости даны 60 точек. Какое наибольшее количество отрезков можно провести, чтобы в любом множестве из $n$ точек нашлись две точки, не соединенные между собой отрезком. Рассмотрите случаи $n=3,4,5,9,10,11$.

Данное множество точек и отрезков можно рассматривать, как граф из 60 вершин. Максимальное количество ребер дает граф Турана T(15,k), где $k=n-1$. Введем обозначение ($1800=\frac{60^2}{2}$): $$ t(k)= 1800 \left(1−\dfrac{1}{k}\right) $$

Тогда, если $k$ — делитель 60, то $r_{max}(60,k) = t(k)$ Значения $n=3,4,5,11$ (отвечающие $k=2,3,4,10$) удовлетворяют этому требованию, так что имеем: $\begin{matrix}\\ n=3: & r_{max}(60,2) = & t(2)=& 900 & | & n=4: & r_{max}(60,3) = & t(3)=& 1200 \\ n=5: & r_{max}(60,4) =& t(4)=& 1350 & | & n=11: & r_{max}(60,10) =& t(10)=& 1620 \end{matrix}$

Осталось рассмотреть случаи $n=9$ и $n=10$:

$n=9:$ Так как $t(8)=1575$ — целое число, то согласно (11) части 2, $r_{max}(60,8)=t(8)-1=1574$

$n=10:$ Так как $k=9$ превышает 8, приходится пользоваться непосредственно (10) части 2. Имеем $t(9)=1600$ и $b=6$ (остаток от деления 60 на 9), так что, согласно (10), $r_{max}(60,9)=1600-\dfrac{6\cdot3}{18}=1599$.

3. На плоскости даны 15 точек, так что никакие три из них не лежат на одной прямой. Какое наименьшее количество отрезков следует провести, чтобы в любом множестве из $n$ точек нашлись две точки, соединенные между собой отрезком. Рассмотрите случаи $n=3,4,5$.

Данное множество точек и отрезков можно рассматривать, как граф из 60 вершин. Условие означает, что в графе не существует независимых подмножеств, содержащих $n$ вершин. Рассмотрим тогда дополнительный граф, то есть граф, соединяющий ребрами те и только те вершины, которые не были соединены в исходном графе. Каждому независимому множеству из $n$ вершин в исходном графе соответствовал бы полный подграф порядка $n$ в дополнительном подграфе. Отсутствие таких множеств означает отсутствие в дополнительном графе полных подграфов порядка $n$. Отсюда в дополнительном подграфе не более $r_{max}(60,k)$ вершин ($k=n-1$). Так как полный 60-вершинный граф имеет $\frac{60 \cdot 59}{2}= 1770$ ребер, исходный граф имеет не менее $1770-r_{max}(60,k)$

Используя результаты предыдущей задачи, обозначив для краткости искомые значения через $c_{min}(60,k)$, получаем: $\begin{matrix}\\ n=3: & c_{min}(60,2) = & 870 & | & n=4: & c_{min}(60,3) = & 570 \\ n=5: & c_{min}(60,4) = & 420 & | & n=9: & c_{min}(60,8) = & 196 \\ n=10: & c_{min}(60,9) = & 171 & | & n=11: & c_{min}(60,10) = & 150 \\ \end{matrix}$

Догадались, где используется условие «никакие три из них не лежат на одной прямой»? Ведь, с формальной точки зрения это геометрическая задача, в которой графы не упоминаются. Если три точки $А, B, C$ лежат на одной прямой, то отрезок, соединяющий крайние точки $A$ и $С$ пройдет через $B$ что, конечно, не существенно в теории графов, зато имеет значение с геометрической точки зрения. Поэтому, такой случай следует исключить. В следующей задаче автор пошел дальше, позаботившись о том, чтобы все линии были скрещивающимися, полностью исключая возможность самопересечений. Появление фразы «никакие 4 не лежат в одной плоскости» в скобках возможно связано с тем, что она была добавлена в последний момент. В рассуждении это условие нигде явно не используется.

4. В пространстве расположено $2n$ ($n\geslant 2$) точек (так что никакие 4 не лежат в одной плоскости) и проведено $n^2+1$ отрезков с концами в этих точках. Докажите, что проведенные отрезки образуют: а) хотя бы один треугольник; б)* не менее $n$ треугольников.

Задачник Кванта. Задача М934. «Квант» 1985 № 7 стр. 42

Пункт а) сразу следует из теоремы Мантеля. Действительно, если граф не содержит треугольников, то количество вершин не превышает $\dfrac{(2n)^2}{4}=n^2$, а так как вершин на 1 больше, то хотя бы один треугольник должен быть.

Пункт b) далеко не столь очевиден. Хотя, если подумать, здесь тоже все логично. Вспомним, что максимум ребер $2n$-вершинного графа дает полный двудольный граф по $n$ вершин в каждой доле, поэтому добавить одну вершину, можно только в какую-то из долей. Поскольку каждая из вершин, которые добавленное ребро соединяет, инцидентна $n$ вершинам другой доли, получаем как раз $n$ новых треугольников.

Однако, вы заметили в вышеприведенном рассуждении изъян? Откуда известно, что какой-нибудь граф, не являющийся максимальным, не даст больше треугольников при добавлении ребра? Как видите, все это не так просто, как кажется на первый взгляд. Приходится пасовать и привести авторское доказательство (С.Б. Гашков. «Квант» 1985 № 11, стр 37-38), которое лишь чуть-чуть детализировано для прояснения моментов, которые могут быть непонятны неискушенному читателю.

Докажем индукцией по $n$ ($n \geslant 2$).

База индукции. При n=2 имеем имеем граф из 4 вершин. Полный граф имеет 6 ребер (4 стороны и две диагонали) и 4 треугольника (по два, прилежащих каждой диагонали). Интересующий нас граф имеет $n^2+1=5$ ребер, то есть одним ребром меньше. Легко видеть, что удаление любого ребра (стороны или диагонали) сохраняет 2 (то есть $n$) треугольника.

Индукционный переход. Допустим, что утверждение верно для $2n$ вершин. Рассмотрим граф из $2(n+1)$ вершин и $(n+1)^2+1$ ребер. Согласно пункту а) (то есть теореме Мантеля) в нем обязательно есть треугольник, назовем его $ABC$. Поскольку треугольников должно быть $(n+1)$, требуется доказать существование еще $n$ из них.

Обозначим количество ребер, выходящих из вершин $A$, $B$ и $C$ не считая ребер треугольника ABC через $k_A$, $k_B$ и $k_C$ соответственно (каждое из этих величин на единицу меньше степени соответствующей вершины). Введем обозначение $k = k_A + k_B + k_C$ и рассмотрим следующие два случая.

Случай 1. $k \leslant 3n-2$. Если каждое из $k_A + k_B$, $k_A + k_С$, $k_A + k_B$ не меньше $2n-1$, то суммируя все три неравенства, получим: $2(k_A+k_B+k_C) \geslant 6n-3$, или $к \geslant 3n-1$, что противоречит предположению $k \leslant 3n-2$. Таким образом, одна из сумм, для определенности $k_A + k_B$ не превосходит $2n-2$. Исключив точки $A$ и $B$, а также все инцидентные им ребра, включая ребра треугольника $ABC$, получим граф из $(n+1)^2+1-(k_A + k_B)-3$ ребер, что не менее $(n+1)^2+1-(2n-2)-3 = n^2+1$ ребер. Согласно индукционному предположению он образует не менее $n$ треугольников, что и требовалось доказать.

Случай 2. $k \geslant 3n-1$. Среди $2n+2-3=2n-1$ вершин, отличных от $A$, $B$ и $C$ рассмотрим по-отдельности вершины, соединенные с одной двумя или всеми тремя вершинами треугольника $ABC$. Обозначим количество таких вершин через $n_1$, $n_2$ и $n_3$ соответственно. Тогда $$ n_1 + n_2 + n_3 \leslant 2n-1 $$ (неравенство вызвано тем, что некоторые вершины могут не быть соединены ни с одной из $A$, $B$, $C$). Подсчитав количество ребер, инцидентных $A$, $B$ и $C$ (кроме ребер треугольника $ABC$) получим: $$ n_1+2n_2+3n_3=k \geslant 3n-1$$

Надеюсь, вы не забыли, что целью всего этого является доказательство существования дополнительных $n$ треугольников. Подсчитаем количество дополнительных треугольников $t$, образованных ребрами треугольника $ABC$. Каждая внешняя вершина соединенная с тремя ребрами из $ABC$ образует три таких треугольника, вершина, соединенная с двумя ребрами из $ABC$ образует 1 треугольник, прочие внешние вершины не образуют треугольников со ребрами треугольника $ABC$. Таким образом, $$ t=n_2+3n_3 \geslant n_2+2n_3 = (n_1+2n_2+3n_3)-(n_1+n_2+n_3) $$

Применяя полученные ранее неравенства, получаем: $t \geslant (3n-1)-(2n-1) = n$, чем ставится окончательная точка в доказательстве.

Одно из красивейших доказательств, которые я когда-либо встречал!

«Друг моего друга мне не друг» или две теоремы теории графов. Часть 2

Окончание. Начало здесь

Граф может содержать треугольники, но не содержать полных подграфов бо́льшего размера. Такой случай был рассмотрен венгерским математиком Палом Ту́раном [Pál Turán].

Как утверждают знатоки венгерского языка, диакритический знак над á означает не ударение, а длительное произношение гласной. Правильно произносить фамилию следует с ударением на первом слоге.

Согласно традиции (а также для того, чтобы нижеприведенные формулы не отличались от тех, которые можно найти в других публикациях), для количества вершин (отсутствующих) полных подграфов мы будем употреблять не $k$, а $k+1$. Как выяснится чуть позже, в этом есть определенное удобство.

Следующее утверждение часто называют теоремой Турана, хотя на самом деле оно является следствием из теоремы Турана, которую обсудим ниже:

В $n$-вершинном графе не содержащем полных $(k+1)$-вершинных подграфов количество ребер не превосходит $\left(1-\dfrac{1}{k}\right)\dfrac{n^2}{2}$.

Обозначив через $r(n,k)$ количество ребер $n$ - вершинного графа без полных $k+1$-вершинных подграфов, данное утверждение можно записать в виде: $$ r(n,k) \leslant \left(1-\dfrac{1}{k}\right)\dfrac{n^2}{2} \qquad(7) \label{eq:Turan} $$

Заметим, что неравенство (5) (теорема Мантеля), доказанное в первой части, является частным случаем неравенства (7) при $k=2$.

Докажем индукцией по $k$.

При $k=1$ неравенство (7) принимает вид $r \leslant 0$. Проверим, верно ли оно. Полный граф размера 2 — это две вершины, соединенные ребром. Следовательно отсутствие полного подграфа размера 2 означает отсутствие ребер. Поэтому $r=0$ и неравенство имеет место.

Пусть неравенство (7) справедливо для некоторого $k$. Докажем его справедливость для $k+1$. Рассмотрим граф размера $n$, не содержащий полных подграфов размера $k+2$. Пусть $A$ — вершина максимальной степени $m$, а $M$ множество вершин смежных с $А$. Множество $M$ содержит $m$ элементов. Рассмотрим порожденный подграф, образованный вершинами из $M$. В таком подграфе не должно быть полных подграфов порядка $k+1$, так как если такой граф найдется, то присоединив к нему вершину A с инцидентными ребрами (как мы помним, вершина A соединена со всеми вершинами из $M$), получим полный подграф порядка $k+2$, что не допускается условием. Поэтому к такому подграфу можно применить индукционное предположение. Получим: $$ r' \leslant \left(1-\frac{1}{k}\right)\frac{m^2}{2} $$

Оценим количество остальных ребер $r''$. Каждое из таких ребер инцидентно хотя бы одной вершине, не содержащейся в $M$. (Говоря по-простому. хотя бы один из концов каждого из остальных ребер находится вне $M$.) Пусть $N$ - множество вершин, дополнительное к $M$ (содержащее все вершины, не содержащиеся в $M$). Обозначим суммарную степень вершин из $N$ через $D$. Так как каждое из $r_2$ ребер инцидентно хотя бы одной вершине из $N$, то $r'' \leslant D$. С другой стороны, в силу максимальности вершины А, степень каждой из $m-n$ вершин в $N$ не превосходит $m$, поэтому: $D \leslant m(n-m)$. Из этих неравенств получаем: $$ r'' \leslant m(n-m) $$.

Теперь можно оценить общее количество ребер: $$ r(n,k+1)=r'+r'' \leslant \left(1-\frac{1}{k}\right)\frac{m^2}{2} + m(n-m) = -\left(1+\frac{1}{k}\right)\frac{m^2}{2}+mn $$.

Выделив полный квадрат в правой части, получаем: $$ r(n,k+1) \leslant -\frac{k+1}{2k}\left(m-\frac{nk}{k+1}\right)^2+\frac{n^2k}{2(k+1)} $$ Отсюда $$ r(n,k+1) \leslant \frac{n^2}{2}\frac{k}{k+1} = \left(1-\frac{1}{k+1}\right)\frac{n^2}{2} $$

Получили неравенство (7) для $k+1$, чем завершается доказательство.

Как вы наверное заметили, в доказательстве использована та же идея, что и в доказательстве теоремы Мантеля, что неудивительно.

Граф Турана

На самом деле, теорема Турана не только дает оценку количества ребер, но указывает $n$-вершинный граф без полных $k+1$-вершинных подграфов, дающий максимальное количество ребер.

В первой части нам удалось найти исчерпывающий ответ для $k=2$: полный двудольный граф с долями почти равной мощности. По аналогии можно предположить, что при большем значении $k$, максимальное количество ребер дает $k$-дольный граф с долями почти равной мощности.

Для построения такого графа разделим $n$ на $к$ с остатком. Получим: $$ n=ak+b, \text{ где } 0\leslant b \lt k \qquad(8) $$

Разбиваем все множество вершин на $b$ подмножеств по $a+1$ вершине в каждом и $k-b$ подмножеств по $a$ вершин в каждом. Легко убедиться, что $$ (a+1)b+a(k-b)=n \qquad(9) $$, то есть множество вершин графа действительно развивается на $k$ подмножеств, причем количества вершин (мощности) каждой пары множеств отличаются по абсолютной величине не более чем на единицу.

Чтобы получить полный $n$-дольный граф, достаточно соединить каждую вершину каждой доли с каждой из вершин других долей (но не своей доли!). Полученный граф называется графом Турана и обозначается $T(n, k)$.

Нижеследующий рисунок дает пример графа Турана для $n=10$ и $k=3$.

Теперь можно сформулировать теорему Турана:

Теорема Турана.(P. Turán, 1943). Граф $T(n, k)$ дает максимальное количество ребер среди всех $n$-вершинных графов не обладающих полными $k+1$-вершинными подграфами.

Теорема Турана была впервые опубликована на венгерском языке в 1941 году:

Turán, P. (1941). Egy gráfelméleti szélsőértékfeladatról (Об экстремальных проблемах теории графов). Matematikai és Fizikai Lapok. 48: 436–452.

Ведь были времена, когда отнюдь не все серьезные математические журналы печатали статьи на английском языке! «Свежо предание, но верится с трудом.» Парадоксальнее всего то, что именно тогда перевести статью было совсем не просто: ведь нужен был не просто переводчик, а математический эксперт, владеющий языком. И все же статья была замечена и теорема Турана стала одной из фундаментальных теорем теории графов. Так стоит ли писать статьи на примитивном английском языке, когда только на родном языке можно выразить мысль четко и однозначно?! На самом деле, больше всего от гегемонии английского языка страдает ... сам английский язык. То и дело на англоязычных сайтах можно найти пожелание: «Не пишите на сложном языке, потому что люди, не владеющие языком в совершенстве, вас не поймут.» Некоторые «корифеи грамматики» додумались до того, что предлагают отказаться от страдательного залога или использования сложных дополнений с предлогом на конце. То ли еще будет! Даже читая английскую литературу 1930х годов, можно заметить, как обеднел язык за эти годы и в лексике, и в стилистике, а если говорить о произведениях, XIX века, то скоро их понять будет не легче, чем Шекспира.

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

Здесь я только покажу, что неравенство (7) является следствием теоремы Турана

Заметим что каждая вершина $(а+1)$-вершинной доли соединяется с $n-(а+1)$ вершинами других долей. Поскольку таких долей $b$, суммарная степень вершин, находящихся в этих долях равна $b(n-a-1)(a+1)$. Каждая вершина $а$-вершинной доли соединяется с $n-а$ вершинами других долей. Таких долей $k-b$, суммарная степень вершин, находящихся в этих долях равна $(k-b)(n-a)a$. Вспомнив лемму о рукопожатиях, согласно которой сумма степеней равна удвоенному количеству ребер, получим: $$ 2r_{max}(n,k) = b(n-a-1)(a+1) + (k-b)(n-a)a = [b(a+1)+(k-b)a](n-a) - b(a+1) $$ где $r_{max}(n,k)$ — количество ребер графа Турана $T(n,k)$, то есть максимальное количество ребер, возможное для графа порядка $n$ без полных подграфов порядка $k+1$.

Согласно (9) выражение в квадратных скобках есть $n$. Производя замену получаем: $$ 2r_{max}(n,k) = n(n-a)-b(a-1) = n^2-a(n+b)-b $$

Сделав, согласно (8), постановку $a=\frac{n-b}{k}$, приходим к $$ 2r_{max}(n,k) = n^2-\frac{n^2-b^2}{k}-b = n^2\left(1-\frac{1}{k}\right) - \frac{b(k-b)}{k} $$

Наконец, $$ r_{max}(n,k) = \left(1-\frac{1}{k}\right)\frac{n^2}{2} - \frac{b(k-b)}{2k} \qquad (10) $$

Легко видеть, результат (9) из части 1 является частным случаем полученного равенства, соответствующем $k=2$.

Так как $0 \leslant b \lt k$, вычитаемое в (10) является числом неотрицательным, откуда в силу максимальности графа Турана, следует неравенство (7).

Из (10) следует, что что при $b=0$ (то есть, если $k$ является делителем $n$), неравенство (7) становится равенством: $r_{max}(n,k)=\left(1-\dfrac{1}{k}\right)\dfrac{n^2}{2}$

Воспользуемся неравенством (10) для оценки нижней границы $r_{max}(n,k)$ при $b>0$. Согласно теореме о средне-арифметическом и средне-геометрическом $b(k-b) <= \dfrac{k^2}{4}$, поэтому: $$ \left(1-\frac{1}{k}\right)\frac{n^2}{2} - \frac{k}{8} \leslant r_{max}(n,k) \leslant \left(1-\frac{1}{k}\right)\frac{n^2}{2} $$

Неравенство показывает, что число $r$ находится в интервале длиной $\dfrac{k}{8}$. Если $k \leslant 8$, длина интервала не превосходит 1, поэтому в нем может находиться одно целое число. Отсюда, если $k \leslant 8$ и не является делителем $n$, $$ r_{max}(n,k) = \begin{cases} \left(1-\dfrac{1}{k}\right)\dfrac{n^2}{2} - 1, & \text{если } \left(1-\dfrac{1}{k}\right)\dfrac{n^2}{2} \text{— целое} \\ \left\lfloor\left(1-\dfrac{1}{k}\right)\dfrac{n^2}{2}\right\rfloor, & \text{если } \left(1-\dfrac{1}{k}\right)\dfrac{n^2}{2} \text{— дробное}\end{cases}\qquad (11) $$

ЗАДАЧИ

3. На плоскости даны 60 точек, так что никакие три из них не лежат на одной прямой. Какое наименьшее количество отрезков следует провести, чтобы в любом множестве из $n$ точек нашлись две точки, соединенные между собой отрезком. Рассмотрите случаи $n=3,4,5,9,10,11$.

Решения задач: здесь

«Друг моего друга мне не друг» или две теоремы теории графов. Часть 1

Начнем с типичной олимпиадной задачи:

На далекой планете есть 20 государств, некоторые из которых установили дипломатические отношения и обменялись посольствами. При этом среди любых трех государств некоторые два еще не установили между собой дипломатических отношений. Доказать, что на этой планете не более 200 посольств.

Вот так условие: «Друг моего друга мне не друг"! Не знаю, как вам, а мне нравится. Помню, как в юности я довольно комфортно чувствовал себя в tête-à-tête, но очень смущался, когда в нашу скромную компанию вливался кто-то третий. Как вы догадались, дело было вовсе не в секретности наших разговоров. (Скажу более, у меня никогда не было желания обсуждать с кем-либо какие-либо тайны, и ко мне относились соответственно.) Всегда получалось так, что в результате этого я оказался выброшенным на обочину беседы, так как весь интерес моего бывшего собеседника переключался на «третьего лишнего», и если я пытался вставить свою робкую фразу, она (случайно или понарошку) оставалась незамеченной. Как спокойно я бы себя чувствовал, зная, что третьего не будет, так как любой другой постесняется хотя бы одного из нас ввиду отсутствия дипломатических отношений!

«В тихом омуте черти водятся». А омут-то тихий, потому что заброшенный и покинутый теми, кто не потрудился в него заглянуть! Вот и проходилось уповать на чертей ... пока не появились блоги. Не удивлюсь, если многие из популярных блогеров в миру являются робкими необщительными людьми, а вести блог начали лишь от желания быть услышанными, совсем не рассчитывая на успех.

Как ни говорите, а все-таки хорошо, когда нет третьих лишних! Это устраняет клановость и уменьшает (если не полностью ликвидирует) возможность заговора. В таком обществе нет ни фаворитов, ни изгоев, так как все связаны одной нитью.

Решение

Будем рассматривать общий случай, обозначив количество государств через $n$... Для начала неплохо, но что делать дальше? Есть какие-то предложения? Таковых нет. Приходится искать крайнего, то есть того, кто лучше или хуже остальных. В данном случае следует присмотреться к самой дружественной стране, то есть той, где есть наибо́льшее количество посольств.

Итак, пусть $A$ — государство с наибо́льшим количеством посольств (то есть наибо́льшим количеством дипломатических отношений). Обозначим это количество через $m$. Возможно, некоторые другие государства также имеют $m$ посольств, но никакое не может иметь их больше $m$.

Пусть $M$ — множество государств, имеющих дипломатические отношения с $A$. Мы знаем, что в $M$ входит $m$ государств. При этом никакие из них не могут иметь дипломатических отношений между собой, так как если найдутся два государства $B \in M$ и $C \in M$, заключившие между собой дипотношения, то в тройке $A$, $B$, $C$ все государства обожают друг друга, что никак не допустимо.

Опять пауза! Надо использовать максимальность $m$, а это вряд ли у нас получится, если дипломатические отношения на столь низком уровне. Что же делать?..

Выход есть! Обратиться за помощью к другим государствам. Пусть $N$ — множество государств не входящих в $M$ (такое множество называется дополнительным). Множество $N$ содержит $n-m$ государств (включая, между прочим, государство $A$). Поскольку государства из $M$ чуждаются друг друга, то в каждом дипломатическом отношении участвует хотя бы одно государство из $N$. Другими словами, каждое дипломатическое отношение создает хотя бы одно посольство в $N$.

Пусть $r$ — общее количество дипломатических отношений (почему именно буква $r$ выяснится чуть позже), а $E$ — количество посольств в государствах из $N$. Тогда согласно приведенным выше рассуждениям $$ r \leslant E \qquad (1) $$

Опять эта неуловимая максимальность $m$ оказалась не у дела! Как ее использовать? Вот как! Поскольку каждое из $n-m$ государств в $N$ не может иметь более $m$ посольств, общее количество посольств в $N$ не превосходит $m(n-m)$: $$ E \leslant m(n-m) \qquad (2) $$

Сравнивая (1) и (2) получам: $$ r \leslant m(n-m) \qquad (3) $$

Неравенство (3) дает оценку сверху для количества дипломатических отношений, а следовательно для количества посольств, которых ровно в два раза больше, так как каждое дипломатическое отношение создает посольства в обоих странах. Правда, неравенство (3) содержит неизвестное значение $m$, но его можно исключить, оценив максимум $m(n-m)$. Для этого у нас есть палочка-выручалочка: неравенство между средне-арифметическом и средне-геометрическом, согласно которому $\frac{m+(n-m)}{2} \geslant \sqrt{m(n-m)}$. Отсюда $$ m(n-m) \leslant \frac{n^2}{4} \qquad (4) $$

Окончательно получаем: $$ r \leslant \frac{n^2}{4} \qquad (5) $$

В частности, при $m=20$, получаем не больше $\frac{20^2}{4}=100$ дипломатических отношений, то есть не более $200$ посольств, что в точности совпадает с оценкой условия задачи.

Фактически была доказана теорема Мантеля, названная по имени голландского математика Вилема Мантела [Willem Mantel], (по непонятным причинам эту фамилию на русском языке принято писать с мягким знаком). Разумеется, настоящая теорема Мантеля ни имеет дело с государствами или дипломатическими отношениями, а относится к теории графов.

Разумеется, речь идет не о дворянском титуле, который по-немецки пишется с буквой "f": Graf. «Наш» граф (в немецком, английском и французском) пишется через "ph": graph, и происходит , от греческого «γράφω» (в латинской транслитерации grapho), что значит «писать». (Между прочим, это греческое слово внесло вклад в такие слова как «автограф», «биограф», «сейсмограф» и т.д.). В страдающем отсутствием суффиксов английском языке слово "graph" означает также «график функции».

Что такое граф понять совсем не сложно. Достаточно на листе бумаги набросать несколько точек, и соединить некоторые из них отрезками. Вот и получился граф! Точки называются вершинами графа, а отрезки ребрами графа. Количество вершин называется порядком графа, а количество ребер — мощностью графа.

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

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

Графы изображенные на рисунках 1а и 1б являются изоморфными, несмотря на то, что на рис. 1а AC — отрезок, тогда как на рис. 1б AC — кривая линия. Важно лишь то, что в обоих графах вершины A и C соединены между собой. При этом не должно смущать то, что на рис. 1а линии AC и BD пересекаются. Это пересечение лишь «кажущееся», так как точка пересечения не является вершиной графа. Чтобы сделать это явным, на рис 1б) ребро AC нарисовано «в обход». В случае, когда можно избавиться от всех «неправильных» пересечений, граф называется плоским. Оба графа на рисунках 1а и 1б являются плоскими, поскольку, хотя линии AC и BD на рис 1а пересекаются, мы знаем, что это можно исправить. Примером графа, не являющегося плоским, является пятиугольник в котором проведены все диагонали. Название «плоский» связано с тем, что в графе, не являющемся плоским, от пересекающихся внутри ребер можно избавиться лишь переместив граф из плоскости в трехмерное пространство, где вершины можно подвинуть, или ребра изогнуть.


1а	1б

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

Заметим, что в графах, изображенных на рис 1а и 1б каждая вершина соединена с каждой из оставшихся вершин, то есть проведены все ребра, какие только можно провести. Такой граф называется полным. Противоположностью полного графа можно считать нуль-граф в котором совершенно отсутствуют ребра.

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

Нас будет особенно интересовать максимальные подграфы образованные заданным подмножеством вершин, то есть, когда к выбранному подмножеству вершин добавляются все ребра исходного графа, соединяющие какую-либо пару выбранных вершин. Такой подграф называется порожденным заданным подмножеством вершин. Заметим, что любой порожденный подграф полного графа является полным графом.

Согласно определению, в каждом графе, не являющемся полным, существуют две вершины, не соединенные ребром. Иногда удается найти и бо́льшее количество вершин, ни одна пара из которых не соединена ребром (то есть никакие вершины не являются смежными друг другу). Такое подмножество вершин называется независимым. Как было замечено, в каждом неполном графе существует независимое подмножество вершин. Очевидно, граф, порожденный независимым множеством вершин является нуль-графом.

Степенью вершины называется количество ребер, инцидентных данной вершине (по-простому: количество ребер, выходящих из этой вершины). Степень вершины $A$ обозначается через $deg(А)$ (англ. degree). Так как каждое ребро соединяет две вершины, оно учитывается в степенях двух вершин, следовательно сумма степеней вершин равна удвоенному количеству ребер: $$ deg(A_1) + deg(A_2) +\;...\;+ deg(A_n) = 2r \qquad(6) $$ где $r$ — количество ребер, $n$ — количество вершин.

Равенство (6) называется леммой о рукопожатиях, в честь неопровержимой истины, известной задолго до появления теории графов: если некоторые члены уютной компании обменялись рукопожатиями, количество людей, пожавших нечетное количество рук, четно. (Надеюсь, читателю понятно, откуда это следует. Если нет, прочтите Чет или нечет того же автора.)

Можно заметить, что в графах на рис 1а и 1б степень каждой вершины равна 3. Это не удивительно, так как в полном графе из $n$ вершин каждая вершина обязана соединяться со каждой $n-1$ остальных вершин. В этом случае суммарная степень вершин равна $n(n-1)$ и, согласно лемме о рукопожатиях, полный $n$-вершинный граф содержит $\dfrac{n(n-1)}{2}$ ребер. Отсюда, в частности следует, что никакой граф из $n$ вершин не может иметь более $\frac{n(n-1)}{2}$ ребер

Может ли граф, не являющийся полным иметь полный подграф? Может, если, конечно, идет речь о подграфе меньшего порядка. Например если из графа на рис 1а (или 1б) удалить ребро BC, в нем останутся полные подграфы, порожденные вершинами ABD а также ACD. Полные графы из трех вершин (такие как ABD и ACD нашем примере) я буду для краткости называть треугольниками.

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

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

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

А как перевести на язык графов «друг моего друга мне не друг»? Здесь тоже довольно ясно: в графе не должно быть треугольников, на официальном языке полных 3-вершинных подграфов.

Итак, мы готовы сформулировать теорему Мантеля, как она звучит на самом деле:
В $n$-вершинном графе, не содержащем полных 3-вершинных подграфов, количество ребер не превосходит $\dfrac{n^2}{4}$.

Для доказательства достаточно перевести решение задачи о посольствах на язык теории графов.

Теорема Мантеля была опубликована в журнале Wiskundige Opgaven (Математические упражнения), № 10 за 1907 год (задача 28). По-видимому, ввиду простоты доказательства, автор постеснялся его опубликовать в отдельной статье, однако публикация была замечена и породила целое направление, называемое «Экстремальной теорией графов».

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

За круглым столом сидят $n$ участников «безумного чаепития». $(n \geslant 3)$ (по мотивам сказки «Льюиса Кэролла «Алиса в стране чудес».) Каждую минуту одна пара соседей меняется местами. Через какое наименьшее время все участники чаепития могут оказаться сидящими в противоположном порядке (так что левые соседи у всех станут правыми и наоборот)? Задачник Кванта задача М955. Журнал «Квант» №11 1985.

Есть идея, как применить теорему Мантеля? Не знаю, получится у вас читать и думать одновременно. В конце концов, можно либо отложить чтение и подумать, либо понадеяться на то, что нижеследующие рассуждения натолкнут на мысль.

Треугольники ... Они упоминаются в теореме Мантеля, но где их взять?. Постараемся вникнуть в задачу. Занумеруем всех сидящих номерами по порядку по часовой стрелке. Легко видеть, что результате всех перестановок они тоже будут сидеть по порядку, но только против часовой стрелки. Расположение как бы вывернулось наизнанку, поэтому если по-прежнему идти по часовой стрелке, порядок любых трех человек должен измениться. Это значит, что двое из них должны были обязательно пересаживаться. (Кстати, почему подобные рассуждения не работают для двух человек?)

Теперь все понятно. Сопоставим каждому «чаепьющему» вершину графа и будем соединять ребрами тех, кто не(!) пересаживался. На основании вышеприведенных рассуждений в таком графе не будет треугольников, поэтому согласно ... (угадайте чему) в нем будет не более $\frac{n^2}{4}$ ребер.

Нас однако интересуют не присутствующие, а отсутствующие ребра. Их мы оценим исходя из того, что полный граф имеет $\frac{n(n-1)}{2}$ ребер. Таким образом, если $p$ — количество пересаживаний, то $$ p \geslant \frac{n(n-1)}{2} - \frac{n^2}{4} = \frac{n(n-2)}{4} \qquad (7) $$ следовательно потребуется не менее $\frac{n(n-2)}{4}$ минут.

Есть возражения? Должны быть! Ведь в задаче требуется не просто оценить снизу, а дать точную оценку, то есть показать, что существует перестановка занимающая точно $\frac{n(n-2)}{4}$ минут, то есть состоящая из ровно $\frac{n(n-2)}{4}$ пересаживаний.

Скажу по секрету, что на самом деле оценка, даваемая (7) точна далеко не для всех значений $n$, и ее необходимо подправить. Однако для начала, проверим на точность саму теорему Мантеля.

Итак, существует $n$-вершинный граф, для которого неравенство (5) является точным? «Только не для нечетного $n$!» — возразит внимательный читатель. Действительно, при нечетном $n$, выражение $\frac{n^2}{4}$ становится дробным, между тем как количество ребер — целое число. Придется подправить и воспользоваться знаком целой части $\lfloor$…$\rfloor$ ($\lfloor a \rfloor$ — наибольшее целое число, не превосходящее $a$): $$ r_{max} = \left\lfloor\frac{n^2}{4}\right\rfloor \qquad (8) $$ где $r_{max}$ — максимальное количество ребер, возможное для графа порядка $n$ без треугольников.

До чего же неприятно иметь дело с целой частью! Давайте начнем с четного $n$ и покажем, что в этом случае неравенство (5) можно обратить в равенство. Тем самым будет доказана справедливость (8) для четного $n$.

Присмотримся к доказательству теоремы. Неравенство (5) вытекает из неравенств (1), (2) и (4), и для достижения нашей цели все они должны стать равенствами. Рассмотрим эти неравенства по-порядку.

Неравенство (1) вытекает из того, что «в каждом дипломатическом отношении участвует хотя бы одно государство из $N$», или, на языке теории графов, каждое ребро графа инцидентно хотя бы одному ребру из $N$. Для равенства требуется не «хотя бы одному ребру» а «точно одному». Другими словами, в $N$ не должно быть вершин, связанных между собой, то есть $N$ должно быть независимым подмножеством. Вспомним, что в $M$ также отсутствуют внутренние ребра. Таким образом искомый граф состоит из двух независимых множеств, так что каждое ребро соединяет вершину одного множества с вершиной другого множества. Такой граф называется двудольным, а независимые множества, из которых он состоит называются долями.

Обратимся к неравенству (2). Оно основано на том, что степень каждой вершины из $N$ не превышает $m$. Для получения равенства необходимо, чтобы степень каждой вершины была равна $m$, то есть каждая вершина из $N$ должна быть соединена с каждой вершина из $M$. Двудольный граф, в котором каждая вершина одной доли соединена с каждой вершиной другой доли называется полным двудольным графом. Именно такой граф нам нужен.

Наконец, когда неравенство (4) становится равенством? Ответ простой: средне-арифметическое равно средне-геометрическому тогда и только тогда, когда числа равны. В данном случае это означает равенство $n$ и $m-n$, то есть обе доли должны состоять из равного количества вершин.

Итак, для четного $n$ все прояснилось: максимум вершин дает полный двудольный граф, по $\frac{n}{2}$ вершин в каждой доле. Так как каждая из $\frac{n}{2}$ вершин одной доли соединена с каждой из $\frac{n}{2}$ вершин другой доли, получаем всего $\left(\frac{n}{2}\right)^2$ или $\frac{n^2}{4}$ ребер — точно по ответу!

Обратимся к случаю нечетного $n$. Если $n=2k+1$, то $\dfrac{n^2}{4}=k(k+1)+\dfrac{1}{4}$, так что дробная часть от $\dfrac{n^2}{4}$ равна $\dfrac{1}{4}$, следовательно $\left\lfloor\dfrac{n^2}{4}\right\rfloor=\dfrac{n^2-1}{4}$.

Таким образом равенство (8) можно переписать в виде: $$ r_{max} = \begin{cases} \dfrac{n^2}{4}, & \text{ если } n \text{ четно} \\ \dfrac{n^2-1}{4}, & \text{ если } n \text{ нечетно} \end{cases} \qquad (9) $$

Теперь стало понятным, как получить требуемый граф при нечетном $n$. На этот раз доли должны содержать почти равное количество вершин, в одной доле должно быть $\dfrac{n-1}{2}$ вершин, а в другой $\dfrac{n+1}{2}$ вершин, то есть одной вершиной больше. Соединив каждое ребро 1-й доли с каждым ребром 2-й доли получаем как раз $\dfrac{n^2-1}{4}$ вершин. Таким образом равенства (8) и (9) справедливы для любого $n$, как четного, так и нечетного.

Используя термин множества почти равной мощности для множеств, количество элементов которых отличается по абсолютной величине не более чем на единицу, полученный результат можно сформулировать следующим образом:

Максимальное количество ребер среди всех $n$-вершинных графов не обладающих полными $3$-вершинными подграфами дает полный двудольный граф с долями почти равной мощности.

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

Рисунки 2а и 2б показывают графы, дающие максимальное количества ребер для $n=6$ и $n=7$.


2а	2б

Теперь в самый раз приступить к чаепитию!

В начале подправим равенство (7) для нечетного $n$, заменив $\dfrac{n^2}{4}$ на $\dfrac{n^2-1}{4}$. Получим: $$ p \geslant \frac{n(n-1)}{2} - \frac{n^2-1}{4} = \frac{(n-1)^2}{4} \qquad (7') $$ для нечетного $n$.

Объединяя (7) и (7'), можно оценить минимальное количество пересаживаний (то есть минимальное количество отсутствующих ребер графа): $$ p_{min}=\begin{cases} \dfrac{n(n-2)}{4}, & \text{если } n \text{ четно} \\ \dfrac{(n-1)^2}{4}, & \text{если } n \text{ нечетно} \end{cases} \qquad(10) $$

Осталось сообразить (и не только на троих, так как $n=3$ лишь частный случай), как организовать пересаживания, которые я с умным видом буду называть транспозициями.

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

Решение. Для упрощения выкладок положим $k=\left\lfloor\frac{n}{2}\right\rfloor$. Разобьем стол «почти диагональю» на почти равные группы: в первой группе $k$ участников, во второй группе остальные $n-k$ участников.

В первой группе занумеруем участников по часовой стрелке. 1-го участника пересаживаем (по часовой стрелке) по очереди со всеми остальными членами группы. Это дает $k-1$ транспозиций, в результате которых 1-й окажется на требуемом месте в конце группы, тогда как другие члены группы не изменят своего положения друг относительно друга. После этого пересаживаем 2-го по очереди со всеми членами группы с бо́льшими номерами (то есть кроме первого). В результате этих $k-2$ транспозиций 1-й и 2-й окажутся на требуемом месте, а другие не изменят своего положения друг относительно друга. Продолжаем это делать до тех пор, пока все окажутся на требуемом месте.

Знакомые с программированием конечно заметили, что фактически сделана хорошо известная сортировка «методом пузырька» (англ. bubble sort).

Подсчитаем общее количество транспозиций: $$ (k-1)+(k-2)+\;...+\;1 = \frac{(k-1)k}{2} $$

Аналогично поступаем для второй группы, в результате чего получаем еще $\dfrac{(n-k-1)(n-k)}{2}$ транспозиций.

Если $n$ четно, то $n-k=k=\dfrac{n}{2}$, поэтому в каждой из групп будет сделано по $\dfrac{\left(\dfrac{n}{2}-1\right)\dfrac{n}{2}}{2} = \dfrac{(n-2)n}{8}$ транспозиций, а всего $\dfrac{n(n-2)}{4}$ транспозиций.

В случае нечетного $n$ получаем $k=\dfrac{n-1}{2}$ и $n-k=\dfrac{n+1}{2}$. Поэтому количество транспозиций в первой группе $\dfrac{\left(\dfrac{n-1}{2}-1\right)\dfrac{n-1}{2}}{2}=\dfrac{(n-3)(n-1)}{8}$, а во второй группе $\dfrac{\left(\dfrac{n+1}{2}-1\right)\dfrac{n+1}{2}}{2}=\dfrac{(n-1)(n+1)}{8}$, давая в итоге $\dfrac{(n-1)^2}{4}$ транспозиций.

В обоих случаях результат согласуется с (10), так что никаких вопросов больше не остается. Итак, потребуется $\frac{n(n-2)}{4}$ минут в случае четного $n$ и $\frac{(n-1)^2}{4}$ при нечетном n, что в пересчете на одного человека дает $\frac{n-2}{4}$ и $\frac{(n-1)^2}{4n}$ минут соответственно.

Окончание следует

Чет или нечет

Что может быть проще, чем четность? Даже дошкольники незнакомые с делимостью понимают, что не всякую группу детей можно объединить парами. Поэтому далеко не случайным является существование специального слова для делимости на два, но отсутствие такового для делимости на другие числа. При этом в ряде языков слово «четный» созвучно слову «пара»: (польск. parzysty, фр. pair, исп. par), да и русское «четный» одного корня со словами «чета» или «сочетать», что также связано с парностью. В других языках четность ассоциируется с гладкостью (англ. even, чешск. sudý, нем. gerade), a нечетность с чем-то лишним или посторонним (англ. odd, чешск. lichý), хотя в математике, конечно, нет ничего лишнего!

$0$ ... $1$ ... $2$!

На ноль делить нельзя, зато само число $0$ делится нацело на все другие натуральные числа, имея таким образом бесконечное количество делителей. Наоборот, на $1$ делится нацело все подряд, зато сама единица делится нацело только на себя, поэтому имеет лишь один делитель. Ох уж эти ноль и единица! Так и норовят все запутать. При решении задачи они могут доставить неприятный сюрприз, так как, позабыв об их существовании, можно упустить довольно существенную деталь.

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

Кстати, никого не удивил то факт, что число $0$ было упомянуто среди натуральных чисел? Ведь утверждают школьные учебники, что натуральные числа — это числа, возникающие в результате счета, тогда как начинать счет с нуля придет в голову разве что программисту на C и подобных ему языках программирования! Однако, вопрос о «натуральности» числа $0$ не имеет однозначного ответа среди математиков. Например, в знаменитой арифметике Джузеппе Пеано, созданной еще в XIX веке, число 0 занимает достойное место среди натуральных чисел, что имеет вполне определенный резон. Автор этих строк предпочитает придерживаться нейтралитета, употребляя бесспорные термины: «целые положительные» или «целые неотрицательные» числа.

Но обратимся к герою нашего повествования, числу 2. Это наименьшее из целых неотрицательных чисел на которое делить можно, причем остаток не всегда равен нулю. Если остаток равен нулю, то число имеет вид $2n$ (здесь и далее буквами обозначаются только целые числа) и называется четным. Если остаток не равен нулю, то ввиду необходимости быть меньше делителя, он обязан быть единицей, поэтому такое число имеет вид $2n+1$ и называется нечетным.

Заметим что $2$ — единственное четное простое число. Другие четные числа делятся на $2$, поэтому они не могут считаться простыми.

Четность суммы

Сумма двух четных чисел является четной: $2m+2n=2(m+n)$. Сумма двух нечетных чисел также является четной: $(2m+1)+(2n+1)=2(m+n+1)$, поскольку единичные остатки как бы компенсируют друг друга. Лишь сумма двух чисел разной четности является нечетной: $2m+(2n+1)=2(m+n)+1$, так как в этом случае единичный остаток не компенсируется. Из сказанного следует, что прибавление четного числа не изменяет четности (так как сохраняет остаток), тогда как прибавление нечетного числа изменяет четность на противоположную, т.е. делает четное число нечетным и наоборот.

Оценим четность суммы нескольких чисел, среди которых могут быть четные и нечетные слагаемые. Так как четные слагаемые не изменяют четности, достаточно узнать четность суммы нечетных слагаемых. Если $m$ — количество таких слагаемых, то

$$ (2n_1+1)+(2n_2+1)+...+(2n_m+1)=2(n_1+n_2+..+n_k)+m $$

Таким образом четность суммы зависит от четности $m$: если $m$ четно, то сумма четна, и наоборот.

Заметим, что четность обладает симметрией: четность числа $a$ совпадает с четностью противоположного числа $-a$. Поэтому четность не изменится, если некоторые слагаемые заменить на противоположные (или, попросту говоря, поменять знак).

Резюмируя сказанное получаем: Четность алгебраической суммы совпадает с четностью количества нечетных слагаемых.

Четность произведения и степени.

С произведением все очевиднее. Достаточно, чтобы среди сомножителей «затесалось» одно четное число $a_i=2n_i$, как результат будет четным: $a_1a_2...a_i...a_k=2a_1a_2...n_i...a_k$. Таким образом, произведение может быть нечетным лишь тогда, кода все сомножители нечетны.

Покажем обратное: произведение нечетных сомножителей нечетно. Для этого воспользуется индукцией по количеству сомножителей. В случае одного нечетного сомножителя он сам является произведением, так что утверждение верно. Допустим утверждение верно для $k$ сомножителей, то есть: $$ (2a_1+1)(2a_2+1)...(2a_k+1) = 2P + 1 $$ где $P$ — целое число. Тогда произведение $k+1$ сомножителей $$ (2a_1+1)(2a_2+1)...(2a_k+1)(2a_{k+1}+1) = (2P+1)(2a_{k+1}+1) = 2(2Pa_{k+1} + P + a_{k+1}) + 1 = 2Q + 1 $$ где $Q=2Pa_{k+1} + P + a_{k+1}$ — целое число. Поэтому произведение $k+1$ сомножителей, также нечетно, что завершает индукционный переход.

Резюмируя сказанное, получаем: Произведение нечетно тогда и только тогда, когда все сомножители — нечетные числа.

Из это следует, что умножение на четное число дает четное число, тогда как умножение на нечетное число не изменяет четность.

В частности четность степени числа (здесь и далее имеется в виду целая положительная степень) совпадает с четностью основания. Кроме того, степень $m$ четного числа делится на $2^m$. Это следует из того, что $\left(2n\right)^m=2^mn^m$.

Рассмотрим степень нечетного числа. Так как $(2k+1)^2=4k(k+1)+1$, квадрат нечетного числа при делении на $4$ дает в остатке $1$, тогда как само число при делении на 4 может давать в остатке либо 1 либо 3. . Более того, поскольку одно из чисел $k$, $k+1$ является четным, число $k(k+1)$ является четным, следовательно $\left(2n+1\right)^2$ дает остаток $1$ при делении на $8$.

Учитывая, что любая четная степень является квадратом: $a^{2n}=\left(a^{2}\right)^n$, приходим к следующему выводу: Четная степень нечетного числа дает остаток 1 при делении на 8.. Другими словами, $(2m+1)^{2n}-1$ делится на 8.

Наконец, рассмотрим нечетную степень нечетного числа и заметим, что при нечетном $a$, остаток от делении $a^{2n+1}$ на 4 или на 8 совпадает с остатком от деления $a$ на 4 или 8 соответственно. Это происходит потому, что $a^{2n+1}-a = a(a^{2n}-1)$ делится на 4 и 8, как было ранее доказано

Четность функций.

Понятие четности применимо также к функциям:

Функция $f(x)$ называется четной, если для любого вещественного $x$ справедливо равенство $f(-x)=f(x)$.

Функция $f(x)$ называется нечетной, если для любого вещественного $x$ справедливо равенство $f(-x)=-f(x)$.

Будем говорить, что функция обладает четностью, если она является либо четной, либо нечетной. Например, функции $y=|x|$ и $y=x$ обладают четностью, так как первая четна, вторая - нечетна. В то же время функция $y=x+1$ не обладает четностью, так как не является ни четной, ни нечетной.

Чем обусловлено такое на первый взгляд неожиданное определение четности функций? Начнем с вполне очевидного, но заслуживающего упоминания факта:
Произведение ненулевых чисел положительно тогда и только тогда, когда количество отрицательных сомножителей четно.

В частности: $$ (-1)^n=\left\{\begin{matrix} 1,\;если\;n\;\text{четно} \\ -1,\;если\;n\;\text{нечетно} \end{matrix} \right. $$

Отсюда следует, что $$ (-x)^n = (-1)^n\,x^n = \begin{cases} x^n,\;если\;n\;\text{четно} \\ -x^n,\;если\;n\;\text{нечетно}\end{cases} $$

Другими словами, степенная функция $y=x^n$ с целочисленным показателем обладает четностью, совпадающей с четностью показателя. По-видимому определение четности функций навеяно указанным свойством степенной функции.

Практическое использование четности чисел.

Здесь приведены практические примеры использования четности и числа 2. Надеюсь, что этот перечень будет пополняться.

Выбор правильного направления для поиска нужного дома.

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

Здесь помогает следующее наблюдение: Если встать так, чтобы с правой стороны были четные номера́, а слева — нечетные, то вы смотрите в сторону возрастания номеров. Таким образом, в нашем случае надо идти по направлению движения автобуса, если конечно идет речь о государстве с правосторонним движением. В Австралии, где движение левостороннее, автобус остановится на левой стороне дороги, поэтому следует идти в обратном направлении.

Система, в которой четные нечетные номера́ находятся по разную сторону от дороги называется Европейской, так как возникла во Франции. Привычка располагать четные номера́ справа по ходу движения по-видимому исходит из привычки писать слева направо, вот и получается, что число 1 помещается слева, число 2 справа и т.д. Хотя возможно это не так: в Израиле, где государственный язык использует запись справа налево, нумерация улиц обычная, однако в Англии, где пишут привычным нам образом слева направо, четные номера́ чаще всего оказываются слева.

Есть примеры обратного расположения (четные номера́ слева) и в странах со общепринятой нумерацией, как например в центре Петербурга, где номера́ домов появились задолго до принятия определенного стандарта, а также в некоторых районах австралийских городов Мельбурн и Сидней. На карте такие улицы как правило оговариваются.

В странах Латинской Америки дома́ нумеруются по аналогии с Европой, но не по порядку а по расстоянию в метрах от начала дороги. Так если дом с номером 10 имеет длину 5 или 6 метров, то следующий дом имеет номер 16.

Карта города Мангейм
Источник: Skyscraper City

Не могу не привести другие примеры нумерации.

Традиционная английская нумерация, бывшая также в ходу в Прусской империи, является «круговой», называемая также бустрофедонской (англ. Boustrophedon numbering) или подковной (нем. Hufeisennummerierung): она идет последовательно (нечетные и четные друг за другом) по левой стороне дороги до конца, после чего продолжается по правой стороне в обратном направлении. В этом есть определенное удобство: можно сразу оценить продолжительность дороги, так как самый маленький и самый большой ее номер оказываются рядом. Однако продолжать такую улицу невозможно, так что приходится для продолжения придумывать новое название (напр. добавлять слово «западный» или «малый»). Такая нумерация сохранилась в центре Лондона для пешеходной улицы Pall Mall а также в центре Берлина и Гамбурга. Ее до сих пор используют в Англии и Австралии для небольших тупиковых ответвлений, которые уж точно никогда не будут продолжаться.

В центральной части города Мангейм (также Манхайм: Manheim) на юго-западе Германии (федеральная земля Баден-Вюртенберг) дома́ адресуются аналогично полям шахматной доски. Например Институт немецкого языка (красный кружок на карте) имеет адрес R5. Бывает так что по данному адресу находится несколько домов или квартир, их указывают дополнительно, например: S6,2

В Чехии и Словаки со времен Богемии сохранилась система конскрипционных номеров (чешск: popisné číslo), где каждому новому дому присваивался очередной номер. Тут даже на карте дом так просто не найдешь! Поэтому наряду с этой используется также обычная европейская адресация.

Нечто похожее бытует в Японии, однако нумерация производится внутри небольшой области микрорайона в порядке застройки или по часовой стрелке. Вот, например, адрес министерства образования, культуры, спорта, науки и технологии Японии в английской транслитерации: 3-2-2 Kasumigaseki, Chiyoda-ku, Tokyo, где Тиёда - район Токио (япон. ku: 区 ), Касумигасеки – микрорайон (япон. chō: 町) внутри района Тиёда, 3 - номер района домов внутри микрорайона (япон. chōme 丁目) 2 – номер блока домов, последнее 2 - номер дома внутри блока. Подробная информация: sci.lang.japan

В усеянном небоскребами городе Доха, столице Катара, улицы хотя и именуются, но дома не нумеруются, в лучшем случае имеют имена. Таким образом для указания адреса в Дохе дается район (область), название улицы, а также (если имеется) название дома. Вот пример адреса (снова в английском варианте): Education Institute. SEC Tower - Aldana area - Doha - Qatar

Дополнителная информация в Википедии.

Почему двоичная система счисления так нравится компьютерам?

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

До чего все просто в двоичной системе счисления! Там 0 — единственная четная цифра, 1 — единственная нечетная цифра, так как других цифр просто нет! Вы, конечно, знаете, что четность числа совпадает с четностью последней цифры (самого младшего разряда) в десятичной записи числа. Происходит это потому, что всякое число можно записать в виде $a=10b+c$, где $c$ - последняя цифра, a $b$ – число записанное всеми предшествующими цифрами. Так как $10$ – четное число, то $10b$ – также четно, следовательно четности $a$ и $c$ совпадают. Вы, конечно, заметили, что вышеприведенное рассуждение применимо не только к десятичной системе счисления, но и к системе счисления с любым четным основанием. В частности, если речь идет о двоичной системе, то для выяснения четности числа надо лишь выделить последний разряд с помощью операции «логическое И» (другое название: конъюнкция): $a\&1$. Если получаем 0 — число четное, а если 1 — нечетное.

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

Может тогда и нам стоит отказаться от десятичной системы в пользу двоичной? Нет, ни за что на свете! Дело не только в многовековой привычке, но и в том, что в двоичной системе числа получаются намного длиннее, чем в десятичной. Представьте себе, что на купюре в 1000 рублей вы вдруг увидите: 1111101000. Тут не сразу сообразишь, много это денег или мало 😲.

ЗАДАЧИ

Вот и наступил момент истины!

Разминка

Те, кто внимательно прочел вышеизложенное (или нашел это слишком тривиальным, чтобы тратить время на чтение) должны дать ответ, почти не раздумывая. Остается надеяться, что он будет правильным.☺

1.1 В несуществующей стране (под названием СССР) использовались денежные купюры в 1 рубль, 3 рубля и 5 рублей. Можно разменять 100 рублей нечетным количеством указанных купюр?

1.2 100 спичек разложили в 19 коробков и на каждом написали количество спичек. Может произведение этих чисел быть нечетным числом?

1.3 Некоторые члены уютной компании обменялись рукопожатиями. Докажите, что количество людей, пожавших нечетное количество рук, четно.

1.4 Число $n$ четно, но не делится на $4$. Может оно быть полным квадратом? А может быть полным квадратом число а)$\,n+1$? б)$\,n-1$?

1.5 $a$ и $n$ — целые числа, причем $n$ — неотрицательно, $a^n$ — нечетно. Может число $a$ быть четным?

1.6 Можно ли все клетки таблицы $9×2020$ заполнить натуральными числами так, чтобы сумма чисел в любом столбце и сумма чисел в любой строке были бы простыми числами?

1.7 Доказать иррациональность $\sqrt[n]{2}$ для целого $n \geqslant 2$.

1.8 Какая функция является одновременно четной и нечетной?

1.9 Какое из нижеследующих утверждений ошибочно: a) сумма функций, обладающих четностью также обладает четностью; b) произведение функций, обладающих четностью также обладает четностью? Скорректируйте ошибочное утверждение.

На старт!

После небольшой разминки приступим к делу.

2.1 Можно число 2018 представить в виде разности квадратов целых чисел?

2.2 Выписано 2018 последовательных чисел (не обязательно начальных). Каждый раз два произвольных числа заменяются их суммой, отчего количество чисел уменьшается на одно. Это продолжается до тех пор, пока останется одно число. Будет это число четным или нечетным? а) Можно определить четность результата, если вместо сумм использовать разности (число с бо́льшим индексом вычитается из числа с меньшим индексом)? б) А если использовать абсолютные величины разностей?

2.3 Сверхточный прямолинейный робот может двигаться вперед или назад, но не в сторону. При тестировании робота заставляют двигаться сначала на 1см, потом на 2см и т.д, при этом направление движения каждый раз выбирается произвольно. Может ли робот после 2018 движений вернуться в исходное положение?

2.4 Произведение 10 целых чисел равно 1. Доказать, что их сумма не равна нулю.

2.5 Доказать, что $(2m+1)^{2^n}-1$ делится на $2^{n+2}$ ($n \geslant 1$). Примечание: $(2m+1)^{2^n}$ понимается, как $(2m+1)^{(2^n)}$.

2.6 Какими должны быть целые числа $p$ и $q$, чтобы для любого целого $x$ значение $f(x) = x^3+px+q$ было: а) четным? б) нечетным?

Вторая скорость

Чуть больше изобретательности!

3.1 Каждая вершина многоугольника раскрашена в один из двух цветов. Доказать, что количество сторон многоугольника с разноцветными вершинами четно.

3.2 В вершинах куба расставлены числа $1$ и $–1$. В центре каждой грани записано произведение чисел, стоя́щих в вершинах этой грани. Может ли сумма всех чисел (в вершинах и на гранях вместе взятых) равняться нулю?

3.3 Одиннадцать монет лежат решкой вверх. Каждый ход состоит в перевертывании любых 10 монет, причем количество ходов не ограничено. Можно при этом уложить все монеты орлом вверх? А если монет 10, и разрешается переворачивать по 9?

3.4 Пусть $p_n$ — произведение первых n простых чисел. Доказать, что $p_n+1$ не является полным квадратом. À propos, может быть полным квадратом а) $p_n$? б)$p_n$ – 1? Открою секрет: последний вопрос не связан с четностью, точнее с числом 2. Однако рассуждения (хотя и для другого числа) довольно похожи. Примечание. Произведение первых $n$ простых чисел иногда называют праймориалом или примориалом (англ primorial, фр. primorielle), что этимологически представляет собой гремучую смесь prime / premier (простое <число>) с факториалом (произведение первых $n$ натуральных чисел).

3.5 Выписано 2018 последовательных чисел (не обязательно начальных). Каждая пара соседних чисел заменяется их суммой (получаем: $a_1+a_2,\;a_3+a_4$ и т.д.), если последнее число оказалось непарным, оно отбрасывается. Это повторяется до тех пор, пока останется одно число. Будет это число четным или нечетным? а) A если вместо сумм использовать разности? б) А если использовать абсолютные величины разностей?
PS. Разница между этой задачей и задачей 2.2 кажется косметической, зато подход совершенно другой!

3.6 В каждой клетке квадратной таблицы 25×25 записано число +1 или -1. Показать, что сумма произведений чисел каждой строки, сложенная с суммой произведений чисел каждого столбца отлична от нуля.

3.7 Пусть $a_1$, $a_2$, … $a_7$ — целые числа, а $b_1$, $b_2$, … $b_7$ — те же числа, взятые в другом порядке. Доказать, что число $(a_1-b_1) (a_2-b_2) \dots (a_7-b_7)$ четно.

Полный ход!

По-прежнему не считаете это серьезным? Тогда попробуйте еще.

4.1 Найти 8 простых чисел, сумма квадратов которых на 992 меньше, чем их учетверенное произведение.

4.2 Доказать, что из любых $2^{n+1}-1$ целых чисел можно выбрать $2^n$ чисел, сумма которых делится на $2^n$.

4.3 На доске написано несколько нулей, единиц и двоек. Разрешается стереть две неравные цифры и вписать вместо них цифру, отличную от стертых (вместо 0 и 1 — цифру 2, вместо 1 и 2 — 0, вместо 0 и 2 — 1). Докажите, что если в результате таких операций на доске окажется одно число, то оно не зависит от порядка, в котором производились стирания.

4.4 Двое играют в такую игру. На стол кладется 25 спичек. Каждый берёт себе по очереди одну, две или три спички. Игра заканчивается, когда все спички разобраны, Побеждает тот, у кого в конце игры окажется четное количество спичек. Кто выигрывает при правильной игре – начинающий или его партнер? А если для выигрыша требуется взять нечетное количество спичек?

4.5 Вершины 12-угольника занумерованы по порядку числами от 1 до 12 и в каждой из них положено по монете. При этом монета в вершине 1 расположена орлом вверх, а во всех остальных — решкой вверх. Каждый раз разрешается перевернуть одновременно монеты четырех идущих подряд вершин (например, вершин 3, 4, 5, 6 или вершин 11, 12, 1, 2). Доказать, что в результате таких операций невозможно расположить монету в вершине 2 орлом вверх, а во всех остальных — решкой вверх. А если вместо четырех вершин переворачивать другое количество, не превосходящее 12?

Ответы на задачи здесь, однако советую не спешить туда заглядывать.

Чет или нечет. Решения задач.

Привожу ответы на задачи, предложенные здесь.

Разминка

1.1 В несуществующей стране (под названием СССР) использовались денежные купюры в 1 рубль, 3 рубля и 5 рублей. Можно разменять 100 рублей нечетным количеством указанных купюр?

Так как достоинством каждой из купюр является нечетное количество рублей, всякая сумма, оплаченная нечетным количеством купюр нечетна, тогда как 100 — четное число.
Ответ. Нельзя.

1.2 100 спичек разложили в 19 коробков и на каждом написали количество спичек. Может произведение этих чисел быть нечетным числом?

Если в каждом из 19 коробков находится нечетное количество спичек, то общее количество спичек — нечетно. Так как 100 — четное число, то хотя бы в одном коробке находится четное количество спичек, следовательно произведение чисел — четное число.
Ответ. Не может.

1.3 Некоторые члены уютной компании обменялись рукопожатиями. Докажите, что количество людей, пожавших нечетное количество рук, четно.

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

1.4 Число $n$ четно, но не делится на $4$. Может оно быть полным квадратом? А может быть полным квадратом число а)$n+1$? б)$n-1$?

Квадрат нечетного числа — нечетное число, а квадрат четного числа делится на 4.
Ответ. Не может.

а) Так как число $n+1$ является нечетным, оно может быть квадратом только нечетного числа. С другой стороны число $n$ при делении на 4 дает в остатке 2, поэтому остаток от деления на 4 числа $n+1$ равен 3. Между тем , как было показано в публикации, остаток от деления квадрата нечетного числа на 4 всегда равен 1. Ответ. Не может.

б) Ответ. Может. Пусть $n=(2k+1)^2+1$. Тогда $n=4k(k+1)+2$ является четным но не делится на 4, причем $n-1=(2k+1)^2$ — полный квадрат. Примеры: $10=3^2+1$, $26=5^2+1$ и т.д.

1.5 $a$ и $n$ — целые числа, причем $n$ — неотрицательно, $a^n$ — нечетно. Может число $a$ быть четным?

Ответ. Может. Пример: $2^0\;=\;1$. Однако при положительном $n$ это невозможно:

Пусть $a$ — целое число. Если $n$ — целое положительное число, то четность $a^n$ совпадает с четностью $a$.

В самом деле, если $n \geqslant 1$, то $a^n$ является произведением чисел одинаковой четности. В этом случае четность результата совпадает с четностью сомножителей.

1.6 Можно ли все клетки таблицы $9×2020$ заполнить натуральными числами так, чтобы сумма чисел в любом столбце и сумма чисел в любой строке были бы простыми числами?

Всероссийская олимпиада, 2002г. 8-й класс. Окружной этап. В оригинале размер таблицы $9×2002$.

Допустим, что таблица о которой идет речь в условии задачи существует. Тогда сумма сумм цифр всех столбцов равна сумме сумм цифр всех строк и равна сумме всех элементов таблицы. Поскольку сумма цифр столбца — простое число, не меньшее 9, каждая из таких цифр — нечетна. Аналогично сумма цифр каждой строки — нечетное число.

Сумма сумм всех столбцов — это сумма 2020 нечетных чисел и является четным число. С другой стороны, сумма сумм всех строк есть сумма 9 нечетных чисел, а следовательно нечетна. Полученное противоречие показывает, что условие задачи не выполнимо.

1.7 Доказать иррациональность $\sqrt[n]{2}$ для целого $n\geqslant2$.

Если $\sqrt[n]{2}$ – рационально, то оно записывается в виде несократимой дроби: $n\geqslant2 = \frac{p}{q}$, где $p$ и $q$ — целые положительные числа.

Возводя в $n$-ю степень получаем: $p^n = 2\,q^n$, откуда $p^n$ — четное число. В силу утверждения предыдущей задачи $p$ — также четное число.

Подставляя $p=2s$, получаем: $2^n\,s^n = 2\,q^n$ или $q^n = 2^{n-1}s_n$. Поскольку $n\geqslant2$, число $n-1$ положительно, поэтому $2^{n-1}$ — четно, откуда следует четность $q^n$, а следовательно четность числа $q$.

Таким образом дробь $\frac{p}{q}$ оказывается сократимой на 2, что противоречит утверждению. Тем самым доказана иррациональность $\sqrt[n]{2}$ для целого $n\geqslant2$.

1.8 Какая функция является одновременно четной и нечетной?

Если для любого вещественного $x$ равенства $f(-x)=f(x)$ и $f(-x)=-f(x)$ выполнены одновременно, то $f(x)=-f(x)$, следовательно $f(x)=0$ для любого вещественного $x$.

Действительно, функция $y = 0$ (тождественный нуль) является одновременно четной и нечетной, причем, как следует из вышеприведенных рассуждений, других таких функций нет.
Ответ.$y=0$.

1.9 Какое из нижеследующих утверждений ошибочно: a) сумма функций, обладающих четностью также обладает четностью; b) произведение двух функций, обладающих четностью также обладает четностью? Скорректируйте ошибочное утверждение.

a) Утверждение верно, если четности функций совпадают: Сумма функций одинаковой четности имеет ту же четность.

Пусть функции $f_1(x)$, $f_2(x)$ … $f_n(x)$ обладают одинаковой четностью. Это значит, что $f_i(-x)=\pm f(x)$ $i=1,2 \dots n$ (Знак $+$ в случае четных функций, знак $-$, если все функции — нечетные). Если $h(x)$ — сумма всех функций, то $$ \begin{align} h(-x) & = f_1(-x) + f_2(-x) + \dots + f_n(-x) \\ & = \pm f_1(x) \pm f_2(x) \pm \dots \pm f_n(x) \\ & = \pm [f_1(x) + f_2(x) + \dots + f_n(x)] = \pm h(x)\,, \end{align} $$ что и требовалось доказать.

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

Пусть $f(x)$ - четна, $g(x)$ – нечетна, $h(x) = f(x)+g(x)$, причем $f(x)$ и $g(x)$ отличны от тождественного нуля.

Тогда существует вещественное число $a$, такое что $f(a) \ne 0$. Отсюда $f(a) \ne -f(a)$, так что $$ h(-a) = f(a) - g(a) \ne -f(a) - g(a) = -[f(a)+g(a)]\,. $$ Выходит, что $h(-a) \ne -h(a)$, так что функция $h(x)$ не является нечетной.

С другой стороны существует число $b$ (возможно совпадающее с $a$), такое что $g(b) \ne 0$. Поэтому $g(b) \ne -g(b)$, следовательно $$ h(-b) = f(b) - g(-b) \ne f(b) + g(b)\,. $$ Таким образом $h(-b) \ne h(b)$, следовательно функция $h(x)$ не является также четной, чем завершается доказательство.

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

b) Докажем следующее утверждение: Произведение функций, каждая из которых обладает четностью и отлична от тождественного нуля, обладает честностью совпадающей с четностью количества нечетных сомножителей.

Пусть имеется $m$ четных функций $f_1(x)$, $f_2(x)$, … $f_m(x)$ и $n$ нечетных функций $g_1(x)$, $g_2(x)$, … $g_n(x)$. Если $h(x)$ — произведение всех функций, то $$ \begin{align} h(-x) & = f_1(x)\,f_2(x)\, \dots \, f_m(x)\,[-g_1(x)]\,[-g_2(x)]\, \dots \, [-g_n(x)] \\ & = f_1(x)\,f_2(x)\, \dots \, f_m(x)\,(-1)^n\,g_1(x)\,g_2(x), \dots \, g_n(x) \\ & = (-1)^n\,h(x)\,, \end{align} $$ откуда следует требуемое утверждение.

Ответ. Ошибочным является утверждение a). Оно станет верным, если потребовать, чтобы четности функций были одинаковыми.

На старт!

2.1 Можно число 2018 представить в виде разности квадратов целых чисел?

Если $2018=m^2-n^2$, то $$ 2018 = (m+n) (m-n) $$ Поскольку $(m+n)-(m-n)=2n$, числа $m+n$ и $m-n$ имеют одинаковую четность. Таким образом возможны два случая: либо $m+n$ и $m-n$ оба четны, тогда их произведение делится на 4, либо $m+n$ и $m-n$ оба нечетны, тогда их произведение нечетно. Между тем, число 2018 четно, но не делится на 4.
Ответ. Невозможно.

PS. а) Всякое нечетное число можно представить в виде разности квадратов. В самом деле представим нечетное число $a$ в виде произведения нечетных чисел $p$ и $q$, где $p\;\ge\;q\;>0$. Решая систему уравнений.
$$ \left\{\begin{matrix}{m+n=p \\ m-n=q}\end{matrix}\right.
$$ получаем $m=\frac{p+q}{2}$, $n=\frac{p-q}{2}$, где оба числа — целые и неотрицательные. Полагая $p=a$, $q=1$, получаем пару $m=\frac{a+1}{2}$, $n=\frac{a-1}{2}$, которая всегда существует, другие пары существуют, если $a$ — составное число, например $15=8^2-7^2=4^2-1^2$

б) Если число $a$ кратно 4, его можно представить в виде произведения четных чисел $p$ и $q$, что снова дает пару целых неотрицательных чисел $m=\frac{p+q}{2}$, $n=\frac{p-q}{2}$. В частности при $p=\frac{a}{2}$, $q=2$, получаем всегда существующую пару целых чисел $m=\frac{a}{4}+1$, $n=\frac{a}{4}-1$. Пример $4=2^2-0^2$, $8=3^2-1^2$, $12=4^2-2^2$ Если число $\frac{a}{4}$ составное, существуют другие пары, например: $24=7^2-5^2=5^2-1^2$.

2.2 Выписано 2018 последовательных чисел (не обязательно начальных). Каждый раз два произвольных числа заменяются их суммой, отчего количество чисел уменьшается на одно. Это продолжается до тех пор, пока останется одно число. Будет это число четным или нечетным? а) Можно определить четность результата, если вместо сумм использовать разности (число с бо́льшим индексом вычитается из числа с меньшим индексом)? б) А если использовать абсолютные величины разностей?

Рассмотрим сумму выписанных чисел $S = a_1\; +\; a_2\; +\; ... \;+\;a_{2018}$.

Замена чисел $a_i$ и $a_j$ ($i \ne j)$ на $a_i\,+\,a_j$ приводит к замене двух слагаемых их суммой, отчего общая сумма не меняется. Поэтому честность единственного числа, оставшегося после 2017 замен, совпадает с четностью суммы первоначальных чисел. Это четность можно определить благодаря тому, что независимо от выбора $a_1$ в последовательности всегда окажется 1009 четных членов и столько же нечетных. Сумма нечетна ввиду нечетного количества нечетных слагаемых.
Ответ. Число будет нечетным.

а) Если члены последовательности $a_i$ и $a_j$ ($i \ne j$) заменить разностью, $a_i-a_j$, сумма изменится на величину $(a_i-a_j)-(a_i+a_j)\,=\,-2a_j$, поэтому ее четность не изменится. Применяя рассуждения предыдущего абзаца получаем:
Ответ. Число будет нечетным.

b) Согласно определению абсолютной величины, $|a_i-a_j|= a_i-a_j$, если $a_i \geqslant a_j$, в противном случае $|a_i-a_j| = a_j-a_i$ . В первом случае сумма изменится на величину $-2a_j$, а во втором на $-2a_i$. В обоих случаях величина изменения четна, поэтому четность суммы не меняется.
Ответ. Число будет нечетным.

Примечание. При решении задачи применен метод инварианты. Суть метода состоит в нахождении величины (в данном случае четность суммы), которая не изменяется в результате проведения операции. В данном случае инварианта помогла определению четности. Как мы вскоре убедимся, инварианта может помочь в доказательстве невозможности достичь какого-либо результата.

2.3 Сверхточный прямолинейный робот может двигаться вперед или назад, но не в сторону. При тестировании робота заставляют двигаться сначала на 1см, потом на 2см и т.д, при этом направление движения каждый раз выбирается произвольно. Может ли робот после 2018 движений вернуться в исходное положение?

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

2.4 Произведение 10 целых чисел равно 1. Доказать, что их сумма не равна нулю.

Так как произведение отлично от нуля, все сомножители — ненулевые. Если бы при этом один из сомножителей по абсолютной величине превосходил 1 (т.е. $|a_i| \geqslant 2$), то абсолютная величина произведения была бы не меньше двух. Отсюда все сомножители равны $\pm 1$. Для того, чтобы их сумма была нулевой необходимо, чтобы количество положительных и отрицательных сомножителей совпадало и равнялось 5. С другой стороны, так как произведение положительно, количество отрицательных сомножителей должно быть четным. Получили противоречие.

2.5 Доказать, что $(2m+1)^{2^n}-1$ делится на $2^{n+2}$ ($n \geqslant 1$).

Докажем индукцией по $n$. Как было показано, $(2m+1)^2-1$ делится на 8, что дает базу индукции.

Пусть $(2m+1)^{2^k}-1$ делится на $2^{k+2}$ Тогда $$ \begin{array}{l} (2m+1)^{2^{k+1}}-1 = (2m+1)^{2^{k}\cdot2}-1\\ \qquad = ((2m+1)^{2^{k}})^2-1 \\ \qquad = ((2m+1)^{2^{k}}-1)((2m+1)^{2^{k}}+1) \end{array} $$

Первый сомножитель делится на $2^{k+2}$ по индукционному предположению, второй сомножитель четен, как сумма двух нечетных чисел. Поэтому произведение делится на $2^{k+3}$, что завершает индукционный переход.

2.6 Какими должны быть целые числа $p$ и $q$, чтобы для любого целого $x$ значение $f(x) = x^3+px+q$ было: а) четным? б) нечетным?

а) В частности $q=f(0)$ — четное число. Отсюда, сумма остальных членов $g(x)=x^3+px$ должна быть четной при любом $x$. Значение $g(x) = x(x^2+p)$ заведомо четно при четном $x$. Чтобы значение $q(x)$ было четным также при нечетном $x$, необходимо, чтобы в этом случае второй сомножитель $x^2+p$ был четен. В силу нечетности $x$ слагаемое $x^2$ нечетно, отсюда $p$ должно быть нечетным.

Легко проверить и обратное: если $p$ — нечетно, а $q$ — четно, то $f(x)$ — четно.

б) Этот случай аналогичен предыдущему. При этом $p$ и $q$ должны быть оба нечетными.

Заметим, что показатель степени 3 можно заменить бо́льшим натуральным числом.

Вторая скорость

3.1 Каждая вершина многоугольника раскрашена в один из двух цветов. Доказать, что количество сторон многоугольника с разноцветными вершинами четно.

Одному из цветов поставим в соответствие +1, другому -1, и каждой вершине присвоим число соответствующее ее цвету. Будем обозначать эти числа буквами $a_1, a_2\;...\;a_n$ Каждой сторон) поставим в соответствие произведение чисел в его вершинах. Легко видеть, что сторона имеет разноцветные вершины тогда и только тогда, когда соответствующее ей число равно -1. Пусть $P$ — произведение чисел всех сторон многоугольника. Так как каждая вершина принадлежит двум сторонам, она дважды участвует в произведении. Таким образом $P=(a_1a_2...a_k)^2$ и потому положительно. Следовательно количество отрицательных сомножителей четно, чем доказана четность количества сторон с разноцветными вершинами.

Примечание. Легко видеть, что данное рассуждение применимо не только к многоугольнику, но к любому графу, каждая вершина которого имеет четную степень. В этом обобщенном случае $P=a_1^{deg(a_1)}a_2^{deg(a_2)}\;...\;a_k^{deg(a_k)}$.

3.2 В вершинах куба расставлены числа $1$ и $–1$. В центре каждой грани записано произведение чисел, стоя́щих в вершинах этой грани. Может ли сумма всех чисел (в вершинах и на гранях вместе взятых) равняться нулю?

Эта задача решается аналогично предыдущей. В кубе 8 вершин и 6 граней. Пусть $V$ и $S$ — произведение всех чисел вершин и граней соответственно. Так как каждая вершина принадлежит трем граням, в произведении $S$ каждое число вершины участвует трижды, следовательно $S=V^3$. Если P — произведение всех 14 чисел (в вершинах и на гранях), то $P=VS=V^4$, следовательно положительно. Если при этом сумма равна нулю, количество положительных и отрицательных чисел должно совпадать и равняться 7, но в таком случае произведение всех чисел не может быть положительным. Противоречие.

3.3 Одиннадцать монет лежат решкой вверх. Каждый ход состоит в перевертывании любых 10 монет, причем количество ходов не ограничено. Можно при этом уложить все монеты орлом вверх? а) А если монет 10, и разрешается переворачивать по 9?

Монете с решкой вверх поставим в соответствие +1, монете с орлом вверх — число -1. При перевертывании 10 монет произведение чисел умножается на $(-1)^{10}$, потому не изменяется. Если все монеты лежат решкой вверх, произведение соответствующих равно 1, если все лежат орлом вверх, нечетное количество отрицательных сомножителей, дает в произведении -1. Это доказывает невозможность получить желаемую ситуацию. Еше один пример использования инварианты!

a)Если переворачивается 9 монет, то произведение раз меняет знак. Так как используется 10 монет, в исходной и конечной позиции произведение равно 1, поэтому общее количество операций должно быть четным, тогда как каждая монета должна переворачиваться нечетное количество раз, чтобы в конце казаться перевернутой относительно начальной позиции. Как вы думаете, существует решение?

п/п	Номера́ участвующих монет
1	1	2	3	4	5	6	7	8	9
2	2	3	4	5	6	7	8	9	10
3	3	4	5	6	7	8	9	10	1
4	4	5	6	7	8	9	10	1	2
5	5	6	7	8	9	10	1	2	3
6	6	7	8	9	10	1	2	3	4
7	7	8	9	10	1	2	3	4	5
8	8	9	10	1	2	3	4	5	6
9	9	10	1	2	3	4	5	6	7
10	10	1	2	3	4	5	6	7	8

3.4 Пусть $p_n$ — произведение первых n простых чисел. Доказать, что $p_n+1$ не является полным квадратом. À propos, может быть полным квадратом а) $p_n$? б)$p_n–1$?

Среди множителей $p_n$ содержится число 2, остальные множители нечетные. Таким образом, $p_n=2(2k+1)=4k+2$. Следовательно $p_n$ и $p_n+1$ дают остатки 2 и 3 при делении на 4 и не могут быть полными квадратами, так как полный квадрат при делении на 4 дает в остатке либо 0, либо 1.

a) Не может, как следует из вышеуказанного рассуждения.

б) $p_n–1$ дает остаток 1 при делении на 4, так что вышеуказанные рассуждения не пригодны. Более того, $p_1-1=1$ является полным квадратом. Поэтому положим $n>1$. Тогда среди множителей числа $p_n$ присутствует 3, так что $p_n-1=3x-1=3(x-1)+2$ и дает остаток 2 при делении на 3. Покажем, что для полного квадрата $k^2$ это невозможно. Действительно, если $k$ делится на 3, то $k^2$ делится на 3. В противном случае остаток равен 1 или 2, так что $k=3q \pm 1$. Отсюда $k^2=9q^2\pm 6q +1 = 3q(3q \pm 2)+1$ дает остаток 1 про делении на 3. Как видим, при делении $k^2$ на 3 возможен остаток 0 или 1, но не 2. Таким образом, $p_n–1$ является полным квадратом только при $n=1$.

3.5 Выписано 2018 последовательных чисел (не обязательно начальных). Каждая пара соседних чисел заменяется их суммой (получаем: $a_1+a_2,\;a_3+a_4$ и т.д.), если последнее число оказалось непарным, оно отбрасывается. Это повторяется до тех пор, пока останется одно число. Будет это число четным или нечетным? а) A если вместо сумм использовать разности? б) А если использовать абсолютные величины разностей?

Соседние (т.е. последовательные) числа имеют разную четность. Поэтому их сумма, разность или абсолютная величина разности нечетна. Следовательно после первой операции получим последовательность, состоящую только из нечетных чисел. В таком случае после второй и всех последующих операций получим последовательности целиком состоящие из четных чисел.
Ответ. Результат будет четным.

3.6 В каждой клетке квадратной таблицы 25×25 записано число +1 или -1. Показать, что сумма произведений чисел каждой строки, сложенная с суммой произведений чисел каждого столбца отлична от нуля.

Пусть $a_i$ — сумма произведений чисел $i$-й строки, $b_i$ — сумма произведений чисел $i$-го столбца. В сумме $$ S = a_1+a_2+\;...\;+a_{25}+b_1+b_2+\;...\;+b_{25} $$ присутствуют 50 слагаемых, каждое из которых равно ±1. Для того, чтобы такая сумма была нулевой, необходимо наличие одинакового количества положительных и отрицательных слагаемых. Следовательно, должно быть 25 положительных и 25 отрицательных слагаемых. Требуется доказать, что это невозможно.

Как это сделать?

3.7 Пусть $a_1$, $a_2$, … $a_7$ — целые числа, а $b_1$, $b_2$, … $b_7$ — те же числа, взятые в другом порядке. Доказать, что число $(a_1-b_1) (a_2-b_2) \dots (a_7-b_7)$ четно.

Олимпиада Англии, 1968г.

Поскольку последовательности $a_1$, $a_2$, … $a_7$ и $b_1$, $b_2$, … $b_7$ состоят из тех же чисел, $$ a_1 + a_2 + \dots + a_7 = b_1 + b_2 + \dots + b_7 $$

Полный ход!

4.1 Найти 8 простых чисел, сумма квадратов которых на 992 меньше, чем их учетверенное произведение.

Итак, требуется найти 8 простых чисел $p_1, p_2,\;...\;p_8$, таких что $$ p_1^2+p_2^2+...+p_8^2=4p_1p_2...p_8-992 $$ или $$ p_1^2+p_2^2+...+p_8^2=4(p_1p_2...p_8-248) $$

Произведение нечетных чисел нечетно, поэтому выражение в скобках (в правой части) также нечетно. Отсюда следует, что сумма квадратов $p_1^2+p_2^2+...+p_8^2$ делится на 4 но не делится на 8. С другой стороны, квадрат нечетного числа при делении на 8 дает в остатке 1. Если $p_i^2=8a_i+1$, то $p_1^2+p_2^2+...+p_8^2=8(a_1+a_2+...a_8)+8$. Таким образом левая часть делится на 8, в то время как правая часть на 8 не делится...

Все понятно! Мы забыли о том, что 2 — тоже простое число. Стало быть, среди $p_i$ должны присутствовать двойки!

Этой подсказки достаточно, что посмотреть на задачу свежим взглядом. Поэтому, советую подумать, прежде чем читать дальше.

Оценим количество $p_i$ отличных от двух. Такие числа обязаны быть нечетными. Заметим, что так как правая часть кратна 4, сумма квадратов всех чисел кратна 4. С другой стороны $2^2=4$, поэтому сумма квадратов всех двоек кратна 4. Таким образом, сумма квадратов нечетных чисел должна быть также кратна 4. Так как квадрат нечетного числа при делении на 4 дает в остатке 1, то сумма квадратов нечетных чисел при делении на 4 дает такой же остаток, как количество этих чисел. Таким образом количество нечетных чисел среди $\{p_i\}$ должно быть кратно 4, но меньше 8, так как мы знаем, что двойки должны присутствовать. Поэтому возможно 0 или 4 нечетных чисел, а следовательно 4 или 8 двоек. Рассмотрим каждый случай в отдельности.

Пусть имеется 4 двойки и 4 нечетных числа. Без ограничения общности можно считать, что $p_1,p_2,p_3,p_4$ — нечетные числа, а $p_5=p_6=p_7=p_8=2$. Тогда вышеуказанное равенство запишется в виде: $$ p_1^2+p_2^2+p_3^2+p_4^2+16=4 \cdot 16p_1p_2p_3p_4-992 $$ Или $$ p_1^2+p_2^2+p_3^2+p_4^2=16(4p_1p_2p_3p_4-63) $$

Что же дальше?

4.2 Доказать, что из любых $2^{n+1}-1$ целых чисел можно выбрать $2^n$ чисел, сумма которых делится на $2^n$.

Докажем индукцией по $n$.

При $n=1$ читаем: «Из 3х целых чисел можно выбрать 2 числа, сумма которых делится на 2». Это действительно так, поскольку что из трех целых чисел как минимум 2 имеют одинаковую четность, и следовательно их сумма четна.

Допустим, что утверждение справедливо для $n=k$, то есть для $2^{k+1}-1$ целых чисел.

Рассмотрим $2^{k+2}-1$ целых чисел и подсчитаем количество нечетных чисел среди них. Если количество нечетных чисел нечетно (следовательно ненулевое), удалим нечетное число, а при четном количестве удалим четное число. (В последнем случае количество четных чисел будет ненулевым, так как общее количество чисел нечетно). В любом случае после удаления получим $2^{k+2}-2 = 2(2^{k+1}-1)$ целых чисел, среди которых количество нечетных чисел четно.

Объединим полученные числа в $2^{k+1}-1$ пар $(p_i,q_i)$, $i=1,2\;...\;2^{k+1}-1$, так что в каждую пару попадают числа одинаковой четности. (Это возможно: так как количество нечетных чисел четно, и общее количество чисел четно, четных чисел также будет четное количество). При этом сумма чисел каждой из пар четна. Пусть $a_i$ – полусумма чисел $i$-й пары. Тогда $p_i+q_i=2a_i$ ($i=1,\;2\;...\;2^{k+1}-1$).

Индукционное предположение пока еще не у дела. Подумайте, как его использовать.

4.3 На доске написано несколько нулей, единиц и двоек. Разрешается стереть две неравные цифры и вписать вместо них цифру, отличную от стертых (вместо 0 и 1 — цифру 2, вместо 1 и 2 — 0, вместо 0 и 2 — 1). Докажите, что если в результате таких операций на доске окажется одно число, то оно не зависит от порядка, в котором производились стирания.

9-я Всесоюзная математическая олимпиада, 1971 год, 8-й класс. Здесь она дается в слегка расширенном варианте.

Пусть $a_k$, $b_k$ и $c_k$ — начальное количество нулей единиц и двоек соответственно после $k$-го вычеркивания ($a_0$, $b_0$ и $c_0$ — начальные количества). Заметим, что после каждого вычеркивания одна из этих цифр увеличивается на 1, другие две цифры уменьшаются на 1. Например, если 0 и 2 заменяем на 1, то $a_k=a_k-1$, $b_k=b_k+1$, $a_k=a_k-1$. При этом четность каждого числа меняется на противоположную.

Попробуйте продолжить самостоятельно, перед тем, как читать дальше.

4.4 Двое играют в такую игру. На стол кладется 25 спичек. Каждый берёт себе по очереди одну, две или три спички. Игра заканчивается, когда все спички разобраны. Побеждает тот, у кого в конце игры окажется четное количество спичек. Кто выигрывает при правильной игре – начинающий или его партнёр? а) А если для выигрыша требуется взять нечетное количество спичек?

Журнал «Квант» за 1970 год. (Задачник «Кванта», М8). К сожалению, предложенное автором решение (Квант №10, 1970, стр 38-42, т.е. 4 с половиной страницы журнала, характеризуемого предельной краткостью в описании решения!) настолько сложное, что предпочитаю дать собственное решение, которое хотя и не отличается общностью, все же дает ответ на все поставленные вопросы задачи. Просьба, внимательно проверить и сообщить, если я где-то напутал.

Если на столе лежит 1 спичка, то у меня нет выбора. Я обязан взять 1 спичку и выигрываю, если у меня до этого хода есть нечетное количество спичек. Наоборот, если на столе 2 спички, я всегда могу выиграть, взяв 2 или 1 спичку, в зависимости от того четно или нечетно количество уже набранных мной спичек. Случай с 3 спичками на столе аналогичен предыдущему: я беру 2 или 3 спички в зависимости от четности набранных спичек и выигрываю.

Случай с 4 спичками на столе уже интереснее. Я не могу взять 1 или 2 спички, так как это оставит моего соперника с тремя или двумя спичками на столе, а в этой ситуации, как было показано, он обязательно выиграет. Поэтому я обязан взять 3 спички и выигрываю, если у меня изначально было нечетное количество спичек.

Продолжим самостоятельно?

Пойдем дальше: 5 спичек на столе. Взять 2 или 3 спички — значит заведомо проиграть, следовательно приходится брать 1 спичку в надежде на выигрыш. Но выиграю ли я? Рассмотрим ситуацию внимательнее. На столе 5 спичек, а всего их нечетное количество (25 спичек, согласно условию задачи). Следовательно на руках четное количество спичек (в данном случае 20), поэтому количество спичек у меня и моего соперника имеет одинаковую четность. Если у меня четное количество спичек, то количество спичек соперника тоже четное. Поэтому после моего хода у соперника будет четное количество спичек с 4 спичками на столе и он проиграет, что мне и надо. Наоборот, если у меня нечетное количество спичек, то с нечетным количеством спичек при 4-х на столе соперник выиграет, а я проиграю. Итак, 5 спичек на столе дают выигрыш в случае четного количества набранных спичек.

Теперь, после того, как логика стала понятной, приведу таблицу, которая составлена следующим образом. Столбец І содержит количество спичек на столе. Столбец ІІ дает условие, в зависимости от четности набранных спичек, при котором игрок, делающий очередной ход, выигрывает. Например, слово «Чет» в строке 5 означает, что игрок, делающий ход, выигрывает, если у него есть четное количество спичек. Столбец III указывает количество спичек, которое игрок должен взять для выигрыша, имея четное количество спичек (прочерк, если выигрыш невозможен). Столбец IV указывает выигрышный ход в случае нечетного количества спичек (или прочерк).

Спичек на столе	Условие выигрыша	Ход ЧЕТ	Ход НЕЧЕТ
I	II	III	IV
1	Нечет	-	1
2	Всегда	2	1
3	Всегда	2	3
4	Нечет	-	3
5	Чет	1	-
6	Всегда	1	2
7	Всегда	3	2
8	Чет	3	-
9	Нечет	-	1
10	Всегда	2	1
11	Всегда	2	3
12	Нечет	-	3
. . .

Приведенная таблица справедлива для любого нечетного общего количества спичек, тогда как с четным количеством спичек игра теряет смысл, поскольку всегда будет оканчиваться вничью. (Почему?)

Настало время еще раз подумать.

Можно заметить, что 9-я строка повторяет 1-ю, 10-я строка повторяет 2-ю и т.д. Таким образом получаем цикл из строк 1-8, что дает следующую стратегию игры:

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

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

«Однако, пользоваться таблицей не подобает солидному игроку!» — возразил бы подписчик журнала «Квант» 1970 года. В XXI-м веке такие возражения вряд ли поступят, так как играют, как правило, online, где любая подсказка останется совершенно незамеченной.

Посмотрим, улыбается ли фортуна начинающему, если в начале игры на столе лежит $25$ спичек. Так как $25=8\times3+1$, следует выбрать строку 1. В этой строке стоит «Нечет», тогда как у начинающего 0 набранных спичек, то есть четное число. Увы, начинающий проигрывает! На самом деле, начинающий проигрывает лишь тогда, когда общее количество спичек равно $8n+1$, поскольку 1 — это единственная нечетная строка (кстати, почему рассматриваются только нечетные строки?), где стоит «Нечет».

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

1) Меняем местами содержимое столбцов III и IV.
2) В столбце II меняем «Чет» на «Нечет» и наоборот.

Вот, что получаем в результате:

Спичек на столе	Условие выигрыша	Ход ЧЕТ	Ход НЕЧЕТ
I	II	III	IV
1	Чет	1	-
2	Всегда	1	2
3	Всегда	3	2
4	Чет	3	-
5	Нечет	-	1
6	Всегда	2	1
7	Всегда	2	3
8	Нечет	-	3
. . .

В строке 1 стоит «Чет» (что, впрочем, и следовало ожидать), значит, начинающий выигрывает, взяв первым ходом одну спичку. Как видно из таблицы, начинающий проигрывает, если общее количество спичек равно $8n+5$.

4.5 Вершины 12-угольника занумерованы по порядку числами от 1 до 12 и в каждой из них положено по монете. При этом монета в вершине 1 расположена орлом вверх, а во всех остальных — решкой вверх. Каждый раз разрешается перевернуть одновременно монеты четырех идущих подряд вершин (например, вершин 3, 4, 5, 6 или вершин 11, 12, 1, 2). Доказать, что в результате таких операций невозможно расположить монету в вершине 2 орлом вверх, а во всех остальных — решкой вверх. a) А если вместо четырех вершин переворачивать другое количество, не превосходящее 12?

5-я Всесоюзная математическая олимпиада, 1971 год, 8-й класс. Здесь она дается в слегка расширенном варианте.

Каждой вершине $i$ поставим в соответствие число $k_i$, означающее количество ее переворотов, которое назовем кратностью (название неудачное, согласен, но все же короче, чем «счетчик перевертываний»).

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

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

Сравним кратности соседних вершин (например, вершин 4 и 5), одну из которых назовем левой (в нашем примере, вершина 4), а другую правой (вершина 5). Одна из четверок идущих подряд вершин содержит левую, но не содержит правую вершину (в нашем примере, четверка 1,2,3,4), назовем ее левой четверкой, другая четверка, наоборот, содержит правую, но не содержит левую вершину (четверка 5,6,7,8), назовем ее правой четверкой. Остальные четверки либо содержат обе вершины одновременно, либо не содержат ни одной из них, поэтому не влияют на разность кратностей.

"Think! Think! Think!" — как твердил, стуча пальцем по лбу, медвежонок Winnie the Pooh в диснеевской интерпретации. Вряд ли он осилил бы эту задачу, даже после данной подсказки, но вам почему бы не попробовать?!

Пусть $k_l$ - кратность левой вершины, $k_r$ - кратность правой вершины. Возможны 4 случая:

Участвующие четверки	$k_l$-$k_r$
Левая, но не правая	1
Правая, но не левая	-1
Левая и правая	0
Ни левая, ни правая	0

Мы видим, что абсолютная величина разности кратностей соседних вершин никогда не больше 1. Но если $|k_l-k_r|=1$, числа $k_l$ и $k_r$ имеют разную четность, а если четность одинакова, то непременно $|k_l-k_r|=0$, то есть $k_l=k_r$. Итак, если кратности соседних вершин имеют одинаковую четность, то они равны, а если разную четность, они отличаются на 1.

Согласно условию задачи, монеты в вершинах 1 и 2 изменили ориентацию, тогда как в остальных вершинах ориентация не изменилась, следовательно $k_l$ и $k_2$ - нечетны, а $k_3$, $k_4$, ... $k_12$ - четны.

Еще одна возможность подумать над решением!

Так как $k_3$ и $k_4$ — кратности соседних вершины одинаковой четности, то $k_3=k_4$, аналогично, $k_4=k_5$, и т.д. Окончательно получаем $k_3=k_4=...=k_12=k$, кроме того, $k_1=k_2=k \pm 1$. Суммируя все кратности получаем: $$ k_1+k_2+\;...\;+k_12=12k \pm 2 $$

С другой стороны, так как в каждой операции участвуют 4 монеты, сумма кратностей равна $4p$, где $p$ — количество операций. Таким образом: $$ 12k \pm 2 = 4p $$

Думаю, что дальше объяснять не надо. Правая часть делится на 4, тогда как левая часть (независимо от фактического знака $\pm$) дает остаток 2 при делении на 4. (Знак $\pm$ имеет значение только при делении на 12, когда $12k+2$ дает остаток 2, тогда как для $12k-2$ остаток равен 10.) Полученное противоречие доказывает утверждение задачи.

а) Пусть за одну операцию разрешается переворачивать $m$ соседних вершин. Тогда последнее равенство преобразуется к виду: $$ 12k \pm 2 = mp $$

Легко видеть, что при $m$, равном 3,4,6,8,9,12 равенство противоречиво: при $m$=8,9 левая часть не делится соответственно на 4 и 3 (а правая делится), для остальных из перечисленных значений $m$ левая часть не делится на $m$.

При $m=1$ мы конечно, переворачиваем монеты в вершинах 1 и 2 по очереди, при $m$=2, обе монеты переворачиваются за одну операцию.

При $m=11$ переворачиваем сначала все монеты, кроме 1-й, затем все монеты, кроме 2-й. При этом первая и вторая монеты перевернутся один раз и изменят ориентацию, а все остальные перевернутся два раза и вернутся к прежней ориентации.

Осталось рассмотреть случаи $m$=5,7 и 10. Во всех этих случаях ответ утвердительный. Решения даны следующими таблицами. Не буду утомлять рассуждениями о том, как я получил эти решения, поскольку с четностью это никак не связано 😉.

$m=5$. Операций - 10, переворотов 4 и 5.

п/п	Номера́ участвующих монет
1	9	10	11	12	1
2	10	11	12	1	2
3	11	12	1	2	3
4	12	1	2	3	4
5	1	2	3	4	5
6	2	3	4	5	6
7	4	5	6	7	8
8	5	6	7	8	9
9	6	7	8	9	10
10	7	8	9	10	11

$m=7$. Операций - 10, переворотов 6 и 5.

п/п	Номера́ участвующих монет
1	9	10	11	12	1	2	3
2	10	11	12	1	2	3	4
3	11	12	1	2	3	4	5
4	12	1	2	3	4	5	6
5	2	3	4	5	6	7	8
6	3	4	5	6	7	8	9
7	4	5	6	7	8	9	10
8	5	6	7	8	9	10	11
9	6	7	8	9	10	11	12
10	7	8	9	10	11	12	1

$m=10$. Операций - 5, переворотов 4 и 5.

п/п	Номера́ участвующих монет
1	5	6	7	8	9	10	11	12	1	2
2	7	8	9	10	11	12	1	2	3	4
3	9	10	11	12	1	2	3	4	5	6
4	11	12	1	2	3	4	5	6	7	8
5	1	2	3	4	5	6	7	8	9	10

То, что во всех случаях монеты 1 и 2 переворачиваются 5 раз — это чистая случайность, хотя...

Ответ. Цель осуществима при количестве одновременно переворачиваемых монет 1,2,5,7,10,11.

п/п	Номера́ участвующих монет
1	1	2	3	4	5	6	7	8	9
2	2	3	4	5	6	7	8	9	10
3	3	4	5	6	7	8	9	10	1
4	4	5	6	7	8	9	10	1	2
5	5	6	7	8	9	10	1	2	3
6	6	7	8	9	10	1	2	3	4
7	7	8	9	10	1	2	3	4	5
8	8	9	10	1	2	3	4	5	6
9	9	10	1	2	3	4	5	6	7
10	10	1	2	3	4	5	6	7	8

п/п	Номера́ участвующих монет
1	9	10	11	12	1
2	10	11	12	1	2
3	11	12	1	2	3
4	12	1	2	3	4
5	1	2	3	4	5
6	2	3	4	5	6
7	4	5	6	7	8
8	5	6	7	8	9
9	6	7	8	9	10
10	7	8	9	10	11

п/п	Номера́ участвующих монет
1	9	10	11	12	1	2	3
2	10	11	12	1	2	3	4
3	11	12	1	2	3	4	5
4	12	1	2	3	4	5	6
5	2	3	4	5	6	7	8
6	3	4	5	6	7	8	9
7	4	5	6	7	8	9	10
8	5	6	7	8	9	10	11
9	6	7	8	9	10	11	12
10	7	8	9	10	11	12	1

п/п	Номера́ участвующих монет
1	5	6	7	8	9	10	11	12	1	2
2	7	8	9	10	11	12	1	2	3	4
3	9	10	11	12	1	2	3	4	5	6
4	11	12	1	2	3	4	5	6	7	8
5	1	2	3	4	5	6	7	8	9	10

п/п	Номера́ участвующих монет
1	1	2	3	4	5	6	7	8	9
2	2	3	4	5	6	7	8	9	10
3	3	4	5	6	7	8	9	10	1
4	4	5	6	7	8	9	10	1	2
5	5	6	7	8	9	10	1	2	3
6	6	7	8	9	10	1	2	3	4
7	7	8	9	10	1	2	3	4	5
8	8	9	10	1	2	3	4	5	6
9	9	10	1	2	3	4	5	6	7
10	10	1	2	3	4	5	6	7	8

п/п	Номера́ участвующих монет
1	9	10	11	12	1
2	10	11	12	1	2
3	11	12	1	2	3
4	12	1	2	3	4
5	1	2	3	4	5
6	2	3	4	5	6
7	4	5	6	7	8
8	5	6	7	8	9
9	6	7	8	9	10
10	7	8	9	10	11

п/п	Номера́ участвующих монет
1	9	10	11	12	1	2	3
2	10	11	12	1	2	3	4
3	11	12	1	2	3	4	5
4	12	1	2	3	4	5	6
5	2	3	4	5	6	7	8
6	3	4	5	6	7	8	9
7	4	5	6	7	8	9	10
8	5	6	7	8	9	10	11
9	6	7	8	9	10	11	12
10	7	8	9	10	11	12	1

п/п	Номера́ участвующих монет
1	5	6	7	8	9	10	11	12	1	2
2	7	8	9	10	11	12	1	2	3	4
3	9	10	11	12	1	2	3	4	5	6
4	11	12	1	2	3	4	5	6	7	8
5	1	2	3	4	5	6	7	8	9	10

п/п	Номера́ участвующих монет
1	1	2	3	4	5	6	7	8	9
2	2	3	4	5	6	7	8	9	10
3	3	4	5	6	7	8	9	10	1
4	4	5	6	7	8	9	10	1	2
5	5	6	7	8	9	10	1	2	3
6	6	7	8	9	10	1	2	3	4
7	7	8	9	10	1	2	3	4	5
8	8	9	10	1	2	3	4	5	6
9	9	10	1	2	3	4	5	6	7
10	10	1	2	3	4	5	6	7	8

п/п	Номера́ участвующих монет
1	9	10	11	12	1
2	10	11	12	1	2
3	11	12	1	2	3
4	12	1	2	3	4
5	1	2	3	4	5
6	2	3	4	5	6
7	4	5	6	7	8
8	5	6	7	8	9
9	6	7	8	9	10
10	7	8	9	10	11

п/п	Номера́ участвующих монет
1	9	10	11	12	1	2	3
2	10	11	12	1	2	3	4
3	11	12	1	2	3	4	5
4	12	1	2	3	4	5	6
5	2	3	4	5	6	7	8
6	3	4	5	6	7	8	9
7	4	5	6	7	8	9	10
8	5	6	7	8	9	10	11
9	6	7	8	9	10	11	12
10	7	8	9	10	11	12	1

п/п	Номера́ участвующих монет
1	5	6	7	8	9	10	11	12	1	2
2	7	8	9	10	11	12	1	2	3	4
3	9	10	11	12	1	2	3	4	5	6
4	11	12	1	2	3	4	5	6	7	8
5	1	2	3	4	5	6	7	8	9	10