iPadを用いた数学の入学試験 (2)

前回のiPadを用いた数学の入学試験 (1)の続きです。この記事は2017年と2018年の記事をまとめたものです。ちょっと古いのですが，記録として残しておくため，2回に分けて報告します。

はじめに

城北高校の推薦入試の数学の試験では，『iPadをを用いて解く問題』を出題しています。今回は2回目となる平成30年1月の入試の報告です。

平成30年1月の推薦入試

平成30年1月22日に城北高校の推薦入試の数学の試験で次の問題を出題しました。
この問題はiPadを用いて解く問題です。

城北高校・推薦入試数学・大問５

（図１）のように，$3\times 3$のマスに１〜８の数字が配置してある。

このマスの中で，次の規則にしたがって数字を移動させていく。

（規則１）空白のマスには，空白のマスの上下，左右の隣り合うマスにある数字のいずれかを移動させ
（規則２）移動した数字の元にあったマスは，新たに空白のマスとなる。

例えば（図１）の状態から１回の移動によって，（図２）の２つのいずれかになる。

（図１）の状態から２つの数字$a$，$b$の位置を入れ替える移動の最小の回数を$<a,\,b>$と表す。例えば，$<6,\,8>=6$である。そのときの移動の様子は次のようになる（\maru1〜\maru6は移動の順番を表している）。

このとき，次の値を求めよ。

(1) $<3,\,5>$
(2) $<1,\,5>$
(3) $<3,\,6>$

問題の作成過程で

これは，一般的に『８パズル』『スライドパズル』と呼ばれているもので，$4\times 4$から１枚除いた15枚の『１５パズル』が有名です。このパズルで遊んだことのある人も多いのではないでしょうか。
配置を崩して，下の図のように順序だった配置に戻すパズルです。

（15パズル wikipediaより）

今回の問題は，

『特定の数字を入れ替えるときに，最小の移動の回数はどうなるのか？』

ということです。当初，動き方を局所的に考えて，その動きを組み合わせることによって，最小の移動の回数を求められるのではないかと考えていました。しかし，答えをチェックすると，『もっと回数を少なくできるんじゃない？』という指摘があり，実際にいろいろ動かしてみたところ，想定した回数よりも少ない移動で数字の入れ替えができることがわかりました。今までならば，その時点で入試問題としてはあきらめます。私たちの想定した規則には当てはまらなかったわけですから，模範解答すら危うい状態です。でも，『iPadもあるし，コンピュータもあるし，もう少し調べてみよう！』と思い，まずは『スライドパズル』について調べてみることにしました。

１５パズル

wikipediaの中に『１５パズル』についての説明がありました。

不可能な配置

このパズルの初期配置として有名な例に「目的の配置から14と15を入れ替えた状態」というものがある。一般化も可能だが、まずはこれを例として考える。

15パズルを数学的に分析すると、1個の駒のスライドという操作は「空き」とその駒の入換えと見ることができ、これは群論でいう「互換」である。ここで、ある状態から操作を続けて元の位置に空きが戻ったとすると、それには必ず偶数回の操作＝偶数回の入換えが必要であり、その配置は元の配置からの偶数回の互換（偶置換）となっている。一方、14と15の入換えは1回の入換えであり、奇置換である。従って、14と15を入れ替えた状態から目的の配置にすることはできない。一般化すると、15パズルではランダムな配置から指定された配置への変換はできないことがある。なお、「奇置換であれば絶対に解けない」のは確かだが、「偶置換であれば必ず解ける」とは限らない。（15パズル wikipediaより）

この説明から，

• 例のように，14と15だけを入れ替えることは不可能である。
• 空白の位置が同じであれば，移動は偶数回必要である。
• 配置不可能なものがあり，どんな配置へも変形できるわけではない。

と理解しました。今回，私たちが作った問題では，２つの数字を入れ替える際に，\textbf{他の数字の配置はかわってもよい}のと，実際に移動できることは確認できているので，まあ，大丈夫かなあと考えました。

困難性

