_{n}denote the smallest number such that for any set of Q

_{n}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 Q

_{3}integers contains a subset of size exactly 3 that sum to a multiple of 3, and Q

_{3}is the smallest such number.

What are Q

_{3}and Q

_{9}?

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

## 5 comments:

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

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.

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?

You are correct that Q3 = 5.

Q9 is not 65, it is much smaller.

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.

Post a Comment