算数オリンピックの問題 その１０

メチャメチャだけど【随時更新】解答に必要な機能まとめ - ニート歴10年からの数学日記と【随時更新】計算量の減らし方まとめ - ニート歴10年からの数学日記を使って、算数オリンピックについて考察していく。
グラフや幾何学の問題や、記述に関するメタ的な問題以外の今までに無い種類の問題について考察する。
　

03年度ファイナル問題　問題1

『あるきまりに従って、式を作っていきます。
1+2=3 4+5+6=7+8 9+10+11+12=13+14+15 ……………
上の各式の「計算結果」は、3、15、42、…です。
2003が含まれる式の「計算結果」を求めなさい。』

i := 0;
i_sum := 0;

{
　i := i + 1;

　i_sum := i_sum + i;

　{
　　i_sum == ? * 2;

　　j := 0;
　　j_sum := 0;
　　j_list := [];

　　{
　　　j := j + 1;

　　　j_list := 追加 := j;
　　　j_sum := j_sum + j;
　　}
　　~{
　　　j_sum == i_sum / 2;

　　　j_list_2 := [ ];

　　　{
　　　　j := j + 1;

　　　　j_list_2 := 追加 := j;
　　　　j_sum := j_sum + j;
　　　}
　　　~j_sum == i_sum;

　　　i_sum := 0;

　　　{
　　　　i >= 2003;

　　　　result := j_list, j_list_2;

　　　　ループ全体を終了;
　　　　,
　　　　それ以外;

　　　　ループを2個抜け出す;
　　　}.1;
　　　,
　　　j_sum > i_sum / 2;

　　　i_sum := 0;

　　　ループを2個抜け出す;
　　}.1;
　　,
　　それ以外;
　}.1;
}
~;

結果におけるresult;

この記述用言語の悪い所が出たなと思う。普通のプログラミング言語では、条件式があってネストしてその中に実行する文が書かれる。これは制約があって、それらを同時に実行するという想定だから、そういう記述にならないし、だから構造が分かりにくくて読みにくい。
もしif文でも似たように記述できるなら、そちらの方が良いかもしれない。内容的には今までと変わらないんで、余計と言ったら余計なのかもしれないけど、重要なのは問題文を記述できるということであって、どう記述するかというのはそこまで問題では無いし、それなら分かりやすい方が良い。
次の問題からはそういう風に記述してみる。多分、for文もそういう風に記述する。

よく分からないからとりあえず、15を含む数列を探してみる。増加分をAとして、少なくとも「(15+15+A)/2*(15+A-15)」、「(30+A)/2*A」が整数でなければならない。つまり増加分Aは少なくとも偶数。15 16 17 18 19 20 21...
で今気付いたけど、例えば「4+5+6=7+8」は、7と8を2ずつ並行移動して、その減らした分が2*2で4になっているのではないか。「9+10+11+12=13+14+15」も、13と14と15を3ずつ平行移動して、その減らした分が3*3で9になっている。
つまり次は、「16+17+18+19+20=21+22+23+24」であるはず。実際、「90=90」で成立する。でなぜか次も5*5の25になっている。そこから10個で35。その次も6*6の36だ。
40*40が1600で、50*50が2500。45*45がgoogle検索で2025。44*44が1936。
つまり、パターンからして、全体は1936~2024。左辺は1936+44=1980まで、右辺は1981~2024だろうと推測できる。
数列の並行移動と、謎の法則を発見できるかどうかが鍵なんだろうか。この問題は正直よく分からない。
　

03年度ファイナル問題　問題3

『図の16個のマスの中からルール①、②に従って6個の数字を取り除きます。

ルール①　たての列、横の行とも、残る数字の個数がすべて偶数になるようにする。
ルール②　残る10個の数字の和が最大になるようにする。

（問い1）残る10個の数字の和はいくつですか。
（問い2）6個の数字の取り除き方は全部で何通りありますか。
　

7	9	11	13
3	5	7	9
5	7	9	11
9	11	13	15

』

table[0] := [7, 9, 11, 13];
table[1] := [3, 5, 7, 9];
table[2] := [5, 7, 9, 11];
table[3] := [9, 11, 13, 15];

() := 移動で6 := table[?][?];

table[0][?].数 == 2 * ?;　　？？every~{table[?1][?] == 2 * ?; table[?][?2] == 2 * ?;}では駄目だったか。?の扱いが分からない。anyとeveryの違いだと思うが。
table[1][?].数 == 2 * ?;
table[2][?].数 == 2 * ?;
table[3][?].数 == 2 * ?;
table[?][0].数 == 2 * ?;
table[?][1].数 == 2 * ?;
table[?][2].数 == 2 * ?;
table[?][3].数 == 2 * ?;

table[?][?].+が最大になるように設定;

