面白い問題おしえて~な@数学板 数理パズル20051015062236

※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

数理パズル10-4

427 名前:426[sage] 投稿日:2005/10/15(土) 06:22:36
これだけでは何なので、問題を出してみます。
以下のような半無限(上と右方向に無限)な平面があります。
一番左下に●が一つだけ置かれています。

++++++
++++++
++++++
++++++
●+++++

これに対して、次のような操作を考えます。

*盤上の●を一つ取り除き、代わりに●が有ったところの一つ上と一つ右に新しい●を配置
+++  +++
+++  ●++
●++  +●+

このとき、●の上や右に既に別の●が有った場合はこの操作を行うことができません。

以上の操作を繰り返して、左下の3x3のマスから●を除くことができるでしょうか?
できる場合はその手順を、できない場合はその証明をしてください。

解答

431 名前:132人目の素数さん[sage] 投稿日:2005/10/15(土) 16:27:19
このように考えるのはどうだろう?

>このとき、●の上や右に既に別の●が有った場合はこの操作を行うことができません。
まず↑このルールを無視して●の重なりを許すことにする
(元のルールでもこの無視したルールの手数以上かかるのは明らか。)

このとき3x3のマスから●をすべて追い出すのに最低かかる手数を考えると19手かかる。(詳細は略)
一手に付き一個●が増えるのだから、つまりその時点で3×3のマスの外に20個の●があることになる。

さて、この20個の●は、3×3のマスの外に出すことしか考えられていないから19手では4×4より外にはない。
ところが3×3のマスの外でかつ4×4のマスの中には7個の●しか存在できないので
20個の●のうち少なくとも13個は4×4の外に追い出すためにさらに移動をしなくてはならない。
もちろんその移動で13個の●は倍の26個に増えているはずだ。

同じように
26個 の●のうち5×5のマスの中にいられるのは9個だけ。少なくとも17個は5×5の外にあるのでその倍の
34個 の●のうち6×6のマスの中にいられるのは11個だけ。少なくとも23個は6×6の外にあるのでその倍の
46個 の‥
そのようにして、このゲームを終えるためにはこの数列がどこかで0以下にならないといけないはずなのだが‥

432 名前:431[sage] 投稿日:2005/10/15(土) 16:34:33
訂正

これを
さて、この20個の●は、3×3のマスの外に出すことしか考えられていないから

これに
さてここで元の●を重ねてはならないルールに立ち戻る。
この20個の●は、3×3のマスの外に出すことしか考えられていないから

442 名前:132人目の素数さん[sage] 投稿日:2005/10/16(日) 01:10:00
それぞれの位置に数を与えて●のある位置の
数の合計が一定になるようにする。
最初の位置に1を与えそこから一つ進むごとに1/2倍の数を与えれば
全部で4で3×3の部分は3+1/16だから全て出すことはできない。

453 名前:132人目の素数さん[sage] 投稿日:2005/10/16(日) 02:40:02
生まれた?●をずっと上に追いやって右側に出来たやつは
それもまた上に追いやってって順繰りにやっても3×3の枡から出ることがないのか?

454 名前:452[sage] 投稿日:2005/10/16(日) 02:52:42
いやいや、そんなことは無いか。ヒントには なるだろうけど。

>>453
俺もそれ考えたけど、オセロの盤で試してみたら無理っぽかった。

455 名前:132人目の素数さん[sage] 投稿日:2005/10/16(日) 03:17:52
>453
無理だよ。

上の議論からもうちょっとだけがんばって見ると
+
++
+++
からなくすこともできないことがわかる。

457 名前:132人目の素数さん[] 投稿日:2005/10/16(日) 07:36:54
>456
あんまり面白くはないんだけど、
マスを全部●で埋めても、ってあったけど、
実際には全部うめることができないでしょ。
例えば一列目には、どんな操作をしても、●は一つしか置けない。
だから一列目に置かれている●の合計値は高々1/8。

こんな風に、より正確に数えてやると
さらに小さな領域でも無理だということがわかる。