Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have been reading this problem,

Prove that of any 52 integers, two can always be found such that the difference of their squares is divisible by 100.

That says,

Prove that of any 52 integers, two can always be found such that the difference of their squares is divisible by 100.

Now, in my understanding, it says, any 52 integers.

So I could just choose 0 and 100, from a random set of integers right?

100^2 - 0^2 = 10000 which is devisible by 100.

What I am not getting here? I read the answers but I still cant figure out what exactly the problem is asking.

Basically I am trying to understand the first answer:

Look at your 52 integers mod 100. Look at the pairs of additive inverses (0,0), (1,99), (2,98), etc. There are 51 such pairs. Since we have 52 integers, two of them must belong to a pair (x,−x). Then x^2−(−x^)2=0(mod100), so that the difference of their squares is divisible by 100.

So he creates a set, and in that set he has sets of cardinality 2. Then he says Since we

have 52 integers, two of them must belong to a pair (x,−x).

This is what I dont get. The integers can be (4, -9) or (15, 40) who says they need to be additive inverses. He just created a new set and made up some rules. I dont get it

share|improve this question
1  
The key is any $52$ (pairwise disjoint) integers. You cannot tell if $0$ or $100$ are chosen at all. –  AlexR Dec 13 '13 at 12:00
    
It only says that two numbers can always be found, given any 52 integers. You have solved the problem only for a set containing 0 and 100. So take this set for example: $S=\{ 10^9+k \mid k=1,\ldots 52\}$. –  Dietrich Burde Dec 13 '13 at 13:02
    
well is he referring to all the integers? so your set is invalid –  test Dec 13 '13 at 13:47
    
One might reword the question as the following "Given a set $A\subset\mathbb{Z}$ whose cardinality is $52$, show that there exist $a,b\in A$ such that $100\mid a^2-b^2$." Does that help clear things up? You have to show it holds for all such $A$. –  Daniel Rust Dec 13 '13 at 13:52
    
Just to clarify, when you say "You have to show it holds for all such A", you mean that for every 2 random number I just pick up ? –  test Dec 13 '13 at 13:59
show 2 more comments

1 Answer 1

The given set of integers may not contain $0$ nor $100$. Hence your proof is not valid...

share|improve this answer
    
what? Who says that? What if my set is S = { -2 .. 100 } ? –  test Dec 13 '13 at 13:48
    
In that case your proof is correct. But you have infinitely many other possibilities to check. When one say "prove that any set ..." you must consider every possibility. Otherwise one would say "prove that for some set ..." –  Emanuele Paolini Dec 13 '13 at 14:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.