読者です 読者をやめる 読者になる 読者になる

等間隔に並ばないように碁石を置く

問題

ずっと昔、小学校高学年の頃なので
すでに17年も前の話になってしまうのですが、
未だに解けない(解こうという意識すら芽生えない)難問があります。

白と黒の2種類の碁石を、
「等間隔に3つ同じ色が存在しないように」並べる。
例えば左から順に、白黒黒白黒白、と並べていくと、
○●●○●○
という状態になるが、これは題意を満たす。
7個目を黒とすると、3・5・7番目が黒となり
7個目を白とすると、1・4・7番目が白となるため、
この配置では6個まで碁石を置けたことになる。

それでは、題意を満たしたまま並べることができる
碁石の数の最大値は何個か?

この答えは8個となります。
例えば
○○●●○○●●
と並べれば、どの3つの同色の石も等間隔ではなく、
また9個目に白も黒も置けません。


8個まで並べられる全てのパターンは以下の6通りとなります。
(反転したものを同じと見なせば3通りです。)
○○●●○○●●
○●○●●○●○
○●●○○●●○
●○○●●○○●
●○●○○●○●
●●○○●●○○


さて、ここからが本題です。
「等間隔に3つ同じ色が存在しないように」
という条件を、
「等間隔にn個同じ色が存在しないように」
と変更すると、答えはどのようになるでしょうか?
(ただし、2 ≦ n とします。)


つまり、題意を満たす最大の個数を求める関数を f(n) として、
f(n) がどのような式で表せるか、という問題です。
上記の例では f(3) = 8 ということになります。


ちなみに f(2) = 2 は自明ですが、
f(4) を求めるにも一苦労するかと思います。
f(n) の一般式を求めるのは後述の本では
現時点で不可能、と書いてあったかと思うので、
(相当古い情報ではありますが。。。)

(1) f(4) を求めよ。
(2) f(5) を求めよ。
(3) f(10) を求めよ。

という入社試験にしても面白いかもしれませんね(誰得w)。
グーグルの採用試験のように「解けるとURLがわかる」
みたいなのもちょっと楽しそうです。


私が今の職に就く前に在籍していた
エリジオンという会社では上記のような問題を
懸賞問題として(1等はノートPC贈呈!)出題していたので、
エリジオンに入社したい方などは解いてみると良いかもしれません(笑)。


とりあえず手元では f(4) を
Python 2.5 / Celeron 1.46GHz / 2.0GB RAM の環境で
2秒程度の計算時間で求めることができていますが、
f(5)、ましてや f(10) となると
さらに高速化が必要ですね。
C/C++言語で実装しないと厳しいような気もします。


出典元は(確か)こちらの本です。

数学パズル・20の解法―これでキミもパズル名人 (ブルーバックス)

数学パズル・20の解法―これでキミもパズル名人 (ブルーバックス)

いかんせん随分と前の話なのでうろ覚えですが、
もしこの本に載っていなくても苦情は受け付けません(笑)。
中村義作さんの本は面白いものが多いので、
パズル好きな方は是非読んでみると楽しめると思います。