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

FAQ

RSS
@quiz_tairikuさんをフォロー

取り出しゲーム（久しぶり投降）

難易度：★★ 　

４０１３ 2012/01/13 18:06

どうも、久しぶりに投降します。４０１３です。
以前は、かってに問題を投降終了にしてドロンするという勝手な真似をしてしまい、すいませんでした。
また、「脱出大陸ＤＥＹＯ！」はまたいつか再開するかもしれませんが、そのときはコードＮＯなどを用いず、普通のクイズとして皆さんと楽しくやっていきたいと思います。
「脱出大陸ＤＥＹＯ！」ＬＶ１・ＬＶ２に解答して下さいました、ずんさん・シャンさん・そうそうさん・あーさん・ケービィさん・受けないさん・パソコン故障さん・羔さん・ずんさん・1412さん・ma-gさん、勝手なことをしてすいません。

前置きが長くなりましたが、クイズ（パズル）を１つ。

『取り出しゲーム』
α君とβ君で「取り出しゲーム」というのをやることにしました。
ルールは
①透明な箱に2個以上の自然数個だけボールを入れる。（ボールは全て同じ物）
②先攻の人から、その箱の中からいくつかのボールを取り出す。
③この時、ルールとして「取り出せるのは箱の中に入っているボールの半分以下の自然数個だけ、そして必ず1個以上取り出さなくてはならない」となっている。

（例えば、箱の中にボールが10個入っていたら、取り出せるボールは　10÷2＝5　より、1個～5個です。）

④先攻→後攻→先攻→後攻…と交互に繰り返し、ルールに従って取り出すことが出来なくなった方が負け。

というルールです。

α君が先攻で、最初の箱の中のボールの数は1000個で始めました。
実はこのゲーム、先攻には必勝法があるのですが、この必勝法を使う時、α君は最初にいくつボールをとりだせばよいでしょうか？

返信は1週間に1度くらいになってしまうかもしれませんが、よろしくお願いします。
解答発表は2月4日（土）頃の予定です。（延期有）
すごい解答、変化球解答、お待ちしています。




	【答えは489個。つまり、残りを511個になるようにします。それから、残るボールを255個→127個→63個→31個→15個→7個→3個→1個　となるようにしていきます。～説明～まず、このゲームにおける勝利は、「自分の番で1個にして相手に渡す」ことです。なぜなら、箱の中に2個ある時は2÷2=1より1個取り出せますが、1個の時は1÷1=0.5より、0.5以下の自然数はないので、取り出せなくなるからです。まずは、4個の時を考えます。この時、取り出せるのは1個か2個です。 2個取り出すと、相手は残り2個から1個にするので、自分は取り出せなくなり負けです。しかし、1個だけならば、相手は3個の状態になります。3÷2＝1.5より相手は1個しか取り出せないので、残るのは2個、つまり1個取り出して勝ちになります。つまり、自分の番に3個にできれば勝ちと言えます。同様に、8個の場合は、1個取り出して7個にすれば、相手は7÷2＝3.5より取り出せるのは1～3個、つまり4～6個残ります。このとき、4-1=3,5-2=3,6-3=3よりどの場合にも3個残しに出来ます。つまり、7個にしたら勝ちとも言えます。同様に、15個残せば7個に出来ます。ここで、法則を考えます。 1→3→7→15…　そう、（２のべき乗ー１個）を残せば勝てるということです。このとき、1000÷2=500 より、500以上1000以下の（２のべき乗ー１）の数を考えると、511が当てはまります。 1000-511=489、よりα君は489個取り出せば勝てるのです。】

回答募集は終了しました。

▲ △ ▽ ▼ No.1

４９７個？

サッチ 2012/01/13 18:08

わからないな

４０１３残念、違います。

▲ △ ▽ ▼ No.2

最初に233個取り出す
以下β君が取り出すときにα君が残す個数を書く
767→383→191→95→47→23→11→5→2

