Friendly Sets

Let S be the set {0,1,2,3,...,m-1} - all residues modulo some integer m.
Let A be a subset of S and c Î S.

Let's define r_A(c) to be number of ways to get c by summing two elements of A modulo m.
Where a₁+a₂ and a₂+a₁ are counted as two distinct ways, but a₁+a₁ is counted as a single way.
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) Let's define two subsets as being friendly the same, except 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

Solution

Sorry, there are no solutions for questions 5 and 6 of this puzzle yet . . . . . . 

1) Prove that two subsets can be friendly only if |A|=|B|.

If A and B are friendly, then the sum for all c in S of r_A(c) - r_B(c) = 0, so the sum for all c in S of r_A(c) equals the sum for all c in S of r_B(c).

The sum for all c in S of r_A(c) is the total number of sums of pairs of elements of A, which is |A|².

The sum for all c in S of r_B(c) is the total number of sums of pairs of elements of B, which is |B|².

Since these two sums are equal, |A|² = |B|², so |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.

Let c be any element of S.  For the moment, let's just consider the elements, a, of A such that c-a is in B.  Let "x" be the number of elements of A such that c-a is in B.  For each of these x elements of A, there is an element of B with the same property.  That is, an element, b=c-a is in B, and c-b=a is in A.  Then there are m/2-x elements of A such that c-a is also in A, and there are m/2-x elements of B such that c-b is also in B.  In other words, r_A(c)=r_B(c)=m/2-x.

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.

Let c be any element of S.  For each pair of elements a₁,a₂ in A such that a₁+a₂=c, there's a pair of elements b₁=a₁+m/2, b₂=a₂+m/2 in B with the same sum.  Therefore, r_A(c)=r_B(c).

4) Prove that the two subsets A and B can only be friendly if m is even.

Assume A and B are friendly, and let c be an element of S that is in either A or B but not both.  For contradiction, let m be odd.  Since m is odd, c/2 uniquely identifies an element of S.  c/2 is in A iff r_A(c) is odd, and since r_A(c)=r_B(c), c/2 is in A iff c/2 is in B, a contradiction.

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 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.

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]