A problem in discrete math (Pigeonhole principle related)

Question

The question is from the multiple choice problem:

A circular region is divided by 5 radii into sectors, as shown above. Twenty-one points are chosen in the circular region, none of which is on any of the 5 radii. Which of the following statements must be true?

I. Some sector contains at least 5 of the points

II. Some sector contains at most 3 of the points.

III. Some pair of adjacent sectors contains a total of at least 9 of the points.

It is not hard to show that I is true while II is not. Intuitively III is also true. But here are my questions:

• How to prove that III is true? (Can Pigeonhole principle be used here?)

• What topics/theorems/principles/ is statement III in this problem related to in combinatorics?

Answer 1

For III, the Pigeonhole Principle will work nicely. Call the sectors, in counterclockwise order, $1$, $2$, $3$, $4$, $5$.

Let $P_1$, $P_2$, and so on up to $P_5$ be the number of points in these sectors.

Look at the sum $$(P_1+P_2)+(P_2+P_3) +(P_3+P_4) +(P_4+P_5)+(P_5+P_1)$$ which is the sum of the numbers of points in adjacent sectors.

It is easy to see that this sum is $42$, so the components average out to $8.4$, which is greater than $8$. But each component is an integer, so at least one of the sums is $9$ or more.

Comment: I somewhat prefer the following variant. Five people are sitting around a round table. Between them they have $21$ dimes. Show that there are two people sitting next to each other who between them have at least $9$ dimes.

Note that the solution took advantage of the circular symmetry. Symmetry is our friend. In solving problems, it is useful to "break symmetry" as late as possible, or not at all.

Answer 2

For every radius define a pointcount which is the sum of the amount of points of the adjacent sectors. Then it is clear that the sum of all five pointcounts must be 42, since every point gets counted twice. Thus by the same reasoning that proves I, one can now prove that at least one of these pointcount must be greater than or equal to 9 QED.

Answer 3

Assume that III is not true. By I, we can find a segment with at least 5 points, call this number of points x. Since we are assuming that III is not true, each of the segments next to the segment with x in it can have at most 8-x points in it.

In the three segments so far, we've accounted for x + (8-x) + (8-x) points, or 16-x points. The remaining two segments must have 21 - (16-x) points in them, or 5+x points. Since x is 5 or more, these last two segments must have 10 or more points in them. This is contrary to our assumption, so III must be true.

Answer 4

I solved all the math GRE form 68 problems (this is one of them). You view my solutions at http://rambotutoring.com/GRE-math-subject-test-68-solutions.pdf