nomanoma 2012/01/13 19:30

これでかてるぞα君!!!

４０１３おしいです！ (;o;)

このようにした時、β君は2個ある時に　2÷2＝1　より1個取り出すことができるので、α君は負けてしまいます！
うまい具合にα君の順番で2個残るようにしないと…

▲ △ ▽ ▼ No.3

答え
最初に487個取り出して513個残すようにすればよい。
こうしておけば以後順番に取り出していってα君が取ったあと3個残るようにすることが出来る。このあとβ君が取ればα君の順番で2個残り、そこで1個を取り出してα君の勝ち。

河野真衣 2012/01/14 14:44

ややこしいけど、これでいいような気がする。どうかな?

４０１３すいません…
大正解！と書いていたのですが、よくよく考えてみると違うのでは？ということが発覚しました。河野真衣さん、本当にすいませんでした。
時間がありましたら、ぜひもう１度解いていただけるとうれしいです。

▲ △ ▽ ▼ No.4

一回で取り出せる個数が１～現在の個数の半分だとする。

n=2
2→1
a win

n=3
3→2→1
b win

n=4
4→3→2→1
a win

n=5
5→3→2→1
a win

n=6
6→3→2→1
a win

n=7
7→5→4→3→2→1
a win

偶数のとき半分とり、
奇数のとき２とる。

n=1000
1000→500→250→125→123→121→119→…5→3→1

un 2012/01/14 14:55

だめ？

４０１３残念…おそらく違います。
1000個の時、例えば
α）500個→β）250個→α）125個→β）63個→α）61個→β）31個→α）29個→β）15個→α）13個→β）7個→α）5個→β）3個→α）2個→β）1個→α）できず負け。
となってしまうことがあります。
β君がいくつ取ろうと勝てる「必勝法」をお願いします。

▲ △ ▽ ▼ No.5

489個
残り個数511個
βが次に取り出せるのは1～255個
βが取り出した後の残り個数は510～256個
残り個数が255個になるよう取る。
（510/2=255なので、必ずそう取れる。）

βが次に取り出せるのは1～127個
βが取り出した後の残り個数は254～128個
残り個数が127個になるよう取る。
（254/2=127なので、必ずそう取れる。）

βが次に取り出せるのは1～63個
βが取り出した後の残り個数は126～64個
残り個数が63個になるよう取る。
（126/2=63なので、必ずそう取れる。）

βが次に取り出せるのは1～31個
βが取り出した後の残り個数は62～32個
残り個数が31個になるよう取る。
（62/2=31なので、必ずそう取れる。）

βが次に取り出せるのは1～15個
βが取り出した後の残り個数は30～16個
残り個数が15個になるよう取る。
（30/2=15なので、必ずそう取れる。）

βが次に取り出せるのは1～7個
βが取り出した後の残り個数は14～8個
残り個数が7個になるよう取る。
（14/2=7なので、必ずそう取れる。）

βが次に取り出せるのは1～3個
βが取り出した後の残り個数は6～4個
残り個数が3個になるよう取る。
（6/2=3なので、必ずそう取れる。）

βが次に取り出せるのは1個
βが取り出した後の残り個数は2個
残り個数が1個になるよう取る。
（というより、取らざるを得ない。）

この時点で、βは手詰まり。

G_Beta 2012/01/14 23:14

切り捨て半分ってのがミソだな。

それにしても、なんで僕が負ける前提で話を進めているんだろうね。

４０１３大正解！完璧です！おめでとうございます！

いえ…別に違いますよ？ (・o・∥)

この問題において負けてしまうのはβ君であって、Ｇ＿Ｂｅｔａさんのことではないですよ！ (^^)

▲ △ ▽ ▼ No.6

４０１３ 2012/01/15 09:04

すいませんでした。
判定ミスをしてしまいました。
今後はこのようなことがないようにしていきます。
河野真衣さん、本当にすいませんでした。

