Руст писал(а):
... T(n) линейный оператор, соответственно на множестве остатков по модулю 2^k ...
Какая линейность?
![$T(1)=2, T(2)=1, T(3)=5$ $T(1)=2, T(2)=1, T(3)=5$](https://dxdy-02.korotkov.co.uk/f/1/b/c/1bc588602c88437698f5cdbaeb434e2c82.png)
Цитата:
В принципе можно представить и решение в явном виде начиная разрешать с конца
Так и есть. Удлинять двоичную последовательность надо с конца. Пристроить нули спереди нет проблем. Чуть сложнее пристроить единицу с некоторым количеством нулей.
Чуть подробнее скажу, чем в цитате выше.
1) Сначала подъём: вместо
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
берём
![$m=n+2^N$ $m=n+2^N$](https://dxdy-01.korotkov.co.uk/f/8/e/f/8efdcc1b82421870c6b33e9931f3ce2782.png)
, тогда очевидно
![$T^i(n)\equiv_2 T^i(n)$ $T^i(n)\equiv_2 T^i(n)$](https://dxdy-03.korotkov.co.uk/f/2/5/f/25f14f8d2d7c52518e14d329028ecedb82.png)
для
![$i=0,1,2, ... , N-1$ $i=0,1,2, ... , N-1$](https://dxdy-03.korotkov.co.uk/f/e/9/a/e9a22c0967ac24c70843d52ae61d41be82.png)
, то есть возникающая из
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
двоичная последовательность не будет отличаться от прежней столь долго, сколько пожелаем.
2) Умножив на
![$2^k, k\ge 0$ $2^k, k\ge 0$](https://dxdy-03.korotkov.co.uk/f/e/4/4/e44ee25d69881023e8d4acb5448df86f82.png)
, получим
![$m'=2^km$ $m'=2^km$](https://dxdy-04.korotkov.co.uk/f/7/3/8/73815e22046b453fdbb096b8aef73d0682.png)
, для которого эта последовательность надстроится
![$k$ $k$](https://dxdy-03.korotkov.co.uk/f/6/3/b/63bb9849783d01d91403bc9a5fea12a282.png)
нулями спереди.
3) Достаточно большое
![$N$ $N$](https://dxdy-04.korotkov.co.uk/f/f/9/c/f9c4988898e7f532b9f826a75014ed3c82.png)
выбираем теперь так, чтобы
![$2^{k+1}m' - 1$ $2^{k+1}m' - 1$](https://dxdy-04.korotkov.co.uk/f/3/b/8/3b83eb3b9af92c5c20fbfa6b709c2a9c82.png)
делилось на
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
.
Согласен, что задача несложная. Цитата перед вами - сам оценивал это как тривиальный факт и когда предлагал её для матбоя, в котором участвовали студенты 1-3 курсов тоже имел сомнения, а не слишком ли она проста. Как оказалось - не слишком.