Из любых $%n$% целых чисел можно найти 4, сумма которых делится на 4.

Найти наименьшее такое $%n$%.

задан 21 Авг '18 10:23

10|600 символов нужно символов осталось
1

По-моему, это известная задача -- для случая делимости на какое угодно число m. Ответом будет 2m-1.

Если взять 6 чисел 0, 0, 0, 1, 1, 1, то четыре подходящих числа не выбрать. Пусть имеется 7 чисел. Среди трёх чисел есть два числа одной чётности. Выбираем такие числа a, b из семи, остаётся пять. Из них выбираем c, d. Остаётся три числа, из них берём e, f. Далее рассматриваем три полусуммы (a+b)/2, (c+d)/2, (e+f)/2. Выбираем из них две суммы одной чётности. Без ограничения общности, пусть это первые две. Тогда a+b+c+d делится на 4.

ссылка

отвечен 21 Авг '18 10:34

@falcao, большое спасибо! А почему в общем случае ответ будет $%2m-1$%?

(21 Авг '18 10:35) Казвертеночка
1

@Казвертеночка: это знаменитая теорема Эрдёша – Гинзбурга – Зива (1961). ТоЮ что 2m-2 чисел не хватает, очевидно. Положительная часть основана на лемме о том, что если факт верен для делимости на m и на n, то он верен для mn. Тогда всё сводится к случаю простого p. Для 2p-1 числа есть масса красивых доказательств, основанных на совсем разных идеях. Про это дело я встречал много хороших популярных статей. Например, у Алона была интересная заметка -- можно поискать в Сети (она на инглише).

(21 Авг '18 10:44) falcao

@falcao, и снова спасибо! Можно и на инглише, и на арабише, и на дойче :) Ну и на иврите, сабо самой.

(21 Авг '18 10:55) Казвертеночка
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,401
×253
×209
×144
×102

задан
21 Авг '18 10:23

показан
357 раз

обновлен
21 Авг '18 10:55

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

по почте:

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

по RSS:

Ответы

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

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