$n\times n$パズルにおいて、最短手数を求める問題はNP困難である。最短手数の定数倍の変形を求める多項式時間アルゴリズムが提案されている。8パズルは任意の可能な配置へ31手以内で変形でき、31手が必要な配置は確認されている。15パズルは任意の可能な配置へ80手以内で変形でき、80手が必要な配置は確認されている。（15パズル wikipediaより）

これにはちょっと参りました。配置Aから配置Bまで，仮に配置可能であったとすると，8パズルは31手以内でできるわけですが，その手順の求め方は単純ではないことが示唆されています。（NP困難と書いてあるし...）今回，２つの数字を交換する最小の移動の回数を調べるにあたり，

『その回数で最小であることが，本当にチェックできるのかなあ？』

と感じました。

コード検索

今回の問題では，『特定の数字を入れ替えるときに，最小の移動の回数はどうなるのか？』ということが知りたいので，特定の配置Aから配置Bまでの最短の手順を調べるコード（プログラム）などを作った人がいないかな？と考え，ネットを検索しました。すると，一番最初の正しい配置に変形するのに何手かかるか調べるコードは存在しました。（参考サイトの２番目）このプログラムをはじめ，１５パズルに関するコードは様々ありました。しかし，それらのコードは

• 特定の配置への最短経路を調べるものではない。
• 『特定の２つ数字以外はどのような並びでもよい。』ということに対応できない。

ということがわかました。結局ネット上に，今回の要件を満たす適当なコードを見つけることはできませんでした。

コード作成

ネット上に利用できるコードはなかったので（探せなかっただけですが...），『自分でプログラムを書くしかない！』ということになったのです。ちょっと不安もありましたが，『こういうことはコンピュータの力を借りて，個人でもできる時代になったんだよな。』と思うことにして，フロー図を考えました。

数字の移動（交換）の仕組み

数字の位置を左図のように①から⑨とし，最初の配置を右図のようにします。（空白のところの数字は0としています。）

１回の移動で0と，どの場所の数字が交換されるのかを調べました。例えば，最初の配列で0は⑨の位置にあります。１回の移動で，⑥または⑧にある数字と0を交換することができます。

空白（0）の位置と交換できる位置をまとめると次のようになります。

• 0が①のときは②，④と交換
• 0が②のときは①，③，⑤と交換
• 0が③のときは②，⑥と交換
• 0が④のときは①，⑤，⑦と交換
• 0が⑤のときは②，④，⑥，⑧と交換
• 0が⑥のときは③，⑤，⑨と交換
• 0が⑦のときは④，⑧と交換
• 0が⑧のときは⑤，⑦，⑨と交換
• 0が⑨のときは⑥，⑧と交換

記録と重複の削除

次に，繰り返しの手順を考えました。

(1) 0の位置を確認し，１回の移動で作られる配置を調べ，移動で得られた配置をリスト（データベース）に追加します。
(2) リストの中を調べ，重複があれば１つだけ残してあとは削除します。
(3) リストの中に求める２つの数字を入れ替えた配置がないか調べます。見つかればそれが求める最小の移動回数（答え）となります。見つからなければ，リストのそれぞれの配置の次の移動を考えます。

具体例

具体例を見てみます。

$\bm{n=1}$ （１回目の移動）

(1) まず，$b$というリストを作ります。最初の配置を$(1,2,3,4,5,6,7,8,0)$とすると，

$$b=((1,2,3,4,5,6,7,8,0))$$

となります。
このリストに移動でできた新しい配置を追加していきます。

最初，$0$は⑨にあるので，⑥にある$6$，⑧にある$8$と交換可能です。

$$(1,2,3,4,5,0,7,8,6)$$

$$(1,2,3,4,5,6,7,0,8)$$

2つの配置を$b$に加えて，

$$b=((1,2,3,4,5,6,7,8,0),\\ (1,2,3,4,5,0,7,8,6),\\ (1,2,3,4,5,6,7,0,8))$$

となります。１回の移動によって，２パターン加わり，配置の数は3となります。

(2) この$b$の中に重複する配置はありません。

(3) 問題の(1)$<3,\,5>$，すなわち，③が5，⑤が3となっているものがあるか探します。今回はありません。（(2)，(3)も同様に探しますが，今回はありません。）

