Привожу ответы на задачи, предложенные здесь.
Разминка
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, поэтому общее количество операций должно быть четным, тогда как каждая монета должна переворачиваться нечетное количество раз, чтобы в конце казаться перевернутой относительно начальной позиции. Как вы думаете, существует решение?
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$ должны присутствовать двойки!
Этой подсказки достаточно, что посмотреть на задачу свежим взглядом. Поэтому, советую подумать, прежде чем читать дальше.
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)$ целых чисел, среди которых количество нечетных чисел четно.
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 спички и выигрываю, если у меня изначально было нечетное количество спичек.
Продолжим самостоятельно?
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 в диснеевской интерпретации. Вряд ли он осилил бы эту задачу, даже после данной подсказки, но вам почему бы не попробовать?!
Комментариев нет:
Отправить комментарий