結果における(table[?][?].+);
結果におけるtable;

まず、一列全部無くなることは無い。そうすると、残り2つでどうやっても3個の行が出てきてしまう。つまり、無くなるのは必ず2個か0個だ。1個でも3個でも全部でも無い。
次に、最善から考えていく。3と5と7を取り除くのが、可能だとしたら最善だ。しかし3個や1個の行や列がある。この時、3を11にずらせば一応各列が偶数個にはなるんだが、しかし11なので最善かは分からない、この場合は42。次に9も含めて考えてみる。
この時、一番端っこの飛び出している9の2つは、9までで作るということなら考えなくても良い。他と共有する行あるいは列が無い。で、7と9が2個だけの行とまた列があるが、それらは決定してしまう。あとは5と5か、3と7か。しかし、これも最善かは分からない、値は42。次は11も含めて考えてみる。
一つ前のが最善じゃない可能性がある理由として、3と5を使い切っていないことだったので、使い切るという前提で始める。もうすでに2個ある列と行は選択肢から外す。で下の5と対応する7と9と11だが、7は試してみても無理だし、11は対応する数字が無いので、9が確定。で上の9と11が確定。42。
もうこうなると42は無さそうだけど、じゃあ13も使うとして、上の13と3と5を使い切ると、13の下の11が確定して、13の横の9が確定する。この値は46。下の13と3と5を使うと、13の横の11が確定し、13の上の9が確定する。46。
まさか、15を使うということはあるまい。15と3と5を使って、この時点で全く数字を含まない行と列は消滅、すでに2個ある行と列も消滅で、15の上の11が確定する。15の横の11も確定。この値は50。
まあ最善になりそうなものは全て試したので、値は42だろう。9まで使うのが2通り。で、まあ全て3は使って、そこから2の倍数でどれだけ多いかで、つまり5を3+2*1で1と考えて自分のノートに表を作って、12減らしたのが答えだと分かって地道に考えてみるに、13と15を使う場合も今までの解答で良い、つまりそれぞれ0通り。問題は11も使う場合だ。
下の9と11を使う場合、右の9と11を使うと、合わせて14(さっき説明した俺の方式で、3+4 + 3+4)になるので無理。その真横を使うのも、最善でも7と9で、俺の方式で12になってしまって、他全てを0にすることはできないので無理、つまり3列以上で展開できないので無理。
右の9と11を使う場合、上の行が最善でも12なので、これまた無理。つまり11も使うパターンは、上の11を使う場合を考えればそれで良い。上の9と11を使う場合、左の3と5が確定、残りは2通りで確かに成立する。上の7と11を使う場合、縦真ん中の5と7が確定、残り2通りで確かに成立する。つまり11を使うパターンは4通り。答えは9までの2通りと合わせて、6通りだ。

多分、すげえ馬鹿な方法を使ったんだろうなと思って答えを見ると、ああ気付かなかった、それぞれの行において、数字は単に2ずつ増えている。つまり縦も、上から6・2・4・8で、その値に1から2ずつ増えていく数値を足したものになっている。
一番下の行と、一番右の列は大きいので無視するとして、残りの9×9マスで、1通り考えれば良い。それでちょうど足される前の数字が、同じだけ均等に足された総和になる。通り数も、上の行で3通り、全く同じ状態は除くとして中の行で2通り、3*2で6通りになる。
　

04年度トライアル問題　問題11

『アテネオリンピックのマラソンの優勝候補はA、B、C、D、Eの5人です。
大介と平太がその5人の順位を次のように予想しました。

	1位	2位	3位	4位	5位
大介	A	B	C	D	E
平太	B	D	A	E	C

結果は、確かにこの5人が1位〜5位になったのですが、順位についての予想は大介はすべてはずれで、平太は2人だけ当りました。
また、『順位がとなりあう2人の順番』が当たっているか（たとえば、結果が、CABEDであれば、大介はABの1組の順番を当てたことになります）についても、大介はやはりすべてはずれで、平太は1組が当たっていました。
実際の、5人の順位を求めなさい。ただし、同順位はなかったものとします。』

!([{A == rank[0]}, {B == rank[1]}, {C == rank[2]}, {D == rank[3]}, {E == rank[4]}].5);
[{B == rank[0]}, {D == rank[1]}, {A == rank[2]}, {E == rank[3]}, {C == rank[4]}].2;
!([{B == rank[0]}, {D == rank[1]}, {A == rank[2]}, {E == rank[3]}, {C == rank[4]}].3);
!([{A == rank[?1], B == rank[?1 + 1]}, {B == rank[?2}, C == rank[?2 + 1]}, {C == rank[?3], D == rank[?3 + 1]}, {D == rank[?4], E == rank[?4 + 1]}].5);
[{B == rank[?5], D == rank[?5 + 1]}, {D == rank[?6], A == rank[?6 + 1]}, {A == rank[?7], E == rank[?7 + 1]}, {E == rank[?8], C == rank[?8 + 1]}].1;
!([{B == rank[?5], D == rank[?5 + 1]}, {D == rank[?6], A == rank[?6 + 1]}, {A == rank[?7], E == rank[?7 + 1]}, {E == rank[?8], C == rank[?8 + 1]}].4);

