Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
    
Sounds like the answer. Please add it! –  user21436 Mar 18 '12 at 2:09
    
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
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$. –  Marc van Leeuwen Mar 27 '13 at 14:17
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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?

share|improve this answer
    
As you mention, this "is not really an answer". Perhaps you have the germ of an idea for asking a generalized version of the question, although it isn't quite polished yet. However the Answer box is only for answers. –  hardmath Mar 27 '13 at 13:38
    
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. –  vonbrand Mar 27 '13 at 13:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.