# Pigeonhole Principle question

There is a row of 35 chairs. Find the minimum number of chairs that must be occupied such that there are some consecutive set of 4 chairs or more occupied.

I would like to have some hints as to approach this problem. This isn't for homework or anything, I'm just curious as to what would be the best strategy for this problem.

-
I'd say worst case is groups of $3$ occupied with $1$ open seat between them. So that's $9 \times 3$ occupied seats and $8 \times 1$ open seats, i.e. $27$ occupied seats. So I think you need $28$ occupied seats. –  TMM Mar 18 '12 at 1:55
Uhm the best strategy is to try and use the pigeonhole principle? i.e. the title you gave the post. So are you asking how to use pigeonhole? –  john w. Mar 18 '12 at 2:50
Somehow everybody understands that the second sentence contains a negation (the word "not"), but unless my eyesight is really betraying me, there is no such negation. For me the answer is obviously $4$. –  Marc van Leeuwen Mar 27 '13 at 14:17

For every $4$ seats you need to keep at least $1$ open to not have $4$ consecutive chairs occupied. So divide the row in sets $S_k = \{4k + 1, 4k + 2, 4k + 3, 4k + 4\}$ for $k = 0, \ldots, 7$ and $S_8 = \{33, 34, 35\}$. For each set $S_0, \ldots, S_7$ you need to keep one seat open, so you need at least $8$ open seats to not have a sequence of $4$ occupied seats. This maximum can also be achieved, by leaving seats open at positions $4k$, for $k = 1, \ldots, 8$.
With respect to applying the pigeonhole principle: If you do have more than $35 - 8 = 27$ seats filled, then you have at least $25$ seats filled for $S_0, \ldots, S_7$. Since $25 / 8 > 3$, by the pigeonhole principle one of them must have at least $4$ seats occupied. But then you get a sequence of $4$ occupied seats. So if $28$ or more seats are occupied, you always have $4$ or more consecutive occupied seats.