на круге 2017 чисел

[daogiauvang]

На круге написать 2017 чисел с 1 до 2017. Мы действуем так, очередно сохранить одно число и убрать одно число. Какое число остается последнее?

[Brukvalub]

daogiauvang в сообщении #1211988 писал(а):

Мы действуем так, очередно сохранить одно число и убрать одно число. Какое число остается последнее?

Это задача с олимпиады по кодированию, и в ней нужно восстановить сообщение, искаженное в результате передачи по зашумленной линии связи?

[gris]

Я понял, что некто ходит по кругу (в узком смысле) и удаляет числа через одно. Ну вот как для пяти:
$(\mathbf{1},2,3,4,5)\to (1,\mathbf{3},4,5)\to(1,3,\mathbf{5})\to(\mathbf{3},5)\to (\mathbf{3})$

Так и хочется сформировать последовательность для первоначального количества чисел:
$1,1,3,1,3,5,7,1...$

[grizzly]

Наверное, эту задачу можно решить как-то красиво. Но можно просто в уме, используя карандаш для ведения лога:
...2016 2017 1 2...
...2015 2017 1 3...
...2011 2015 3 7...
...2003 2011 3 11...
...1987 2003 3 19...
...1955 1987 3 35...
...1923 1987 3 67...
...1859 1987 67 195...
...1731 1987 195 451...
...1731 1987 195 451...
...1475 1987 451 963...
1987 963
1987

Алгоритм всей этой записи по-дубовому прост

-- 23.04.2017, 19:44 --

gris в сообщении #1212011 писал(а):

Так и хочется сформировать последовательность для первоначального количества чисел:
$1,1,3,1,3,5,7,1...$

Точно! Как я сразу не догадался? A006257

[gris]

Я. конечно, не удержался и заглянул в OEIS, хотя там как-то сложновато. Рекурсию тут несложно посчитать, удваивая количество чисел. При этом через круг мы получаем похожую раскладку. Ну и так видно, что при $n=2^k$ мы останавливаемся на единичке. А в промежутках всё заполняется последовательными нечётными числами, начиная с тройки. То есть надо найти чуть меньшую степень двойки.
$D(2017)=(2017-1024)\cdot 2+1=1987$. Ура, совпало!
Теперь надо обобщать на пропуск не одного, а $k$ чисел.

[grizzly]

gris в сообщении #1212066 писал(а):

Теперь надо обобщать на пропуск не одного, а $k$ чисел.

Или сразу так: $k$ чисел пропускаем, $m$ чисел вычеркиваем. Мой алгоритм такое не тянет :)

[gris]

А что, если вычёркивать по прежней схеме, но с вероятностью $0.5$. И найти матожидание оставшегося числа?

[VAL]

grizzly в сообщении #1212123 писал(а):

gris в сообщении #1212066 писал(а):

Теперь надо обобщать на пропуск не одного, а $k$ чисел.

Или сразу так: $k$ чисел пропускаем, $m$ чисел вычеркиваем. Мой алгоритм такое не тянет :)

Не удивительно! За подробностями обращайтесь к maxal'у. Он большой специалист в этих вопросах.

PS: Вот и выросло поколение не знакомое со стариной Иосифом Флавием
(Исходная задачка подробнейшим образом обсуждается в 3-м параграфе первой главы книжки Кнута, Грэхема и Паташника "Конкретная математика".)

[grizzly]

VAL в сообщении #1212171 писал(а):

PS: Вот и выросло поколение не знакомое со стариной Иосифом Флавием

Ну или это поколение дорослось до того, что начало забывать прочитанные в юности книги