Question

Prove #3(The integers 1,..., 2n are arranged in any order on 2n places
numbered 1,..., 2n. Now we add its place number to each integer. Prove that
there are two among the sums which have the same remainder mod 2n.:

Answer 1

http://midcitiesmathcircle.files.wordpress.com/2012/02/math_circle_invariants.pdf

Answer 2

Hint: read the title

Answer 3

i bet it is pigeon hole

Answer 4

That is part of it

Answer 5

sort of

Answer 6

slightly

Answer 7

but don't base your proof off of it

Answer 8

Another Hint:
think about the sums of the numbers and the sums of the places (mod 2n)

Answer 9

do u know the answer?

Answer 10

Yes

Answer 11

dont u use contradiction?

Answer 12

Yes

Answer 13

\[s _{1} = 2(1+2+...+2n)=(2n+1) =0\]??

Answer 14

=2n(2n+1) = 0 i mean

Answer 15

If by that you mean that the sum of the bases and numbers (mod 2n) is congruent to 0, then yes

Answer 16

so u want the sum of the remainders?

Answer 17

well, that is the invariant:
\[0+1+2+...+2n-2+2n-1 = n (\mod 2n)\]

Answer 18

therefore:
\[2(0+1+2+...+2n-2+2n-1) = 0 (\mod 2n)\]

Answer 19

now what would it mean if no two sums had the same remainder (mod 2n)?

Answer 20

no idea. actually all the sudden i feel feverish and have a headache haha

Answer 21

this is descrete mathematics?

Answer 22

therefore::

Answer 23

Now, if no 2 numbers have the same remainder (mod 2n). we have:

Answer 24

*sum of number and place

Answer 25

not number alone

Answer 26

Therefore, some numbers must have the same remainder

Answer 27

:)

Answer 28

Quantum Electro Dynamics

Answer 29

Also just realized that I typoed contradiction...

Answer 30

i still think it is pigeon hole

Answer 31

1, 2, 3, 4, 5, 6, 7, 8, 9, 10
8, 9, 10, 1, 7, 2, 6, 3, 5, 4
9, 11, 13, 5, 12, 8, 13, 11, 14, 14 ------> SUMS
Now I see only one remainder 9 when divided by 10 to all sums

Answer 32

But that isn't the thing we are trying to prove

Answer 33

We are just proving that at least 2 of them have the same remainder

Answer 34

oh........ I got it now.