97年度ジュニア算数オリンピックへの考察
俺の直感は書くなと言っているが、自分の直感はむしろ当たらない事が多いので、書くことにする。運で上手く行くことはあるが、それは俺の場合は最初の感覚とはほとんど関係無い。自転車で横の道に入ったら面白いということはあるけども、今まで感覚に反するのに同じように上手く行った場合が自分の場合は結構あった、直感には反するが。
このページではプログラミングはしない。ジュニア算数オリンピックの、幾何学と、記述方法に関するメタ的な問題以外の問題への考察を書き表す。各項ごとに書いて、それぞれ追記で考察も加えていく。
直接的にプログラミングはしないが、『ペーパープログラミング』と自分で呼んでいる方法は使っていこうと思う。ただフローチャートで各ステップを日本語で書いていくだけのことだけども、構想段階でしかも大量に問題を扱わなければならない今回に限って、まあ方法として必要だと思ったのでやる。
追記：しかし結果このページでは今の所ペーパープログラミングはやらなかった。
後日追記：制約を入れたら答えを弾き出すようなプログラム、つまり制約プログラミングと呼ばれているものが必要なのは分かった。ただ機能が素人にはゴチャゴチャしているので、手順を書き出しておいて、必要な機能が見つかり次第に実装できるようにする。最悪機能が見つからなかった場合は、こういう機能があればできるという予想だけ書いて飛ばすことにする。
後後日追記：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
トライアル問題
問題６
『ゆうや君のトランプは、全部で52枚あるはずなのに、ハート、ダイヤ、スペード、クローバーの4種類のうちどれか1種類のカードだけが10枚なくなって、42枚になってしまいました。
どの種類の10枚がないのかを、1枚ずつめくってしらべていこうと思います。
もっとも早くわかるのは、何枚めくったときでしょうか。
また、もっともおそくわかるのは、何枚めくったときでしょうか。
ジョーカーは、初めから1枚も入っていないものとして考えなさい。』
https://after10.hatenablog.com/entry/2019/05/07/065700
問題８
『整数の中には、「2個以上の連続する整数の和」の形で表わせるものがあります。
たとえば、9は 9 = 4 + 5
9 = 2 + 3 + 4
のように、「2個以上の連続する整数の和」の形で表わす方法が2通りだけあります。
（問い１）このような表し方が3通りだけある整数のうち、いちばん小さいものをもとめなさい。
（問い2）このような表し方が5通りだけある整数のうち、いちばん小さいものをもとめなさい。』
この問題は、例えば「2個の連続する整数の和」と日本語で書かれているものを、「n+(n+1)」のような、数学的な形式での表現に落とし込むことができるかにかかっている。後は小さい数字からマッチしていけば良い。
この問題から、まず現段階として「自然言語を形式に落とし込む→プログラムに落とし込む」という作業の流れが仮説として思い描かれる。
後日追記：これは制約プログラミングを使わず解決する。
ファイナル問題
問題３
『9枚のカードに1から9までの整数が一つずつ書かれています。
これらの9枚のカードを使って、平太君と真理さんが次のようなゲームをしています。
（ゲームのルール）
1．9枚のカードを数字が見えるようにならべて置く。
2．交互に1枚ずつ取る。
3．2人が取ったカードの全部の数字をたしていく。
4．この2人のカードの和が40以上となるカードを取った方を勝ちとする。
平太君が先攻、真理さんが後攻とすると、ある戦法を使えば、必ずどちらかが勝つことができます。
さて、必ず勝てるのは、平太君、真理さんのどちらでしょうか。どちらかに○をつけて答えなさい。
また、そのときの戦法をわかりやすく説明しなさい。』
ぶっちゃけ、筆者はこの問題の解答を見た。分からなかった。どんどん見ていきたい。
答えは「必ず勝てるのは先攻の平太君で、まず5を取り、その後に相手が1〜4を取った時は和が5になるように、例えば2だったら3を選び、6〜9だったら和が15になるように、例えば6だったら9を選ぶ」だった。
この解答はかなり偶然的というか発明的というか、倍数が5になるように取るという簡単な発想では無く、例えば最終値が60であり得ないがもう2回15があったら無理で、分岐する方法1と方法2が絶妙に補い合っている。
まあしかし、発想のキーはフローチャートに集合論を見出す、ということなのかもしれない。例えば似たような問題の同じ数字を再び選択できるパターンでは、総和が10になるようにして、10の倍数でこちらが勝つということになるわけだけど、10の倍数で合わせていくことで各往復ターンごとに同一性が出る。フローチャートは発散していくので、そこに無理やり異質である集合論を見出して落とし込んでいくのがキーになるのかもしれない。
後日追記：これはフローチャートにむりやり同一性を見出して計算量を少なくするという工夫を採用した時点で、もう解答に行き着いていると言えるのではないか。解答法を統一するという目的に対しては、これで十分なのではないか。
問題6
『A国、B国、C国、D国の4か国、4組の夫妻が、あるパーティーでまるいテーブルを囲んで座ることになりました。
ところが、8人はみんなやきもちやきなので、自分の夫が他の国の女性のとなり（あるいは、自分の妻が他の国の男性のとなり）の席にならないように座ることにしました。
このような座り方は全部で何通りありますか。A国の夫の席がすでに決まっているものとして答えなさい。
また、席順が同じでも、右回りと左回りでは別の座り方とみなします。』
夫婦が必ず隣り合うとは限らず、女と男がかたまって座って接する所だけが夫婦というパターンがある。
この問題はグラフの問題だ。人間の場合はその2つの形態があることを思いついて、その中身の場合分けをするわけだけども。
自分はこの文章を書いていて2つ目を思いついて、発想ルートとしては「夫婦は可」というルールから1つ目を、「同性は可」というルールから2つ目を発想するわけだけども、まあそしてその間の形態に思い至って無理だと分かって、という感じ。
具体的な夫婦や国を考える前に、夫婦か同性かの2択でシミュレートして無理かどうかを確かめる。
追記：プログラムで解くと言うと全自動を思い浮かべられるかもしれないが、この問題を分けることで計算量を減らすというのもアルゴリズムの概念なのであって、このレベルで現実化すればもう目標に対して十分だと言える。（というよりむしろそれ以上は目的から外れる。）
後日追記：よく考えたら、夫婦4組がそれぞれ同性同士をくっつけるように座るのがあり得た。しかし制約プログラミングで解くなら、「全体の中の1つがA国の男」みたいな制約を8回繰り返して、「リストの番地+1は同性か同じ国で無ければならない、かつ最後の番地は最初の番地と同性か同じ国でなければならない」みたいな制約を入れて、例えばリストの最初をA国の男にすれば良いのかもしれない。
後後後日追記：『[円リスト]の中に[A国男、A国女、B国男、B国女、C国男、C国女、D国男、D国女]からカブり無しで8個』『円リストnの性別 = 円リストn+1の性別 or 円リストnの国 = 円リストn+1の国』。
