а) Докажите, что из любых двадцати пяти различных натуральных чисел всегда можно выбрать девять различных чисел так, что их сумма будет делиться на девять.

б) Можно ли выписать 24 различных натуральных числа, чтобы среди них не нашлось 9 различных чисел, сумма которых делится на 9?

задан 17 Сен '18 21:15

я конечно могу ошибаться, но по-моему такой вопрос уже когда-то задавали...

(17 Сен '18 22:48) all_exist
1

@all_exist: да, похожий вопрос (для числа 4 вместо 9) звучал здесь. Только оценки 25 и 24 сильно завышены. Нам самом деле, для 16 чисел есть простой контрпример, а для 17 и более чисел утверждение верно.

(17 Сен '18 23:13) falcao
10|600 символов нужно символов осталось
1

Это варианты хорошо известной задачи. Но, поскольку здесь сильно завышена оценка, я напишу ответ.

Есть такая теорема Эрдёша - Гинзбурга - Зива (1961). Для любых 2n-1 целых чисел можно найти n из них так, что их сумма делится на n. Для 2n-2 чисел легко строится контрпример из n-1 нуля и n-1 единицы. Поэтому для делимости на 9 теорема будет верна уже для 17 чисел, и тем более для 24 и 25.

Рассмотрим сначала случай n=3. Такая задача, про 2n-1=5 чисел, встречается в ряде олимпиадных сборников. Числа заменяем на их остатки от деления на 3. Получаются значения 0, 1, 2. Если какое-то значение встречается трижды, то сумма трёх чисел делится на 3. То же, если число каждого из трёх типов встречается. В противном случае типов чисел не более двух, и чисел каждого типа не более двух -- тогда чисел не больше 4 -- противоречие.

Далее следует несложная лемма: если теорема верна для значения m и для значения n, то она верна для значения mn. Тогда при m=n=3 мы получаем утверждение теоремы для 2mn-1=17 чисел. Доказательство здесь такое же, как по ссылке, где m=n=2. А именно, сначала мы из 2mn-1 чисел выбираем несколько раз по m штук, сумма которых делится на m. Последний раз это удастся сделать, когда остаётся 2m-1 число. Это значит, что m чисел мы выбрали уже ((2mn-1)-(2m-1))/m=2n-2 раза. Значит, мы всего 2n-1 раз выберем наборы из m чисел.

В каждом наборе рассмотрим среднее арифметическое -- оно целое. Имеем набор из 2n-1 средних. В нём выбираем n штук, чтобы сумма делилась на n. Тогда во всех выбранных в итоге наборах имеется mn чисел, а их сумма делится на mn.

Самый трудный случай -- это n=p, где p простое. В силу леммы, всё сводится именно к нему. Там имеется много разных доказательств, часть из которых обсуждается в этой статье. Там есть как достаточно элементарные рассуждения (на основе леммы Коши - Дэвенпорта), так и доказательства с использованием алгебраических понятий и конструкций. Среди них я бы выделил то, которое основано на теореме Олсона.

ссылка

отвечен 17 Сен '18 23:53

@falcao, большое спасибо!

(18 Сен '18 0:45) Казвертеночка

@falcao, странно, что теорема Эрдёша - Гинзбурга - Зива не нашлась в Википедии.

(18 Сен '18 1:03) Казвертеночка
1

@Казвертеночка: в Вики-статьях она упоминается в контексте разных обобщений. Например, здесь.

(18 Сен '18 1:37) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,405
×985
×275

задан
17 Сен '18 21:15

показан
609 раз

обновлен
18 Сен '18 1:37

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru