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.

Ok, here is how I solved it. I pictured 19 squares of increasing size on top of eachother, like a pyramid that had it's pieces aligned to 2 sides.

Converting that to numbers and variables, that is

(n)² + (n+1)² + (n+2)² + ... + (n+18)²

That equals (n²)+(n²+2(1)n+1²)+(n²+2(2)n+2²)+...+(n²+2(18)n+18²)

Adding the like terms gives 19n²+2(1+2+3+...+18)n+(1²+2²+3²+...+18²)

Using the old formula (a*(a+1))/2 to add up 1 to a, (18*(19))/2 =9*19.

Adding up the squares, gives 2109 which is 111*19

So the terms are 1(19)n²+9(19)n+111(19), and factoring gives 19(n²+9n+111), which is obviously divisible by 19 if integers n are used (as stated in problem)

Posted by Gamer on 2003-03-15 02:52:45