[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

308.0. "Colorado Springs Math Olympiad" by TOOLS::STAN () Mon Jun 17 1985 23:09

With George's permission, I am posting information about the
Colorado Spring's Math Olympiad, in which he participated as a judge.
If you have a particularly nice solution to one of the problems,
feel free to enter it as a response to this note.

				- Stan -

From:	NEWTON::GWB          "George W. Berry" 17-JUN-1985 19:00
To:	TOOLS::STAN
Subj:	RE: olympiad

Dr. Alexander Soifer, Professor of Mathematics at the University of Colorado in
Colorado Springs, grew up in Russia where competitve mathematics was an
accepted part of mathematical training for students at all levels. He believes
that such contests help develop an interest in mathematics in young students,
and therefore wanted to have an Olympiad style mathematics contest open to
Colorado Springs high school students.

As an added incentive to the students, he managed to get various local
businesses (including Digital) to contribute to a prize fund to be awarded to
the winners. First prize this year was a $500 scholarship and a TRS computer.
(Lesser prizes were awarded for other places -- in fact, one of Dr. Soifer's
goals was to spread the awards to the majority of the participants).

How did I get involved in all this? Well, Dr. Soifer does not like multiple
choice math tests.  Instead he prefers a test in which students are graded on
their work rather than just the answer. Actually, it is possible to get 75%
credit on a problem even if you get the wrong answer! What counts is that your
method is correct.

Scoring this type of test is a time consuming process, and a lot of judges are
needed. Scoring worked as follows: every paper was reviewed by two judges
independently (i.e., neither judge knew what score the other assigned). Those
papers in which the judges agreed on the score for each problem were considered
done (for the time being). Other papers were reviewed by a third and sometimes
a fourth judge. Finally, the top ten papers were reviewed again by selected
judges (including Dr. Soifer) to assign a final rank.

Needing a large body of judges to score papers, Dr. Soifer accepted anyone who
claimed a passing familiarity with mathematics and who was willing to spend a
day scoring papers. In a moment of weakness, I volunteered.

(Although it was a lot of work, it was also fun. You never knew when you would
stumble over a paper that contained a really original solution to one of the
problems. Also, I agree with Dr. Soifer's opinion of multiple-guess testing and
so was willing to assist in any way that I could.)

Here are the problems in case you want to try them. For the most part they are
very easy, but remember that they were intended as a test for students in
grades 9 to 12.

		SECOND ANNUAL COLORADO SPRINGS MATHEMATICAL OLYMPIAD
				April 19, 1985

	Write complete solutions; show all your work. We will give no credit
	for answers submitted without supporting work (even correct answers).
	Conversely, a minor error that leads to an incorrect answer will not
	substantially reduce your credit.

1. A box contains 100 marbles. There are 30 red ones, 30 blue ones, 30 green
   ones; the remaining 10 consist of some black and some white ones. If we
   choose marbles from the box without looking, what is the smallest number of
   marbles we must pick in order to be absolutely certain that among the chosen
   marbles at least 10 are of the same color?

2. Twenty-five basketball teams are entered in a tournament; the tournament
   will last ten days. Show that at the end of the fourth day of the
   tournament, at least one of the teams has played an even number of games.
   (Remark: Zero is an even number.)

3. Each of the 49 entries of a square 7 x 7 table is filled by an integer
   between 1 and 7, so that each column contains all of the integers
   1,2,3,4,5,6,7, and the table is symmetric with respect to its diagonal D
   going from its upper left corner to its lower right corner. Prove that this
   diagonal D has all of the integers 1,2,3,4,5,6,7 on it.

4. Suppose you are given a list consisting of the numbers 1,2,3,4,5,6,7,8,9 in
   some order, where each number occurs exactly once. You try to put the list
   in increasing order by using the following procedure. Compare the numbers in
   the first and second positions. If they are in increasing order, make no
   changes; if they are not in increasing order, switch them. (If you made a
   switch, the number originally in the first position is now in the second
   position.) Now compare the numbers in the second and third positions. As
   before, switch them if they are not in increasing order. Continue in this
   fashion, finally comparing numbers in positions eight and nine, switching if
   necessary. As the example shows, this procedure does not always put the list
   in increasing order.

	Example: Original List   - 2 1 3 4 9 6 5 7 8
		 After Procedure - 1 2 3 4 6 5 7 8 9
					   ^ ^

   How many different original lists are put in increasing order after using
   our procedure.

5. Is it possible to put 1985 straight line segments on a plane in such a way
   that each segment has each of its ends lying on inside points of some of the
   other segments?
T.RTitleUserPersonal
Name
DateLines
308.1TURTLE::GILBERTTue Jun 18 1985 17:167
A few answers appear below.  If you enjoy good problems, no peeking! 

Some of the answers aren't extremely pleasing.  Have you a nice proof?

					- Gilbert

Hey!  No fair peeking.  I'll post 'em in a while!
308.2ALIEN::POSTPISCHILTue Jun 18 1985 17:3642
Quick and dirty (that is, I do not support all of my statements, or are they
all as formal as they should be):

1)	With 9 red marbles, 9 blue, 9 green, and all 10 of the black/white
	ones (which might be all black or all white, but we can't be sure),
	it is not possible to pick another marble without getting 10 of one
	color.  Nor is it possible to have another configuration of colors
	with more marbles with this property, since if you had less than 9 red
	marbles, you could pick red marbles until you had 9.  Similarly, you
	could get 9 blue, 9 green, and 10 of the black/white marbles.  Thus,
	picking 9+9+9+10+1, or 38, marbles will guarantee 10 of one color.

2)	Each game played by two teams adds one to the game-count of each team,
	which adds two to the sum of the game-counts of all the teams.  This
	sum shall be called the total-game count.  Clearly, the total-game
	count is even.

	Suppose all twenty-five teams have odd game-counts (that is, each has
	played an odd number of games).  Adding twenty-five odd numbers
	results in an odd number, which means the total game-count is odd.
	This is a contradiction, therefore the supposition is false.  It is
	not true that all twenty-five teams have odd game-counts, so one must
	have played on even number of games.

