Friendly Sets

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.

Lets define r_A(c) to be number of combinations of getting c by summing two elements of A modulo m.
Where a₁+a₂ and a₂+a₁ are counted as 2 but a₁+a₁ is counted as 1.
Let two different subsets, A and B, be called friendly if r_A(c)=r_B(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) Lets define two subsets as being friendly the same only that r_A(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

Click here for the answer.

Related pages in this website

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]