Об одной забытой задаче

45

МАТЕМАТИЧЕСКИЙ КРУЖОК

Об одной забытой задаче

А.ТОЛПЫГО

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

С.Бобров. Волшебный двурог

Для начала сформулируем две задачи. Задача A. Докажите, что из любых n целых чисел можно выбрать несколько, сумма которых делится на n. Задача B. Докажите, что из любых (2n – 1) целых чисел можно выбрать n чисел, сумма которых делится на n. Задача А широко известна и решается с помощью принципа Дирихле («если (n + 1) кроликов требуется рассадить по n клеткам, то хотя бы в одной клетке будет не менее двух кроликов»). А именно, надо рассмотреть числа $S_{0} = 0, S_{1} = a_{1}, S_{2} = a_{1} + a_{2}, S_{3} = a_{1} + a_{2} + a_{3}$, …, $S_{n} = a_{1} +^{…} + a_{n}$. Роль «клеток», по которым нужно рассадить этих «кроликов», играют остатки от деления числа на n. По принципу Дирихле, какие-то два из «кроликов» попадают в одну «клетку», т.е. дают одинаковый остаток от деления на n. Поэтому их разность делится на n, а это и есть то, что требуется. Напротив, задача В (когда-то она была опубликована в журнале «Квант» за 1970 год под номером М45) сейчас незаслуженно забыта. А между тем тут имеется не только замечательный математический факт, но и ряд красивых идей вокруг ее решения. Правда, как будет видно дальше, некоторые из них ведут к доказательству, другие нет. Тем не менее, полезны и те, и другие: если некоторые из них недостаточны для решения этой задачи – пригодятся в другой раз. Ниже будет обсуждаться именно задача В. Но предварительно рассмотрим еще пару задач аналогичного типа.

1. Еще две задачи

Задача C. Даны N – 1 натуральных чисел $a_{1},^{…}, a_{N} -_{1}$. Все они больше нуля и меньше N. Известно, что если выбрано любое k, 0 < k < N, и любые k чисел из этого набора, то их сумма не делится на N. Докажите, что все числа в наборе равны между собой. Задача D. Дано 100 чисел, каждое из которых больше 0 и меньше 94. Докажите, что из них можно выбрать несколько чисел, сумма которых при делении на 101 дает остаток 95. Решение задачи C. Предположим, что $a_{1} \ne a_{2}$. Рассмотрим суммы $S_{0} = a_{1}, S_{1} = a_{2}, S_{2} = a_{1} + a_{2}, S_{3} = a_{1} + a_{2} + a_{3},...$

…, $S_{N} -_{1} = a_{1} + a_{2} +$ … $+ a_{N} -_{1}$. (Первые две суммы равны первым двум членам, остальные – суммы от первого до соответствующего). По предположению, ни одна из этих сумм не дает остаток 0 при делении на N. Следовательно, две из них дают одинаковый остаток, причем это не первая и вторая. Но тогда разность двух соответствующих сумм делится на N, а это противоречит условию. Решение задачи D. Сразу признаемся, что мы ограничились числом 101, отчасти чтобы облегчить формулировку, а отчасти – чтобы немного «замутить воду» и слегка прикрыть идею. На самом же деле факт верен в достаточно общей ситуации. А именно, заменим число 101 на любое простое p, а число 95 – на любое число между нулем и p и докажем, что из (p – 1) чисел, дающих ненулевой остаток от деления на p, можно составить сумму, которая дает любой наперед заданный ненулевой остаток при делении на p. Упорядочим данные числа произвольным образом. Выберем любое $k, 0 \le k \le ( p - 1 )$, и возьмем первые k наших чисел. Составим из них всевозможные суммы (одно число или ни одного – тоже сумма; сумма пустого множества чисел предполагается равной 0) и запишем все различные получившиеся остатки от деления этих сумм на p. В частности, на первом шаге (если k = 0) есть единственная сумма, и она равна 0. При произвольном k получились некоторые числа $M_{1}$, … $, M_{n}$. Если среди них уже есть все возможные остатки, то доказывать нечего. Пусть это не так. Добавим к уже выбранным (k + 1)-е число (пусть оно равно r) и опять выпишем все суммы и все остатки. В результате получатся, во-первых, числа $M_{1}$, … $, M_{n}$ (ведь последнее число можно и не брать), а во-вторых, остатки от деления чисел $M_{1} + r$, … $, M_{n} + r$ на p. Теперь мы утверждаем, что во второй группе есть хотя бы одно число, не встречающееся в первой. В самом деле, допустим противное. Тогда получается, что если остаток N совпадает с одним из $M_{i}$, то и остаток N + r также совпадает с каким-то другим числом из множества ${ M_{i} }$. Но тогда также и остаток N + 2r = (N + r) + r также совпадает с какимто другим числом из множества ${ M_{i} }$, то же верно для N + + 3r = (N + 2r) + r, и так далее. Отсюда легко следует, что среди ${ M_{i} }$ уже встречаются все возможные остатки от деления на p, а мы предположили, что это не так. Таким образом, до тех пор, пока выписаны не все остатки, число различных чисел увеличивается на каждом шаге. Поскольку число шагов равно p, то не позднее чем на последнем шаге число разных остатков будет не меньше чем p, что и требуется. Поскольку нулевая сумма возникла на первом шаге (там, где чисел не было вовсе), то нет гарантии, что можно получить сумму с остатком 0. И действительно, если взять все числа равными между собой, то остаток 0 не получается (и это, согласно задаче С, единственный случай, когда этот остаток не получается). Все остальные суммы получаются так или иначе.

