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

2 Answers 2

up vote 2 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
    
There are 8 pigeonholes.We need to find the minimum pigeons so that at least one pigeon hole contains 4 pigeons.In generalized pigeon hole principle if there are n pigeons and k holes at least one pigeonhole should have $\lceil n/k \rceil$ pigeons.Therefore if we have $\lceil 25/4 \rceil$=4.So why isn't the answer=25 but 28? –  sam_rox Nov 18 at 3:55
    
:typo not $\lceil 25/4 \rceil$ but $\lceil 25/8 \rceil$ –  sam_rox Nov 18 at 4:02
    
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.) –  TMM Nov 19 at 17:26

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

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.