Разделы 
Дополнительно
Задача по математике - 1448
2018-12-13 
Первые 1511 натуральных чисел расставлены по порядку вдоль окружности. Затем, последовательно вычеркивается каждое второе число (2; 4; $\cdots$; 1510; $\cdots$). Этот процесс продолжается до тех пор, пока не останется только одно число. Какое это число?
Решение:
Пусть первоначально вдоль окружности расположено $n$ чисел. Искомое число обозначим $f(n)$. Тогда, по условию, имеем рекуррентные соотношения: $f(2n) = 2f(n) - 1$ и $f(2n + 1) = 2f(n) + 1$. Применяя эти соотношения, последовательно получим:
$f(1511) = 2f(755) + 1; f(188) = 2f(94) - 1; f(11) = 2f(5) + 1;$
$f(755) = 2f(377) + 1; f(94) = 2f(47) - 1; f(5) = 2f(2) + 1;$
$f(377) = 2f(188) + 1; f(47) = 2f(23) + 1; f(2) = 2f(1) - 1;$
$f(23) = 2f(11) + 1$;
Очевидно, что $f(1) = 1$. Далее, $f(2) = 1; f(5) = 3; \cdots ; f(1511) = 975$.
Используя метод математической индукции, можно доказать, что если вдоль окружности расположено $n$ чисел, причем $n = 2^{k} + m$, где $m < 2k$, то при последовательном вычеркивании каждого второго числа последним останется число $2m + 1$. Поскольку 1511 = 1024 + 487 = 210 + 487, то в нашем случае останется число $2 \cdot 487 + 1 = 975$.
Первые 1511 натуральных чисел расставлены по порядку вдоль окружности. Затем, последовательно вычеркивается каждое второе число (2; 4; $\cdots$; 1510; $\cdots$). Этот процесс продолжается до тех пор, пока не останется только одно число. Какое это число?
Решение:
Пусть первоначально вдоль окружности расположено $n$ чисел. Искомое число обозначим $f(n)$. Тогда, по условию, имеем рекуррентные соотношения: $f(2n) = 2f(n) - 1$ и $f(2n + 1) = 2f(n) + 1$. Применяя эти соотношения, последовательно получим:
$f(1511) = 2f(755) + 1; f(188) = 2f(94) - 1; f(11) = 2f(5) + 1;$
$f(755) = 2f(377) + 1; f(94) = 2f(47) - 1; f(5) = 2f(2) + 1;$
$f(377) = 2f(188) + 1; f(47) = 2f(23) + 1; f(2) = 2f(1) - 1;$
$f(23) = 2f(11) + 1$;
Очевидно, что $f(1) = 1$. Далее, $f(2) = 1; f(5) = 3; \cdots ; f(1511) = 975$.
Используя метод математической индукции, можно доказать, что если вдоль окружности расположено $n$ чисел, причем $n = 2^{k} + m$, где $m < 2k$, то при последовательном вычеркивании каждого второго числа последним останется число $2m + 1$. Поскольку 1511 = 1024 + 487 = 210 + 487, то в нашем случае останется число $2 \cdot 487 + 1 = 975$.
