# Maths (ILP) puzzle from a programming contest

This programming contest puzzle concerns itself with "cards", each of which bears a certain pattern of either one circle, one square, one triangle, two circles, two squares, etc. up to three circles, three squares, and finally three triangles -- all the 9 combinations, that is. Now, one can pick 3 cards (called sets) such that in each of the two characteristics -- the shape or the number thereof -- the cards are either all equal or all different. One is to write a program to find out the largest number of sets that can be formed from the given set of card. Each set of cards is given as a pair from 1-3 and circle-square-triangle. I started with the following thoughts. I collate all the cards that come in the test case into a 3x3 matrix, where e.g. $$a_{11}$$ is the total number of one-circle-type of cards, and analogously for the rest. All the three cards in a valid set now either come from a row, column, the two diagonals, or indeed from each individual cell of this matrix. This way, one obtains an integer program with inequality constraints, where the objective function is linear. (There are 3+3+9+2=17 variables and 9 inequality constraints.) I can feel though there is a "shortcut" and I must be missing something. What do you think?

EDIT: actually there can be a total of 21 types of sets -- 3+3+9+6, where the last 6 comes from choosing all "independent" cells from the matrix (i.e. distinct in both row and column).

EDIT: After some thinking, here are some updates. If we could not form a set by taking three cards of the same type, this problem could be nicely modeled as a network flow problem. However, we can, therefore some greedy logic is required. We notice that each card-type can participate in 5 different configurations -- one we'll call trivial, which is taking three cards of this type, and four non-trivial, where at least one characteristic differs. Now, what happens when there are four cards of type x (say, of type one-circle). We would want to look into the four non-trivial configurations and see if we have enough to "send over" the four given cards to these respective configurations, to form 4 sets. If this condition does not hold, we are better off by just forming one set using 3 cards (with 1 left over) -- indeed, we better not "disturb" other cells. Let me see if I can translate this into an algorithm.

EDIT: I've made some progress on the problem. It goes like this. There are 21 configurations in all, and in the optimal solution we will be left off with a matrix such that for each of the "non-trivial" 12 configurations at least one cell is 0, and none of the cells contains a number larger than 2. Indeed, if there existed a configuration such that all the participating cells contain at least 1, we could have improved our solution. That said, the residual matrix will be a 3x3 matrix consisting of entries 0-2, i.e. we are dealing with a ternary number. I have already done some computations, and there are exactly 1603 configurations that could serve as residual matrices. One of them is e.g.

2 0 1
1 0 0
0 0 0


This takes us to the idea of fixing some such configuration, and trying to solve an underdetermined system of linear equations with 9 rows and 21 variables. Do you think this might work?

EDIT: As it turns out, the rank of the above-mentioned 9x21 matrix is 9, as shown here: https://matrixcalc.org/en/#rank%28%7B%7B1,0,0,1,0,0,1,1,0,0,0,0,3,0,0,0,0,0,0,0,0%7D,%7B1,0,0,0,1,0,0,0,1,1,0,0,0,3,0,0,0,0,0,0,0%7D,%7B1,0,0,0,0,1,0,0,0,0,1,1,0,0,3,0,0,0,0,0,0%7D,%7B0,1,0,1,0,0,0,0,1,0,0,1,0,0,0,3,0,0,0,0,0%7D,%7B0,1,0,0,1,0,1,0,0,0,1,0,0,0,0,0,3,0,0,0,0%7D,%7B0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,3,0,0,0%7D,%7B0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,3,0,0%7D,%7B0,0,1,0,1,0,0,1,0,0,0,1,0,0,0,0,0,0,0,3,0%7D,%7B0,0,1,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,3%7D%7D%29 Now, what does this mean in terms of solving the system? When I diagonalize it using e.g. Gaussian elimination, we'll have 9 diagonal non-zero entries. What to do with the other 12 variables though?

EDIT: answering my previous question, since diagonalization process would not depend on the RHS in any way, here is what we get with Gaussian elimination:

 3 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0
0 3 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
0 0 3 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0
0 0 0 3 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1
0 0 0 0 3 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0
0 0 0 0 0 3 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0
0 0 0 0 0 0 3 0 0 1 1 0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 3 0 0 0 1 0 0 1 0 1 0 0 1 0
0 0 0 0 0 0 0 0 3 0 0 0 0 0 1 0 0 1 1 0 1


That is, there are exactly 4 "trailing" ones to account for the "free" variables. What to do with those? We remind ourselves that the aim is to choose the variables that their sum is maximal.

EDIT: I got accepted with the optimizations based on the above observations.

• Note that Set allows you choose any of the six diagonals, not just the two main ones. I.e. one circle three square two triangle is also a valid set. – Alexander Geldhof Nov 11 '19 at 10:28