ABC377-E の帰納法による証明

本記事はABC377-E (Permuate K times 2)の解説で説明されている

求める答えは $(P_i^{2^k})_i$です。

の帰納法による証明です。

サンプル1において、$i → P_i$に辺を張ったグラフを書くと、以下のようなグラフとなります。

たとえば、$K = 3$のとき、証明すべき命題が真であるとすると、最終的な列の1番目の値となるのは、1頂点1から8回移動した頂点である6になります。これはサンプルの出力例と一致しています。他の頂点についても同様に成り立ちます。

$K\ge0$とします。また、解説にある操作によって得られるグラフのうち、ある1つの連結成分・ある1つの頂点についてのみ記します。他の連結成分についても同様にすることで、証明することができます。

1. $K=0$のとき成り立つことを示す
   $K = 0$とは、入力として与えられる列をそのまま出力するという操作を意味します。
   構築したグラフの定義から、頂点番号$i$から$2^0 = 1$だけ移動すると$P_i$となります。したがって、帰納法の仮定で得られる列と、構築すべき列は一致することが示せます。

2. $K = k$のとき成り立つと仮定して、$K = k+1$のときも成り立つことを示す
   解説の操作で得られるグラフの連結成分が、$l, m$を含んでいると仮定します。($1 \le l, m \le N$)本解説の表記を採用すると、$k$回目の操作後、以下のような状態になっています。
   
   ここで、例えば$P_l^{2^k} = m$であったとします。このとき、$k+1$回目の操作における頂点$l$の移動先は、$k$回目の操作における$m$番目の値、即ち$P_m^{2^k}$です。
   帰納法の仮定から、$l$から$2^k$回移動すると$P_l^{2^k} = m$に移動し、$m$からさらに$2^k$回移動することで$P_m^{2^k}$に到達します。したがって、$l$から$P_m^{2^k}$までの移動にかかる総数は
   

   $$2^k + 2^k = 2^{k+1}$$
   
   となり、頂点$l$において、$k+1$回目の移動においても帰納法の仮定が成り立つことが示せます。他の頂点・他の連結成分についても同様に示すことができるので、全体で$K = k+1$のときも成り立つことが示せました。

1, 2より、

求める答えは $(P_i^{2^k})_i$

であることを示すことができました。