UNO High School Problem of the Week Competition
Problem 12
Given any 3 integers, it can clearly be shown that there is at least
one subset of two integers whose average is also an integer.
Prove that given any 5 integers, there is at least one subset
of three integers whose average is also an integer.
Also, determine the smallest number k (with proof), such that given any k integers,
there is at least one subset of four integers whose average is also an integer.
Solution
Observation #1: When a number is divided by an integer n, we can consider its remainder
upon division by n. Therefore a number k is considered "congruent" to one of the n integers
from the set {0, 1, 2, ..., n-1}. This is a result of the Divison Algorithm on the integers.
Observation 1 actually gives us more information. It says that for every integers n and d (d positive), there
exist unique integers p and r such that n = pd + r where r is a positive integer less than d.
Observation #2: A sum of k numbers is divisible by an integer m if and only if the sum of
the k remainders is divisble by m. The proof of this observation is fairly trivial and will be omitted.
From Observation 2, we know that if we have more than 3 (or 4) of any one remainder,
then the set of 5 (or k) integers has a subset with the desired property.
One method to solving these type of problems is to argue by counterexample. If a counterexample cannot be
found while exhausting all of the possible cases, then the statement is considered true. Otherwise, the statement
is false.
Proof of Part A:
Suppose there exists a set of five integers that has no subset of three integers whose average is also
an integer. Since this set has no subset whose sum is a multiple of 3, we know that we cannot have 3 or
more of any one remainder. Therefore the 5 integers must be spread amongst 3 boxes (the remainders) with
each box having at most 2. This implies that we must have at least one of each remainder and thus any set
of 5 integers MUST have at least one subset of three whose average is also an integer.
Proof of Part B:
Clearly k must be at least 4.
Having k = 4 is not sufficient enough since a set of 4 integers, whose remainder distribution is
{1,0,0,3} for remainder 0, 1, 2 and 3 respectively does not have an average as 1*0 + 3*3 = 9 is
not divisible by 4.
Having k = 5 is also not sufficient enough since a set of 5 integers, whose remainder distribution
is {0,0,3,2} is a valid counterexample. Notice here that the sum of all remainders is 3*2 + 2*3,
or 12. Any subset of 4 from this set of 5 is either missing an integer with remainder 2 or remainder 3.
The sum of such a subset is 12-2=10 or 12-3=9. As neither of these are divisble by 4, we have our
counterexample.
For k = 6, consider the set whose remainder distribution is {3,3,0,0}. Here the sum of all remainders
is 3 and any subset of 4 is either missing an integer with remainder 0 or 1, and thus the sum of this subset
is eitehr 3-0=3 or 3-1=2. As neither of these are divisible by 4, we have a counterexample.
For k = 7, if such a set of 7 integers had the property that no subset of four had an average that is
an integer, we know that we must have at least 3 of one remainder. Since if we had at most two of every
remainder, then we would be trying to place 7 integers into 4 boxes with each box receiving at most 2 intgers.
Therefore every remainder, except for one, would appear twice. And upon simple checking of the four remainder
distributions having this property, namely ({2,2,2,1}, {2,2,1,2}, {2,1,2,2} and {1,2,2,2}), we cannot reach a
counterexample and thus if a counterexample exists, it must have at least 3 of one remainder. Furthermore,
since we do not want to have any remainder a total of 4 (or more) times, we know that at least one remainder
occurs exactly 3 times.
Finally a simple check on the remainder distributions where at least one remainder
occurs exactly 3 times, namely
({3,3,1,0}, {3,3,0,1}, {3,1,3,0}, {3,0,3,1}, {3,1,0,3}, {3,0,1,3}, {1,3,3,0}, {0,3,3,1}, {1,3,0,3},
{0,3,1,3}, {1,0,3,3}, {0,1,3,3}, {3,2,2,0}, {3,2,0,2}, {3,0,2,2}, {3,2,1,1}, {3,1,2,1}, {3,1,1,2},
{2,3,2,0}, {2,3,0,2}, {0,3,2,2}, {2,3,1,1}, {1,3,2,1}, {1,3,1,2}, {2,2,3,0}, {2,0,3,2}, {0,2,3,2},
{2,1,3,1}, {1,2,3,1}, {1,1,3,2}, {2,2,0,3}, {2,0,2,3}, {0,2,2,3}, {2,1,1,3}, {1,2,1,3}, {1,1,2,3}).
None of these distributions provide the necessary counterexample. As we have exhausted every possibility,
then the statement holds when k=7.
Generalization: Given any 2k-1 integers, there always exists at least one subset of k integers whose
average is also an integer. The proof here, requires some number theoretic arguments, especially when
k is a prime integer.