問題7823・・・やどかりさんのブログ http://blogs.yahoo.co.jp/oka_yadokary/34767964.html より Orz〜
図のように、縦に並んだ５マスの 上２マスに白の碁石，下２マスに黒の碁石を置いてあり、
１回の移動で 次の条件の碁石１個を空所に動かし 最少の移動回数で、
その配置が逆である 下２マスが白石，上２マスが黒石になるようにします。
(移動1) 空所のすぐ上のマスの石 または 空所のすぐ下のマスの石．
(移動2) 空所のすぐ上２つのマスの石の色が違うとき 空所の２つ上のマスの石
または 空所のすぐ下２つのマスの石の色が違うとき 空所の２つ下のマスの石．
このとき、黒の矢印で示した「移動1」が４回，赤の矢印で示した「移動2」が４回です。
では、縦に並んだ 55マスの上27マスに白石，下27マスに黒石を置き、最少の移動回数で
その配置を逆にするときの 「移動1」は何回？ また、「移動2」は何回？
解答
白石，黒石をそれぞれ n 個を (2n＋1)マスに置く場合を考えます。
最少の移動回数にするために、白石は下方向，黒石は上方向の移動に限定します。
また、白石からの移動でも黒石から移動でも同じことですので、白石からの移動にします。
一番上のマスまたは一番下のマスからの同じ色の石の連続はＯＫですが、
それ以外で同じ色の石が連続していると 他の色の石の移動ができなくなるので、
移動の仕方はおのずから決まります。
( 下図は n＝4 の場合の例ですが、次に移動させる石を ▽▲ △▼で表しています )
白黒白黒……と移動する碁石の個数を数えると、１個，２個，３個，……，ｎ個 となり、
移動回数 1＋2＋……＋n＝n(n＋1)/2 で、上から白黒が交互に並びます。
次に、最終状態からの逆移動を考えると n(n＋1)/2 回の移動で 下から白黒が交互に並びます。
上から白黒が交互に並んだ状態を 下から白黒が交互に並ぶ状態にするのにｎ回の移動が必要で、
移動回数は全部で n(n＋1)/2＋n＋n(n＋1)/2＝n(n＋2) です。
また、2n 個の石を (n＋1)マス分移動させますので、のべ 2n(n＋1)マスの移動になります。
よって、「移動2」は 2n(n＋1)−n(n＋2)＝n2 回で、「移動1」は n(n＋2)−n2＝2n 回です。
n＝27 のとき、「移動1」が 2･27＝54回，「移動2」が 272＝729回の、合計783回の移動になります。
[参考]
白石，黒石をそれぞれ n 個を (2n＋1)マスに置く場合を考えます。
最少の移動回数にするために、白石は下方向，黒石は上方向の移動に限定します。
実際に配置を逆にする方法があるかどうかを別にすれば、
どの ○と● についても、○● を ●○ にするのに、○●×⇒×●○ または ×○●⇒●○× 、
○，● のいずれかが飛び越すことになり、その回数は n2 です。
全部で 2n 個の石を (n＋1)マス分移動させますので、
隣への移動回数は 2n(n＋1)−2n2＝2n です。
*最初なかなかわからず…^^;
同じ色の石は相手方の石n個を飛び越すか飛び越されるかしないといけない…
2-2の場合、2回飛び越し/飛び越され、2回は一つ移動
1-1の場合、1回飛び越し/飛び越され、2回は一つ移動
so…n個のどの石も同じようになるわけだから…n*(n+2)回と推論…^^;;
移動2はn*n回、移動1は2n回ということ…
つまり、n=27 の場合なら…
移動1=2*27=54回
移動2=27^2=729回
合計=783回 ♪ (ちといい加減…^^;)
かえるの飛び越しという問題をむかしひよこさんのサイト
|
コメント（1）
