メチャメチャだけど【随時更新】解答に必要な機能まとめ - ニート歴10年からの数学日記と【随時更新】計算量の減らし方まとめ - ニート歴10年からの数学日記を使って、算数オリンピックについて考察していく。
グラフや幾何学の問題や、記述に関するメタ的な問題以外の今までに無い種類の問題について考察する。
『A君、B君、C君、Dさん、E君の5人で勉強会をしました。勉強会では、全部で100ページの本を順番に読んでいきました。
A 君：最後に読んだ人は、ぼくより読んだページ数が1ページ少なかったよ。
B 君：ぼくの読んだページの最後のページの数字は、A君の読み始めたページの数字のちょうど2倍だったよ。
C 君：一番読んだページ数が多い人と、少ない人でも、10ページはちがわなかったね。
Dさん：私の読み始めと読み終わりのページの数字の和は、C君の読み始めと読み終わりのページの数字の和の3倍でした。
E 君：読んだページ数は全員ちがったね。
このとき、それぞれの人がどのような順番で何ページ読んだかを答えなさい。』
A + B + C + D + E == 100;
A != B != C != D != E;
people := [A, B, C, D, E];
already_read := [];
pages := 0;
people.[最大] - people.[最小] < 10;
while(people.数 != 0){
reading := 1 : 移動 := people;
pages := pages + reading;
already_read := 末尾に新しく := reading;
}
already_read[4] == A - 1;
already_read[?].@[?1: ?1 <= B].add == (already_read[?].@[?2: ?2 < A].add + 1) * 2;
(already_read[?].@[?3: ?3 < D].add + 1) + (already_read[?].@[?4: ?4 <= D].add) == ((already_read[?].@[?5: ?5 < C].add + 1) + already_read[?].@[?6: ?6 <= C].add) * 3;
結果における(already_read, A, B, C, D, E); ？？要素名を参照しつつ、その中身も参照したいのだが
滅茶苦茶読みにくい。プログラミング言語や数学記法的なものの宿命かとも思うが、そろそろ概念を整理したい。
A+(A-10)+(A-9)+(A-8)+(A-7)=100と考えても、Aは27には行かないので、最大でも26。A+(A+10)+(A+9)+(A+8)+(A+7)=100と考えても、Aは14にはならないので、最小でも15。15<=A,B,C,D,E<=26（答えを見て分かったんだが、最低で14最高で27らしい、疲れた）。それで全部違うわけだから、結構絞られている。
一番制約が大きいのはDさんの証言じゃないかと思うので、その方向で行く。3倍は凄い。例えばあり得ない仮定だが均等に20ページずつ読んだとして、1番目の人は0+20=20ページ、2番目の人は20+40=60ページ、3番目の人は40+60=100ページ、4番目の人は60+80=140ページ、5番目の人は80+100=180ページ。最初が26ページで、もし三番目が最低値でも(26+15)+(26+15+16)=98ページなので、1番目が入っているなら1番目と2番目。いや絞れるのかな。
B君の証言の方に着目すると、2番目以降なので絞りやすいのではないか。1番目の始めは0だし、2番目の始めだと、1つの中に2倍ほどの振れ幅が無いので、どうやっても3番目の終わりにはならない。すると、3番目の始めと4か5の終わり、4の始めと5の終わり、の3通りに絞ることができる。5の終わりの場合、もう一方は50で、これは3番目でも4番目でもあり得る。4番目の終わりは74<=?<=85なので、その半分は37<=?<=42。これは2つ分の総和でしかあり得ないので、3番目の始めだろう。3と4か、3と5か、4と5か。
そのどれにしても、Cさんは1か2。Cが1番目ならDは2番目に決まりだが、Cが2番目ならどうだろう。最初の人からVWXYZとしたら、(V+1+V+W)*3 == (V+W+1+V+W+X)、は無理なので3番目では無い。== (V+W+X+1+V+W+X+Y)だと、6V+3W+3 == 2V+2W+2X+Y+1、4V+W+2 == 2X+Y。2X+Yは最大で77で、左辺は最小で78。4番目も無理。(V+1+V+W)*3 == (V+W+X+Y+1+V+W+X+Y+Z)、6V+3W+3 == 2V+2W+2X+2Y+Z+1、4V+W+2 == 2X+2Y+Z。可能そうなので、Cが2番目ならDは5番目。
まずゴチャゴチャしているCが1番目でDが2番目の場合を考えると、C+1+C+D == C*3、C == D+1。
Aが3番目の場合、Aの読み始めはC+D+1。Bが4番目だと、Bの終わりはその2倍なので、(C+D+1)*2 == C+D+A+B、2C+2D+2 == C+D+A+B、C+D+2 == A+B。Eは最後でA-1なので、A+B+C+D+E == 3A+2B-3 == 100、3A+2B == 103。103は奇数なので、少なくともAは奇数。Aが25だとBは14、Aが23だとBは17、Aが21だとBは20、Aが19だとBは23、Aが17だとBは26だろう。
Aが25だと最後のEが24だとして、100-(25+14+24)=17。一番目から、Cが9、Dが8、ってこれは範囲に収まってないか。
これいつまで続けるんだろう。そろそろ答えを見るか…。
答えを見ると、Aが3番目でBが5番目の場合、3人で合わせて51ページ、前半の2人で49ページを読んだことになる。すると、前の2人が24・25ページ、後の3人が16・17・18ページということになる。このときもし、Cが1人目じゃなかったら、C君の最初と最後のページの和は少なくとも74になる。この3倍は200を超えてしまう。よってCは1人目。すると、最初と最後のページの和は25か26になる。それぞれの場合において2番目の人の和を考えると、74、75になり、Dさんの発言を満たさない。よってAが3番目でBが5番目では無い。
次にAが4番目でBが5番目の場合、Aの最初のページは50となり、AとBで合わせて51ページ、残りの3人で49ページ読んだことになる。しかしこの場合はC君の発言に矛盾してしまう。
以上のことから、Aが3番目でBが4番目だと分かる。すると、順番として可能性があるのは、ECABD、CEABD、CDABEのいずれかとなる。
ECABDの場合、まずDの読んだページ数を考える。Bの証言から、Bの最終ページは偶数なので、Dのページ数は偶数だと分かる。Dさんの証言より3の倍数なので、24ページか18ページかのいずれかだと分かる。前者であればAは+1で25ページ、後者であればAは19ページ。Bの最終ページが決まったので、Bの証言からAの最初のページが決まり、AとBで合わせて読んだページが決まる。前者が39ページで、後者が42ページになる。よって、Aを引いて、B君の読んだページはそれぞれ14ページ、23ページとなる。C君の発言から差は9以内なので、Dさんが24ページ読んだ場合は条件を満たさないことが分かる。よって残りの18ページの場合について考える。Dさんの発言を考えると、C君が21ページから40ページの計20ページを読んだことが分かるらしい。しかしこれでは1番目も20ページになってしまう。これはあり得ない。
CEABDの場合、Cの読んだページは最大でも27ページ、なので最初と最後を足しても28ページ。一方、Dの読み終わりは100ページ、これは28の3倍より大きい。よってこの場合は無い。
CDABEの場合。Cの読んだページ数を仮にXとする。するとDさんの条件から、Dさんの読んだページ数がX＋2と分かります。そしてB君の発言より、B君の最終ページが2X+6となります。E君の読んだページ数がこのことから決まり、A君の条件からA君の読んだページ数も決まる。よってXを決めることで全員のページ数が決まる。Xを順番に考えていくと条件を満たすのは18の場合だけ。
よって答えは、Aが3番目で23ページ、Bが4番目で17ページ、Cが1番目で18ページ、Dが2番目で20ページ、Eが5番目で22ページ。
ああ疲れた。今日はもうこの問題だけで良い。
『3の倍数個のマスでできた図形を、縦1マス、横3マスの長方形の板（以下、1×3の板）を重ねることなく並べて作りたいと思います。
例えば、5×5のマスから右上の1マスを除いた24個のマスでできている図形を作ることができるかを考えてみます。
縦、横の1×3マスに1、2、3が1つずつ入るように数字を書き入れてみます。もしも1×3の板を重ねることなく並べてこの図形を作れるとすれば、1、2、3の個数は等しいはずです。
図1では1、2、3の個数が8個ずつで等しくなっています。しかし、実際に1×3の板を重ねることなく並べることはできません。
なぜなら、図2のように数字を書き入れた場合は、1が9個、2が7個、3が8個になっているので、この図形は1×3の板を重ねることなく並べては作れないことがわかります。
一方、5×5のマスから中央の1マスを除いた図形について同様に調べると、図3のように、1×3の板を重なることなく並べて作ることができるとわかります。
（図1）
| 1 | 2 | 3 | 1 | |
| 2 | 3 | 1 | 2 | 3 |
| 3 | 1 | 2 | 3 | 1 |
| 1 | 2 | 3 | 1 | 2 |
| 2 | 3 | 1 | 2 | 3 |
（図2）
| 1 | 2 | 3 | 1 | |
| 3 | 1 | 2 | 3 | 1 |
| 2 | 3 | 1 | 2 | 3 |
| 1 | 2 | 3 | 1 | 2 |
| 3 | 1 | 2 | 3 | 1 |
（図3は省略。渦巻状に配置）
（問い1）縦8マス×横11マスの長方形から1マスを除いた図形の中で、1×3の板を重ねることなく並べて作ることができるものは何種類ありますか。
（問い2）縦100マス×横2011マスの長方形から1マスを除いた図形の中で、1×3の板を重ねることなく並べて作ることができるものは何種類ありますか。
なお、（問い1）、（問い2）とも、回転したり裏返すと同じになるものもそれぞれ1種類と数えることとします。』
この問題は、問題文を書いてしまったけど、飛ばすことにした。幾何学だとかグラフに近い問題だと思った。
『A君、B君、C君はそれぞれ自然数（※）が書かれたカードを持っています。
それぞれ、自分以外の2人のカードの数字は見えますが、自分のカードの数字はわかりません。また、3人のカードの数で一番大きい数は、他2人のカードの数の合計になることがわかっています。
この条件で、A君、B君、C君は自分のカードに書かれた数について、順番に次のように発言しました。
A君：「わかりません。」
B君：「わかりません。」
C君：「自分のカードに書かれた数は、15です。」
このとき、A君、B君のカードに書かれた自然数の組み合わせを3通り答えなさい。
（※）自然数とは、1以上の整数のことをいいます。』
これ全然分からない。二つの異なる数字があったとして、それを足した数値が自分なのか、引いた数値が自分なのか、どうして分かるのかが分からない。俺がC君だったら、そりゃ分からないと答えるよね、で終わりだ。もちろん答えはあるんだとは思うが。
答えを見ると、A君の発言から、A:B:C=2:1:1でないことがわかる。その後のB君の発言から、A:B:C=1:2:1,2:3:1でないことがわかる。この後、C君が自分の数がわかったので、A:B:Cは以下のどれかだとわかる。
①1:1:2
②2:1:3
③1:2:3
④2:3:5
Cのカードは15(=3*5)なので、②、③、④の場合に条件を満たします。よって答えは、(A,B) = (10,5), (5,10), (6,9)。
モンティホール問題みたいなことなんだろうか？分からない。出題者が間違うということも普通にあると思うんだけど。
『たて横の線が11本ずつある碁盤があります。
いま、碁盤の目に○と●を置いてきます。ただし、どの1×1の大きさの正方形を見ても●と○が2個ずつあるように配置するとします。例えば、3本ずつのたて横の線がある碁盤の時には下の図のように置くことで条件を満たしています。
このような置き方は何通りありますか。
ただし、回転して同じになるものも別の置き方として数えます。
（図。囲碁においては線と線が重なりあった所に石を置く）
●●○
○○●
●●○』
table := [~10][~10]のリスト;
table[?][?] := 全部:カブり有り := ["●", "○"];
every.[table[?1][?2], table[?1+1][?2], table[?1][?2+1], table[?1+1][?2+1]] ∋["●", "●", "○", "○"];
結果における数;
上の一辺が決まれば、大体1通りに定まる。一つ例外があって、上の一辺に連続する●●や○○が無い場合は、2通りあり得る。
まず、どんな一辺でも、下のを逆さにすれば対応できないということは無い。○○など連続するものの下は、●●など一通りに定まり、その隣も上2つと横1つの数で1通りに定まる。全く連続しない場合は、同じものを配置するか、逆のものを配置するかの2通りあり得る。
上の一辺は、2^11通り。加えて完全に交互なのが2通り。2^11 + 2 = 2050通りが答えだろう。
縦2つとそこから横への展開、4つセット、9つセット、いろいろな区切りでのルールを探したが、アルゴリズムでいう線形走査法のように考えるようにすることで、上下左右にフローが散らばらないようにすることができたのだと思う。
しかし答えを見ると、4094通りだった。基本的には白と黒が交互に出てくる。俺の場合は縦の場合だけで、横の場合もあるから×2して、それから市松模様の場合を引くらしい。
一行目が交互の場合、一旦逆に置いても、また同じ風に置いたりもできるわけで、俺はそこを見逃していた。
『何チームかでサッカーのリーグ戦（各組み合わせ1試合ずつの総当たり戦）を行いました。
2点以上の差をつけて勝つと勝ち点が3、1点差で勝つと勝ち点が2、1点差で負けると勝ち点が1、2点差以上で負けると勝ち点が0とします。
ただし、引き分けはありませんでした。
（1）参加チームが12チームであるとき、あるチームは6勝5敗でした。このチームの勝ち点としてあり得る最大の値と最小の値を求めなさい。
（2）いま、チームAは勝利数が単独1位でしたが、勝ち点では単独最下位となってしまいました。一方で、チームBは勝利数が単独最下位でしたが、勝ち点は単独1位でした。
このとき、リーグ戦に参加したチームは少なくとも何チームですか。』
teams := [A, B, C, D, E, F, G, H, I, J, K, L];
end_teams := [];
for(i := 0; i < teams.数; i++){
for(j := 0; j < teams.数; i++){
if(i == j){continue;}
i_point := ?;
j_point := ?;
i_point ≠ j_point;
if(i_point - j_point >= 2){
teams[i][0] := teams[i][0] + 3;
teams[i][1] := teams[i][1] + 1;
teams[j][2] := teams[j][2] + 1;
} else if(i_point - j_point == 1){
teams[i][0] := teams[i][0] + 2;
teams[j][0] := teams[j][0] + 1;
teams[i][1] := teams[i][1] + 1;
teams[j][2] := teams[j][2] + 1;
} else if(i_point - j_point == -1){
teams[i][0] := teams[i][0] + 1;
temas[j][0] := teams[j][0] + 2;
teams[j][1] := teams[j][1] + 1;
teams[i][2] := teams[i][2] + 1;
} else if(i_point - j_point <= -2){
teams[j][0] := teams[j][0] + 3
teams[j][1] := teams[j][1] + 1;
teams[i][2] := teams[i][2] + 1;
}
}
end_teams := 末尾 : 移動 := teams[i]; ？？あるいはteamsからteams[i]を移動すべきか
i := i - 1;
}
結果における(end_teams[?].[?1: ?1[1] == 6, ?1[2] == 5][0].[最大]);
結果における(end_teams[?].[?1: ?1[1] == 6, ?1[2] == 5][0].[最小]);
記述としてはこんな感じではないか。2問目は、
teams := 要素がn個のリスト;
という風に記述して、
end_teams[?].[?2: ?2 == A][1] == end_teams[?][1].[最大]; ？？要素名の参照について問題がある気がする
end_teams[?].[?2: ?2 == A][0] == end_teams[?][0].[最小];
end_teams[?].[?3: ?3 == B][1] == end_teams[?][1].[最小];
end_teams[?].[?3: ?3 == B][0] == end_teams[?][0].[最大];
nを最小化するように命令;
結果におけるn;
という感じで良いのではないか。ABCDと自動で命名するような感じで。バグの温床みたいになってしまうんだろうか。
問い1は、普通に出せば良いだけだと思うけど。勝ち点3と2だったら、3は2を含むわけだから大きくなるだろうし。
問題は問い2で、1チーム増えるごとに、試合数がそれまでのチーム分増えるので、勝った数も負けた数も同じだけ増える。チーム数2だと試合数1、3だと3、4だと6、5だと10、6だと15、7だと21、8だと28。いやこれは、チーム数をxとして、(x-1+1)/2*(x-1)=x(x-1)/2、でもありそうだな。例えば8だったら7から1までの数字を足し合わせるわけだから。勝利数+敗北数=(x-1)で、勝利数の単独1位と最下位が、勝ち点で逆転し得る場合を考えれば良い。ただ、例えば8勝0敗と0勝8敗で逆転することは無いだろうな、どの勝ちも負けの上位互換だから、少なくともどちらかは交じる必要はある。その試合数の最善で入り交じるのと交じらないのでは交じった方が上位互換だろうから、多分両方交じる。
5チームの、3勝1敗と2勝2敗と1勝3敗を考えてみると、勝ち点は前者は6点で、後者は6点。6チームの4勝1敗と3勝2敗と2勝3敗と1勝4敗を考えてみると、1つ目が少ない方の最善で8点、2つ目が少ない方の最善で6点、3つ目が多い方の最善で9点、4つ目が多い方の最善で7点。最初の3つと最後の3つのどちらかだけで構成できるなら、それが答えになる。
最初の3つなら、全部で15勝ある内の、4勝1敗と2勝3敗で合わせて6勝4敗。それからも3勝2敗で勝利が増えていくので、これは勝利数と敗北数が釣り合わないので無理。最後の3つでも似たような感じ。
7チームの5勝1敗・4勝2敗・3勝3敗・2勝4敗・1勝5敗だったらどうだろう。1つ目から少ない方の最善で、10点・8点・6点、真ん中から多い方の最善で、12点・10点・8点。これなら、4勝2敗の8点と2勝4敗の10点と3勝3敗で行けるのではないか。大負けと大勝ちは合わせて3点、小負けと小勝ちは合わせて3点、これらをセットになるようにすれば、3勝3敗は9点になる。可能なので、おそらく7チームが答えだろう。正解だった。
『A〜Fの6人が、それぞれ1枚以上のカードを持っています。持っているカードの枚数について6人が次のように言いました。
A：「私は、Dより1枚多い枚数のカードを持っています。」
B：「私は、Cより3倍の枚数のカードを持っています。」
C：「私は、Bより5枚少ない枚数のカードを持っています。」
D：「私は、Eより7枚多い枚数のカードを持っています。」
E：「私は、Aより9枚多い枚数のカードを持っています。」
F：「6人合わせて20枚のカードを持っています。」
6人のうち、2人がウソをついているとき、次の各問いに答えなさい。
（1）ウソをついている2人はだれとだれですか。
（2）A〜Fの6人がそれぞれ持っているカードの枚数を答えなさい。』
result_list := [];
A, B, C, D, E, F >= 1;
or(それ以外否定で4){
A == D + 1;
result_list := 追加 := "A";
,
B == C * 3;
result_list := 追加 := "B";
,
C == B - 5;
result_list := 追加 := "C";
,
D == E + 7;
result_list := 追加 := "D";
,
E == A + 9;
result_list := 追加 := "E";
,
A + B + C + D + E + F == 20;
result_list := 追加 := "F";
}
結果における("A", "B", "C", "D", "E", "F").[?1: ?1 ∉ result_list];
結果における(A, B, C, D, E, F);
or機能の中で更に「,」を使いたくなった時は、{}で囲めば良いのではないか。あるいは、else ifみたいにorで連ねても良いし。次はそれで試してみるか。
BとCは両立しないし、AとDとEもどれかは違う。それをFの条件と照らし合わせて絞り込むという問題ではないか。
まず、Aが違う場合、E=A+9で、D=(A+9)+7=A+16なので、Fの条件の中に「3A+25」があることになってしまう。これは違う。
次に、Dが違う場合、A=D+1で、E=(D+1)+9=D+10なので、Fの条件の中に「3D+11」があることになる。保留。
Eが違う場合、D=E+7で、A=(E+7)+1=E+8なので、Fの条件の中に「3E+15」があることになる。保留。
もしBが違う場合、C=B-5より、Bは6以上ということになる。
Cが違う場合、B=3Cより、Fの条件の中に「4C」があることになる。
そのどちらにしても、「3E+15」では20以上になってしまう。よって、まず違うのはDだと分かる。
「3D + 11 + 2B - 5 + F = 20」か、「3D + 11 + 4C + F = 20」か。「3D + 2B + F = 14」か、「3D + 4C + F = 9」か。
後者は、同じ数のものがあって良いなら、DとCが1でFが2であり得るか。それなら条件を見ても確かに成立する。
前者は、Bが6以上だったはずなので、これは成立しない。
ということは、ABCDEFの順番で、2、3、1、1、11、2、が正解ということになる。
今回で算数オリンピックの幾何学とか以外の問題について終了した。機能を直して、計算量の削減方法もとりあえずは今までの解答から分析して直して、それから幾何学とかの問題にどういう種類があるかまとめたいと思う。その問題のジャンルの解き方を考えて、後はジャンルごとに、気になった問題を解いていく、という風にしようと思う。