2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Возрастающая последовательность натуральных чисел
Сообщение10.08.2012, 11:53 
Аватара пользователя
Дана возрастающая последовательность натуральных чисел $(a_n)$.
Известно, что среди сумм $a_i+a_j$, где $i\le j$ нет двух одинаковых.
Для каждого $n\in\mathbb N$ найти наименьшее возможное значение $a_n$.

Мне удалось найти только нижнюю границу: $$a_n\ge \lceil\frac{1}{4}n^2+\frac{1}{4}n+\frac{1}{2}\rceil$$
Действительно, для каждого $a_n$ рассмотрим суммы $a_i+a_j$, где $i\le j$ и $i, j\le n$.
Таких сумм будет ровно $\frac{1}{2}n^2+\frac{1}{2}n$.
Поскольку эти суммы принимают только натуральные значения (наименьшее возможное из которых равно 2), а также поскольку нет двух одинаковых сумм, приходим к выводу, что наибольшая из этих сумм (а именно $a_n+a_n$) не меньше $\frac{1}{2}n^2+\frac{1}{2}n+1$. Но тогда $a_n\ge\lceil\frac{1}{4}n^2+\frac{1}{4}n+\frac{1}{2}\rceil$.

Но это - лишь нижняя граница, так как уже при $n=4$ мы не можем построить последовательность, удовлетворяющую условию задачи, если $a_4=\lceil\frac{1}{4}\cdot 4^2+\frac{1}{4}\cdot 4+\frac{1}{2}\rceil=6$ (тупым перебором можно в этом убедиться).

Пожалуйста, помогите разобраться.
Заранее благодарна!

 
 
 
 Re: Возрастающая последовательность натуральных чисел
Сообщение10.08.2012, 15:14 
Ну вот в OEIS есть что-то похожее: http://oeis.org/A005282

-- Пт авг 10, 2012 15:34:27 --

Хотя для данной задачи эта последовательность может служить лишь верхней оценкой. Например, наименьшее значение $a_4$ не превосходит 7, если взять последовательность ${a_n}=1, 2, 5, 7$.

 
 
 
 Re: Возрастающая последовательность натуральных чисел
Сообщение10.08.2012, 16:33 
Простое соображение, что все разности $a_i-a_j$(которых $\frac{n^2-n}{2}$) различны дает нам оценку $a_n\geq \frac{n^2-n}{2}+1$

Перебор на компьютере до $n\leq 9$ дает следующие результаты
$1,2,4,7,12,18,26,35,45$

(Соответствующие последовательности)

1,2
1,2,4
1,3,6,7
1,3,8,11,12
1,6,8,14,17,18
1,3,8,16,22,25,26
1,3,13,20,26,31,34,35
1,4,10,18,20,33,40,44,45

 
 
 
 Re: Возрастающая последовательность натуральных чисел
Сообщение10.08.2012, 16:35 
Аватара пользователя
Есть ощущение, что там будут степени двойки :?

 
 
 
 Re: Возрастающая последовательность натуральных чисел
Сообщение11.08.2012, 13:47 
Предполагается, что нахождение этого минимального максимума - NP-полная задача
http://en.wikipedia.org/wiki/Golomb_ruler
http://en.wikipedia.org/wiki/Sidon_sequence

 
 
 
 Re: Возрастающая последовательность натуральных чисел
Сообщение20.03.2013, 21:05 
Ответ: Треугольные числа

 
 
 
 Re: Возрастающая последовательность натуральных чисел
Сообщение20.03.2013, 22:02 
Почему?

Приведённые Cash числа
Cash в сообщении #604797 писал(а):
$1,2,4,7,12,18,26,35,45$
на треугольные не похожи — разности не те.

 
 
 
 Re: Возрастающая последовательность натуральных чисел
Сообщение09.04.2013, 03:11 
Аватара пользователя
Cash в сообщении #604797 писал(а):
Перебор на компьютере до $n\leq 9$ дает следующие результаты
$1,2,4,7,12,18,26,35,45$

Это A003022(n)+1.

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group