Question
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?
|
Introduction
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.
Discussion
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.
Note
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
