問題

置換 $p, q \in \mathfrak{S} _ N$ が与えられる。 次のように定義する:

  • $a_1 = p$
  • $a_2 = q$
  • $a _ {n+2} = a _ {n+1} \circ a_n^{-1}$

このとき $a_K$ を答えよ。

考察過程

  1. 愚直 $O(NK)$
  2. とりあえず対称群の言葉で書き直した (整理)
  3. 見ていけば周期性がありそう (推測)
  4. 周期性なかった (実験)
  5. 連結成分ごとに解く?
  6. やたら疎な行列の累乗に持ち込みたい
  7. 上から落としていってうまく再帰できないか

    これ下からやるのと同じ

    #!/usr/bin/env python3
    import re
        
    a = []
    a += [ 'p' ]
    a += [ 'q' ]
    for _ in range(14):
        a += [ a[-1] + ''.join(reversed(a[-2])).swapcase() ]
    print(*a, sep='\n')
        
    b = [ re.subn(r'(pP|Pp|qQ|Qq)', '', a_i)[0] for a_i in a ]
    print(*b, sep='\n')
    
    $ ./a.py
    p
    q
    qP
    qPQ
    qPQpQ
    qPQpQqpQ
    qPQpQqpQqPqpQ
    qPQpQqpQqPqpQqPQqPqpQ
    qPQpQqpQqPqpQqPQqPqpQqPQpQqPQqPqpQ
    qPQpQqpQqPqpQqPQqPqpQqPQpQqPQqPqpQqPQpQqpQqPQpQqPQqPqpQ
    qPQpQqpQqPqpQqPQqPqpQqPQpQqPQqPqpQqPQpQqpQqPQpQqPQqPqpQqPQpQqpQqPqpQqPQpQqpQqPQpQqPQqPqpQ
    qPQpQqpQqPqpQqPQqPqpQqPQpQqPQqPqpQqPQpQqpQqPQpQqPQqPqpQqPQpQqpQqPqpQqPQpQqpQqPQpQqPQqPqpQqPQpQqpQqPqpQqPQqPqpQqPQpQqpQqPqpQqPQpQqpQqPQpQqPQqPqpQ
    ...
    
  8. それでも周期性に頼る他はなさそう。「ある $k$ で不動点 $a_k(i) = i$ がある」を仮定するとどうか

    この方向だと $O(N^2)$ がありそう

  9. 「ある $k$ で等式 $ a_ {k+1}(i) = a_k(i)$ がなりたつ」を仮定するとどうか

    よって $a _ {k+2}$ が不動点 $a_k(i)$ を持つ

  10. 「ある $k$ で等式 $ a_ {k+2}(i) = a_k(i)$ がなりたつ」を仮定するとどうか

    苦しい

  11. 諦め。周期性の検討以外に手を思い付かなかったため

解法

$a_n = A_n \circ B_n \circ A_n^{-1}$ と整理すると $(A_n, B_n)$ の列に関して周期性がある。

反省

  • $a_n = ABA^{-1}$ という発想がなかった
  • 周期性までは見えていた。 $a_n^{-1}$ も併記して観察すれば辿り着けていたかもしれない

特性方程式

乗法群でなく加法群として見て $a _ {i+2} = a _ {i+1} - a_i$ の特性方程式 $x^2 = x - 1$ の解は $x = \frac{1 \pm \sqrt{-3}}{2}$ となる。これは符号がどちらの場合でも $x^3 = -1$ つまり $x^6 = 1$ となるような点である。

リンク