Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorial Number Theory Problem

  1. Apr 25, 2012 #1

    I would like to see a solution to the following problem:

    Let A be a finite collection of natural numbers. Consider the set of the pairwise sums of each of the numbers in A, which I will denote by S(A). For example, if A={2,3,4}, then S(A)={5,6,7}. Prove that if S(A)=S(B) for two different finite sets of natural numbers A and B, then |A|=|B|, and |A|=|B| is a power of 2.

    I find this problem interesting, but I am working on other problems. Anyone have ideas?

  2. jcsd
  3. Apr 25, 2012 #2


    User Avatar
    Science Advisor

    You haven't defined |A| for this situation.
  4. Apr 25, 2012 #3
    For a set C, |C|=the cardinality of C.
  5. Apr 25, 2012 #4

    Well, if one considers zero a natural number (many do) then both claims above are false, as [itex]\{2,3,4\},\{0,2,3,4\}[/itex] , otherwise...perhaps by induction on [itex]|A|+|B|[/itex] ...

  6. Apr 26, 2012 #5
    Maybe I'm missing something, but it looks like for A = {1,2,3,4,5,6,7} and B = {1,2,3,5,6,7}

    S(A) = {3,4, ... 12,13} = S(B), but |A|=7 and |B|=6

    Maybe there should be some other restrictions on A and B?

    (guessing) If neither A nor B may be a subset of the other, then consider {1,2,3,4,6,7,8,9}, {1,2,3,5,7,8,9} . Cardinalities 8 and 7.
  7. Apr 27, 2012 #6
    Great Scott, you may be right catellus!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook