2
$\begingroup$

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.

  • 1
    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$.2013-03-27

2 Answers 2

4

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.

  • 0
    Hi Sam. The reason is that there are 35 = 4×8+3 seats. You can apply the pigeonhole to the first 32 seats like you did, so you know that out of those 32 seats, it is possible to fill 24 seats. Add to that the other 3 seats, and you see it is possible to fill 27 seats. (But not 28.)2014-11-19
0

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?

  • 0
    This really _is_ an answer, but needs a bit of spit and polish. Wellcome! But consider that this site looks for complete, closed (and we also wish for brilliant, no harm in wishing so near Easter ;) answers to questions. Please try for a more complete answer next time.2013-03-27