задачки

[avva]

Две красивые задачки с элементарным, но не совершенно тривиальным решением. Мне понравились. Не знаю, насколько они известны; я наткнулся на них в старом выпуске American Mathematical Monthly.

1. Пусть S — множество всех натуральных чисел, у которых нет простых делителей, больших, чем 3. Доказать, что любое натуральное число можно представить в виде суммы набора чисел из S, так, что числа в наборе не повторяются, и ни одно число в наборе не кратно никакому другому.
   
   
2. Пусть T — множество всех натуральных чисел, у которых нет простых делителей, кроме 2, 5 или 7. Доказать, что заключение предыдущего пункта выполняется (для T, а не для S, естественно) для любого достаточно большого натурального числа.
   
   

Если вдруг (хоть я в это не верю) не появится правильное решение в комментариях за несколько дней, то я опубликую своё доказательство. Тому, кто хочет решать сам, в комментарии лучше не заглядывать (я хоть и буду скрывать на время правильные решения или значительные шаги к ним, но не всегда оперативно).

Comments

[french-man.livejournal.com]

А, конечно.

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

[flaass.livejournal.com]

Блин, комп дохнет, почти готовая запись пропала. Повторю попозже.
А идея такая: для двух простых общего числа сумм не хватает, если простые "слишком" велики.

[flaass.livejournal.com]

Ага, написал про два простых.

[french-man.livejournal.com]

Да, и с "локальным условием" неверна. ОК, подумаем. Надо с Севой Львом обсудить, у него хорошая интуиция на такие штучки.

[flaass.livejournal.com]

Надо заставить ее еще медленнее расти, твое условие слишком слабо.
И заключение сделать такое: либо мн-во непредставимых чисел конечно, либо оно содержит бесконечную арифметическую прогрессию.

[french-man.livejournal.com]

Да, похоже на то.