[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

472.0. "Colorado Springs Math Olympiad" by NEWTON::GWB () Mon Apr 21 1986 22:36

I just finished helping with the scoring of the 1986 Colorado Springs Math
Olympiad. This year over 400 high school students in the Colorado Springs area
took part in the Olympiad.

The organizer of the Olympiad is Dr. Alex Soifer of the University of Colorado
at Colorado Springs. A number of local businesses, including Digital, are
sponsors of the event, so there is a substanial prize fund. This year the
winner will receive a $1500 scholarship to a math/computer camp for the summer.

The Olympiad test has five problems, the first three are (fairly) easy and the
last two somewhat difficult (only a dozen students solved the fourth problem
and only one solved the fifth one). None of the problems require any advanced
knowledge, so it would be possible for a 9th grader to take first place. In
fact last year a 9th grade student took second prize.

Scoring is rather involved. Students can be awarded fractional grades for
incomplete solutions, and can get special awards for particularly clever
solutions. Also, we used a "double blind" approach to scoring. Worksheets were
numbered, so the judges did not know the names of the students being graded.
Then each paper was scored independently by two judges so the second judge
would not know the grades assigned by the first. After the papers had been
graded twice, the scores were compared, and, where there was a descrepency, a
third (or fourth or fifth) judge reviewed the paper. Finally, all papers that
are potential prize winners were reviewed by the senior judges, including
Dr. Soifer.

You might have fun solving the two most difficult problems.

1. Given a rectangular pool table of size p x 2q, where p and q are odd
integers, which has four corner pockets [at (0,0), (p,0), (0,2q) and (p,2q)]
and two side pockets [at (0,q) and (p,q)], prove that a pool ball shot from one
of the corners at an angle of 45 degrees with respect to the side rail will
eventually fall in a pocket, and, furthermore, that the pocket it ends up in
will always be a side pocket.

2. Given any set containing n integers, prove that you can always find a subset
such that the sum of the integers in the subset is a multiple of n.


(I will apologize for any errors in the wording of the problems. The actual
questions were more carefully stated than the versions given to be clearer to
high school students, and, not having a test in front of me, I can not remember
the exact wording.)

			Regards,
			   George
T.RTitleUserPersonal
Name
DateLines
472.1first shot at #2CLT::GILBERTJuggler of NoterdomTue Apr 22 1986 07:0040
Given any set containing n integers, prove that you can always find a non-empty
subset such that the sum of the integers in the subset is a multiple of n.

A proof of this follows.

We prove this by induction on n.

The theorem is trivially true for n = 1.  Assume that the theorem is true
for 1 thru n-1.


Now, if n is composite, let n = p q.  We split the n integers into p groups
of q integers each.  Each group of q integers has a non-empty subset of
integers with a sum equal to a multiple of q.  These p sums, each divided
by q, form a smaller problem, which, by the inductive hypothesis, must have
a sum that's a multiple of p.  Thus, the overall sum is a multiple of p q,
and thus must be a multiple of n. 


Now, if n is a prime, we assert that either one of the integers is a multiple
of n (in which case the result follows immediately), or that some non-empty
subset of the n integers has a sum that's a multiple of n.  This later result
is proved by induction on m.  Given a set S(m) of m integers (m <= n), such
that none are 0 modulo n (n is prime), let T(S(m)) denote the set of of
different sums modulo n formed by non-empty subsets of S(m).  Our inductive
hypothesis is: |T(S(m))| > |T(S(m-1))|.  That is, with each additional integer,
the number of different sums modulo n increases; and because |T(S(1))| = 1,
|T(S(n))| = n, and therefore some subset of the n numbers has a sum congruent
to 0 modulo n.

We prove the inductive step by contradiction.  Let S(m) = S(m-1) U {x}, and
assume |T(S(m))| = |T(S(m-1))|.  Thus, for each s in T(S(m-1)), x+s (modulo n)
is also in T(S(m-1)).  Since x+s is in S(m-1), so is 2x+s.  Continuing, we see
that kx+s (modulo n) is in T(S(m-1)) for all integers k.  As each number
has a multiplicative inverse modulo n, we may let k = (n-s)(x^-1) (modulo n),
so that 0 is in T(S(m-1)).


The statements for the prime case are not quite precise, but it's close
enough for the moment (i.e., late).
472.2CLT::GILBERTJuggler of NoterdomTue Apr 22 1986 11:5828
Reworking part of .-1 ...

Now, if n is a prime, we will find the following result useful.

Let T(S) denote the set of different sums modulo n formed by non-empty
subsets of a set of integers S.  We have either:

	x = 0 modulo n,
    or	|T(S)| = n		(i.e., all sums modulo n are generated),
    or	|T(S+{x})| > |T(S)|	(i.e., there are more different sums modulo n).

We assume that x is non-zero modulo n, and we prove that one of the other two
conditions must hold.  T(S+{x}) is a (non-strict) superset of T(S), namely
T(S+{x}) = T(S) U Q, where Q = { (x+t) modulo n | t is in T(S) }.  If Q
contains elements not found in T(S), then the third condition holds immediately.
Otherwise we must have, for each t in T(S), that (x+t) modulo n is also in T(S).
Since (x+t) modulo n is in T(S), then so is (2x+t) modulo n.  Continuing,
(kx+t) modulo n must be in T(S), for all integers k.  Since n is prime,
and x is non-zero, kx modulo n generates all integers modulo n, as must
(kx+t) modulo n.  Thus, 0 thru n-1 must be in in T(S), and so |T(S)| = n.

Given any set of n integers S (n prime), none equal to 0 modulo n, |T(S)| = n.
This is proved by the above result, and a trivial induction on the number
of integers in S.  For the proof of our main theorem, with n prime, this
implies that we either have some element equal to 0 modulo n (and so our
theorem is proved immediately), or the sums of subsets of integers modulo n
includes n different numbers, and so contains 0 -- that is, some subset
has a sum congruent to 0 modulo n.
472.3BEING::POSTPISCHILAlways mount a scratch monkey.Tue Apr 22 1986 18:4221
        Here is another proof for the second problem (we should also assume
    the given set is non-empty).
    
    Take any ordering for the integers in the set, m[0], m[1], . . .
    m[n-1].
    
               k = i
    Let f(i) =  sum   m[k].   In particular, f(-1) = 0.
    	       k = 0
    
    			                  k = j
    Observe that when j > i, f(j)-f(i) =   sum  m[k].
    			                 k = i+1
    
    Consider the set { f(i) | -1 <= i < n }.  It has n+1 elements.  Two of
    them, f(a) and f(b), a <> b, must be congruent modulo n.  Without loss
    of generality, assume b > a.  Then f(b)-f(a) represents a sum of b-a
    elements which is a multiple of n. 
    
    
    				-- edp
472.4BEING::POSTPISCHILAlways mount a scratch monkey.Tue Apr 22 1986 19:005
    In the first problem, if p = q, the requested proof is clearly
    impossible:  The ball heads straight for a corner and falls in.
    
    
    				-- edp
472.5re: .4NEWTON::GWBTue Apr 22 1986 20:348
1. Given a rectangular pool table of size p x 2q, where p and q are odd
					       ^

so if p=q the ball would go directly in the SIDE pocket, not a corner pocket.


			Regards,
			   George
472.6BEING::POSTPISCHILAlways mount a scratch monkey.Tue Apr 22 1986 21:204
    Oops, I was working as if it were shot from a side pocket.
    
    
    				-- edp
472.7BEING::POSTPISCHILAlways mount a scratch monkey.Wed Apr 23 1986 14:0347
    Here is a proof for the first problem.
    
    Consider that the horizontal (parallel to x-axis) distance the ball
    rolls is the same as the vertical distance.  Since it starts at integer
    coordinates, the coordinates of the ball at any time until it bounces
    are either both integers or both non-integers.  When the ball hits a
    wall, the constant coordinate of the wall is an integer, so that
    coordinate for the ball is an integer, and so must be the other
    coordinate.  The ball then bounces away from the wall, again starting
    from integer coordinates, so the both integer, both non-integer
    property remains even after bounces. 
    
    When the ball has traveled a horizontal distance of p from its starting
    point, it is at the other edge.  It then bounces (assuming it has not
    reached a pocket) and travels a horizontal distance of p back to the
    other edge.  We see that the ball is at a vertical edge when and only
    when the horizontal/vertical distance it has traveled is a multiple of
    p.  Starting again, when the ball has traveled a vertical distance of q,
    it is at the midpoint.  When it travels another distance of q, it is at
    a horizontal edge.  We see that the ball is on the same horizontal
    level as a pocket when and only when the horizontal/vertical distance
    traveled is a multiple of q.  If it is an even multiple, the ball is on
    a level with corner pockets, otherwise it is on a level with side
    pockets. 
    
    If the distance traveled is a multiple of p and q, the ball is in
    the same location as a pocket, so it presumably falls in. 
    
    When the distance traveled is pq, the ball has reached a pocket
    if it has not fallen in one already, so the ball will eventually
    fall into some pocket.  Suppose the first pocket the ball falls
    into is a corner pocket.  Let x be the distance traveled.  Since
    the ball has reached a pocket, x is a multiple of p.  Let x = np.
    Since the ball has reached a corner pocket, x is an even multiple
    of q.  Let x = 2mq.
    
    What happens when the ball has traveled only half this distance? The
    vertical distance traveled is mq, which is a multiple of q, so the ball
    is on a horizontal level with a pocket.  Since np = x = 2mq, mq = np/2.
    Since mq is an integer, np/2 is an integer. Since p is odd, n must be
    even, so the horizontal distance traveled is (n/2) p, which is a
    multiple of p.  Thus, the ball falls into a pocket before it reaches
    the assumed corner pocket, so the assumption is false.  The ball
    always falls in a side pocket.
    
    
    				-- edp 
472.8CLT::GILBERTJuggler of NoterdomThu Apr 24 1986 03:2615
re .3
	Ayup.  With competition problems, I usually find it best, once
	a workable approach has been chosen, to stick with it, because
	the time element is so crucial.  Besides, once all the problems
	are solved, better proofs can be sought in the remaining time.

	A pidgeon-hole principle looked reasonable (of 2^n-1 numbers,
	one must = 0?), and constructing a solution from two parts having
	congruent sums looked reasonable (unfortunately, I didn't think
	of limiting the two parts to a strict superset relation, sigh),
	and considered showing that each additional number increased
	the number of distinct sums.  But when I noticed that composite
	numbers could be easily handled, and visualized the 'shifting'
	and 'alignment' that would be needed for the prime case to fail,
	I stuck with it, even though the better proof eluded me.
472.9CLT::GILBERTJuggler of NoterdomThu Apr 24 1986 03:537
We introduce the variable t for time.  The ball is at a vertical edge
when t = 0 modulo p, and is at a horizontal edge when t = 0 modulo 2q.
The ball reaches a pocket when t = 0 modulo p and t = 0 modulo q; any
solution of these two equations puts the ball at a pocket.  In addition,
it's a corner pocket iff t = 0 modulo 2q.  As t = pq/gcd(p,q) is the
smallest non-zero solution to the two equations, and this is odd, the
ball must first reach a side pocket.