Conference rusure::math

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).

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.

        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

    In the first problem, if p = q, the requested proof is clearly
    impossible:  The ball heads straight for a corner and falls in.
    
    
    				-- edp

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

    Oops, I was working as if it were shot from a side pocket.
    
    
    				-- edp

    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 

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.

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.