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

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

99年度ファイナル問題　問題5

『小学生によるマラソンレースが行われました。走るのが得意なA、B、C、D、Eの5人も参加してレースが始まりました。折り返し地点を過ぎてからは5人ともそれぞれに一定の速さで走っています。
5人が折り返し地点を過ぎてからX、Y、Zの3人が別々の場所でレースの写真を1枚ずつ写しました。
最初に写したのはX、続いてY、最後がZでした。下の会話は後日、X、Y、Zの3人がそれぞれ自分の写した写真を持ちよったときのものです。

X：「ぼくのは5人が折り返してから10分後に写した写真だけど、5人がABCDEの順に20mおきに同じ間隔で写っているぞ！」
Z：「わたしのは5人が折り返してから30分後に写した写真だけど、5人がBECADの順に30mおきに同じ間隔で写っているわ！」
Y：「ううむ………僕はいつ写したんだっけ……全然覚えてないや。ただ僕の写真も、5人が同じ間隔で並んでいるよ！」

さて、Yの写真は5人が折り返してから何分何秒後に写したものでしょうか。』

B == A - 20;
C == B - 20;
D == C - 20;
E == D - 20;

記録1;

A := A + F;
B := B + G;
C := C + H;
D := D + I;
E := E + J;

E == B - 30;
C == E - 30;
A == C - 30;
D == A - 30;

(記録1)において、{
　A := A + (F / 20) * K;
　B := B + (G / 20) * K;
　C := C + (H / 20) * K;
　D := D + (I / 20) * K;
　E := E + (J / 20) * K;

　(ランナー) := (A, B, C, D, E);

　(トップ) := 移動で1 := (ランナー);
　i := 1;

　{
　　(対象) := 移動で1 := (ランナー);

　　(対象) == (トップ) + i * L;

　　i := i + 1;
　}
　~(ランナー) == ();
};

(結果)における(10 + K);

うん、まあ、この（ランナー）とか（トップ）とか（対象）とかは英語で書いたほうが良いかもしれない。で、「結果における」とかはカッコを取ってそのまま書く感じが良いんじゃないか。まだまだ模索中で。

解答としては、Aを基準に考えて、時間あたりで相対的にどれだけ差が出るかを出すのはできると思う。問題は同じ間隔になる瞬間を出すことなのだけど、予想では、追い越すタイミングに着目して計算を省くんじゃないか。誰が誰を追い越すかは分かっているわけだし。まあよく分からないから答えを見るけど。
答えを見ると、えーっと、何かグラフを書いて、幾何学的に相似だとかで解いてるんですけど。今やる問題じゃ無かったな。しかしこういう計算を、幾何学、つまりグラフの問題として解くっていうのはつまりどういうことなんだろうな。
　

99年度ファイナル問題　問題6

『1から順にふえていく整数の列の中には、たとえば1から3までの場合は、
　1 + 2 = 3
1から20までの場合には、
　1 + 2 + 3 + 4 + ……… + 14 = 15 + 16 + 17 + … + 20
のように順序を変えないまま、途中でうまく2つのグループに分けて、各グループの数の和を等しくできるものがあります。
このような整数の列のうち、上の例以外で、最も短いものは1からいくつまでですか。』

i := 0;

{
　i := i + 1;
　j := 0;
　i_sum := 0;

　{
　　j := j + 1;

　　i_sum := i_sum + j;
　}
　~i == j;

　{
　　i_sum = ? * 2;
　　,
　　それ以外;

　　次のループへ;
　}の1つ;

　k := 0;
　k_sum := 0;

　{
　　k := k + 1;

　　k_sum := k_sum + k;
　}
　~{
　　i_sum / 2 == k_sum;

　　{
　　　i == 3
　　　,
　　　i == 20
　　　,
　　　それ以外;

　　　終了;
　　}の1つ;
　　,
　　i_sum / 2 < k_sum;
　}の1つ;
}
~;

この問題文には2の倍数になるという情報は入っていないので、入れるべきでは無かったかもしれない。あと、jとかkをもう少し良い名前にすべきだったかもしれない。

