Let p be a prime. Let S be a set of (p-1) integers, none of which are divisible by p. Show that some subset of S has a sum that has a remainder of 1 when divided by p.

(The sum of a set is defined as the sum of the elements of the set)

As pointed out, we need only start with p-1 values in the interval [2,p-1]. But we actually have access to only about have of these values, as they come in pairs that add to p+1. Thus, you can have values of 2 and p-1, but not both. as a special case, we can have at most one value of (p+1)/2. With p-1 or p-2 numbers taking on (p-3)/2 values, for p>3 we have at least one value occuring at least three times.

I have been spending some spare time thinking about how looking at consecutive sums of this value can't hit "mates" of other values (if it does, we are done), and if a sum lands on another value that we have, we can use that value to boost the sum sequence even further. If we can push the sequence on, the primality of p hands us a sum of 1 sooner or later. As a matter of fact, we know 1 will occur before 0, which means within the first p-1 sums!

But I can't string it together in the time alotted, so I thought I would throw it out in case someone may find something of use in this rubbish. Nice problem, David!

Posted by owl on 2005-01-31 05:56:11