問題 (3) は、9人掛けのベンチに何人かが座っており、誰も隣り合っていない。もし自分が座ろうとすると、必ず誰かの隣になる。この条件を満たすとき、ベンチに座っている人の数の最小値を求めよ、という問題です。

1. 問題の内容

問題 (3) は、9人掛けのベンチに何人かが座っており、誰も隣り合っていない。もし自分が座ろうとすると、必ず誰かの隣になる。この条件を満たすとき、ベンチに座っている人の数の最小値を求めよ、という問題です。

2. 解き方の手順

ベンチの席を $n_1, n_2, n_3, ..., n_9$ とします。

隣り合わないように人が座るためには、1人座ったら少なくともその隣の席は空けておく必要があります。

例えば、

$n_1$に人が座ったら、$n_2$には座れません。

$n_1$, $n_3$, $n_5$, $n_7$, $n_9$ に人が座れば、条件を満たします。このとき、5人座っています。

しかし、問題文より、自分が座ろうとすると必ず誰かの隣になるので、人が座っていない席が連続しているとそこに座ることが可能になります。

そのため、人が座っていない席は最大で1つまでです。

もし、4人だけが座っていた場合、5つの空き席があります。

すると、必ず2つ以上の空き席が連続するので、そこに座ることができてしまいます。

したがって、少なくとも5人が座っている必要があります。

$n_2, n_4, n_6, n_8$ に人が座っていたとすると4人です。このとき、自分は $n_1, n_3, n_5, n_7, n_9$ のどの席にも座れません。座ったら誰かの隣になるからです。

$n_1, n_3, n_5, n_7, n_9$に人が座っていたとすると5人です。このとき、自分は $n_2, n_4, n_6, n_8$ のどの席にも座れません。座ったら誰かの隣になるからです。

人が5人座っているとき、空いている席は4つです。

5人が座っている席の間には最大で1つの空き席しかありません。

したがって、5人が座っている場合の空き席は最大で1つです。残りの席は両端に座ることで隣に人がいなく座ることができてしまうため、条件を満たしません。

したがって、人が隣り合わず、かつ、どこに座っても必ず誰かの隣になるためには、ベンチに座っている人は少なくとも5人でなければなりません。

例えば、

$n_1, n_3, n_5, n_7, n_9$ に人が座っている場合、自分が $n_2, n_4, n_6, n_8$ に座ろうとすると隣に人がいるので座ることができません。

3. 最終的な答え

5人