[Search for users]
[Overall Top Noters]
[List of all Conferences]
[Download this site]
| 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 20: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.R | Title | User | Personal
Name | Date | Lines |
|---|
| 308.1 | | TURTLE::GILBERT | | Tue Jun 18 1985 14:16 | 7 |
| 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.2 | | ALIEN::POSTPISCHIL | | Tue Jun 18 1985 14:36 | 42 |
| 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.3 | | METOO::YARBROUGH | | Tue Jun 18 1985 16:35 | 14 |
| 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.4 | | ALIEN::POSTPISCHIL | | Tue Jun 18 1985 17:31 | 14 |
| 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.5 | | TURTLE::GILBERT | | Tue Jun 18 1985 19:28 | 38 |
| 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.
|