以上の仮定の下では、1番左(1番)を一番右(n番)に移すのに、n-1本の横棒が必要になる。このとき、2~n番は左に1つずつシフトする。n本の縦棒の場合に順番を逆転する横棒の数をp[n]とすれば、先ほどシフトした2~n番を逆順に並べ替えるのに、p[n-1]本の横棒が必要。よって、p[n]=p[n-1]+(n-1)という漸化式が成立する。p[1]=0は自明なので、p[n]=Σ(i=1~n-1)i=n(n-1)/2。n=100000001=10^8+1なら、p[n]=10^8×(10^8+1)/2=5×10^7×(10^8+1)=5×10^15+5×10^7。反則技:横棒が「隣り合う2本の縦棒」以外を連結するような入れ方をOKにする。n=2k-1の奇数の場合、k-1番目とk+1番目の縦棒2本を、例えば中央のk番目の縦棒の下に書いてある数字の下を通るようにして、直接連結する。同様に、k-i番目とk+i番目(i=1~k-1)を結べば、題意を満たす順番の入れ替えができる。必要な横棒の本数はk-1本。出来たあみだくじは、玉葱を上下に真っ二つにした断面みたいになるかな。n=100000001=10^8+1=2×(5×10^7+1)-1なら、5×10^7本で済む。100000001C2本が答えだと思います。1→1へ自由に線を引き、2→2にも自由に線を引くとします。このとき交点が少なくとも1個できます。3個、5個...と複数の交点を作ってもいいですが。この引いた線上(曲線でもOK)を伝っていきます。これはまさにあみだくじの仕組みです。交点上を通過することが、横棒を通過することに対応しています。自由に引いた曲線をうまく真っ直ぐにして真下の数字とつながるようにしたとき、交点が横に引き伸ばされて横棒になったと思うと全く同じ図を書いていることになります。言葉だと非常に理解しにくいのでn=3の場合に図示してみました。左の列の場合、本来は赤→黒(一番左の包絡線)と通るはずですが、交点が存在するためにそこで黒への移動が起こらず、赤(左から二番目の包絡線)を通り、...というようになっています。対応するあみだくじが隣に書いてあります。交点が複数ある場合は、例えばn=2のときに交点が3つあるような引き方をした場合は、線のたどり方は上で書いたような単純なものではなくなるのですが、要するに2本の縦棒の間に3本の横線が引かれているという状況に対応しています。ちなみに3曲線が1点で交わるような交点を作ってしまうと、1つの横棒で3つの直線が結ばれている状況に対応してしまい、あみだくじとして不適切です。よって交点は必ず異なるようにさせます。要するに、この問題は、1,2,3,...,nとn,n-1,...,1を線で結んだとき、一番交点が少なくなるように結ぶと何個の交点が出来ますか?という問題と等しいわけです。この問題においては、数字の配置の関係で、必ずすべての直線がすべての直線と交差するようになっています。