【随時更新】解答に必要な機能まとめ - ニート歴10年からの数学日記と【随時更新】計算量の減らし方まとめ - ニート歴10年からの数学日記を使って、算数オリンピックについて考察していく。
グラフや幾何学の問題や、記述に関するメタ的な問題以外の今までに無い種類の問題について考察する。
いくつかグラフや幾何学の問題か分からなかったものがあったが、飛ばした。どうせいつかは全ての問題を解く。
『「あみだくじ」というくじがあります。
＜あみだくじの作り方＞
①同じ長さのたて棒を人数分ひく。
②となりどうしのたて棒を、たて棒に垂直なよこ棒でつなぐ。
③たて棒とよこ棒が十字に交わってはいけない。
＜あみだくじの進み方＞
①たて棒の一番上のはしから出発して、下に向かって進む。
②曲がりかどでは必ず曲がる。
たとえば、図1のあみだくじでは、Aは③、Bは②、Cは①に進みます。
（図1） 略
さて、アからコまでの10人があみだくじをしたところ、それぞれ図2のような位置に進みました。かくれている部分によこ棒は最低何本あるでしょうか？
（図2） アイウエオカキクケコ
エケアカウコキイクオ』
あみだくじ[ア, イ, ウ, エ, オ, カ, キ, ク, ケ, コ]。
[
あみだくじ[?1] ← あみだくじ[?1 + 1]。（相互作用しないという想定）
あみだくじ[?1 + 1] ← あみだくじ[?1]。
]
〜の数 = a。[あみだくじ] = [エ, ケ, ア, カ, ウ, コ, キ, イ, ク, オ]。
aが最小になるように設定。
[結果]におけるa。
これは答えを見るまで分からなかったのだけど、あみだくじでは、同じよこ棒を同じ方向には通らないらしくて（通ったら同じ答えになる）、でよこ棒一本で一つ移動するから、どれだけズレたかだけ見れば良い。
でしかし見かたが独特で、まずアに着目して、元々アの右にあったのに左に来ているのを数えると、エとケで2。これをイ以降でも続ければ答えが出る。で説明が終わっている。
図1の例にしても、どれだけズレたかを数えただけでは答え（実際の図では3本だった）に行かないと思うのだけども。何かアルゴリズムの並び替えみたいなことなのかもしれない。よく分からない。
後日に見直してみると（複数日に分けて書いている）、つまり答えから逆方向に、アから始めて少しずつ問題を切り分けていくような感じか、最初からアの左にあるカナは無い。最低でも例えばアはそれだけ移動しなければいけないから、最低限それだけは必要なのは保証されている。毎回その最低限でできるかは保証されていない気もする。
『次の図のA、B、C、D、Eの5つのお皿には、それぞれいくつかのキャンディがのっています。このうち1皿を取るか、つながった2つ以上のお皿を取ることによって（たとえば、AとB、DとEとA、など）、お皿の上のキャンディで、1から21までのすべての個数を作ることができます。それぞれのお皿にのっているキャンディの個数を求めなさい。
（図） 循環リストで[A, B, C, D, E]』
複数の皿[A, B, C, D, E]。
複数の皿[?] ∪ 複数の皿[?1] + 複数の皿[?1 + 1] ∪ 複数の皿[?2] + 複数の皿[?2 + 1] + 複数の皿[?2 + 2] ∪
複数の皿[?3] + 複数の皿[?3 + 1] + 複数の皿[?3 + 2] + 複数の皿[?3 + 3] ∪ [複数の皿]の総和 は[1~21]を含む。
[結果]における[A, B, C, D, E]。
でこれまた答えを見ると、そもそも、1つ選ぶ場合が5通り、2つ選ぶ場合が5通り、3つ選ぶ場合が5通り、4つ選ぶ場合が5通り、全部選ぶ場合が1通りで、全部で21通り。これを明らかにすることによって、全体を利用して、他のと被ったらその選択肢は違う、という絞り方ができるようになる。
で、1と2をくっつける所から始まって、今までに無い数字が出てきたらその数字を使う、その数字の位置は全通りを試す、という直線的な探索計画を立てることができるようになる。結果1と2はくっつけないことが分かる。
『193人の人が横一列に並んですわっています。
まず、まん中の1人が立ちあがりました。そこからは、次のルールでみんな立ったりすわったりします。
① となりの人が立ちあがってから、1秒後に、自分も立ちあがります。
② 立ちあがったら、1秒後にすわります。
③ ただし、両どなりの人が同時に立ちあがった場合は、1秒たっても自分はすわったままでいます。
（1）最初の1人が立ちあがってから8秒後に、何人が立ちあがりますか。
（2）96秒後には何人が立ち上がりますか。』
[カウント] ← 0。
[ループ] ← [
[
[カウント] = 96。
[人] ← [座り]。
,
[それ以外]。
[人] ← [立ち]。
]の1つ。
[カウント] ← +1。
]
〜の数 = 192。
[横一列の人] ← [ループ]における[人]。（普通に挿入した方が簡単だったか）
[
[一秒前] ← [横一列の人]。
[
[一秒前][?1 - 1] = [立ち]。
[一秒前][?1 + 1] ≠ [立ち]。
[一秒前][?1] = [座り]。
[横一列の人][?1] ← [立ち]。
,
[一秒前][?1 + 1] = [立ち]。
[一秒前][?1 - 1] ≠ [立ち]。
[一秒前][?1] = [座り]。
[横一列の人][?1] ← [立ち]。
,
[一秒前][?1] = [立ち]。
[横一列の人][?1] ← [座り]。
,
[一秒前][?1 + 1] = [立ち]。
[一秒前][?1 - 1] = [立ち]。
[横一列の人][?1] ← [座り]。
]
〜理論上あり得る全ての[横一列の人][?1]において。
]
〜の数 = 96。
[結果]における[横一列の人]の[座り]の数。
答えでは、この問題は図として書き出してみないと分からない問題で、（1）で実際に書き出してみて、2の倍数だと同じ数になるという法則性を発見して、（2）に答えるということらしい。このルールを見つければ、96→48→24→12→6→3で、3までで答えが分かる。
答えの図を見ると、ライフゲームみたいな感じだ。区分的にはルール？なのかな？
『1から50までの数字を一つずつ書いたカードが50枚あります。このカードは、片面が青に、もう一つの面が赤にぬられていて、どちらの面にも同じ数字が書かれています。生徒が50人いるクラスの先生がこの50枚のカードをすべて青の面を上にして机に並べ『さあ、これから出席番号順に1番の人から一人ずつ前に出てきて、自分の出席番号の倍数になるカードはすべてうらがえし、青だったら赤に、赤だったら青にしなさい』と言いました。
さて、出席番号50番の最後の生徒が先生に言われたようにうらがえしたあと、赤の面が上になっているカードは何枚ありますか。』
カード集[要素が50個ある集合]。
[カウント] ← 0。
[
[
カード集[?1 - 1] = 青。
カード集[?1 - 1] ← 赤。
,
カード集[?1 - 1] = 赤。
カード集[?1 - 1] ← 青。
,
それ以外。
カード集[?1 - 1] ← 赤。
]
〜理論上あり得る全ての[?1 : ?1 = [[カウント]+1] * ?2, 1 <= ?1 <= 50]において。
[カウント] ← +1。
]
〜の数 = 50。
[結果]における[カード集]の[赤]の数。
答えを見る。
約数を考えると、例えば24は、1と24、2と12、3と8、4と6、という風になる。つまり1と24の時にひっくり返って、2と12の時にひっくり返って、という風になって元に戻る。
この約数が奇数個の数字を考えれば良い。それは36のような同じ数字の掛け合わせの時だ。よって、1、4、9、16、25、36、49の7個。
『平太君のクラスの中から4人の委員を選ぶことになりました。クラスの全員がそれぞれ、自分を含めたクラス全員の中から4人の名前を選んで1枚の投票用紙に書きました。
平太君がすべての投票用紙を集めて調べたところ、おもしろいことに気づきました。2枚の投票用紙をどのように取り出してみても、どちらの投票用紙にも共通して書かれている名前が必ず1人だけ見つかるのです。
このクラスの人数は何人ですか。ただし、1枚の投票用紙に同じ名前を2人以上書いた人はいませんでした。』
クラス[要素がa個]。
[
クラス[?1] ← 4個 ← [1 <= ? <= [クラス]の数]のカブり無し。
]
〜理論上あり得る全てのクラス[?1]において。
[理論上あり得る全ての[クラス][?2] ∩ 理論上あり得る全ての[クラス][?3]]の数 = 1。（?2と?3は必ず≠か、もしそうなら?1はどうするか）
[結果]におけるa。
答えを見ると、仮に10人のクラスだったとして、合計40票が10人に分配される。最高得票数が3票だったら合計30票なので、少なくとも1人は4票以上獲得した人がいて、その人を仮にAさんとする。
用紙1、2、3、4にAさんの名前が書かれていて、もし5枚目の紙にAさんの名前が書かれていると、6枚目の紙にもAさんの名前を書くしか無い。なぜなら1人以外は違う名前を書かなければいけないし、だから12345の紙はAさん以外はバラバラで、それらを書くことはできない。これでは、20人のクラスだと、Aさん以外に60人いなければならない。だからAさんの最高得票は4票までで、これは他の人間にも言えるので、全員が4票ずつ得ている。
用紙1234で13人だが、もし14人目がいると、その14人目はどこかに書かれて無ければならないが、同時に用紙1234のAさん以外も書かれて無ければいけないので、これは矛盾。
よって13人以外は無理で、最後に13人で問題があるかを確認する。
というようなことが答えに書いてあるわけだけど、難しすぎる。仮定して矛盾して、で輪郭を求めていく。
思ったのだけど、フローの記述は本質では無いかもしれない。もちろん土台なので幾何学やグラフの問題でもまずは記述を試みるが、難しいのはそれを軽くすることなのであって、慣れてきたら書かなくても良いかもしれない。
『ある整数を、0より大きい整数の和で表わす方法が何とおりあるかを考えます。使う数が同じで順番だけが違うものは、1とおりに数えます。
また一個の整数だけを使うものも、1とおりとして数えます。0を使ってはいけません。
（1）たとえば、6を三個以下の整数の和で表わす方法は、
1
5 + 1
4 + 2
3 + 3
4 + 1 + 1
3 + 2 + 1
2 + 2 + 2
の7とおりあります。
では、50を三個以下の整数の和で表す方法は、何とおりありますか。
（2）7を3以下の整数の和で表す方法は、
3 + 3 + 1
3 + 2 + 2
3 + 2 + 1 + 1
2 + 2 + 2 + 1
3 + 1 + 1 + 1 + 1
2 + 2 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 1
の8とおりあります。
では、50を3以下の整数の和で表わす方法は、何とおりありますか。』
50 = a。
50 = b + c。
50 = d + e + f。
[答え] ← 理論上あり得る全てのaの数 + 理論上あり得る全ての[b, c]の数 / 2 + 理論上あり得る全ての[d, e, f]の数 / 6。（他に表現方法がある気もする）
[結果]における[答え]。
50 = [3]*g + [2]*h + [1]*i。
[結果]における理論上あり得る全ての[g, h, i]の数。
単純ミスをしていたので答えを見ると、まず理論上あり得る全ての[b, c]の数は49通りだが、答えは25通り。
で、dが1の時は24通り、2の時は23通り、3の時は21通り、同様に4では20通り、5では18通り、6では17通り、7では15通り。つまり1、2、1、2という規則へ減っている。
そこで2つずつペアにすると、(24+23)、(21+20)、(18+17)と、6ずつ減っているので、そのまま続けて最後には5。更に最初の(24+23)と最後の5を足して52、(21+20)と5の一つ前を足しても52、でそういうのが4セットできるので、52*4=208。正解は1+25+208=234通り。
次の問題も、gがマックスで16、hは2通り、残りは自動的に埋まる。15だと3通りで、14だと5通り、13だと6通り、12だと8通り、11だと9通り、という前と似たようなパターン。(2+3)、(5+6)、(8+9)と考えると6ずつ増えていて、最後を考えると(23+24)。5+47=52で、いろいろあって、52*4+26=234通りが答え。