GPCC2006問題


シンペイ

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

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

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

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

解答へ


和にならない分割

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

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

分割の例: (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 となってしまう)

解答へ