答えを見ると、階段の図を描いて、折り返して重ならなかった部分が等しくなるような場合を考えれば良いらしい。
その折り返してはみ出した、上で無く下の方の面積がA×(A+1) / 2になるらしく、上の方は、階段の下の方の重なった辺の長さがBとして、B×B（横向きのピラミッドみたいな形になっている）。重なっている部分は共有しているので、A×(A+1)/2 = B×B、になった時に折り返した部分でちょうど面積が半々になることになる。
AとA+1は連続する整数なので、どちらか一方は奇数で、もう一方は偶数だが、その2つの公約数は1だけ。
このことから、奇数は○×○、となりの偶数 / 2は□×□、という風に表されることが分かるらしい（多分、=B×Bという条件からBは○×□というのも含めて）。それで、(○×○) × (□×□) = B×B。Bは○×□。
その式に当てはまる整数を探しつつ、かつ、となりの偶数は□×□×2なので、○×○に1を足したり引いたりして当てはまる必要もある。
偶数×偶数は偶数になってしまうので、奇数の1から順番に当てはまるものを探していって、49 * (50 / 2) = 35 * 35。最初の式より、Aは49、Bは35。
折り返した部分を元に戻して、A+B+B=49+35+35=119。答えは1から119まで、ちなみに折り返し地点は84まで。
滅茶苦茶難しい。そもそも幾何学に置き換えるっていう解法はまだ分からない。
　

99年度ファイナル問題　問題7

『たくさんの荷物があり、それらの荷物の総重量は19500kgです。1つ1つの荷物の重さはわかりませんが350kgより重い荷物は1つもありません。いま、最大で1500kgの荷物を運べるトラックが何台かあり、これらの荷物をすべていっぺんに運びたいと思います。
1つ1つの荷物の重さがどのような場合でも、必ずすべての荷物をいっぺんに運びきるために必要なトラックの台数は、最も少ない場合で何台ですか。（荷物の容積は考えないものとします）
考え方も書きなさい。』

Baggage := (要素がA個の集合);

Baggageの総和 == 19500;
Baggageのそれぞれ <= 350;

Truck := (要素が?個の集合);

Truckの総和 <= 1500;

Trucks := (TruckがB個の集合);　？？ポインタと変数の違いのようなものがある気がする

{
　Trucksの1つの1つ := 移動 := Baggageの1つ;
}
~Baggage == ();

Bを最小化するように設定;

結果におけるB;

自分だったらこういう最適化の問題は、最悪の場合を考えて、349キロ毎回余るということがあり得るかをまず考える。
1500-349=1151。1151/4=288ぐらい。残り349キロが枷になるには、荷物は全て350キロで無ければならない。
そこで考えを変えて、1500/5=300、ということで、荷物が全て300キロとカウントされないくらい少しの場合、毎回300キロぐらい余る。
これ以上多かったらロスが減ってしまうし、細かいのがあると埋まってしまうし、完全な答えとは思えないけどこれでどうだろう。
19500/300=65、65/4=16の余り1、17台が答えじゃないか。

しかしビックリで答えは違う。19500/1500=13台が最善として、まず、12台のトラックで最後の1個の荷物をのせるとはじめて1500キロをこえるように荷物を積む。
これらの重量は1500以上*12=18000以上になるから、この時残った荷物は19500-18000以上=1500以下で、1台のトラックに積むことができる。
つぎに、12台のトラックの最後の荷物をそれぞれ別のトラックに移動する。荷物の一つ一つは350キロ以下なので、4つずつで3台で済む。
12+1+3=16で、答えは16台。
えーっとつまり、俺は全部で19500だということを忘れてたんだな。ああ、末尾に、実際301キロの荷物64個と236キロの荷物1個だったら16台必要と書いてあるや。
最善とか最悪とかを考える、ということではあるんだろうが。
　

00年度トライアル問題　問題7

『異なる1以上の47個の整数があり、それらの和は2000です。
この47個の整数の中には、最も少ない場合、偶数は何個ありますか。』

integer := (要素が47個の集合);

integerのそれぞれ >= 1;
integerの全部で≠;　？？
integerの総和 == 2000;