2. Задача В. Составные числа

Вернемся теперь к задаче В. Для удобства обозначим ее утверждение как BC ( n ) («выбор суммы»); таким образом, запись BC ( 21 ) есть сокращение утверждения «верно, что из любых 41 целых чисел можно выбрать 21, сумма которых делится на 21».

46

КВАНТ 2010/№2

Заметим, прежде всего, что оценку нельзя улучшить. В самом деле, если взять только 2p – 2 числа, то легко строится контрпример: достаточно взять p – 1 нулей и p – 1 единиц. Можно также нули и единицы заменить другими числами (если n простое – любыми двумя различными, случай составного n мы предоставляем разобрать читателям). Для краткости ниже мы будем называть «набором» совокупность данных нам (2p – 1) чисел, а «группой» – его подмножество из нескольких чисел, сумма которых делится на p. Требуется доказать, что существует группа из p элементов. Полное решение задачи (иначе говоря, утверждение BC ( n ) для любого n) мы приведем в конце статьи, начнем же с доказательства несложного утверждения: если BC ( p ) и BC ( q ), то BC ( pq ). Доказательство. Пусть n = pq, и дано 2n – 1 чисел ${ a_{k} }$; согласно BC ( p ), из них можно выбрать группу из p чисел, сумма которых делится на p. Отложим эту группу в сторону и рассмотрим оставшиеся числа. Поскольку остались неиспользованными более чем (2p – 1) чисел, из них можно выбрать еще одну группу, сумма которых также делится на p. Действуя так и дальше, мы получим много групп по p чисел, сумма каждой из которых делится на p; легко убедиться, что можно получить (2q – 1) групп. Пусть $S_{1} = p \cdot r_{1}, S_{2} = p \cdot r_{2}$, … $S_{2} q_{-} 1 = p \cdot r_{2} q_{-} 1$ – их суммы. Поскольку ${ r_{k} }$ – целые числа, из них, согласно BC ( q ), можно выбрать q чисел, сумма которых делится на q. Тогда и сумма соответствующих ${ S_{k} }$ делится на pq, причем в этой сумме ровно столько чисел ${ a_{k} }$, сколько требуется. Существенно заметить, что в этом доказательстве неважно, будут ли числа p и q взаимно просты или нет. Поэтому достаточно доказать BC ( n ) для случая, когда n = p – простое число. Только этим случаем мы и будем заниматься в дальнейшем. Докажем теперь утверждение BC ( p ) для некоторых значений p. Заметим, что хотя мы будем излагать доказательство для конкретного числа, однако факты будут верны для разных чисел. Поэтому читателю рекомендуется всякий раз прикидывать: проходит ли данное рассуждение только для данного p или его можно обобщить.

3. Доказательство для p = 7

