Results 1 to 1 of 1

Math Help - A Question Concerning Arranging Tokens into a Grid with Rules

  1. #1
    Senior Member MacstersUndead's Avatar
    Joined
    Jan 2009
    Posts
    291
    Thanks
    32

    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| \leq |B| \leq |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
    \begin{matrix}A\\BB\\CC\\DDD\end{matrix}
    then here are some possible configurations

    \begin{matrix}A&BB&DDD\\C\end{matrix}
    which has a remainder of C
    \begin{matrix}A&BB\\C&DD\\D\end{matrix}
    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?
    Last edited by MacstersUndead; November 14th 2012 at 01:28 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Arranging numbers in a 3X9 grid
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 18th 2010, 08:41 AM
  2. Arranging numbers in a grid
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 21st 2010, 08:03 AM
  3. Arranging cross shaped particles on a 2D grid
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 23rd 2009, 11:22 AM
  4. help with arranging no. question
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 14th 2009, 11:04 PM
  5. Re-arranging formula question
    Posted in the Algebra Forum
    Replies: 4
    Last Post: September 18th 2008, 04:00 PM

Search Tags


/mathhelpforum @mathhelpforum