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.

This question is from the multiple choice test:

Picture

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.

I am interested mostly in III here (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?

share|improve this question
1  
"As shown above"... is it just that it is divided into five regions? –  Arturo Magidin Jun 6 '11 at 3:51
    
@Arturo Magidin:Oops, I missed the picture here. Since I don't know how to add a picture here, I would like to edit the question here. –  Jack Jun 6 '11 at 3:55
    
I added you a picture, If you try to edit it now, you can probably see how it's done. –  gfes Jun 6 '11 at 4:18
    
@gfes: nice work! I'm curious about what software you used to draw that picture. –  Jack Jun 6 '11 at 4:22
    
I used Paint.NET actually. Nothing fancy. –  gfes Jun 6 '11 at 4:54

4 Answers 4

up vote 7 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
I don't think that the answer in this document is really any different to some of the ones posted already here, that solved the question nicely, so I'm not sure that this is the best place for a link to your solution booklet. If you are going link to it though, I think it would be very helpful if you mentioned where in the booklet the solution to this problem can be found. –  Tom Oldfield May 23 '13 at 0:49
    
You're right. But I think most people that come to this page will have come searching for the solution to the GRE problem. It's problem 45. –  Charles May 23 '13 at 4:22

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.