Timeline for Sum of sets modulo a square
Current License: CC BY-SA 2.5
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 4, 2010 at 9:12 | comment | added | Fedor Petrov | $n^2(n-1)/2$ is not always $0$ modulo $n^2$, but it always differs from $n^2(n-1)/2+n$ | |
| Aug 4, 2010 at 7:40 | comment | added | Aaron Meyerowitz | It is cute! Line up the elements of A_1 by increasing residue mod n. underneath them put the elements of A_2 in decreasing order (mod n). The sums (reduced mod n^2) are 0, n,2n,...,(n-1)*n in some order for a grand total of nn*(n-1)/2 which is 0 mod n^2. Now cyclically shift the second row. The n sums (reduced mod n^2) would be 1 n+1, ...,(n-1)n+1 for a grand total of nn*(n-1)/2+n*1 which is n mod n^2. But the grand total should remain unchanged since it is the sum sum of 2n integers. | |
| Aug 4, 2010 at 7:24 | vote | accept | Fedor Petrov | ||
| Aug 4, 2010 at 7:09 | comment | added | Gerry Myerson | @Fedor, I don't follow your proof. | |
| Aug 4, 2010 at 6:44 | answer | added | Aaron Meyerowitz | timeline score: 2 | |
| Aug 4, 2010 at 6:39 | comment | added | Fedor Petrov | Well, the easy proof is as follows: assuming contrary, consider all $n$ remainders with remainder $r$ modulo $n$, sum up. We get that sum of all elements of $A_1$ and $A_2$ equals $r+(r+n)+\dots+r+(n^2-n)$. But this does depend on $r$. Contradiction! | |
| Aug 4, 2010 at 3:51 | comment | added | Kevin O'Bryant | @Tsuyoshi: thanks. @darij Can you write more about "summing up"? | |
| Aug 4, 2010 at 3:16 | answer | added | Aaron Meyerowitz | timeline score: -1 | |
| Aug 4, 2010 at 2:23 | comment | added | Tsuyoshi Ito | All elements of A_i must be different mod n, so the set {0,2} is not allowed for n=2. | |
| Aug 4, 2010 at 2:21 | comment | added | Kevin O'Bryant | I must not understand the question. Modulo 4, isn't {0,1}+{0,2}={0,1,2,3}? | |
| Aug 4, 2010 at 0:05 | history | edited | Gjergji Zaimi |
edited tags
|
|
| Aug 3, 2010 at 22:24 | comment | added | darij grinberg | For $n$ even it is easy to get a contradiction by summing up, but for $n$ odd? | |
| Aug 3, 2010 at 21:48 | history | asked | Fedor Petrov | CC BY-SA 2.5 |