A Question Concerning Arranging Tokens into a Grid with Rules
an endeavor of curiosity. if you just want to post possible techniques I could use to solve the problem, that would be appreciated as well. if you need clarification on the problem, please let me know. thank you for your time.
--
Suppose you have a random finite set of colored tokens and you have to arrange them in a grid according to the following set of rules.
1) As many tokens as possible must be used in the grid.
2) A cell can have at most one color of token in it
3) Each row and column cannot have two cells which share the same color
4) For each row, the number of tokens in the first cell must be exactly 1 or 0, in the second cell exactly 2 or 0, ... in the kth cell exactly k or 0 and so on
5) For each row, you cannot fill in a cell if the previous cells have not been filled.
Here are my initial thoughts
- For ease, we can consider colors with capital letters A, B, C, ... and so on, and the frequency of how many colored tokens with repetition of a letter. ex. AAA means that there are three tokens of color 'A'. We can introduce |A| as notation as well. In the previous example, |A| = 3
- Without loss of generality, we can relabel as necessary so that |A| 
|B| |C| and so on.
- If we consider m = amount of tokens and n = color of tokens, then an upper bound for the number of one color of token that can be used in the grid is 1 + 2 + ... + n = n(n+1)/2
- Brute force can work for this problem if you think in terms of n x n 'bingo' cards that covers all the permutations of which colors can go into each cell (first disregarding number), then filling them in as much as possible and then by inspection checking which results in the smallest remainder. It just isn’t elegant and it produces a lot of bingo cards for large n. [I'm also not sure how to approach the problem if we allow for infinities]
Here is an example. Again, if this is unclear, let me know.
Given
then here are some possible configurations
which has a remainder of C
which also has a remainder of C.
--
Again, this is only for curiosity's sake. Without loss of generality, is there a way to design an algorithm that can organize a random set of tokens into a grid to get a least remainder?
