いきなりですが問題です.
上の図のように,□に入った隣同士の2つの数について,大きい数から小さい数をひいた答えが,2つの数の下の□に入ります.
段数が増えても同じです.下の図には,□が6つありますが,1から6までの数を1つずつ入れます.(あ)と(い)には,どんな数が入るでしょうか.
元ネタです.
- 作者: 日本数学検定協会
- 出版社/メーカー: 日本数学検定協会
- 発売日: 2017/02/01
- メディア: 単行本
- この商品を含むブログ (1件) を見る
昨日付の記事(イオンへ行ったらあっという間に2時間が過ぎるのはなぜか)およびサブブログの記事(数検10級に見る,かけ算の順序 - かけ算の順序の昔話)で取り上げた本の一つです.第1回の最後の大問(p.15)に,掲載されていました.
さっそくですが解答を考えてみます.5と3は配置済みなので,1,2,4,6をどこに入れればいいかとなります.最下段が「3」なので,(あ)とその右隣には,1,4が入ります.どちらがどちらかは,まだ,分かりません.
まず,(あ)に4が入るとすると,どうなるでしょうか.そうすると,(あ)の右隣には1が入ります.次に,5の右隣に1を入れれば,5−1=4となるのです…が,1は中段で使用済みです.ということで,この選択は失敗です.
それでは,(あ)には4ではなく,1を入れましょう.(あ)の右隣には4が入ります.5の右隣に6を入れれば,6−5=1の関係が成立します.(い)には,最後に残った2を入れます.そうすると,6−2=4となり,うまくいきます.(あ)は1,(い)は2で,全体は以下のようになります.
書籍を離れて問題です.
下の図に1から15までの数を1つずつ入れて,どの左右に隣あった2つの数についても,大きい数から小さい数をひいた答えが,2つの数の下の□に入るようにしましょう.
何通りあるでしょうか.左右反転は別の解答と見なします.
さっそくですが解答です.次の2通りだけです.
何段になっても,条件を満たす配置が求められるよう,Rubyスクリプトを作りました(trisub.rb).Gistに公開しています.引数は,段数を表す正整数nで,デフォルトは3です.nに対し,最上段はn個の箱,その下はn-1個の箱,…,で最下段は常に箱は1個です.総数はmax=n+(n−1)+…+1=n(n+1)/2で,1からmaxまでの数を1個ずつ,箱に入れることとします.
プログラムの中では,nをもとに1からmaxまでの値の配列を生成し,変数aに代入しています.このaの値をもとに,すべての組み合わせを試します.Rubyで順列といえば,Array#permutationというメソッドが使えます.計算量を減らすため,最上段のn個について,すべての組み合わせを獲得してbとし,「隣同士の2つの数について,大きい数から小さい数をひいた答えが,2つの数の下に入る」の要領でひき算をして,bの後ろに順次,追加していきます.最下段の1個に対応する数まで入ったら,bに格納された数値を並べ替えて,1からmaxまでになる(aと等しい)とき,bを解として出力します.
解の出力には「テキスト」と「SVG (Scalable Vector Graphics)」を採用しました.n=5のときの最初の解は,テキストでは以下のとおり出力します.「=>」で区切って3つの配列があり,最初は最上段,次は最上段を含むすべての配置(5個,4個,3個,2個,1個と区切って読みます),最後はすべての配置を小さい数から順に並べ替えたものです.
[6, 14, 15, 3, 13] => [6, 14, 15, 3, 13, 8, 1, 12, 10, 7, 11, 2, 4, 9, 5] => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
SVG画像(XML文書)の生成にあたっては,昨年より利用可能となった,「UDデジタル教科書体」を使用しています(「4」の上部がくっついていないのが特徴的です).Inkscapeを起動して,少し操作したところ,フォントに「UD Digi Kyokasho NK-R」が選べるのを知りました.「4」の文字を表示させて,SVGで保存し,Emacsで開いてみると,text要素のstyle属性の中に「font-family:'UD Digi Kyokasho NK-R'」と書かれていました.Firefoxでも,Chromeでも,UDデジタル教科書体で表示してくれます.
SVGからビットマップ(PNG)への変換について,Cygwinのconvertコマンドも,inkscapeコマンドも,このフォントを認識してくれず,「4」の上部がくっついたゴシック体で,PNG画像が作られてしまいました.GUIで動かすInkscapeのフルパスを指定して,「/cygdrive/c/Program\ Files/Inkscape/inkscape.exe -f SVGファイル名 -e PNGファイル名」の形で実行してみると,期待通りのPNG画像になりました.
nを1から5までに変えたときのテキスト出力は以下のとおりです.なおn=6は数分の計算ののち,一つも解を出力しませんでした.7以上で解は期待できません.
[1] => [1] => [1]
[1, 3] => [1, 3, 2] => [1, 2, 3]
[2, 3] => [2, 3, 1] => [1, 2, 3]
[3, 1] => [3, 1, 2] => [1, 2, 3]
[3, 2] => [3, 2, 1] => [1, 2, 3]
[1, 6, 4] => [1, 6, 4, 5, 2, 3] => [1, 2, 3, 4, 5, 6]
[2, 6, 5] => [2, 6, 5, 4, 1, 3] => [1, 2, 3, 4, 5, 6]
[4, 1, 6] => [4, 1, 6, 3, 5, 2] => [1, 2, 3, 4, 5, 6]
[4, 6, 1] => [4, 6, 1, 2, 5, 3] => [1, 2, 3, 4, 5, 6]
[5, 2, 6] => [5, 2, 6, 3, 4, 1] => [1, 2, 3, 4, 5, 6]
[5, 6, 2] => [5, 6, 2, 1, 4, 3] => [1, 2, 3, 4, 5, 6]
[6, 1, 4] => [6, 1, 4, 5, 3, 2] => [1, 2, 3, 4, 5, 6]
[6, 2, 5] => [6, 2, 5, 4, 3, 1] => [1, 2, 3, 4, 5, 6]
[6, 1, 10, 8] => [6, 1, 10, 8, 5, 9, 2, 4, 7, 3] => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[6, 10, 1, 8] => [6, 10, 1, 8, 4, 9, 7, 5, 2, 3] => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[8, 1, 10, 6] => [8, 1, 10, 6, 7, 9, 4, 2, 5, 3] => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[8, 3, 10, 9] => [8, 3, 10, 9, 5, 7, 1, 2, 6, 4] => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[8, 10, 1, 6] => [8, 10, 1, 6, 2, 9, 5, 7, 4, 3] => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[8, 10, 3, 9] => [8, 10, 3, 9, 2, 7, 6, 5, 1, 4] => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[9, 3, 10, 8] => [9, 3, 10, 8, 6, 7, 2, 1, 5, 4] => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[9, 10, 3, 8] => [9, 10, 3, 8, 1, 7, 5, 6, 2, 4] => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[6, 14, 15, 3, 13] => [6, 14, 15, 3, 13, 8, 1, 12, 10, 7, 11, 2, 4, 9, 5] => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[13, 3, 15, 14, 6] => [13, 3, 15, 14, 6, 10, 12, 1, 8, 2, 11, 7, 9, 4, 5] => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
得られた解の数は,1+4+8+8+2=23個なのですが,(あ)と(い)の入った画像を加えて,24個にすると,画像一覧でうまく収まりました.