$\bm{n=2}$ （２回目の移動）

(1) ２回目の移動ですが，最初の配置は検討しなくてもいいので，新しくできた2つの配列を考えます。

$$(1,2,\dot3,4,\dot5,0,7,8,\dot6)$$

は⑥の位置に$0$があるので，$0$は③にある$3$，⑤にある$5$，⑨にある$6$と交換可能です。

$$(1,2,0,4,5,3,7,8,6)$$

$$(1,2,3,4,0,5,7,8,6)$$

$$(1,2,3,4,5,6,7,8,0)$$

の3つの配置ができました。これらを$b$に加えます。

$$(1,2,3,4,\dot5,6,\dot7,0,\dot8)$$

は⑧の位置に$0$があるので，$0$は⑤にある$5$，⑦にある$7$，⑨にある$8$と交換可能です。

$$(1,2,3,4,0,6,7,5,8)$$

$$(1,2,3,4,5,6,0,7,8)$$

$$(1,2,3,4,5,6,7,8,0)$$

の3つの配置ができました。これらを$b$に加えます。

(2) いま，$b$は9個の配置となっていますが重複しています（下の波線部分）。

$$b=(\bm{(1,2,3,4,5,6,7,8,0)},\\ (1,2,3,4,5,0,7,8,6),\\ (1,2,3,4,5,6,7,0,8),\\ (1,2,0,4,5,3,7,8,6),\\ (1,2,3,4,0,5,7,8,6),\\ \bm{(1,2,3,4,5,6,7,8,0)},\\ (1,2,3,4,0,6,7,5,8),\\ (1,2,3,4,5,6,0,7,8),\\ \bm{(1,2,3,4,5,6,7,8,0)})$$

重複を除いて，$b$を7個の配置とします。

