Does any of you know the name of the problem described below? I am especially interested in possible generalizations of this problem.

I looked through my textbooks on combinatorics but could not find a similar problem.

Problem Statement. I have 36 different coins. Each side has a number printed on it ranging from 1 to 6.

With notation {NumberSideA, NumberSideB} this would give:

{1,1}, {1,2}, ..., {1,6},
{2,1}, {2,2}, ..., {2,6},
{6,1}, {6,2}, ..., {6,6}.

I want to divide all of these into a number of bins such that in each bin, there are at most 4 different indices on Side A and at most 4 different indices on Side B. Furthermore, any combination of 2 bins should contain coins with at most 5 different indices on Side A and at most 5 different indices on side B.

  • What is the minimum number of bins for which this is possible?
  • $\begingroup$ you can think about partitioning your grid. And by grid I mean the 6x6 matrix the problem admits. This males it clear it can be done in 4 bins. But I don’t know if that will necessarily give you the min $\endgroup$ – T. Fo Dec 19 '18 at 15:44
  • $\begingroup$ Six bins is minimal as shown in my completely rewritten answer. $\endgroup$ – Daniel Mathias Jan 4 at 17:14

The problem is a variation of Latin Square. It is equivalent to ask how many colors are needed to color a 6x6 grid lattice such that:

  1. each color occupies at most 4 grids of any row and any column.
  2. no two color together occupies a whole row or a whole column.

This certainly cannot be done with two colors. The following example shows with 3 colors, this is possible. enter image description here

  • What is the minimum number of bins for which this is possible?

My previous claim that 7 bins is minimal was incorrect. I wrote a short program in C to search for a solution in 6 bins. This is the output:

0 0 0 1 1 2
0 0 0 1 1 3
0 0 0 4 4 5
1 4 5 1 1 5
2 2 3 3 4 2
2 2 3 3 5 2

The numbers in this grid indicate which bin each coin is in. The indices for the coins are the (x, y) column and row values (not shown). This is known to be a minimal solution because the program would not have assigned any coin to the sixth bin if could be placed into one of the first five subject to the stated restrictions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.