5)	Suppose it is possible to put 1985 line segments on a plane in such
	a way that each segment has each of its ends lying on the inside
	points of some of the other segments.

	Consider an arbitrary point on the plane, P.  One of the 1985 line
	segments must have an endpoint which is not closer to P than any other
	endpoint.  Call this endpoint C.  C must be on the inside point of
	some other segment.  Call this segment AB.  Draw a circle with center
	P and radius CP.  Clearly, the circle cuts segment AB, so one of the
	endpoints of AB is outside the circle and farther from P than C is,
	which is a contradiction.  Therefore the supposition is false.

	It is not possible to put 1985 line segments on a plane in such
	a way that each segment has each of its ends lying on the inside
	points of some of the other segments.


				-- edp
308.3METOO::YARBROUGHTue Jun 18 1985 19:3514
I came up with the same solutions for 1. and 2. as [.-1].

3. Since each column has one each of {1,2,3,4,5,6,7} there are a total of
7 1's, 7 2's, etc. For diagonal symmetry, there must be 3 1's above and 3
1's below the diagonal, so 7-3-3=one 1 on the diagonal. Ditto for 2, 3,...

4. Exactly 8 comparisons are made in the course of the process, and each
compares two elements. There are therefore 2^8 resolvable cases, or 256.

5. Consider the smallest circle that wholly includes the set of line segments.
Some line segment must have a point which lies on this circle (else it 
could be smaller.)
That end point is not interior to any segment, since the segment would 
have to lie partially outside the circle.
308.4ALIEN::POSTPISCHILTue Jun 18 1985 20:3114
Re .3:

Your answer to 4 is not complete.  Considering a given pattern of possible
switches/non-switches, you can work backwards to determine a list which, when
the given switches/non-switches are performed properly, give the list
"1 2 3 4 5 6 7 8 9".  However, you must also show that this list will give the
same pattern of switches/non-switches when the comparisons are made.
Otherwise, maybe some switch/non-switch will be made differently, resulting
in something besides a sorted list.

I'm pretty sure this is possible, however, my proof is unwieldy.


				-- edp
308.5TURTLE::GILBERTTue Jun 18 1985 22:2838
Having given some others a crack at it, here are the answers I'd originally
planned to post in .1.  I think a couple are pretty good, but the use of
circles for problem 5 is definitely better.  Is there a nice answer for 4?

1.  38, by the pigeon-hole principle.  The maximum number of marbles that
    could be chosen without having at least 10 of the same color is 37,
    consisting of 9 red, 9 blue, 9 green, and 10 black or white balls.

2.  Consider the number of games played by each team, summed over the teams.
    This sum is always even (it's initially even, and increases by two after
    each game).  Assume that after the fourth day each team has played an odd
    number of games.  This implies the sum (of 25 odd numbers) is odd.  Since
    the sum must be even, our assumption is false; at least one of the teams
    has played an even number of games.

3.  There are an odd number of 1s on the diagonal, since the same number
    of 1s are above the diagonal as are below it, and an odd number of 1s
    are in the square as a whole.  Similarly, each of the other numbers
    appears on the diagonal an odd number of times.  Thus, each must appear
    at least once on the diagonal; as this distribution fills the diagonal,
    each number must appear exactly once on the diagonal.

4.  Consider running the procedure in reverse on the ordered list.  Each
    exchange may be made, and may be made independently, and each different
    sequence of exchanges results in a different original list which the
    procedure would put in increasing order.  As each of the eight exchanges
    may or may not be made, a total of 2^8 different original lists are put
    in ascending order by the procedure.

5.  No.  Suppose such an arrangement were possible, and consider the rightmost
    point in the arrangement (as there are a finite number of endpoints, the
    arrangement can be rotated so that there is no vertical line segment
    between any two endpoints, making the rightmost point unique).  This
    cannot be an inside point of a line segement (as this would imply a point
    further right).  So it must be an endpoint, yet cannot be, since the
    arrangement requires each endpoint be on an inside point of of some other
    line segment (and we've shown that this cannot be an inside point). 
    Our assumption is false, and we conclude no such construction is possible.