$$b=((1,2,3,4,5,6,7,8,0),\\ (1,2,3,4,5,0,7,8,6),\\ (1,2,3,4,5,6,7,0,8),\\ (1,2,0,4,5,3,7,8,6),\\ (1,2,3,4,0,5,7,8,6),\\ (1,2,3,4,0,6,7,5,8),\\ (1,2,3,4,5,6,0,7,8)）$$

これで，２回以内の移動でできる配置のリストができました。

(3) 残念ながら，問題の(1)(2)(3)を満たす配置はまだありません。

このように調べていって，問題の(1)(2)(3)を満たす配置を調べることにしました。人間の手でやろうとすれば，樹形図的な広がりがあるので，すぐに厳しくなることは予想されます。また，『リストを調べ，重複があれば１つだけ残してあとは削除します。』と書きましたが，人間の手が行おうとすればとても大変な作業です。もちろん，コンピュータでやっても大変な作業で，もしかすると，途中で計算が終わらない可能性もありましたが，これはやってみなくてはわからないので，まず，この方針でコードを書くことにしました。

Mathematica

さて，実際にコードを書くわけですが，当初，『julia』，『Python』，『swift』のどれかで書こうと思っていました。ただ，私のコードのスキルでは，リストを並べ替えるだけで悩んでしまうので，今回は諦めました。今回選んだのは，『Mathematica』です。古くからある数式処理ソフトです。有償ですが，数学の関数は豊富に揃っています。かつて，利用した経験もありました。

まず，最初の配置をリスト$b$に入れます。

b = {{1, 2, 3, 4, 5, 6, 7, 8, 0}}

次に0の位置によって，次の移動がどうなるかを考えて，リストに配置を追加する手続き関数$P$を作りました。

P := Which[
  Position[b[[i]], 0][[1]][[1]] == 1,
    b = Append[b, {b[[i]][[2]],
      b[[i]][[1]],b[[i]][[3]],
      b[[i]][[4]],b[[i]][[5]],
      b[[i]][[6]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[9]]}];
    b = Append[b, {b[[i]][[4]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[1]],b[[i]][[5]],
      b[[i]][[6]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[9]]}],
  Position[b[[i]], 0][[1]][[1]] == 2,
    b = Append[b, {b[[i]][[2]],
      b[[i]][[1]],b[[i]][[3]],
      b[[i]][[4]],b[[i]][[5]],
      b[[i]][[6]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[9]]}];
    b = Append[b, {b[[i]][[1]],
      b[[i]][[3]],b[[i]][[2]],
      b[[i]][[4]],b[[i]][[5]],
      b[[i]][[6]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[9]]}];
    b = Append[b, {b[[i]][[1]],
      b[[i]][[5]],b[[i]][[3]],
      b[[i]][[4]],b[[i]][[2]],
      b[[i]][[6]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[9]]}],
  Position[b[[i]], 0][[1]][[1]] == 3,
    b = Append[b, {b[[i]][[1]],
      b[[i]][[3]],b[[i]][[2]],
      b[[i]][[4]],b[[i]][[5]],
      b[[i]][[6]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[9]]}];
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[6]],
      b[[i]][[4]],b[[i]][[5]],
      b[[i]][[3]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[9]]}],
  Position[b[[i]], 0][[1]][[1]] == 4,
    b = Append[b, {b[[i]][[4]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[1]],b[[i]][[5]],
      b[[i]][[6]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[9]]}];
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[5]],b[[i]][[4]],
      b[[i]][[6]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[9]]}];
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[7]],b[[i]][[5]],
      b[[i]][[6]],b[[i]][[4]],
      b[[i]][[8]],b[[i]][[9]]}],
  Position[b[[i]], 0][[1]][[1]] == 5,
    b = Append[b, {b[[i]][[1]],
      b[[i]][[5]],b[[i]][[3]],
      b[[i]][[4]],b[[i]][[2]],
      b[[i]][[6]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[9]]}];
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[5]],b[[i]][[4]],
      b[[i]][[6]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[9]]}];
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[4]],b[[i]][[6]],
      b[[i]][[5]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[9]]}];
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[4]],b[[i]][[8]],
      b[[i]][[6]],b[[i]][[7]],
      b[[i]][[5]],b[[i]][[9]]}],
  Position[b[[i]], 0][[1]][[1]] == 6,
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[6]],
      b[[i]][[4]],b[[i]][[5]],
      b[[i]][[3]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[9]]}];
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[4]],b[[i]][[6]],
      b[[i]][[5]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[9]]}];
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[4]],b[[i]][[5]],
      b[[i]][[9]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[6]]}],
  Position[b[[i]], 0][[1]][[1]] == 7,
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[7]],b[[i]][[5]],
      b[[i]][[6]],b[[i]][[4]],
      b[[i]][[8]], b[[i]][[9]]}];
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[4]],b[[i]][[5]],
      b[[i]][[6]],b[[i]][[8]],
      b[[i]][[7]],b[[i]][[9]]}],
  Position[b[[i]], 0][[1]][[1]] == 8,
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[4]],b[[i]][[8]],
      b[[i]][[6]],b[[i]][[7]],
      b[[i]][[5]],b[[i]][[9]]}];
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[4]],b[[i]][[5]],
      b[[i]][[6]],b[[i]][[8]],
      b[[i]][[7]],b[[i]][[9]]}];
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[4]],b[[i]][[5]],
      b[[i]][[6]],b[[i]][[7]],
      b[[i]][[9]],b[[i]][[8]]}],
  Position[b[[i]], 0][[1]][[1]] == 9,
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[4]],b[[i]][[5]],
      b[[i]][[9]],b[[i]][[7]],
      b[[i]][[8]],b[[i]][[6]]}];
    b = Append[b, {b[[i]][[1]],
      b[[i]][[2]],b[[i]][[3]],
      b[[i]][[4]],b[[i]][[5]],
      b[[i]][[6]],b[[i]][[7]],
      b[[i]][[9]],b[[i]][[8]]}]
  ]

追加された$P$の中の重複を削除するときに，Mathematicaの『Union』という関数が使えます。Mathematicaを選んだ１番の理由のは，この関数があったことです。