integerの(?1: ?1 = 2 * ?)の数 == A;

Aを最小化するように設定;

結果におけるA;

「の」っていうのを厳密にできれば、例えばjavascriptみたいに「.」に置き換えることができるんだけど。javascriptについて少し勉強してみるか。

どれだけ解答に幅があるかを確かめるために、まず極端な場合で1〜47を足し合わせてみる。(1+47)/2*47=1128。なんか無駄というか意味が無さそう。

次に、最善を考えてみる。ある値までの足し算から、その値までの偶数を引いて、2000ピッタリにならないか考えてみる。
ある値をaとして、(1+a)/2*a - ((1+a/2)/2 * a/2)*2 = (1+a)/2*a - (1+a/2)/2*a = (1+a-1-a/2)/2*a = (a/2)/2*a = (a^2)/4。
90*90/4 = 8100/4 = 2025。89*89/4 = (90-1)*(90-1)/4 = (8100 - 180 + 1)/4 = (2025 - 45 - 1/4) = 1980 - 1/4。（aが90だと89までの奇数の足し算になる。）
でも、aが90だと、45個しか数字が無い。あと2個必要。今気付いたけど、aは偶数じゃないと4で割った時に半端な数になる。
完全な解答では無い気がするけど、先頭の89を2に持ってきて、89-2=87をマイナスすることができる。2025-87、で考えると62猶予がある。30と32で、偶数3つなら何とかなるんだけど、2個以下が無いかと言われたら。

減らすより増やす方が簡単そうだから、aを88で考えてみる。1936。数字は44個なので、あと3つ。
奇数の数字を一斉に横に2つ（奇数から奇数だから）ズラすと、結局は起点になった数字を先頭に持ってくるのと同じだけ移動コストがかかる。
ズラして間に入れようと考えた所で、結局は新しい所に数字を追加したのと同じなのであって、やっぱり3つは偶数である必要があるのではないか。

すると答えもそうだった。しかしもっと簡単な説明だった。2000は偶数なので、奇数が偶数個と、47個なので偶数が奇数個必要。偶数が1個の場合、(1+91)/2 * 46 = 2116、しかしオーバー。偶数が3個の場合、(1+87)/2 * 44 = 1936、残りを偶数3個で表せるのでこれが答え。
　

00年度トライアル問題　問題9

『たろうくんは1から順番に1、2、3、4、5、………とある数までを黒板に書きました。じろうくんがその中の1個の数を消してしまいました。すると残りの数の平均は590/17になりました。
じろうくんの消した数はいくつですか。』

i := 0;
all_number := (要素がA個の集合);

{
　i := i + 1;

　all_numberの中 := i;　？？今までのやり方ではall_numberが置き換わってしまうか？しかしもう少し体系的な記述方法が無いか
}
~i == A;

B := 移動 := all_numberの1つ;

all_numberの総和 / all_numberの数 == 590/17;

結果におけるB;

((A+1)/2*A - B) / A-1 = 590/17。手がかりはこれだけじゃないか。

色々試行錯誤した後に答えを見ると、まず、連続する数の一番小さな「1」を抜いた時に、平均値は1/2下がるらしい。連続する数の最大値を抜くと、平均値は1/2上がるらしい。一番平均的な数の大きさが真ん中だからだろう。つまり、元々の平均値は34+7/34より大きく、35+7/34より小さい。
次に、全ての数の平均は、最後の数が奇数だったら(n+1)/2で整数だし、偶数だったら整数+1/2になるので、この2つの条件より、考えられる数は34+1/2か、35。
平均値は(n+1)/2なので、それぞれを2倍して-1すれば最大値のnが出る。68か、69。
しかし、1個消した平均が590/17なので、すべての数の個数は17の倍数+1のはず。
これにより、全ての数の個数は69。
69までの全ての数を足し合わせた数値から、引いた後の平均値*68を引けば、答えが出るはず。答えは55。

滅茶苦茶難しい。12歳なんてIQ60のくせに…、IQ150でもIQ90なのに…。
一番最初の条件が分からなかった。