Делимость на 9

[Ktina]

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

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

[wrest]

Ktina
a) Сортируем числа по возрастанию.
Берем первые пять.
Среди них находим три, сумма которых делится на три. Это всегда можно сделать: выпишем остатки от деления на три. Если какого-то остатка три или больше, берем три этого остатка. Если каждого остатка меньше трех, значит каждого минимум по одному: тогда берем по одному каждого.
Откладываем эти три числа в сторону. Два невыбранных числа возвращаем в кучу.
Опять сортируем, берем первые пять из оставшихся, из них выбираем вторую тройку и откладываем в сторону, два числа возвращаем в кучу.
Таким образом откладываем в сторону пять троек, сумма каждой тройки делится на три. Для этого нам понадобилось $3\cdot 5+2= 17$ (а не $25$) разных чисел. Теперь из пяти троек выбираем три по этому же алгоритму (делим сумму каждой тройки на три и из получившихся пяти чисел выбираем три, сумма которых делится на три , а две тройки чисел возвращаем в кучу. Отложенные $9$ чисел -- искомые.
б) Нет: из любых $17$ можно выбрать $9$ сумма которых будет делиться на $9$.
Да, похоже на то, что или все исходные числа различаются или какие-то повторяются -- все равно. А, и сортировать по возрстанию в начале не надо. Просто берем любые пять и погнали, т.к. все равно нас только остатки интересуют...

[Ktina]

wrest
Большое спасибо!

[Dmitriy40]

25 чисел в условии требовалось если не возвращать по два числа обратно, тогда из пяти пятёрок чисел выбираем пять троек, из которых три тройки, в сумме делящиеся на 9. А Вы вишь какой финт придумали с возвратом ... Кстати и сортировка не обязательна, она нигде не используется.

[wrest]

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

То есть из любых 17 цифр можно составить 9-значное число, которое делится на 9 (числа с ведущими нулями допускаем на конкурс).

[Ktina]

wrest
Dmitriy40
Существует теорема Эрдёша - Гинзбурга - Зива, она как раз об этом.

[wrest]

Ktina в сообщении #1339858 писал(а):

Существует теорема Эрдёша - Гинзбурга - Зива, она как раз об этом.

а... глянул.
доказательство для общего случая вроде и не сложное, но и не такое простое.
ну в качестве головоломки и только для девятки ничотак, мне понравилось. для тройки бы совсем уж просто бы было.
а чего для 25 тады просили, если известно, что минимальный набор 17?

[Ktina]

wrest в сообщении #1339861 писал(а):

а чего для 25 тады просили, если известно, что минимальный набор 17?

«Красная тряпка».