リスト$b$の中の重複を削除して，問題の3，5の入れ替え，1，5の入れ替え，3，6の入れ替えがあるか調べます。あれば，移動の回数をアウトプットします。なければ，次の移動に進みます。手作業でも15回以内で答えは見つかっていたので，繰り返す回数は15としました。

  Do[
    Do[P, {i, Length[b]}];
    b = Union[b];
    Do[
      If[
        b[[i]][[3]] == 5
        &&
        b[[i]][[5]] == 3,
        Print[k]],
        {i,Length[b]}],
    {k, 15}]

   Do[
    Do [P, {i, Length[b]}];
    b = Union[b];
    Do[
      If[
        b[[i]][[1]] == 5
        &&
        b[[i]][[5]] == 1,
        Print[k]],
        {i,Length[b]}],
    {k, 15}]

   Do[
    Do [P, {i, Length[b]}];
    b = Union[b];
    Do[
      If[
        b[[i]][[3]] == 6
        &&
        b[[i]][[6]] == 3,
        Print[k]],
        {i,Length[b]}],
    {k, 15}]

これらのコードはMacBook Proで実行しましたが，10秒かからずに結果が出ました。（実際に20回くらい繰り返すと数分待つ感じだったので，回数が多くなると，時短を考えなくてはならなかったようです。）

（Mathematicaのフロントエンド）

この結果から，新しくわかったこともあります。

(3)の答えは$<3,6>=12$（回）ですが，これは１通りしかありません。途中はわからないのですが，結果の形は1つしかないということです。実際にどのような並びかアウトプットしてみました。

In[15]:= Do[Do
          [P, {i, Length[b]}];
          b = Union[b];
          Do[If[b[[i]][[3]] == 6
              && b[[i]][[6]] == 3,
              Print[b[[i]]]],
               {i, Length[b]}], {k, 12}]

Out[15]:= {1,5,6,4,0,3,7,2,8}

この配置に必ずなるようです。

GeoGebra

これで，今回の問題の答えは確定しました。あとは，入試問題としてどのように出題するかです。この問題は数え上げを頭の中だけで行うのは困難が伴います。実際に動かして（スライドパズルを体験して）最小の移動回数を作業を通して求めてもらうのがよいのではないかと考えました。そのためには，実際にスライドパズルを用意する必要があります。本物を用意しても良かったのですが，iPadを利用した経験があったので，iPadの中にスライドパズルを用意することにしました。昨年の入試でGeoGebraを用いて立体図形の3Dモデルを作ったノウハウがあったので，スライドパズルもGeoGebraで作成することにしました。GeoGebraで公開されている教材の中でスライドパスルのコンテンツもあり，その作り方を参考にして，今回の入試用のものを作成しました。(参考サイト４番目）

（スライダーパズル　入試用にGeoGebraで作成）

動きなどを確認し，昨年と同様の手順で準備をしました。

おわりに

この問題は，昨年の立体図形の問題とは異なり，iPadのスライドパズルを利用しないと，答えを求めるのは非常に難しいです。（頭の中でパズルを動かして考えられる生徒もいるようですが...）
動かし方を組み合わせて計算でできる問題でもありません。それでも，この問題を出題したのは，このような問題にチャレンジしていってほしいというメッセージです。この出題は『数学の問題としては不適切なのではないか？』という指摘も想定しました。ご意見などいただけたら幸いです。いままでは難しいと考えられてきた，避けられてきた問題を，iPadなどのツールを用いることによって，考えたり，解決したり，答えを出したりできるのではと考えています。また，そういった教育を今後も展開していきたいです。

【推薦入試の答え】

(1) $\bm{<3,5>=7}$

(2) $\bm{<1,5>=9}$

(3) $\bm{<3,6>=12}$

【参考URL】

15パズル
https://ja.wikipedia.org/wiki/15パズル

１５パズル自動解答プログラムの作り方
http://www.ic-net.or.jp/home/takaken/nt/slide/solve15.html

Mathematica
https://www.wolfram.com/mathematica/

スライドパズル（GeoGebra 参考サイト）
https://www.geogebra.org/m/b38dxFu2

スライドパズル（GeoGebra 入試用）
https://www.geogebra.org/m/CgABfuYE