At first,
you might think you'll need people sitting in every other
seat to force the next person to sit next to someone else.
But that's not so -- it's enough to
have only every third seat occupied as shown in the following
picture (blue seats are occupied, red are empty):
And you can leave one seat unoccupied on either end.
Let's do a simpler version of
the problem to see what we really need.
If there were only
10 seats in the row, we could occupy seats 2, 5, 8 and 10, or
1, 4, 7 and 10. Either
way, we'll need to occupy 4 of the 10 seats.
How about 30 seats? The best
way this time is to occupy seats
2, 5, 8, 11, 14, 17, 20, 23, 26 and 29 -- this is 10 seats.
So for a row of 120 seats, it's
enough to occupy every
third seat starting with
seat number 2 -- this will make 40
occupied seats, and
then the next person will
have to sit next to someone already there.
If 120 seats are arranged in a row (that is one really long row!),
what is the least number of
seats that must be occupied so the next person seated must sit next to
someone?
