Пусть дано множество из m натуральных чисел из отрезка [1,n] (n- натуральное) такое, что значение сумм всех пар этих чисел различны. Верно ли, что $$m \leq 2(n)^{1/2} + 1?$$ Можно ли добавить к этому множествус ещё одно число, если $$m^3+m < n?$$

задан 27 Апр 0:16

изменен 27 Апр 0:29

1

Первое неравенство следует из очевидного неравенства $%C_m^2\le2n-1$%.

Второе утверждение следует из задачи math.hashcode.ru/questions/48407/ и постулата Бертрана.

(27 Апр 16:54) EdwardTurJ

@EdwardTurJ: здесь, как я понимаю, имеется в виду несколько иное утверждение. По ссылке указан способ построить достаточно много чисел с разными попарными суммами, и оценка там существенно лучше. Здесь же дано m каких попало чисел, удовлетворяющих условию, и надо показать, что к ним всегда можно добавить новое.

(28 Апр 23:46) falcao

@falcao: Да, это иная задача.

(29 Апр 9:33) EdwardTurJ
1

Пускай $%a_1,...,a_m$% - выбранные числа, а $%s_1,...,s_{c_{m+1}^2}$% - их попарные суммы. Разности $%a_i-s_j$% могут принимать не более, чем $%m\cdot C_{m+1}^2=\frac{m^3+m^2}2$% различных значений. Поэтому найдётся такое число $%x\le m^3+m$%, отличное от всех $%a_i$% и всех $%a_i-s_j$%. Его можно прибавить к множеству $%a_1,...,a_m$%, поскольку $%x\ne a_i$% и $%x\ne a_i-s_j$% для всех $%i$% и $%j$%.

(29 Апр 11:03) EdwardTurJ
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,052
×104
×40
×9

задан
27 Апр 0:16

показан
143 раза

обновлен
29 Апр 11:27

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

по почте:

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

по RSS:

Ответы

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

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