In any set of 181 square integers, prove that one can always find a subset of 19 numbers, the sum of whose elements is divisible by 19.

(In reply to vague outline by Charlie)

Charlie almost has it.  Take advantage of the fact that all 181 numbers are squares.  There are exactly 10 remainders which come from squares.  They are 0, 1, 4, 9, 16, 6, 17, 11, 7, and 5.  Since there are 181 squares, at least one of these remainders, say r, must occur at least 19 times.  For, if each remainder occured only 18 times or less, then that's at most 180=10*18 squares.  Hence, adding up 19 of those squares whose remainder is r gives a sum divisible by 19.

Posted by McWorter on 2005-04-02 19:54:29