3.1. Повышение кратности нуля. Если среди данных чисел встречаются все 7 возможных остатков, то доказывать нечего, так как 0 + 1 + 2 + … + 6 делится на 7. Поэтому можно считать, что среди наших 13 чисел встречается не более 6 разных остатков. Но тогда какой-то из них встречается не менее трех раз. Количество раз, которое тот или иной остаток встречается в нашем наборе, мы назовем его кратностью. Будем считать, что кратность три (или более) имеет остаток 0. (В п. 3.3 мы покажем, как общий случай свести к этому). Если кратность нуля не меньше 7, то доказывать опятьтаки нечего. В противном случае есть не менее 7 ненулевых остатков, и, согласно задаче А, из них можно выбрать несколько (скажем, k), сумма которых делится на 7. Правда, нет оснований думать, что k = 7. Пусть k < 7; рассмотрим два случая. а) Если k > 3, то мы можем взять эти числа и добавить к ним несколько нулей (от одного до трех); получится группа из 7 чисел, и утверждение доказано. б) Пусть теперь $k \le 3$. Здесь надо поступить до-другому. Заменим данный набор новым. В нем k чисел, сумма которых

равна нулю, все заменены нулями, как в таблице:

Исходный набор

0 0 0 2 2 3 1 …

Измененный набор

0 0 0 0 0 0 1 …

(Поскольку 2 + 2 + 3 делится на 7, мы заменили эти числа нулями, а остальные оставили без изменения.) Допустим, что для нового набора утверждение задачи проверено: в нем есть группа из 7 чисел, сумма которых делится на 7. Тогда то же верно и для старого набора. В самом деле, пусть в этой группе есть несколько нулей (скажем, r нулей, $r \ge 0 ).$ Если $r \le 3$, то мы берем те же числа из старого набора (ведь там есть три нуля); если же r > 3, то мы можем взять вместо трех нулей три числа старого набора, замененных нулями (сумма от этого не изменится), а прочие числа – те же, что в новом наборе. Итак, мы свели дело к новому набору, где нулей больше, чем было (назовем это так: «прием повышения кратности нуля»). Дальше уже понятно: либо у нас уже набралось 7 нулей, либо можно повторить то же рассуждение. Мы либо получим нужный набор сразу, либо опять увеличим число нулей, и так далее. Впрочем, для семи ясно, что дальше второго шага двигаться не придется. Можно ли применить такое же рассуждение для произвольного p? Ответ понятен: можно, но только в том случае, если нулей достаточно много: не менее чем (p – 1)/2. Для больших p мы, конечно, на это рассчитывать не можем, так что придется искать другие пути. Тем не менее, «прием повышения кратности» нам пригодится и дальше; только там одного его недостаточно. Пока же закончим доказательство для случая p = 7. 3.2. Индукция? Очевидно, приведенное в п. 3.1 рассуждение естественнее было бы строить методом индукции. Что же принять за ее параметр? Удобнее всего считать n (параметр индукции) равным (p + 1 – k), где k – кратность нуля (или того остатка, который встречается чаще всего): «если $n \le 1$, то один из остатков встречается не менее p раз, и утверждение очевидно; поэтому если удалось доказать, что наивысшую кратность можно увеличить (как мы делали в п. 3.1), то все доказано». Тем не менее применять индукцию нам неудобно, и вот почему. Для произвольного p индукция, к сожалению, не проходит: если бы удалось доказать, что наивысшую кратность можно увеличить, все было бы в порядке, но доказать этого мы не можем. А в случае p = 7 применение индукции вполне корректно, но… было бы «стрельбой из пушек по воробьям»: какая же индукция, если все заканчивается максимум за два шага? 3.3. Сведение общего случая к частному: транзитивность. Наше рассуждение из п. 3.1. предполагало, что наивысшую кратность имеет остаток 0. Пусть теперь чаще всего встречается, например, остаток 2. Тогда вычтем 2 из всех 13-ти данных чисел; теперь чаще всего встречается 0. При этом смысл нашей задачи не изменился: если какая-то группа из 7 чисел имела сумму, делящуюся на 7, то послевычитания двоек из суммы вычтено 14, т.е. она по-прежнему делится на 7. Таким образом, предположение, что наивысшую кратность имеет именно такой-то остаток (нам было удобно считать, что это – остаток 0), никак не нарушает общности рассуждения: вычитая из всех данных чисел одно и то же, мы