|
|
|
Let S be the set {0,1,2,3,...,m-1} - all remainders modulo some integer m.
Let A be a subset of S and c some integer �S.
Let's define rA(c) to be number of combinations of getting c by
summing two elements of A modulo m.
Where a1+a2 and a2+a1 are counted as
2 but a1+a1 is counted as 1.
Let two different subsets, A and B, be called friendly if rA(c)=rB(c)
for any c�S.
1) Prove that two subsets can be friendly only if |A|=|B|.
2) If m is even, A is a subset of S and |A|=m/2 and B={n|n�S,n�A}, prove that A and B are friendly.
3) Prove that if m is even, A is a subset of S and B={b|b=n+m/2,n�A} then A and B are friendly.
4) Prove that the two subsets A and B can only be friendly if m is even.
5) Prove or Disprove that if p is prime and m=2p then the two only kinds of friendly subsets are of the kind described in Q2 and Q3.
6) Let's define two subsets as being friendly the same, except that rA(c) will be counting the different combinations of differences instead of sums modulo m. Prove that if the two subsets A and B are friendly in the first sense they are also friendly in this sense.
Source: Yatir Halevi
The webmaster and author of this Math Help site is Graeme McRae.