問題文を読む(2593 文字)
◎解答・解説 | 【発見的に解いていきましょう。 次の図で、◎はお年玉金額=X以下と判明している値、※はXよりも大きいと判明している値、○はまだ◎なのか※なのか検証できていない値をさすものとします。なお、○……○は○が何個かあるものを省略しています。もちろん、各記号は100づつ離れていて左から右へと順に並んでいるものとします。 ◎○○○○○……○※ 例えば今回のお年玉問題では、最初の段階で左端の◎は5100、右端の※は15000です。 子は親に何回か質問することで○がなくなり、◎と※とが隣り合うように出来れば、全ての◎のなかで一番右端のものが、お年玉金額=Xです。 例題で考えてみます。 ◎○○○○○○○○○○※ ◎は5100、※は5800としましょう。 4回の推定値宣言でXを確定できるでしょうか。 この4という回数に着目します。○のならびにおいて、左から4番目にあたる値を推定値として親に訊ねます。(図参照) ◎○○○?○○○○○○※ この問いにたいして、親は?が◎なのか※なのかについて答えます。 次の展開の図を二通り用意しました。 《?>Xと判定》 ◎○○○※※※※※※※※ 《?≦Xと判定》 ◎◎◎◎◎○○○○○○※ さらに個々について以下に検討します。 《?>Xと判定》 ◎○○○※※※※※※※※ 同じことですが、◎○○○※ この場合には親から一度《?>Xと判定》されていますから、あと1回しか、《?>Xと判定》を受けられません。また、全部で4回のうち1回ぶん、親に訊ねる回数を消費していますので残りは3回です。 ◎○○○※ の○は3個ですから左から順に1個づつ訊ねていけば◎と※とが隣接できるようになります。 実はこの目的があって、さきほど、【4という回数に着目、○のならびにおいて、左から4番目にあたる値を推定値として親に訊ねる】ことにしたのでした。 重要な点はここにあります。ひとたび《?>Xと判定》されてしまうと、残っている○については左から順に(小さいもの順に)1個づつ(100円づつ増やして)親に訊ねていくことが必然となります。 次のパターンです。 《?≦Xと判定》 ◎◎◎◎◎○○○○○○※ 同じことですが、◎○○○○○○※ です。 この場合には、《?>Xと判定》されていません、まだまだ、2回の判定を受けられます。 すなわち ◎○○○○○○※が3回の推定値の宣言で処理できれば良いことになります。 この例題は以下略とします。 === 話を元に戻します。一般化してみます。 子どもたちが1回だけ推定値の宣言をできるときには、 ◎○※ よりも長い○の列を処理できません。 子どもたちがn回だけ推定値の宣言をできるときに処理できる○の個数を f(n) とすると f(1)=1 です。 また、f(n)個の○が並んだ ◎○○○○○……○※ において、最初に推定値として着手すべき値は、○のうち左からn番目です。 《?>Xと判定》のケース ◎○←全部で(n−1個)→○※※※※※ このときには残り(n−1個)の ○を左から順に片付けます。 《?≦Xと判定》 ◎←全部で(n+1個)⇒◎○○○○○○※ このときには最初にf(n)個あった○がn個減っています。 ですから残り(n−1)回の推定値の宣言で、(f(n)−n)個の○を処理できれば良いこととなります。 === 以上から、以下のようになります。 f(1)= 1 f(2)= 2+f(1) f(3)= 3+f(2) f(4)= 4+f(3) …… f(11)= 11+f(10) f(12)= 12+f(11) f(13)= 13+f(12) ここで立ち止まりますと f(13)=1+2+3+4+5+6+7+8+9+10+11+1213=91 ですから、13回の推定値の宣言だけでは、出題の、5100≦x<15000 の98個の○を処理できないことがわかります。 f(14)=105ですから、14回の推定値の宣言で処理するのに充分とわかります。 】 |
解答判定ワード | 【手順をつくせば14回となります】 |
お年玉がもらえますっ おめでとうございます。 | 【14】 |
お年玉がもらえますっ おめでとうございます。 | 【14】 |
スローガン:囁き欄あり(答えがわかったら皆に内緒で囁いてね!)
ロック中につき閲覧専用となってますPage: 1 | 2 | 3 | |
Page: 1 | 2 | 3 | |