Originally Posted by

**Arie** 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