All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Divisibility (Posted on 2003-03-14)
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.

 See The Solution Submitted by Anoop Rating: 3.0000 (8 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 vague outline | Comment 8 of 9 |
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

 Search: Search body:
Forums (0)