Олимипиадная задачка по математике, просьба подробно расписать

2

Для того, чтобы понять, о чем я говорю, попробуйте сами проделать первые шаги.

Я заметил следующее: на каждом шагу мы оставляем только те числа, которые дают один и тот же остаток при делении на 2^(текущий шаг).
Первым числом в каждом новом списке и будет наш остаток, а каждый следующий - на 2^(текущий шаг) больше.
При этом на каждом нечетном шаге остаток увеличивается на 2^(предыдущий четный шаг), так как начало списка сдвигается. На каждом же четном шаге остаток не меняется, так как начало списка не сдвигается.


1) Мы оставляем числа, которые сравнимы с 2 по модулю 2 (первый остаток именно 2, а не 0, так как нуля в списке не было)
2) Мы оставляем числа, которые сравнимы с 2 по модулю 4
3) Мы оставляем числа, которые сравнимы с 6 по модулю 8
4) Мы оставляем числа, которые сравнимы с 6 по модулю 16
5) Мы оставляем числа, которые сравнимы с 22 по модулю 32
6) Мы оставляем числа, которые сравнимы с 22 по модулю 64
7) Мы оставляем числа, которые сравнимы с 86 по модулю 128
8) Мы оставляем числа, которые сравнимы с 86 по модулю 256
9) Мы оставляем числа, которые сравнимы с 342 по модулю 512
10) Мы оставляем числа, которые сравнимы с 342 по модулю 1024

Проверено программой на Python:

 L = [] 
X = 1 
while X < 1025: 
    L.append(X) 
    X += 1 
step = 1 
while step < 11: 
    if step%2 == 1: 
        N = 0 
        while N < len(L): 
            L.pop(N) 
            N += 1 
    if step%2 == 0: 
        N = 1 
        while N < len(L)+1: 
            L.pop(N) 
            N += 1 
    step += 1 
print(L) 

Можно так всё это схематизировать:
1) В первый раз мы вычеркиваем слева направо последовательность чисел 1+2(n-1), где n от 1 до 1024/2=512, последнее вычеркнутое число (ПВ) 1023, последнее (по направлению вычеркивания) не вычеркнутое (ПНВ) 1023+2/2=1024
и
2) на следующем шаге начинаем с 1024 вычеркивать уже справа налево последовательность 1024-2²·(n-1) , где n от 1 до 1024/2²=256, ПВ=4, ПНВ=4-4/2=2
и
далее всё по той же схеме, теперь опять слева направо и т.д.
Собственно, нас и интересует это ПНВ после 10 шага.
Достаточно, чтобы уловить закономерность.
...
На k-ом шаге вычеркивается последовательность:
Pₖ₋₁+(-1)ᵏ⁺¹·2ᵏ·(n-1) в кол-ве 2¹⁰⁻ ᵏ чисел
Pₖ это ПНВ - последнее не вычеркнутое число k-го шага, вычисляется по рекуррентным формулам:
P₁=2¹⁰, Pₖ₊₁=Pₖ+(-1)ᵏ⁺²·(2¹⁰-2ᵏ)
...
Ну, придется 9 раз вычислить, что поделать.
P₂=2, P₃=1022, P₄=6, P₅=1014, P₆=22, P₇=982, P₈=86, P₉=854,
и наконец P₁₀=342
Yes!

------------------------
6/13/24