задачки

[avva]

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

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

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

Comments

[oblomov-jerusal.livejournal.com]

А для 2,5,7 нужен другой метод? (Этот требует индукции от всех k меньших n).

[avva.livejournal.com]

Основная идея та же. Но несколько труднее обеспечить существование аналога "степени двойки" достаточно большого, и это получается сделать только для достаточно больших чисел, поэтому спускаться вниз до упора невозможно, и нужна "стартовая площадка" для индукции - интервал определённого размера, на котором все числа точно раскладываются.

[oblomov-jerusal.livejournal.com]

Вопрос еще, как не попасть слишком низко, ниже "площадки".

[avva.livejournal.com]

Для этого просто нужно, для данного n, выделить интервал, который начинается достаточно высоко, но не доходит до самого n, так что если x лежит в этом интервале, то n-x после спуска вниз на один шаг не окажется ниже "площадки", но, с другой стороны, окажется меньше x. При этом интервал должен быть достаточно обширным, чтобы обязательно вмещать аналог "степени двойки".