sasaharayuugo.net

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

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

 

92年度トライアル問題 問題3

『A君、B君、C君、D君の4人が○×式のテストを受けました。全10問の4人の解答とA君、B君、C君の点数は下の表のようになりました。このテストは1問10点で100点満点です。
さて、D君は何点だったでしょうか。』


A[○, ×, ○, ×, ○, ○, ×, ×, ×, ○]。
B[○, ○, ×, ×, ×, ○, ○, ○, ×, ×]。
C[×, ×, ×, ○, ○, ×, ○, ×, ○, ×]。
D[○, ○, ×, ×, ○, ×, ○, ×, ×, ×]。

[カウンター] = 0。
[点数][A] = 0。
[点数][B] = 0。
[点数][C] = 0。
[点数][D] = 0。

[○加算]# ← [
 [
  [#][カウンター] = ○。
  [点数][#] ← +10。
  ,
  それ以外。
 ]の1つ。
]。

[×加算]# ← [
 [
  [#][カウンター] = ×。
  [点数][#] ← +10。
  ,
  それ以外。
 ]の1つ。
]。

[
 [
  [○加算] ← 全部 ← [A, B, C, D]。
  ,
  [×加算] ← 全部 ← [A, B, C, D]。
 ]の1つ。

 [カウンター] ← +1。
]
〜[カウンター] = 9。

[A点数] = 70。
[B点数] = 70。
[C点数] = 60。

[結果]における[D点数]。


結局引数が必要だと分かった。
この計算を軽くするには、まず答えのリストを宣言して、リストとしてAと7個同じ、Bと7個同じ、Cと6個同じ、という風に並列化する。
AとBで最低4個カブるはずで、その4個が見つかり、Cはそのどれとも共有していないので、残りの部分はCが正解。これで最後まで行く。
 

92年度トライアル問題 問題4

『プールの中に立って手のひらで水面をたたくとたたいたところから波が広がっていきます。このような波の速さは、水の深さだけに関係があります。水の深さがどこも同じなら、立ち止まって作った波も歩きながら作った波も、強くたたいて作った波も、弱くたたいて作った波も、みんな同じ速さで進んでいきます。波とは不思議なものですね。
さて、ある遊園地のプールに、10秒間に6つの波を作る機械が取り付けられています。この機械はプールの底にしかれたレールにそって一定の速さで動かすことができます。また、このプールはどこも同じ深さで、波は10秒に12mの速さで進みます。
またこのとき、波のいちばん高いところを波の山とし、いちばん低いところを波の谷とします。

①この機械が止まったまま波を作っているとき一つの波の山からとなりの波の山までの距離は何mですか。
②太郎君は止まったまま波を作っている機械に向かって、10秒に4mの速さで歩いています。
 太郎君は10秒間にいくつの波の山に出会いますか。時間は、波の谷がちょうど太郎君の位置に来たところから計ることにします。
③今度は止まっている太郎君に向かって、機械が10秒に4mの速さで近づきながら波を作っています。太郎君はいくつの波の山に出会いますか。時間は、波の谷がちょうど太郎君の位置に来たところから計ることにします。
④機械と太郎君はそれぞれ10秒に4mの速さで向かいあって進んでいます。太郎君は、10秒間にいくつの波の山に出会いますか。時間は、波の谷がちょうど太郎君の位置に来たところから計ることにします。』


迷ったけど、結局これは計算式を適切に立てるだけの問題なので、スルーする。速度(メートル/秒)とか間隔とかが厄介。
 

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

『ここにA君、B君、C君、D君、E君、F君、G君、H君、8人のせりふがあります。
一人一人は自分自身を含む8人について言っています。よく読んで下の問に答えなさい。

A君 「私たちの中で少なくとも1人は正しいことを言っています。」
B君 「私たちの中で少なくとも2人は正しいことを言っています。」
C君 「私たちの中で少なくとも3人は正しいことを言っています。」
D君 「私たちの中で少なくとも4人は正しいことを言っています。」
E君 「私たちの中で少なくとも1人はまちがったことを言っています。」
F君 「私たちの中で少なくとも2人はまちがったことを言っています。」
G君 「私たちの中で少なくとも3人はまちがったことを言っています。」
H君 「私たちの中で少なくとも4人はまちがったことを言っています。」

まちがったことを言っている人はだれですか。すべて選んで記号で答えなさい。
また、いないときはいないと答えなさい。』


セリフ[[セリフ]の1個。, [セリフ]の2個。, [セリフ]の3個。, [セリフ]の4個。, ![[セリフ]の1個]。, ![[セリフ]の2個]。, ![[セリフ]の3個]。, ![[セリフ]の4個]。]のn個。

[結果]における[セリフ]。


フローと集合の同一視は問題じゃないだろうか。
BはAを含み、CはBを含み、DはCを含む。FはEを含み、GはFを含み、HはGを含む。
A〜Dは、それぞれが正しければ、例えばDが正しければAとBとCも正しいので、即座に条件を満たして他に考慮することは無くなる。
問題はE〜Hだ。最も条件が難しいHから順番に考えていく。結果Hは無理で、それ以外は何通りも答えが出てくる。
 

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

『高校で習う数学にちょう戦してみましょう。大学の入学試験に出ても少しもおかしくない問題ですが、小学5年までの算数の力がしっかりついていれば、解ける問題です。
(問題)
ある決まりにしたがってならんだ数の列を「数列(すうれつ)」といい、数列の中の一つ一つの数を「項(こう)」といいます。
そして第1番目の項に、ある数を次々にかけて行ってできる数列を「等比数列(とうひすうれつ)」と呼びます。かけて行く数は整数とは限りません。
例えば、{3、6、12、24、48、96、192}は、3に次々に2をかけて行って作った、項の数が7個の等比数列です。
すべての項が100以上、1000以下の整数で、もっとも多くの項がならんだ等比数列を作りなさい。
ただし、1をかけて行ってできる数列は除きます。』


[数列] ← a。

[ループ] ← [
 a ← a * b。
]
〜c回。

[数列]の末尾。 ← [ループ]における[a]。

100 <= [数列]の要素 <= 1000。

cを最大化するように命令。


まずaの最善を考えると、これは100だ。なぜなら、例えば101は(100+1)だからだ。だから100以上のある数字にある回数かけることができるとしたら、必ず100にもかけることができる。
次にbの最善を考えると、これは2だ。なぜなら、例えば3は(2+1)だからだ。だから2以上のある数字をある回数かけることができるとしたら、必ず2でもかけることができる。

まあ証明にはなってないだろうけど、最善を考えるという方法論で解ける。最善だと確かめる際には、まあルールを使う。
[ループ]で、どの地点の値を参照すれば良いかが分からなかったのはマズい。操作される前の初期値を[0]に蓄えておくべきか?
 

92年度ファイナル問題 問題2

『ある工場で、1個を売って1000円の利益を得る製品を11個作りました。
しかし、その中の1個が売ることのできない不良品であることが分かりました。
そこで、次の性質を持つ機械を使って、良品を選んで売ることにしました。

(機械の性質)
①1回にいくつの製品でも調べることができます。
②1回調べるたびに、1000円の費用がかかります。
③調べた製品の中に不良品が見つからなかった場合、調べた製品はすべて1個1000円の利益で売ることができます。
④調べた製品の中に不良品が見つかった場合、いっしょに調べた製品もすべて不良品になってしまい売ることができなくなります。

例えば、この機械を使って1個ずつ製品を調べて行くと、次のような可能性が考えられます。
「一個ずつ調べて行ってもっとも運のいいとき」……1回目に不良品が見つかる。
  →調べるのに1000円かかり、残り10個を1個1000円の利益で売れる。1000×10−1000=9000円の利益。
「一個ずつ調べて行ってもっとも運の悪いとき」……10回目まで不良品が見つからない。
  →最後の1個は、調べなくても不良品だと分かる。それまでの製品は1000円で売れるが、調べるのに1回に1000円かかっているので、全く利益はない。

(問題)調べる個数や順序によっていくつかの調べ方が考えられますがその中で「もっとも運が悪いとき」に得られる利益を一番高くするにはどのような調べ方をすればよいでしょうか。
その調べ方を分かりやすく説明し、その場合「もっとも運の悪いとき」に得られる利益を答えなさい。』


製品リスト[要素が11個の集合]。

[製品リスト] ← 1個 ← [不良品]。

[
 [
[製品リスト]の数 >= a。

[チェック用リスト]の中を削除する。

  [チェック用リスト] ← 移動でa個 ← [製品リスト]の先頭から。
  ,
  それ以外。

  [チェック用リスト]の中を削除する。

  [チェック用リスト] ← 移動で[製品リスト]の数 ← [製品リスト]の先頭から。
 ]の1つ。

 [
  [チェック用リスト]が[不良品]を含む。

  B = [製品リスト]の数*1000。

  終了。
  ,
  それ以外。
 ]の1つ。
]
〜[製品リスト]の数 = 0。

あらゆる[Bの最小値]を最大化するようにaを設定。

[結果]におけるa。


全通り考えてみる以外に方法があるのかね。そんなにステップ数が多いわけでは無いし。


こんなので記述するのに意味があるのか、という意見もあるだろうが、記述できるようになっただけで意味があるのだと思う。
理論上と現実上を分けるというコンセプト自体は正しいはずで、そこを見て欲しいと思う。