Results 1 to 8 of 8

Math Help - Unique representation of N integers randomly chosen out of a set of M (N<M) numbers

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    4

    Unique representation of N integers randomly chosen out of a set of M (N<M) numbers

    Is it possible to uniquely represent N integers randomly selected out of a larger set of M integers? For example, if M = {1,2,3,...,200} and N = 12, is it possible to map any 12 numbers randomly selected out of M into the set K = {1,2,3...,12}?
    In other words, if I have 200 devices with IDs in the range of 1 to 200, and I randomly grab 12 devices out of the lot, is there an algorithm which will allow each device to INDEPENDENTLY change its ID to a UNIQUE number from the set {1,2,3,...,12}?
    Note: INDEPENDENTLY means the devices donít need to communicate with other devices or with some central processing unit in order to solve the problem, and UNIQUE means there are no clashes between the new IDs.
    Intuitively it seems that there's no way to uniquely reduce 200 numbers into 12. However, on the other hand, knowing that there's a unique prime factorization for every integer, makes you wonder if there is a way to map the unique vector of primes (for each integer) into a unique number in the reduced set.
    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Feb 2009
    From
    Tallahassee Florida
    Posts
    6

    Creating function to map set {1,2,...N} to randomly chosen set of N integers.

    It's not necessary to specify an algebraic or analytic formula to define the function which maps the integers {1,2,3...N} onto the N integers chosen at random,
    from a larger set of integers.

    For example, recently I wrote an formula in Microsoft Excel that mapped one set of names into another set of names. I used the vlookup function in Excel to do this.

    For example suppose you choose randomly, the numbers [123,2,49,6,11,22,199]
    and want a function that uniquely assigns them to [1,2,3,4,5,6,7].

    Then you simply name and define your function to do exactly that.


    RF[1] = 123
    RF[2] = 2
    RF[3] = 49
    RF[4] = 6
    RF[5] = 11
    RF[6] = 22
    RF[7] = 199

    Kermit Rose
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Arie View Post
    Is it possible to uniquely represent N integers randomly selected out of a larger set of M integers? For example, if M = {1,2,3,...,200} and N = 12, is it possible to map any 12 numbers randomly selected out of M into the set K = {1,2,3...,12}?
    In other words, if I have 200 devices with IDs in the range of 1 to 200, and I randomly grab 12 devices out of the lot, is there an algorithm which will allow each device to INDEPENDENTLY change its ID to a UNIQUE number from the set {1,2,3,...,12}?
    Note: INDEPENDENTLY means the devices don’t need to communicate with other devices or with some central processing unit in order to solve the problem, and UNIQUE means there are no clashes between the new IDs.
    Intuitively it seems that there's no way to uniquely reduce 200 numbers into 12. However, on the other hand, knowing that there's a unique prime factorization for every integer, makes you wonder if there is a way to map the unique vector of primes (for each integer) into a unique number in the reduced set.
    Thanks
    The way you're asking the question, the answer is obviously no, there is no injective function from M to K, when M and K are finite sets with |M| > |K|. Maybe you should think more carefully what you are asking. Is it possible to have a solution to your problem when M = {1,2,3} and K = {1,2}? If so, then you're not asking the question you mean to ask. This is my opinion.

    (Edit: silly typo.)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2010
    Posts
    4
    To Kermit1941: Thanks for the reply, but it doesn't answer my question - perhaps I need to clarify. What I'm after is:

    "Given any number from the (larger) set M, determine the index of its mapped representative in set N."

    I.e., in your example, if you are given the number 49, can you figure out that the index in the RF array would be 3?

    That is the meaning of the requirement for the algorithm to be INDEPENDENT - i.e. I need the algorithm of determining the target (mapped) integer in set N to be independent of any knowledge about other chosen numbers.

    Arie
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2010
    Posts
    4
    Quote Originally Posted by undefined View Post
    Maybe you should think more carefully what you are asking. Is it possible to have a solution to your problem when M = {1,2,3} and K = {1,2}?

    (Edit: silly typo.)
    You are probably right, but I didn't get your altered question - could you please explain.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Arie View Post
    You are probably right, but I didn't get your altered question - could you please explain.
    Well when we have sets as small as M = {1,2,3} and K = {1,2}, it's easy to list out all possibilities exhaustively. So, there are only 8 functions from M to K, they are

    {(1,1),(2,1),(3,1)}
    {(1,1),(2,1),(3,2)}
    {(1,1),(2,2),(3,1)}
    {(1,1),(2,2),(3,2)}
    {(1,2),(2,1),(3,1)}
    {(1,2),(2,1),(3,2)}
    {(1,2),(2,2),(3,1)}
    {(1,2),(2,2),(3,2)}

    And none of these work.

    But I was asking because I wasn't sure if you had asked the question properly. If you could produce a solution to this small case, then it would act as an example that we could use to figure out what you're really asking.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jul 2010
    Posts
    4
    Quote Originally Posted by undefined View Post
    But I was asking because I wasn't sure if you had asked the question properly. If you could produce a solution to this small case, then it would act as an example that we could use to figure out what you're really asking.
    The real-world problem I am trying to solve is the one I mentioned in my original question:"If I have 200 devices with IDs in the range of 1 to 200, and I randomly grab 12 devices out of the lot, is there an algorithm which will allow each device to INDEPENDENTLY (= autonomously) change its (own) ID to a UNIQUE number from the set {1,2,3,...,12}?". On the face of it it's impossible, but thought there might be perhaps some clever way forward.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Arie View Post
    The real-world problem I am trying to solve is the one I mentioned in my original question:"If I have 200 devices with IDs in the range of 1 to 200, and I randomly grab 12 devices out of the lot, is there an algorithm which will allow each device to INDEPENDENTLY (= autonomously) change its (own) ID to a UNIQUE number from the set {1,2,3,...,12}?". On the face of it it's impossible, but thought there might be perhaps some clever way forward.
    The answer is no.

    EDIT: You can read about the pidgeonhole principle, but in all honesty, it should be obvious from the start.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Randomly chosen family
    Posted in the Advanced Statistics Forum
    Replies: 13
    Last Post: October 12th 2011, 11:06 AM
  2. Replies: 1
    Last Post: August 1st 2010, 09:40 PM
  3. Replies: 2
    Last Post: June 1st 2010, 03:49 AM
  4. Replies: 3
    Last Post: January 26th 2010, 11:08 AM
  5. probability that a randomly chosen member
    Posted in the Statistics Forum
    Replies: 1
    Last Post: November 2nd 2009, 03:09 PM

Search Tags


/mathhelpforum @mathhelpforum