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.

My first thought had been that to avoid divisibility by 19 you could have at most 18 numbers that are congruent to 1 mod 19, and 18 that are congruent to 2, etc. up to 18 that are congruent to 10. This is 180 numbers. If you add a 181st number, it has to be one of two possibilities: either it has the same congruency mod 19 as the numbers in one set already collected, in which case it completes a set of 19, that bring the total back to divisibility by 19; or it has a congruency that is complementary to one of the existing sets, that is 11 mod 19 is complementary to 8 mod 19, and therefore combined with one of those, produces a sum of 2 numbers that are divisible by 19, then the task becomes to find a set of 17 that add to a multiple of 19, which can be accomplished by taking 16 from any set, say the 1-mod-19 set, and then one from a set that is two higher.

This has to be generalized, as there are no assurances that the sets of 18 that mutually share a congruence value be neatly in consecutive order: you might have 18 1-mod-19, 18 3-mod-19, 18 7-mod-19, etc. We'd have to show that it would always be possible to have a set that is denominated 2 higher than another.

Further, it has to be considered that sets smaller than 18 exist. This of course results in some pairs forming between complementary mods, like the previously mentioned 8-mod-19 and 11-mod-19, so the fewer members of each set, below 18, necessarily makes for more of these pairs that add to a multiple of 19. As an easy example, if there were 9 of each mod value, 9 8-mod-19 could be combined with 9 11-mod-19 and one 0-mod-19 to produce a required set. It would have to be shown that the presence of complementary pairs would offset the loss of full sets of 18.

Posted by Charlie on 2003-03-18 03:48:29