Monday, April 6, 2015

[OlympiadXPH20150405] Seats in a Hall as Pigeonholes?

There are  25  rows of seats in a hall, each row having  30  seats.  If there are  680 people seated in the hall, at least how many rows have an equal number of people each?

     This is a mathematics olympiad type of question for primary / elementary school, I believe.  Let us make sure we understand the question.  Each row of seats has a certain number of people, which I shall call the “headcount”.  We want all the headcounts to be as different as possible, and yet we do not want so many rows to have the same headcount.  The number of rows with the same headcount should be kept as low as possible.  How low is low?

Solution 1
     One strategy to solve this is to start filling up the empty seats with as many as possible.  Indeed this is the approach taken by the official “model answer”, which for copyright reasons I cannot show.  However I am going to do something even better: to explain the solution visually.  Recall that the sum of an arithmetic progression is 
                   ½ ´ number of terms ´ (first term + last term)
     After filling up the empty seats with different numbers of people, we would have filled up  30 + 29 + ... + 7 + 6 = ½ ´ 25 ´ (30 + 6) = 450  seats.  This is stage 1, shown in orangey-yellow in the diagram below.  We have now  230  people remaining to be seated. 

     For stage 2, we try to fill in the remaining seats with as many people as possible but keeping the headcounts all different.  So we ramp up  6 to 30,  7 to 29,  8 to 28, ... etc.  The additional number filled up is  24 + 22 + ... + 2 = ½ ´ 12 ´ (24 + 2) = 156.  This is stage 2, shown in green.  We have  74  seats remaining.
     For stage 3, we ramp up  18 to 30,  19 to 29,  20 to 28, ... etc.  The additional number filled up is  12 + 10 + ... + 2 = ½ ´ 6 ´ (12 + 2) = 42.  This is stage 3, shown in blue.  We have  32  seats remaining.
     For stage 4, we ramp up  19 to 30,  20 to 29,  21 to 28, ... etc.  The additional number filled up is  11 + 9 + 7 + 5 = 32.  We are done.  This is the final stage, shown in pink. 

     It turns out that there is another way to look at the problem.  The above solution can be depicted in a “ball and bin diagram” as shown below.

There are  25  balls in the diagram, each representing a row’s headcount.  There are  4  rows with 30 people,  4 rows with 29 people, ...,  3 rows with 26 people,  3 rows with 25 people,  2 rows with 24 people, and  1 rows with 26 people.  We can actually calculate the totals for rows with repeated headcounts.  For example in the diagram, there are  4  layers of balls with each layer representing 30 + 29 + 28 + 27 (shown in dark turquoise) and the sum is = 4 ´ [½ ´ 4 ´ (30 + 27) ] = 456.  Those with rows with three of the same headcounts total up to  153  (shown in pink).  The rows with two of the same headcounts total up to  48  (shown in yellowish green).  There is one and only one row with  23  (shown in dirty green).  All this give a grand total of  680.  We can calculate the grand total  for every ball and bin diagram in this fashion.  We want a grand total of  680 and there must be 25 balls.  Using this diagram and a generalised version of the Pigeonhole Principle, we can have a very short and sweet solution.  Before that, let me briefly explain the Pigeonhole Principle.

     Let us say there are 30 pigeonholes and 31 envelopes.  We can represent this with a ball and bin diagram using 30 columns (for pigeonholes) and 31 balls (representing the envelopes).  If you try to put one envelope into each pigeonhole it is impossible.  One of the pigeonholes will have two envelopes.  In the ball and bin diagram, there will be at least column with two balls.  If you try to put everything flat to one layer, that is 30 balls and you still have one ball left.  You will have to put this remaining ball somewhere on the second layer.  This illustrates the Pigeonhole Principle.

     Likewise if you have  91  balls and  30 columns, there must be one column with  4  balls.  If it is all  3  balls, that fills with only 90 balls.  Your remaining ball has to go somewhere on the fourth layer.  This illustrates the Extended (or Generalised) Pigeonhole Principle.

Solution 2
     I am going to further extend the Pigeonhole Principle to Pigeonholes with Valuations (with some number attached to each configuration e.g. grand total).  We have 25 balls and 30 bins (columns) and we want to fill up the grand total number as quickly as possible achieving a grand total of  680, using as few layers as possible.

     Starting from  30  downwards and, using  3  layers,  we have  8  balls for each layer, filling all the colums for  30,  29,  ... ,  23.  We now have used up  3 ´ 8 = 24 balls that represents a grand total of  3 ´ [½ ´ 8 ´ (30 + 23) ] = 636.  There are 44 seats left over, but only one remaining ball.  The best we can do is to put the remaining ball at  22  for one layer.  That leaves  22 unallocated seats.  So  3  layers are not enough.  We need  4  layers.

     To show that  4  layers are enough, we can imagine filling up  4  layers of  30 + 29 + ... + 25.  That gives a grand total of  4 ´ [½ ´ 6 ´ (30 + 25) ] = 660,  with  20 left over.  This can be handled by putting the remaining ball on  20  for one layer.  And we are done.  The latter configuration is an alternative configuration to the one given in the model answer.  But most importantly, it works.  We have shown that at there must be least  4   rows with the same number of people each.  

1.  There can be more than one set of  4  rows with the same number of people each, but we just need to show that there exists (one set or more of)  4   rows with the same headcounts.
2.  One can imagine configurations that have  5  rows with the same number each, but it would not be “least”.
3.  To answer the question in the title of this article, the seats are not the pigeonholes.  Rather, the pigeonholes (or bins, or columns) represent possible numbers of people in a row.  Each ball in bin  j  represents a row that has  j  people.

H02. Use a diagram / model
H03. Make a systematic list
H04. Look for pattern(s)
H05. Work backwards
H06. Use before-after concept
H07. Use guess and check
H08. Make suppositions
H09. Restate the problem in another way
H11. Solve part of the problem

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.