結果におけるrank;

答えを見ると、つまり2人の順位が当たり、残り3人のうち2人の前後関係が合っていて順位は外れていたので、そのようなことが可能なのは当たったのが1位と2位、4位と5位、1位と5位の場合だけ。（より読みやすくするための校正で「その他の3人のうちの」が欠落したらしく、違う解答でもOKとのこと）
その中で大介くんの順位と照合して、問題無いものが解答。
　

04年度トライアル問題　問題12

『連続する4個の整数（すべて1以上）A、B、C、D（A ＜ B ＜ C ＜ D）があり、順に7の倍数、9の倍数、11の倍数、13の倍数になっています。
この条件に合うA、B、C、Dの最小の組み合わせのAを求めなさい。』

A >= 1;
B == A + 1;
C == A + 2;
D == A + 3;
A == 7 * ?;
B == 9 * ?;
C == 11 * ?;
D == 13 * ?;

Aを最小化するように命令;

結果における(A, B, C, D);

答え方としては普通に総当りだと思うが、いやあるいは計算式でも立てるのか、しかし自分としてはよく分からないので普通に総当りでやっていく（問題を細かく分けているので厳密には総当りでは無い）。
まず7の倍数+1が9の倍数になる場合を考える。7*5=35、9*4=36。7*14=98、9*11=99。7*23=161、9*18=162。7*32=224、9*25=225。まあ普通に、最初に一致した値から公倍数で増えている感じだろう。
じゃあ次に9の倍数+1が11の倍数になる場合。9*6=54、11*5=55。11*14=154、9*17=153（個人的に作戦を変えて、11の倍数はgoogle検索で計算して、それ-1の各ケタの和が9の倍数になるかを見ていった。これは有名な方法で、10=9+1だから可能になる。3でも10=3*3+1なので可能）。11*23=253、9*28=252。これも同じく、最初に発見された値から9と11の公倍数で増えていく。7と9と11と13はそれぞれ素だから（こういう言い方したよな？いや調べたら、やっぱりそれぞれ共通の約数を持たないことをこう言うらしい）、これは簡単に求まりそうな予感だ。
9が簡単だったので、13の倍数-2と9の倍数で見ていくことにした。13*5=65、9*7=63。13*14=182、9*20=180。多分これもそういうことだろう。

次に、今回は9を基準に、9*(4+7の倍数)、9*(6+11の倍数)、9*(7+13の倍数)、で最小のものを考えていく。まあつまり(4+7*X)かつ(6+11*Y)かつ(7+13*Z)の数字を考えていく。
で、11の倍数と13の倍数だと、ちょうどそれぞれが1ずつ増えた時に、13の倍数の方が相対的に2増える。つまりそれを2ステップで7+2*2=11、更に3ステップで2*3=6なので、合わせて5ステップでちょうど11の倍数だけズレるはず。6+11*5=61、7+13*5=72。6+11*6=72で、まず(6+11の倍数)と(7+13の倍数)は72。そこからは11と13の公倍数の143で増えていくだろう。
同じ考え方で、7の倍数と11の倍数だと、1ステップで11の倍数の方が4増える。6+4*2=14で7の倍数、更に4*1=4、合わせて3ステップで前者が7の倍数だけ少なくなるはず。4+7*3=25、6+11*3=39。つまり4+7*5=39で、(4+7の倍数)と(6+11の倍数)は揃った。あとは7と11の公倍数の77で増えていくだろう。
72+143*?と、39+77*?で揃う時か。なんだか解答に自信が無くなってきた。今度こそ、72+143*X=39+77*Yで考えてみるか。X=(7*Y-3)/13。
Xが整数である必要があるなら、Yは6、その時Xは3。72+143*3=501、39+77*6=501。つまり9*501=4509が最小。どうだろう。

答えを見ると、まずAは7で割り切れる数。でBの条件から、更にAは9で割ったら8余る数。Cの条件から、Aは11で割って9余る数。Dの条件から、13で割って10余る数。
更に、それぞれ2倍にすると、余りは16-9=7、18-11=7、20-13=7、になる。
これらの情報を元にAを考えると、7*9*11*13+7=9016、/2で、4508。
最初からAの計算式に置き換えるというのは答えを想定しなくても出てくる発想だろう。それができていれば、この方法に至れたかもしれないし、そうじゃなくても簡単にはなった。