「今月の問題」　第７９回　（平成１８年４月）

石の入れかえゲームに挑戦しよう！


　上図（ア）のように、白と黒の２個ずつ、まん中に１個分の枠をあけて並んでいます。

　この石を次の１、２のルールで、白黒関係なく１つずつ動かし、図（イ）のように、白と黒の石を入れかえることにするゲームです。

（ルール１）
あいている枠に１つ分だけ横にずらすことができる。

（ルール２）
色の違う石を、１つだけならとびこすことができる。


　

　

　左の問題を考えたところ、石を動かす回数をできるだけ少なくすると、上図のように８回でできることがわかりました。また、そのうち（ルール２）の色の違う石をとびこす回数はACDFの４回であることがわかります。

　ここで問題です。白と黒の４個ずつの石をできるだけ少ない回数で入れかえることにします。この時、（ルール２）の違う石をとびこす回数を求めて下さい。

　

＜正解者一覧表＞　 　　　　　　　　
正解者順位 　　　　ｎａｍｅ　　　 　　メール到着日時　　 　　備　考　　
　１ゴンとも　さん2006/4/1　0:18　
　２teki　さん2006/4/1　0:26大阪府　
　３石井怜　さん2006/4/1　0:30京都府京田辺市14歳
　４ふじも　さん2006/4/1　0:33大阪府池田市　
　５teki　さん2006/4/1　0:26大阪府　
　６寺脇犬　さん2006/4/1　0:45　
　７経友会の進作　さん2006/4/1　1:03京都府木津町・67歳
　８oguchan1　さん2006/4/1　1:07鹿児島県　
　９りーくん　さん2006/4/1　1:09埼玉県　
１０テ　さん2006/4/1　1:18三重県　
１１いちもく　さん2006/4/1　5:57立川市　
１２翔鶴　さん2006/4/1　14:12　
１３巷の夢　さん2006/4/1　17:14　
１４川上智弘　さん2006/4/1　17:25兵庫県生まれ
１５2709　さん2006/4/1　23:54兵庫県西宮市
１６なにわ　さん2006/4/2　1:42西宮市　
１７信三　さん2006/4/2　5:36シリコンバレーの住人
１８lapin　さん2006/4/2　9:55大阪府交野市
１９uchinyan　さん2006/4/2　21:42東京都
２０kasama　さん2006/4/2　23:26和歌山県プログラマ
２１Michael　さん2006/4/3　0:33　
２２tl　さん2006/4/3　1:22福岡県飯塚市
２３una　さん2006/4/3　10:28答えと年齢が同じです
２４fisherman　さん2006/4/3　11:59豊岡市
２５カエ　さん2006/4/3　12:44千葉県
２６中1(進級)航空アニマル　さん2006/4/4　17:33東京都26市内
２７翔　さん2006/4/4　20:08香川県　
２８imopy　さん2006/4/5　13:37　
２９ぴーしゅん　さん2006/4/5　19:01　
３０CHOPELIX　さん2006/4/7　3:34茅ヶ崎市民　
３１エトランゼ　さん2006/4/8　3:40　
３２スモークマン　さん2006/4/8　21:22目指せ囲碁4段！　
３３koba　さん2006/4/9　10:19　
３４nobu　さん2006/4/11　23:42石川県　
３５すてっぷ　さん2006/4/30　16:30　

答えは、１６回です。

　


　
[194] これはカエル飛び問題と 投稿者：ゴンとも 投稿日：2006/04/01(Sat) 00:47 

本(NHKの中学実力アップコース1997　ワンダー数学ランド)
にありました。今回問題の答えは飛び越しの回数でしたが
最小何回の手順で終わるかだと難しいと思います。
その本を見るとn=3(15回が最小)で大変そうで本問でn=4は
さぞかしでしょうか?
今風邪引いてるのであとやりたいと思います。
(やらないかもしれません。)


[193] 一般的に 投稿者：teki 投稿日：2006/04/01(Sat) 00:19

ｎ個ずつの石を入れ替えるのに必要な飛び越しの回数はｎ＾２回になります。
理由は明白で、ｎ個の石がｎ個の石を全て飛び越えたときに位置が入れ替わるからです。

　

メールでも送っていただきました。

teki　さんより

４個の白石が、４個の黒石を全て飛び越えると、位置が入れ替わ
るため、４×４で、１６回ですね。
一般的にｎ個ずつの石を入れ替えるのに必要な飛び越しの回数は
ｎ＾２回になります。

テ　さんより
白石を@A　BC　黒石をAB　CDとして第１段階から第５段階まで移動する。
第１段階　@A　BC　AB　CD
第２段階　@A　AB　BC　CD
第３段階　AB　@A　BC　CD
第４段階　AB　@A　CD　BC
第５段階　AB　CD　@A　BC
第１段階から第２段階のように入れ替えるのに　ルール２を　４回使う。
第２段階から第３段階のように入れ替えるのに　ルール２を　４回使う。
第３段階から第４段階のように入れ替えるのに　ルール２を　４回使う。
第４段階から第５段階のように入れ替えるのに　ルール２を　４回使う。
たがって、　ルール２を１６回使う。

翔鶴　さん
1個の石が4個の石を飛び越えなければならない。
飛び越える石は4個あるので、
4×4＝16 [回]
です。

経友会の進作　さんより
（１）：白黒2個ずつの場合、色の違う石を飛び越す
　　　　回数は4回。
（２）：このようにK個の同色の石がこれに相対する
　　　　K個の異色の石を全て飛び越し、入れ替えが
　　　　完成するのには、K^2回の飛び越しを要する。　　　　
（３）：題意はK=4なので、4^2=16。即ち16回である。
　答え：16個回。