Thursday, April 30, 2009

Number Theory Problem

Let Qn denote the smallest number such that for any set of Qn integers, there exists a subset of n integers that sum to zero mod n (i.e., a multiple of n). For example, for n = 3, any set of Q3 integers contains a subset of size exactly 3 that sum to a multiple of 3, and Q3 is the smallest such number.

What are Q3 and Q9?

(Hint: proof of sufficiency uses the pigeon-hole principle and proof of minimality uses a constructed counter-example.)

5 comments:

Anonymous said...

Qn = n + 1 since C(Qn,n) = n+1. Qn>=n. If set Qn=n, easy to come up with counter examples.

Yisong said...

For n=3, then I can give you a counterexample showing that Q_n cannot be 4. Suppose the 4 integers are {1,2,4,5}. Then no subset of three integers chosen from those 4 will sum to a multiple of 3.

faaaaang said...

Is it Q3 = 5? Since in the set if 3 numbers or more share the same residue, then apparently there's a desirable subset. If at most 2 numbers share the same residue, since there're only 3 holes for possible residue, there must be a subset like (3a+1, 3b+2,3c).

counter example for Q3 = 4: any set like (3a+1, 3b+1, 3c+2, 3d+2).

Similarly Q9 = (9-1)^2+1? Counter example not sure. maybe 8 ones, 8 twos, ...,8 eights?

Yisong said...

You are correct that Q3 = 5.

Q9 is not 65, it is much smaller.

John Carrino said...

I can come up with a lower bound by making a set with n-1 0's and n-1 1's. So Q(n) must be at least 2n-1. I'll try to come up with an argument for the upper bound.