Сколько чисел нужно вставить? (КПК)

[Ktina]

Какое наименьшее количество целых чисел нужно вставить между числами 1 и 2011 так, чтобы сумма любых двух соседних чисел в этом ряду была степенью двойки (с целым неотрицательным показателем -- прим. ред.)?

[shukshin]

4? 3, 5, 27, 37
все числа положительные?
просто если нет, то можно 3: 1 7 -5 37 2011, уже 3 - оценка сверху

[Ktina]

shukshin в сообщении #655811 писал(а):

4? 3, 5, 27, 37
все числа положительные?

В том-то и дело, что не обязательно положительные. Если обязательно положительные, задача решается однозначно -- перед 2011 может стоять только 37, перед 37 -- только 27, перед 27 -- только 5, перед 5 -- только 3, а перед 3 -- только 1.

[shukshin]

ну одно точно нельзя:
$1+x=2^m, 2011+x = 2^n$
откуда вычитанием:
$2010 = 2^n - 2^m$ или $1005 = 2^{n-1}-2^{m-1}$, нетрудно убедиться в неразрешимости этого уравнения в целых числах.
Ну и так же попробовать разобрать случай с двумя.

[Ktina]

shukshin в сообщении #655837 писал(а):

ну одно точно нельзя:
$1+x=2^m, 2011+x = 2^n$
откуда вычитанием:
$2010 = 2^n - 2^m$ или $1005 = 2^{n-1}-2^{m-1}$, нетрудно убедиться в неразрешимости этого уравнения в целых числах.
Ну и так же попробовать разобрать случай с двумя.

В принципе верно. Но не стоит забывать, что единичка -- тоже степень двойки (с нулевым показателем), а Вы тут на 2 делите. В данном, частном, случае это прокатывает.

[shukshin]

ну для уверенности можно убедиться что x ≠ 0, -2010

[Ktina]

shukshin в сообщении #655851 писал(а):

ну для уверенности можно убедиться что x ≠ 0, -2010

Мало что даст. Но убедиться, конечно, можно.

[shukshin]

в смысле, что при таких $x$ , как можно заметить, те самые $2^m$ и 2^n$ не будут единичкой. И не будет дыр в предложенном решении.

[Ktina]

shukshin в сообщении #655866 писал(а):

в смысле, что при таких $x$ , как можно заметить, те самые $2^m$ и 2^n$ не будут единичкой. И не будет дыр в предложенном решении.

Пусть будет.
Можно было и написать "очевидно, одного числа не достаточно".

[shukshin]

да, ну и для двух так же:
$1+x=2^k$
$x+y=2^l$
$y+2011=2^m$
складываем первое со третьим и вычитаем второе:
$2012 = 2^k + 2^m - 2^l$, убираем вырожденные случаи:
$2^l = 1$, $2^m = 1$, $2^k = 1$, убеждаясь, x ≠ 0, -2010
$ 2^k + 2^m - 2^l = 2012 $ спокойно делим на 2:
$2^{k-1} + 2^{m-1} - 2^{l-1} = 1006$, убираем еще три случая с единицами
окончательно $2^{k-2} + 2^{m-2} - 2^{l-2} = 503$, не имеет решений в целых числах
(что несложно проверить).
Для трех я пример привел.

[Shadow]

Ну и двумя нелзя. Получается такое уравнение:
$503+2^b=2^c+2^a$

$503=111110111_{(2)}$
мммм, "очевидно, что двух чисел недостаточно"

[TOTAL]

Двух не достаточно.
$1, 2^a - 1, 2^b - 2011, 2011$
$2^a + 2^b - 2012= 2^c$
$2^a + 2^b +2^5+2^2= 2^c+2^{11}$
В двоичной записи слева по крайней мере 3 единицы.

1, 31, -29, 37, 2011

[Ktina]

TOTAL в сообщении #655881 писал(а):

Двух не достаточно.
$1, 2^a - 1, 2^b - 2011, 2011$
$2^a + 2^b - 2012= 2^c$
$2^a + 2^b +2^5+2^2= 2^c+2^{11}$
В двоичной записи слева по крайней мере 3 единицы.

А трёх достаточно:

(Если любопытно:)

Мой пример: 1, 7, -5, 37, 2011
Два примера BSK:
1, 7, 2041, -2009, 2011
1, 31, 2017, -2009, 2011