先日まで長期育児休業を取得していた、元編集部社員・現情報システム部社員です。

佑人社では模擬試験や入試問題の製作・採点業務・成績処理、および採点システムの提供を行っています。
最近では、共通テストで日常生活に関係した内容が出題されているように、社内で見かける問題も日常生活に絡めたものが増えてきました。

そこで、育児中や日常生活の中で「こんな問題も考えられるなぁ」と思ったもののうち、ボツ案を紹介してみます。

先日、子どもとできる遊びを考えている際に、「あみだくじ」で線を指でなぞって遊ぶことを思いつきました。

上の例だと、左から順に12345と並んでいたものが、あみだくじの結果24351と変わっていて、線をなぞるだけの遊びです。
さて、縦線が5本のあみだくじについて考えているときに、次の2点について疑問に思いました。
・横線の引き方を変えれば、5!(＝120)通りの結果を全部作ることができるのか。
・120通り全部を作れる場合、最低何本の横線があれば、120通り全パターンを作ることができるか。
・縦線の本数がn本のときはどうなるか？

この疑問を持ったときは、どうすれば解決するか少し悩みました。
120通り全パターンを作れるかどうかは、実際にやってみるしかないのだろうか。
また、上の例だと横線を13本引いているが、無駄をなくせば横線5本だけで24351の結果を作れる。では、最も多いの場合(おそらく結果が54321の場合)だと何本必要だろうか。
更には、縦線の本数をn本にして一般化できるのだろうか。

（読んでいる皆さんも考えてみてください。少し下に私なりの考えを書いています。）

色々と考えているとき、あることに気が付きました。
あみだくじを上から下に見て12345から120通りの数字列を作るのではなく、下から上に見ることで「120通りの数字列を、バブルソートを用いて12345の昇順に並び替えできるかどうか」を考えればよいと。

※バブルソートは、左から順に隣同士の数字を比べて左が大きければ交換するといったアルゴリズムです。24351の場合、次のようになります。
（傍線が注目している2数字、"→"は交換なし、"⇒"は交換あり）
24351→24351⇒23451→23451⇒23415→23415→23415⇒23145→23145→23145⇒21345→21345→21345⇒12345
交換ありが5回なので、あみだくじで横線が5本あれば、24351は12345に並べ替えられることになります。

バブルソートは、必ずソートできること、計算量は最大でもn(n-1)/2であることが知られています。
そのため、「あみだくじの縦線（元々の数字の個数）がn本のとき、横線がn(n-1)/2本あれば、どのパターンの結果でも作ることができる」ことがすぐに分かりました。

皆さんに馴染みのある「あみだくじ」ですが、実はITパスポートでも出題される「バブルソート」に繋がるんですね。
（調べてみたら、2022年度センター試験の情報関係基礎で、「あみだくじ」と「バブルソート」について出題されていました。自分よりも先に気が付いた人がいるのは少しだけ悔しいです……）

こんな風に、日常生活でよく見る何気ない事柄について深く考察するのが好きな方は、試験問題を扱っている佑人社と相性が良いかもしれないので、興味を持っていただけたらと思います。