а) Доказать, что среди первых $%N$% натуральных чисел можно выделить не менее $%\sqrt{N}$% чисел таким образом, что среди трёх выделенных чисел ни одно не будет равно полусумме двух других.

б) Придумать как можно более сильную оценку снизу для количества выделяемых чисел вместо $%\sqrt{N}$%.

задан 1 Янв '15 20:03

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

$$f(1)=1,f(2)=2,f(2^k+i)=3^k+f(i),i=1,2,3,...,2^k,$$ то, что нет арифметических прогрессий длины 3, хорошо видно из записи в троичной системе:

1,2,

11,12,

101,102,111,112,

1001,1002,1011,1012,1101,1102,1111,1112.

Это лучше, чем $%\sqrt{N}.$%

ссылка

отвечен 2 Янв '15 0:46

@EdwardTurJ: я так понимаю, эта конструкция даёт оценку порядка $%2^k$% на $%3^k$%, то есть $%N^{\log_32}$%. Это действительно превышает $%\sqrt{N}$%.

Вообще, там есть оценки, превышающие $%N^{1-\varepsilon}$% при достаточно больших $%N=N(\varepsilon)$%, но они несколько сложнее строятся.

(2 Янв '15 0:52) falcao

@falcao: Это я "жадным алгоритмом".

(2 Янв '15 0:57) EdwardTurJ
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,414

задан
1 Янв '15 20:03

показан
3050 раз

обновлен
2 Янв '15 0:57

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

по почте:

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

по RSS:

Ответы

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

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