▲ △ ▽ ▼ No.7

nomanoma 2012/01/15 17:30

まちがってますでしょうか…
α君が2個残せば、次にβ君が1個とって、最後の1個はα君が取れると思うのですが…

４０１３いえ、1個残っている時に1個取り出そうとしても、　1÷1=0.5　より、半分以下の自然数個という条件に当てはまらなくなってしまいます。（１＞0.5より）
かといって、必ず1個以上取り出さなくてはならないという条件もあるので、α君はルールに沿って取り出すことができず負けになってしまうのです。

▲ △ ▽ ▼ No.8

G_Beta 2012/01/15 18:23

nomanomaさん@>>7

”取り出せるのは箱の中に入っているボールの半分以下の自然数個だけ”

という文面を考えると、
たとえば残り個数が11個の時は
11/2=5.5　つまり5.5個以下の自然数個だけ取ることができることになります
つまり、切り上げ半分の6個は5.5個を超えるので取れず、
切り捨て半分の5個までしか取れないということのようです。

同じように、残り個数が1個の時は
1/2=0.5 つまり0.5個以下しか取れなくなる、すなわち
0個しか取る選択肢がなく、手詰まりになるということのようです。

ここが問題文として誤解を生んでいるんじゃないかと思ったので
コメントさせていただきます。

４０１３解説、ありがとうございます。 (^_^)

▲ △ ▽ ▼ No.9

489個

たぬきおやぢ 2012/01/15 22:44

ですね。

４０１３正解！おめでとうございます！
時間があれば、解説の囁きもよろしくお願いします。

▲ △ ▽ ▼ No.10

答え
最初に489個取り出して511個残せばよい。
511個残せばあとはβ君がどんな取り方をしても、α君は自分が取った後の残り個数を
255→127→63→31→15→7→3→1とすることができ、α君の勝ちとなる。

河野真衣 2012/01/16 19:27

4013さん、そんなに謝ってもらうとかえってこちらが恐縮します。私は別に気にしていませんので。
二度目の回答を考えていたら、中学生の孫が横からいろいろ口を出すので、「それじゃ、あんたがやってごらんよ。」と言ってやったら、囁き欄に書き込んだような答えを持ってきました。答えの◎×を判定する自信がないのでよろしく。もし◎なら、お年玉の追加をしなくてはいけませんので、◎であって欲しいような欲しくないような…。

４０１３大正解！おめでとうございます！ (^_^)

しかし、これでお年玉追加になってしまいましたね。 (・o・∥)

▲ △ ▽ ▼ No.11

最初に489個とる。
その後の残す数は
511→255→127→63→31→15→7→3→1

nomanoma 2012/01/16 20:22

G_Betaさんありがとうございました (＞o＜)

もう一度考え直しましたので、判定よろしくお願いします

４０１３大正解！おめでとうございます！
そうです！そういうことなんです！ (^_^)

▲ △ ▽ ▼ No.12

初手 489個とる

通りすがり 2012/01/17 00:04

少ない数で試していたら気付いた

４０１３正解！おめでとうございます！ (^_^)

よろしければ解説もお願いします！

▲ △ ▽ ▼ No.13

ヒミツ

un 2012/01/17 03:24

これでっ。

▲ △ ▽ ▼ No.14

解説：
(1). 1個にして相手に渡すと勝ちが確定する。
(2). (2のn乗-1)個にして相手に渡すと、自分の番には決して(2のn乗-1)個の形にはならない。相手から(2のn乗-1)個以外が渡された場合に(2のn乗-1)にして相手に渡すことが可能である。つまり、一旦(2のn乗-1)個にして相手に渡すことに成功すれば、次回から常に(2のn乗-1)個にして相手に渡すことが可能となる。
(3). 上記(2)をn=1になるまで繰り返せば必ず勝てる。
詳細：
(2)をさらに詳細に説明する。(2のn乗-1)個にして相手に渡すと、相手が次に取れる数は1個以上(2の(n-1)乗-1)個以下である。自分に渡されるのは(2の(n-1))乗以上(2のn乗-2)以下の数となる。このとき、1個から(2の(n-1)乗-1)個取ることで、次に相手に(2の(n-1)乗-1)個を渡すことができる。
まとめ：
このゲームは最初の数が(2のn乗-1)であれば後手必勝。それ以外は先手必勝である。

