電気手袋の刑(解答)

　もし全員が小さい順に並んだときに自分の順位がいくつになるかがわかれば，作戦は簡単だ。例えば，それが奇数位なら右手にプラスで左手にマイナス，反対に偶数位なら右手にマイナスで左手にプラスと決めて全員が手袋をはめれば，触れ合う手袋はどこもプラスどうし・マイナスどうしとなり電流は流れない。

　問題は，自分の数値がわからないから自分の順位を知りようがないことだ。この問題は一見どうしようもないような気がするが，実は知りたいのは，自分の順位そのものではなくその奇偶性だけである。

　古い記事をご記憶の読者は，2010年8月号の「チームで参加！ 何でもオリンピック」 （単行本『パズルの国のアリス』に収載）で置換の奇偶性を扱ったことを覚えておられるかもしれない。今回の問題の設定はそのときとよく似ているが，実は同じアイデアが解決策になり，スペードのエースから兵士たちへの指示もそれを応用したものだ。

　まず置換とその奇偶性を定義するために，40人全員に1から40までの番号を振る。これは好き勝手でよい。例えば, スペードのエースから10までを1番から10番，ハートのエースから10までを11番から20番などとしておくのが覚えやすくて簡単だろう。

　帽子をかぶせられると，全員が自分を除いてはどういう順に並んで手をつなぐかがわかる。自分の位置はわからないが，そこは気にせずに自分の数値が一番小さくて先頭にくるものと仮定しよう。そこで，最初は1番から40 番まで振った番号順に並んでいたと仮定し，自分を先頭に帽子の数値の小さい順に並び替えることを考えてみる。このとき2人ずつの位置交換を何度か行うが，並び替えが終了するまでの交換回数を数える。これが奇数回だったものは右手にプラス，左手にマイナスの手袋をはめ，逆に偶数回だったものは右手にマイナス，左手にプラスの手袋をはめる。

　以上でスペードのエースからの指示はおしまいだ。これでなぜ全員が電撃を免れるのかを考えてみよう。

　まず全員を正しく数値の小さい順に並べ替えたとし，これにM回の位置交換が必要だったとしよう。また，正しい順位がnの兵士が自分を先頭とする並び替えに要した交換回数をk_nとする。同じ並び替えは正しい並び替えからn−1回の交換を経ても作ることができる。その奇偶性は交換の手順によらないから

M＋（n−1）≡k_n（mod 2）

が成り立っている。Mはnによらない定数だから，これが何を意味するかというと，順位が1違いの2人は必ず奇偶性が異なるということだ。よって，一方が左手にプラスの手袋をはめれば，他方は右手にプラスの手袋をはめることになり，手をつないでも電流は流れない。

　この戦略は40人でなくとも偶数人ならうまくいくので，6人の場合で確かめてみよう。

　1番から6番の兵士の帽子に書かれた数値を順にc，b，f，d，e，aとし，a＜b＜c＜d＜e＜fとしよう。1番の兵士の数値cは第3位だが，1番の兵士はそのことを知らないので，自分を先頭にc，a，b，d，e，fという順に並び替えようとするが， それは

a↔b，b↔f

の2回の交換で済むから偶数回である。そのすぐ後の第4位の数値dを持つのは4番の兵士だが，同様に自分を先頭にd，a， b，c，e，fという順に並び替えようとする。それは

d↔c，a↔b，b↔f

の3回で可能だから交換回数は奇数回だ。このように順位が1違いの2人の奇偶性は必ず異なる。読者は別の順位づけや人数で確かめられたい。

　ちなみに，奇数人の輪ではプラス・マイナスの手袋が奇数ずつになるから電気ショックを受ける犠牲者が必ず出る。しかし，その場合でも上の戦略は有効で，電撃を受けるのは最高順位と最低順位の数値を持つ2人に限ることができる。