Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

задачка - разбор решения

Что ж, помучавшись еще пару дней, честно не заглядывая в комментарии, я не смог решить задачку, которую запостил в четверг:
N - степень двойки (возможно, это условие лишнее, не уверен). Даны 2N-1 целых чисел. Доказать, что можно выбрать ровно N из них так, что сумма выбранных делится на N.
— и заглянул в комментарии, где меня ожидало несколько решений и полезных ссылок (спасибо!).

Оказалось следующее. Это утверждение верно для любого N, и доказано было в 61-м году Эрдешем, Гинзбургом и Зивом (поэтому ее называют теоремой EGZ). Это доказательство не то чтобы очень легкое, хотя и элементарное. Но для частного случая, когда N степень двойки, есть гораздо более простое доказательство по индукции (даже два разных), до которого я, возможно, дошел бы своим умом, если бы внимательно отнесся к этому условию. А я его почти полностью игнорировал, потому что "чувствовал", что утверждение верно для любого N, и пытался его доказать для любого N. Кроме того, меня зациклило на использовании принципа Дирихле, с помощью которого тривиально решается похожая, но совсем другая задача (дано N чисел, доказать, что из них можно отобрать сколько-то, неважно сколько, в сумме делящихся на N). Задача про 2N-1 чисел сводится к этой, более простой, если N-1 из чисел - нули (по модулю N); я все время пытался свести общую задачу как-нибудь к этому простому случаю, но у меня ничего не вышло.

Уроки на будущее:
1) более тщательно следить за условием, стараться использовать все данные факты;
2) если нет ничего очевидного, попробуй индукцию; если индукция не проходит, попробуй другую индукцию;
3) не зацикливаться на одном подходе, если не выходит каменный цветок - даже если кажется очевидным, что все должно идти через него;
4) не тупить.

Далее следует разбор двух решений для N - степени двойки, и полное доказательство для любого N, пересказанное своими словами из статьи 61-го года (спасибо за ссылку!).



1. Если N - степень двойки. Случай N=2 тривиален: из трех чисел всегда можно найти два, сумма которых четна. Теперь докажем по индукции для всех N степеней двойки. Шаг индукции: если можно выбрать N чисел, в сумме делящихся на N, из 2N-1, то можно выбрать 2N чисел, в сумме делящихся на 2N, из 4N-1.

Этот шаг можно доказать двумя разными способами:

1a. У нас есть 4N-1 чисел, возьмем из них две группы по 2N-1, и в каждой выберем N чисел, делящихся в сумме на N: пусть их суммы равны xN и yN. Если x+y четное число, то сумма отобранных 2N чисел будет делится на 2N, и это то, что надо; но, может быть, x+y нечетно. Однако у нас в запасе есть еще 2N-1 чисел (4N-1 первоначальных минус 2N только что отобранных): из них отберем еще N чисел с тем же свойством, с суммой zN. Среди чисел x,y,z есть два, сумма которых четна - например, y и z; тогда те N чисел, сумма которых yN, плюс те, сумма которых zN, вместе дадут 2N чисел, сумма которых делится на 2N, что и требовалось доказать. Суть этого решения в том, что нужно увидеть, что мы можем использовать "отброски" из двух первых групп, и эти числа заново собрать в новую группу, из которой отобрать еще N.

1b. Соберем все четные числа в пары (в каждой паре - два четных числа), и нечетные тоже в пары; поскольку всего чисел 4N-1 (нечетное число), у нас в итоге останется либо одно непарное четное, либо одно непарное нечетное, про это лишнее число забудем. Всего пар (четных и нечетных) будет 2N-1, чисел в них 4N-2. Для каждой пары чисел x и y, положим в новый набор чисел число (x+y)/2 (оно целое, потому что x+y четное - и для четной пары, и для нечетной). Всего в новом наборе 2N-1 чисел, поэтому из них можно выбрать N чисел вида (x+y)/2, в сумме делящихся на N; это значит, что сумма этих N пар (x+y) в сумме делится на 2N; эти N пар и есть искомые 2N чисел.

Теперь доказательство для любого N, по Эрдешу-Гинзбургу-Зиву. Оно состоит из двух частей: сначала для любого простого N, потом доказывается, что если верно для N=x и N=y, то верно для N=xy, и отсюда следует для любого N.

1. N простое число, N > 2.

У нас есть 2N-1 чисел. Рассмотрим их всех по модулю N (т.е. они от 0 до N-1) и расположим в порядке возрастания:

a1 <= a2 <= ... a2N-1 < N

