クイズ大陸クイズ大陸

参加型ナゾトキサイト『クイズ大陸』で、脳トレをどうぞ!

FAQ
feedRSS


財布の中のお年玉をゲットしよう
難易度:★★★  
?s_hskz 2015/12/18 13:22
 
太郎と次郎は双子の兄弟です。毎年の正月の親からの《お年玉》は、親から出されるパズルを解ければもらえ、解けなければもらえないという、子どもにとっては残念なしきたりになっています。
そこで、来年の春に《お年玉》をもらえる確率を少しでも上げたいと、太郎と次郎は年の暮れも近い頃、親に交渉してみました。
太郎「ねえ、来年のお年玉のことなんだけど、いつもの問題、いまのうちから教えてくれないかなあ。」
親「?…いや、来年の問題は簡単にするつもりだったし、今から聞いたら面白くないんじゃないの?」
次郎「そこをなんとか。ねえ、お願いだよー。」
親「ふーん……では教えてやろう。」
太郎・次郎「やったあ、ありがとうっっ!!」

兄弟が聞いた問題は、かいつまむと以下のようなものでした。

1:2人が個々にもらえるお年玉の金額Xを当てること、そして当てるための確実かつ最短最良手順を探りあてることが目標。当然のことながら金額は平等。合計金額は2X。当日は財布の中にお年玉をいれてあるというけれど、触らせてはもらえない……

2:お年玉の金額Xは100円刻みの金額である。1円単位や10円単位の端数はない。

3:Xは5000円より大きく、15000円より小さい。

4:金額を当てるルールは以下の通り。

(1)太郎がXの推定値を言う。(100円刻みに限る。)推定値がX以下ならば再度(1)へ、Xより大きければ(2)へ。分岐の判定は親が行う。
※但し、子どもたち側に自信があればいつでも(3)へ。

(2)次郎がXの推定値を言う。(100円刻みに限る。)推定値がX以下ならば再度(2)へ、Xより大きければ(3)へ。分岐の判定は親が行う。
※但し、子どもたち側に自信があればいつでも(3)へ。

(3)太郎と次郎がここまでで推定値を述べた回数が、(あらかじめ親が調べておいた)最良手順による回数を越えていたら、お年玉はもらえない。終了。そうでなければ(4)へ。

(4)太郎と次郎は協議のうえ、Xの最終推定値を言う。これがはずれていれば終了。お年玉はもらえない。


太郎と次郎は抗議しました。
「難しいじゃないかっ」

親「今から問題教えるんだから文句は言わないこと。お前たちも足し算できるんだからこんな問題は簡単だろう?……それに、金額もはずんである。ありがたく思いなさい。今年は3000円だったんだし。」
太郎と次郎「今年は問題解けなかったんだ!!(涙ぐむ)」

===

さて出題です。お年玉の金額Xを当てるために2人が推定値を言う回数は何回ですますことができるでしょう。(1)と(2)とで推定値を述べる回数の合計についてお答えください。(4)での、最終推定値を述べることは、回数には含みません。
もちろん、最良手順にして最小回数、それでいて確実にお年玉がもらえなくてはいけません。

かってに君をやとっています。自然数のみ半角で推定回数の正解を当てると反応すると思います。(たまに失敗するかもしれません……)
 
Answer発見的に解いていきましょう。
 
次の図で、◎はお年玉金額=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
■
回答募集は終了しました。

このクイズのヒント

    ヒント知らないよ

このクイズの参加者(6人)

ジャンル・キーワード

携帯用ページ


携帯電話のQRコード読み取り機能でこのページを見られます。

広告 お買い物は下記のリンクからどうぞ

広告
Codyl Hi!
広告

広告


広告
クイズ大陸関連書籍