98年度ジュニア算数オリンピックへの考察
このページではプログラミングはしない。ジュニア算数オリンピックの、幾何学と、記述方法に関するメタ的な問題以外の問題への考察を書き表す。各項ごとに書いて、それぞれ追記で考察も加えていく。
直接的にプログラミングはしないが、『ペーパープログラミング』と自分で呼んでいる方法は使っていこうと思う。ただフローチャートで各ステップを日本語で書いていくだけのことだけども、構想段階でしかも大量に問題を扱わなければならない今回に限って、まあ方法として必要だと思ったのでやる(と書いたがやらない場合が多い)。
後日追記:制約を入れたら答えを弾き出すようなプログラム、つまり制約プログラミングと呼ばれているものが必要なのは分かった。ただ機能が素人にはゴチャゴチャしているので、手順を書き出しておいて、必要な機能が見つかり次第に実装できるようにする。最悪機能が見つからなかった場合は、こういう機能があればできるという予想だけ書いて飛ばすことにする。
後後日追記:googleのOR-toolsを使うことにした。どこだったか見てインストールして、https://developers.google.com/optimization/cp/cp_solverとhttps://github.com/google/or-tools/blob/stable/ortools/sat/doc/reference.mdを参考にしつつ。他にはhttps://labix.org/python-constraintとhttps://github.com/eomahony/Numberjackを見つけたけど、まあ比較的ドキュメントとかサンプルコードが充実しているように見えたんで。以下は全部「後後日追記」で解決していくけど日は別々。
後後後日追記:諦めて解答に必要な制約をまとめるだけにした。https://after10.hatenablog.com/entry/2019/05/25/140213
トライアル問題
問題2
『下の表の①〜⑯のそれぞれの場所に、5円玉、10円玉、50円玉のどれかが1枚ずつ置いてあります。
表の合計は①+②+③+④=75、①+⑤+⑨+⑬=80のように、たて、横一列にならんだ4個の硬貨の合計金額を示しています。
このとき、表の①〜⑯のそれぞれの場所には、どの硬貨が置いてありますか。
置いてある硬貨が5円玉のときは「5」、10円玉のときは「10」50円玉のときは「50」を書き入れなさい。
合計 | |||||
---|---|---|---|---|---|
① | ② | ③ | ④ | 75円 | |
⑤ | ⑥ | ⑦ | ⑧ | 65円 | |
⑨ | ⑩ | ⑪ | ⑫ | 35円 | |
⑬ | ⑭ | ⑮ | ⑯ | 30円 | |
合計 | 80円 | 30円 | 20円 | 75円 |
それぞれの行・列ごとに実は使われる硬貨は決まる値になっている。
それらを発見する時に計算量をより少なくするならば、全体があるなら否定の否定を狙って、例えば5円と10円だけで試して無理なら50円を挿入して残り3つで続きをやる、という形になるのだろう。
そこまでできたら、こういう表のような形で論理的に答えを弾き出すプログラムがネット上にあるはずだから、後は普通にそれを探してくるということになるだろう。
後日追記:それぞれのマスで、数値が5か10か50か、という制約を入れる。後は縦と横の足し算を制約に入れて実行。元々の方法では、例えば5円がA・10円がB・50円がCだとして、全体の中で2つがAというような制約を入れれる必要がある。
後後日追記:
from ortools.sat.python import cp_model model = cp_model.CpModel() x1 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x1') x2 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x2') x3 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x3') x4 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x4') x5 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x5') x6 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x6') x7 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x7') x8 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x8') x9 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x9') x10 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x10') x11 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x11') x12 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x12') x13 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x13') x14 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x14') x15 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x15') x16 = model.NewIntVarFromDomain(cp_model.Domain.FromValues([5, 10, 50]), 'x16') model.Add(x1 + x2 + x3 + x4 == 75) model.Add(x5 + x6 + x7 + x8 == 65) model.Add(x9 + x10 + x11 + x12 == 35) model.Add(x13 + x14 + x15 + x16 == 30) model.Add(x1 + x5 + x9 + x13 == 80) model.Add(x2 + x6 + x10 + x14 == 30) model.Add(x3 + x7 + x11 + x15 == 20) model.Add(x4 + x8 + x12 + x16 == 75) solver = cp_model.CpSolver() status = solver.Solve(model) if status == cp_model.FEASIBLE: print('x1 = %i' % solver.Value(x1)) print('x2 = %i' % solver.Value(x2)) print('x3 = %i' % solver.Value(x3)) print('x4 = %i' % solver.Value(x4)) print('x5 = %i' % solver.Value(x5)) print('x6 = %i' % solver.Value(x6)) print('x7 = %i' % solver.Value(x7)) print('x8 = %i' % solver.Value(x8)) print('x9 = %i' % solver.Value(x9)) print('x10 = %i' % solver.Value(x10)) print('x11 = %i' % solver.Value(x11)) print('x12 = %i' % solver.Value(x12)) print('x13 = %i' % solver.Value(x13)) print('x14 = %i' % solver.Value(x14)) print('x15 = %i' % solver.Value(x15)) print('x16 = %i' % solver.Value(x16))
x1 = 10 x2 = 10 x3 = 5 x4 = 50 x5 = 50 x6 = 5 x7 = 5 x8 = 5 x9 = 10 x10 = 10 x11 = 5 x12 = 10 x13 = 10 x14 = 5 x15 = 5 x16 = 10
問題3
『数字の0〜5が一つずつ表に書かれた白と黒のカードが6枚ずつ合計12枚あります。
この12枚のカードの中から白1枚、黒1枚の合計2枚のカードを抜きとり、残り10枚のカードを裏にして次のルールでならべたところ下の図のようにならびました。
ルール1.数字の小さい順に左から右へとならべる。
2.白と黒のカードの数字が同じ場合には必ず黒のカードを白のカードの左にならべる。
(図) 黒白黒白白黒白黒黒白
最初に抜き取った白と黒のカードの数字はそれぞれいくつですか。』
人間だったら「黒白黒白黒白黒白黒白黒白」を思い浮かべて、その差分から一瞬で分かるのだけど。厳密には黒でのシミュレートと白でのシミュレートを分けて、部分的な特徴(白が2つ続くということはその間に黒があったはずだ)に着目して答えに至ってそれを合わせることができるのだけども。
機械だったら6*6=36で36通りを再現して、マッチするしか無いのかねえ。分からん。
後後後日追記:『[ ]の中に[(白,0),(白,1),(白,2),(白,3),(白,4),(白,5),(黒,0),(黒,1),(黒,2),(黒,3),(黒,4),(黒,5)]からカブり無しで12個』、『並びの制約』『制約の優先順位』で、1『リストnの数値 < リストn+1の数値』、2『黒 < 白』。
問題4
『A〜Fの6チームでサッカーのリーグ戦(総当り戦)をしています。
どのチームも15試合もしくは16試合が終了した時点での順位は下の表の通りです。
順位は勝率(勝ち数を試合数で割ったもの)順にならんでいます。
勝ち数、敗け数の書かれていない部分(ア〜キ)に適当な数字を入れなさい。ただし引き分けはありません。
勝ち数 | 負け数 | |
---|---|---|
1位 Aチーム | (ア) | 5 |
2位 Bチーム | (イ) | 7 |
3位 Cチーム | (ウ) | (カ) |
4位 Dチーム | (エ) | (キ) |
5位 Eチーム | (オ) | 8 |
6位 Fチーム | 4 | 12 |
この問題は答えを見た。で、要するに「2位の負け数は7だから勝ち数は8か9、5位の負け数は8だから勝ち数は7か8、ここでそれぞれ9と7じゃないと3位と4位が困る。でその辺りで2位から6位が埋まって1位が埋まる。」という感じだったと思う。
(イ)と(オ)のあり得る場合を出すまでは良いとして、勝率(勝ち数を試合数で割ったもの)順というルールで3位と4位を弾き出すのがプログラム的には課題になるのかもしれない。
何というか、どこまでプログラムでやれば良いかがまだ掴めていない。数学の様々なジャンルを同じ枠組みで解くという話で、で解き方という意味では簡単になるだろうと思うのだけども。まあ全部で15か16だから負け数が8だったら勝ち数は7か8っていうのも1つのルールだし、ルールとルールでこの結果を弾き出したりとかできたりすんのかなあ。
この15か16というのも、プログラム的には(15-負け数)or(16-負け数)という風になるのだろうし、2つのルールの結果を合わせて1つと見なすみたいな動きが必要になるはずなんだよね。否定の否定みたいな話も含めて、探せばそういうプログラムが見つかると思うんだけどな、「制約プログラミング」とかそういうようなイメージで。
後日追記:「(Aチーム勝ち数 / 勝ち数 + 負け数) > Bチーム > Cチーム > Dチーム > Eチーム > Fチーム」、「勝ち数 + 負け数 = 15 or 16」。前者はあるとして、後者のorを実現する機能があるかどうか。
問題6
『同じ大きさの10個の玉A〜Jがあります。これらの10個の玉のうち、8個は1個の重さが10gで、残りの2個は1個の重さが12gです。
これらの玉をはかりにかけたら下の(ア)〜(ウ)のようになりました。
はかりのかたむきから考えて、12gの玉はどれとどれですか。
(ア)「A + B + C < D + E + F」 (イ)「G + H > I + J」 (ウ)「B + H + J = E + G + I」』
実際には(ア)(イ)(ウ)は、はかりの絵で示されていて、値が大きい方が下に傾いている。
どちらが大きいかという意味で、1つ前の問題と同じ種類のルールが出てきている。
後日追記:これも、全体の中の2つが12gというような制約を入れる機能があれば解決する。要素の中で一番数値が大きなものを弾き出す機能があれば、それでも一応解決はする。
後後後日追記:『[A,B,C,D,E,F,G,H,I,J]の中に[12,12]からカブり無しで2つ』『[A,B,C,D,E,F,G,H,I,J]の中に[10,10,10,10,10,10,10,10]からカブり無しで8つ』、後は数式を制約として入力。
ファイナル問題
問題6
『時計をいたずらして、長針と短針の区別ができないようにしてしまいました。
でも、2つの針の指す位置から判断して、たいていの場合、1通りの正しい時刻がわかります。
それでも、正しい時刻がどうしても2通り考えられる場合があります。
それは正午から午前0時までの12時間で何回あるでしょう。
ただし、正午と午前0時は含みません。また、秒針はないものとします。』
これは問題分を書いている途中に気づいたのだけど、表記の問題なのでパス。
今回の考察を終えて
もし制約プログラミングがキーになって、しかもこれからの問題もそれで解けてしまいそうなら、この考察もここで打ち切って習得を目指したい。
どうもジュニア算数オリンピックと算数オリンピックで結構問題がかぶっていて、多分学校での進み具合に合わせて問題が差し替えられてるんじゃないかと思うけど、案外サラッと攻略できてしまうのかもしれない。取らぬ狸の皮算用って奴だが。
最終的にはユークリッド幾何学をどう制約プログラミングで解くかっていう、結構聞いたことがあるような研究テーマになるのかもしれない。まあでもその場合でも、数学基礎論とかプログラミング意味論とか集合論とフローチャートの越境とか、結構本質的な概念を持っているんで、他の研究者と比べて不利ってことは無いと思うけど。
まあ普通に明日あたりにまた99年度の考察を更新することになるのかもしれないが。
追記:いや、明日はそこら辺を調べるんで、更新するなら明後日だな。