Matching Multisets

Given a large set of shopping cart chips with different colors, you can choose multisets of cardinality k. In this case repetition of colors is allowed and the order of the chosen chips doesn't matter. This way we have (n+k-1) C k combinations. Jared McComb suggested to construct a rectangle with all combinations so that the neighbors in x- and y-direction differ in only one element. So I wrote a program to solve the problems for n=8 and k=3 with a total of 120 pieces. After the 10x12 rectangle was finished I produced the pieces to display the solution.

If you want to place the pieces according to the computer solution, it's reasonable to divide the whole set into subsets with two or three same colors and subsets with all colors different.

For 8x15, 6x20, 5x24 and 4x30 rectangles we have fewer matching conditions and the solutions were found faster.

Because the lengths of the missing rectangles with smaller widths are rather large, I decided to construct spirals of width 3, 2 or 1. Especially the spiral with width 1 can easily be made by hand.

Index