Для каждого ai+1 нас особенно интересует число ai+N, т.е. находящееся "через N-1 шагов" по последовательности. Поскольку между ai+1 и ai+N, включая их самих, есть ровно N чисел, можно предположить, что ai+1 строго меньше ai+N (если равно, просто возьмем эти N равных чисел, и все, готово).
Поэтому bi = ai+N - ai+1 больше 0. Чисел вида bi существует N-1 штук, от

b1 = aN+1 - a2 до bN-1 = a2N-1 - aN.

Пусть сумма всех чисел a1+....+aN (первые N чисел) равна S по модулю N. Можно предположить, что S не равно 0, потому что иначе просто берем первые N чисел и все. Тогда N-S - число от 1 до N-1. Предположим, что нам удалось найти какое-то подмножество чисел bi, в сумме дающее N-S по модулю N. Тогда наше доказательство окончено: ведь добавляя число bi к сумме a1+...+aN мы просто заменяем ai+1 на ai+N, так что все равно остается N слагаемых из исходного набора; а их общая сумма получается S + N-S, т.е. 0 по модулю N.

Как мы найдем подмножество bi, в сумме дающих N-S? Во-первых, если все bi равны друг другу, то (учитывая, что N простое) последовательные суммы bi с самим собой пробегают все остатки по модулю N, в том числе N-S. Если же они не все равны друг другу, то нам нужна лемма:

Лемма. Если есть числа b1, b2, ... bs, взаимно простые с N, и s < N, и b1 не равно b2 по модулю N, то среди сумм всех возможных подмножеств этих чисел есть как минимум s+1 разное число по модулю N.

Эта лемма утверждает, что суммы разных наборов чисел bi не могут быть слишком повторяющимися. Если применить эту лемму к s = N-1 (внимание, тут используется тот факт, что N - простое: мы знаем, что наши bi не равны 0, и из этого и того, что N простое, следует, что они взаимно просты с N, т.е. удовлетворяют условию леммы) то выйдет, что среди всех возможных сумм подмножеств чисел bi есть s+1 = N разных чисел по модулю N - т.е. вообще все возможные, включая и искомое N-S.

Доказательство леммы. Лемма доказывается индукцией по s, от s=2 до s=N-1. В случае s=2 требуется доказать, что числа b1, b2, b1+b2 все разные по модулю N; это следует из того, что b1 не равно b2, и они взаимно просты с N.

В шаге индукции (s от 2 до N-2) мы составили все суммы подмножеств чисел от b1 до bs и получили не меньше s+1 разных чисел; теперь нам позволяется еще добавить bs+1 в эти суммы и мы хотим получить не меньше s+2 разных чисел. s+1 разных сумм у нас уже есть, потому что новое число можно просто не добавлять; вопрос только в том, приведет ли добавка bs+1 к одной из уже существующих сумм к какой-то новой до сих пор невиданной сумме. То, что приведет, следует из того условия, что bs+1 взаимно простое с N. Действительно, обозначим имеющиеся s+1 сумм через c1... cs+1; если бы добавление bs+1 к любой из них давало всего лишь другую сумму из набора (по модулю N), то добавляя bs+1 снова и снова и снова, мы бы в конце концов получили замкнутый круг ci + bs+1 + ... (K раз) + bs+1 = ci; но тогда K*bs+1 делится на N. Дано, что bs+1 взаимно простое с N, из чего следует, что длина цикла K делится на N, но это противоречит тому, что у нас пока есть только s+1 < N разных сумм.

Поэтому лемма верна, и мы можем подобрать такие b_i, что в сумме они "нейтрализуют" по модулю N сумму первых a1...aN, и тогда сумма их всех вместе даст N исходных слагаемых с суммой, которая будет делится на N.


2. N=x и N=y верно, докажем N=x*y.

Это похоже на первое из двух решений для степеней двойки. У нас есть 2xy-1 чисел. Повторяем следующую операцию: берем любые 2x-1 из них, отбираем x делящихся в сумме на x (используя решение для N=x), остальные возвращаем в общую кучу. Мы сможем это проделать 2y-1 раз, получив 2y-1 наборов по x чисел, сумма каждого из которых делится на x - например, равна ci*x. Из этих 2y-1 чисел ci мы теперь выбираем y таких, что их сумма делится на y (используя решение для N=y). Всего мы выбрали x*y чисел, организовав их в y наборов, так что сумма каждого набора равна ci*x, а сумма всех отобранных ci делится на y, так что общая сумма делится на x*y, и это доказывает N=x*y.

Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 21 comments