June 1st, 2008

moose, transparent

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

Что ж, помучавшись еще пару дней, честно не заглядывая в комментарии, я не смог решить задачку, которую запостил в четверг:
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-го года (спасибо за ссылку!).

Collapse )