If I have two positive integers N and M, I need to construct N equally-sized sets that can contain numbers from 1 to M. These sets do not need to be disjoint. The catch is that all of the products of any two numbers from different sets must be unique.
For example, the sets: {1,2,3,4,5} and {6,7,8,13,17} would not be allowed because 3∗8=24 and 4∗6=24. Essentially, the products of the cartesian products of the sets must be unique.
The goal is to derive some sort of algorithm or technique that could maximize the size of each set. Intuitively, I first thought about taking all of the primes from 1 to M and dividing them into N equal sets, however I was told that there were better solutions.
I would appreciate any and all guidance towards properties or techniques that can help me produce an optimal solution.
Disclaimer: This was a problem for a math/programming competition. The event is now over and I am curious to see what solutions are out there.