задачка - разбор решения
Jun. 1st, 2008 07:37 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaЧто ж, помучавшись еще пару дней, честно не заглядывая в комментарии, я не смог решить задачку, которую запостил в четверг:
Оказалось следующее. Это утверждение верно для любого 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.
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.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2008-06-01 08:15 am (UTC)[a1...aN], [a2...aN+1] ,...
то их будет ровно N а это уже задача которую вы описали выше с некоторой модификацией, что надо рассматривать пересечения и разности множеств. + очевидно что в худшем случае не должно быть среди этих n сумм суммы, делящейся на N, ну а дальше просто
Оффтоп
Date: 2008-06-01 08:20 am (UTC)Re: Оффтоп
Date: 2008-06-01 08:23 am (UTC)no subject
Date: 2008-06-01 08:24 am (UTC)no subject
Date: 2008-06-01 10:11 am (UTC)Тоже мораль: всегда искать обобщения.
no subject
Date: 2008-06-01 10:51 am (UTC)Единственное, я не понял вот этот момент:
Как мы найдем подмножество bi, в сумме дающих N-S? Во-первых, если все bi равны друг другу, то можно просто взять первые N-S из них, и сумма будет делится.
Например, N = 7, S = 6, bi = 2. Тогда bi*(N-S) = bi*1 = 2. Но нам нужно bi*4 = 8 = 1 (mod 7).
Здесь, кажется, снова надо использовать факт, что bi и N взаимнопростые. Тогда все числа (bi*k mod N), где k = [1 .. N-1], разные и отличны от нуля. То есть среди них найдется (N-S).
no subject
Date: 2008-06-01 02:13 pm (UTC)no subject
Date: 2008-06-01 02:49 pm (UTC)no subject
Date: 2008-06-01 06:35 pm (UTC)no subject
Date: 2008-06-02 11:07 am (UTC)no subject
Date: 2008-06-03 03:49 am (UTC)no subject
Date: 2008-06-03 04:23 am (UTC)no subject
Date: 2008-07-05 10:55 pm (UTC)no subject
Date: 2008-07-05 11:52 pm (UTC)no subject
Date: 2008-07-06 06:11 am (UTC)no subject
Date: 2008-07-06 08:03 am (UTC)Всё в порядке?
no subject
Date: 2008-07-06 12:30 pm (UTC)no subject
Date: 2008-07-06 12:36 pm (UTC)no subject
Date: 2008-07-06 12:36 pm (UTC)no subject
Date: 2008-07-13 05:10 pm (UTC)no subject
Date: 2008-07-13 06:08 pm (UTC)no subject
Date: 2008-07-14 02:15 pm (UTC)