GPCC2006問題

シンペイ

ボードゲーム「シンペイ」で、序盤戦のうちで敗北する駄目な手を洗い出せ (ゲームを完全に解いても良い)

例えば2手目で、1手目に隣接しない位置に置くと、負けてしまう。このような駄目な手をなるべくたくさん見つける。

シンペイのルールについては、発売元のバンダイの解説を参照。ゲームの考案者は高橋晋平氏。Web上で遊ぶこともできる(要FLASH)。

ゲームの細かいルールを簡単にまとめておく。

• 勝ちの条件
  • 4個並べても勝ちではない。
  • 相手のコマを3個並べても相手の勝ちにはならない。
  • 4個並んだ状態から1個移動しても勝ちではない。
• 飛ばし方
  • コマをはさんだら必ず別のマスに飛ばさなければならない。
  • 2,3,4個同時に飛ばす場合は、すべてその2,3,4個のマス以外の場所に飛ばさなければならない。
  • 飛ばした結果自分のコマがはさまれても、飛ばされない。
• 4個とも動けなくなった場合はパスになる。

解答へ

和にならない分割

  1,2,3,...N の数字を順番にk 個の集合のどれかに入れていく
  そのとき、どの集合のどの3つの元a、b、c をとっても、
          a + b = c
  の関係を満たさないようにする。
  k = 2, 3, 4 に対して条件を満たす最大のNはすでに求まっている。
  k = 5 に対して条件を満たす、なるべく大きいNを見つけよう。

参考:
"Dr. Ecco's Cyberpuzzles: 36 Puzzles for Hackers and Other Mathematical Detectives" (amazon)
また、「思考力を養う数学パズル」デイビッド・Ｌ・シルバーマン の「ラック(棚)」の問題

分割の例: (k = 2 の場合)
    1 , 2 を適当に入れてみる
                                     集合1: { 1 }         集合2: { 2 }

    3を最初の集合1に入れてみる
                                     集合1: { 1 , 3 }     集合2: { 2 }

    4を集合1に入れると 1 + 3 = 4 となってしまうので
    集合2に入れるしかない
                                     集合1: { 1 , 3 }     集合2: { 2 , 4 }

    5はどちらでもよいが集合1に入れてみる
                                     集合1: { 1 , 3 , 5 } 集合2: { 2 , 4 }

    6はどちらにも入れられないので この場合5までしか入れられない
    ( 集合1で 1 + 5 = 6, 集合2で 2 + 4 = 6 となってしまう)

解答へ