たぬきおやぢ 2012/01/17 10:04

解説です。

４０１３その通りです！分かりやすい解説、ありがとうございます！ (^_^)

▲ △ ▽ ▼ No.15

答え：489個
必勝法：(２のべき乗)-1 残すようにする。

ＲＥＥ 2012/01/17 10:05

うむ

４０１３大正解！おめでとうございます！ (^_^)

▲ △ ▽ ▼ No.16

最初の答え：フィボナッチ数列の系列にし、なおかつ相手が１になるように条件を合わせて取る。
最初の答え訂正：系列ではアルファベットで割り振られた４種があり、誤解を招きますので、以下のように訂正します。「フィボナッチ数

列の数になるようにして、なおかつ相手が最後に1になるように条件を合わせて取る。」
以下、プログラムです。なお、石取りゲームは対戦はできません。
「十進ベーシック」で開くと吉。
【フィボナッチ数列】です。「十進ベーシック」に付属しているプログラム集もあるようです。
【石取りゲーム】Aが勝った後、Bの手番になる問題を修正。
▼▼▼ここから【フィボナッチ数列】のプログラム▼▼▼
1000 PRINT"フィボナッチ数列を何個まで求めたいですか？"
1100 PRINT"求めたい個数nを自然数で、半角英数を用いて入力してください。"
1200 INPUT n
1300 DIM A(n+2)
1400 LET A(1)=1
1500 LET A(2)=1
1600 FOR i=1 TO n
1700 LET A(i+2)=A(i)+a(i+1)
1800 PRINT i;A(i)
1900 NEXT i
2000 END
▲▲▲ここまで【フィボナッチ数列】のプログラム▲▲▲
▼▼▼ここから【石取りゲーム】のプログラム▼▼▼
!このプログラムではコンピューターとの対戦はできません。人対人で対戦してください。
0100 PRINT"石取りゲームです。ルールは二つです。"
0200 PRINT"ルール(1)山となる数nの半分以下の数を取ることができます。"
0300 PRINT"ルール(2)1の半分は0.5で、取れません。"
0600 PRINT"山となる数nを自然数で、半角英数を用いて入力してください。"
1000 INPUT n
1100 LET i=0
1200 PRINT "Aの番です。nの半分以下の数を半角英数で入力してください。"
1300 INPUT A
1400 IF A=<n/2 THEN GOTO 1600
1500 IF A>n/2 THEN GOTO 1200
1600 LET n=n-A
1700 LET i=i+1
1800 PRINT "A"
1850 PRINT " i A n"
1900 PRINT i;A;n
2000 IF n=1 THEN GOTO 2200
2100 IF n><1 THEN GOTO 2300
2200 PRINT"Bは1を取れないので、Aの勝ちです。"
2250 GOTO 3500
2300 PRINT "Bの番です。nの半分以下の数を半角英数で入力してください。"
2400 INPUT B
2500 IF B=<n/2 THEN GOTO 2700
2600 IF B>n/2 THEN GOTO 2300
2700 LET n=n-B
2800 LET i=i+1
2900 PRINT "B"
2950 PRINT " i B n"
3000 PRINT i;B;n
3100 IF n=1 THEN GOTO 3400
3200 IF n><1 THEN GOTO 1200
3300 GOTO 1100
3400 PRINT"Aは1を取れないので、Bの勝ちです。"
3500 END
▲▲▲ここまで【石取りゲーム】のプログラム▲▲▲

un 2012/01/17 13:23

長い回答ですみません。 (;o;)