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.
On
This is not really an answer ........Fill the pigeonholes in blocks of 3 with 1 separator (shown as ~) 123~456~789~101112~131415~161718~192021~222324~252627 You can see that 27 is the max that can be occupied with 4 in a row. So if 28 or more seats are occupied, you always have 4 or more consecutive occupied seats. I just made many people's explanation into that...........What is The GENERALISING statement for this type of pigeonhole questions?
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.