Partitioning sets of integers Let A={1,2,3,…,n}. Consider the problem of partitioning A into subsets such that if S is one of the subsets, and i and j are distinct elements in S, then i+j and i-j are not square numbers. So, for instance, 1 and 3 could not be in the same subset, since 1+3=4 is a square number; also, 8 and 9 could not be in the same subset, because 9-8=1 is a square. Let’s say a partition like this has Property N (for non-square).
For example, if A={1,2,3,4,5,6,7,8,9,10}, we can partition A into the subsets S1 ={1,7}, S2={2,4,9}, S3={3,5,10}, and S4={6,8}. Note that every element of A is in exactly one of the S sets: this is what it means to partition A.
Now, in this example the partition had four subsets.
What is the smallest number of subsets a partition of A with Property N can have?
Investigate this problem for particular n by showing first that the problem is equivalent to coloring a certain graph. Then design and solve an LP, using lpsolve, that solves the coloring problem of that graph, and use that coloring to answer the question of the minimal partition of A with Property N.
Do this for lots of values of n (how large an n can you solve the problem for?), draw lots of graphs, with color, etc. Make some tables, perhaps make some conjectures.
For this assignment, be sure to completely mathematically describe the coloring LP you will be using. Write about it in your own words, but feel free to copy the mathematical notation from lecture.
Please include all code, and at least some examples of lpsolve input files and lpsolve output.
0 comments