wpoms.
Step by step ...


Пусть $k$ --- фиксированное положительное целое число. Альберто и Беральдо играют в следующую игру:
дано начальное число $N_0$ и начинает Альберто, они по очереди выполняют такую операцию: заменяют число $n$ на число $m$ так, что $m < n$ и $m$ и $n$ отличаются, в их представлении по модулю 2, точно в $\ell$ последовательных цифрах для некоторого $\ell$ такого, что $1 \leq \ell \leq k$.
Тот, кто не может сделать ход, проигрывает.
Назовем неотрицательное число $t$ победителем, если игрок получивший число $t$ имеет выигрышную стратегию, он может выбрать следующее число так, чтобы обеспечить свою победу вне зависимости от действий другого игрока. Иначе назовем число неудачником.
Докажите, что для каждого положительного целого числа $N$, общее количество неотрицательных чисел-неудачников, меньших чем $2^N$, равно $2^{N-\lfloor \log_2(min\{N,k\}) \rfloor}$.
Пояснение: запись вида $\lfloor x \rfloor$ означает наибольшее целое число меньшее или равное $x.$ Например, $\lfloor 3{,}14 \rfloor = 3$, $\lfloor 2 \rfloor = 2$, $\lfloor -4{,}6 \rfloor = -5$.



@темы: Теория чисел