『今週の問題−第122回』


今回のテーマは『サンタと雪だるまの入れ替え問題』です。
(生徒の入れ替え問題 Part4にあたります。)

今、次のように、サンタ4人と雪だるま3人(?)が交互に並んでいます。
これをサンタはサンタ、雪だるまは雪だるまで並ぶようにして欲しいのです。

 サンター雪だるまーサンター雪だるまーサンター雪だるまーサンタ
       ↓
 サンターサンターサンターサンター雪だるまー雪だるまー雪だるま
 または
 雪だるまー雪だるまー雪だるまーサンターサンターサンターサンタにする。
ただし、移動は次のようにして行います。

  1. 1回の移動で隣り合った2人を必ず同時に移動する。

  2. 空いている場所が2カ所あり、そこへ移動することができる。

  3. 最終的に全体が最初の位置から平行移動されていても、サンタと雪だるまが別れていればよいとします。
    ただし、並んでいる2人の間に、空間があってはいけません。
    サンタと雪だるまの間にも空きはなく、7人が連続して並んでいるようにしてください。

【問題1】

入れ替えの手順を示してください。


 Internet Explorer 4.0以上またはNetscape Navigator3.0以上の方は実際に実験してみることができます。
移動ボタンをクリックして動かしてみてください。
クリックしたサンタまたは雪だるまがその右隣とともに移動します。
もう一度やるときは、新規ボタンをクリックしてください。

◆図1  回数

履歴


【問題2】

サンタ5人、雪だるま4人になった場合、同じ条件で、入れ替えの手順を示してください。


それでは実際に実験してみましょう。

◆図2  回数

10 11

履歴


【問題3】

サンタ6人、雪だるま5人になった場合、同じ条件で、入れ替えの手順を示してください。


それでは実際に実験してみましょう。

◆図3  回数

10 11 12 13

履歴


【おまけ】

サンタ(N+1)人、雪だるまN人になった場合、入れ替えにかかる最短手数を求めてください。

【おまけ2】

クリスマスといえば、こちらをどうぞ。


 ●正解者リスト ●寄せられた解答

  解答用紙はこちらです。

 ◆過去問はこちらです。


 ◆ 今週の問題

数学の部屋へもどる。