Results 1 to 4 of 4

Math Help - Relations in a set

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    91

    Relations in a set

    Hello,
    Given is a positive integer k. Prove that out of every set of integers which has more than 3^k elements one can pick out a sub-set S with k+1 elements and the following quality:
    for any two subsets A,B\subseteq S the sum of all elements in A is different from the sum of all elements in B.


    I've been trying to play with base-system representation for a while but it leads me nowhere. Your help will be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Pim
    Pim is offline
    Member
    Joined
    Dec 2008
    From
    The Netherlands
    Posts
    91
    I'm not sure about this, but I do have an idea about how you could approach this. Maybe you can prove that there is a subset you can make such that all numbers are "out of reach". For example, for k = 3 and the set is all numbers up until 27, the numbers 1, 4, 9 and 27 satisfy S.
    Maybe if you order them and pick the 3^0th, 3^1th, 3^2th, 3^3th, etc. ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    91
    Ok, but these numbers don't have to start with 1 and increment by 1, they can be any numbers, including negatives.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Pim
    Pim is offline
    Member
    Joined
    Dec 2008
    From
    The Netherlands
    Posts
    91
    Yeah, I know. Hence the "maybe if you order them".
    I have no idea how to actually prove this, but this was something that sprang to mind.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relations and Functions - Inverse Relations Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2011, 12:20 PM
  2. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  3. [SOLVED] More Relations on A
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 20th 2010, 04:43 AM
  4. help with relations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 6th 2008, 03:56 PM
  5. Can someone please help me with relations?
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: March 21st 2008, 07:28 PM

Search Tags


/mathhelpforum @mathhelpforum