Let's say there are N terms in each factor (where N = 100 in this problem). Then there are 2^N such factors since there are 2 choices of sign for each of the N terms. If we were to multiply them all together as polynomials, we'd have to add up every possible component where we choose exactly one term from each of the 2^N factors. There are N^(2^N) such components, but we can simplify.
Consider any component where we chose the ith term from the jth factor. Now, some other factor, the kth, is identical to the jth except for the sign of the ith term. We know this because ALL possible combinations of terms are factors. Now, if we exchange our choices for these two factors, we arrive at a different component whose sign is the opposite of this one. That's because only the ith term's sign is different so the exchange swaps that sign but leaves the sign of the other term (whatever it is) the same. And of course, these two components cancel each other out in the sum and do not contribute.
EXCEPT
If our component chose the ith term from BOTH the jth and kth factors to begin with, then swapping isn't possible since it results in the same component, not a different one. And THOSE terms won't cancel out. But what that means is that the only contributing components are those in which terms are chosen in pairs. Otherwise there will be an opposite component to cancel it out.
But if the only contributing components have terms in pairs, all of those square roots all balance out and those components will all be integers. And their sum, too, will be an integer.
|
|
Posted by Paul
on 2015-09-21 15:19:24 |
Not especially rigorous but hopefully valid solution
