Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By Kiwi_Dave

Math Help - Hard combinatorics question

  1. #1
    Newbie
    Joined
    Apr 2013
    From
    Bucaramanga, Colombia
    Posts
    2

    Hard combinatorics question

    Let's say that I have a chess board (64 squares), and I want to color it using 5 colors (green, red, blue, yellow and black), but making sure that neither of the colors touch each other. How many different boards can I make?

    To clarify a bit: let's say that the square b2 is blue. Then the following squares can't be blue: b3, b1, a2 and c2. But the following squares can be blue: a3, c3, a1 and c1.
    Last edited by oveluus; April 24th 2013 at 12:38 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: Hard combinatorics question

    Hey oveluus.

    Are you willing to use a computer to solve this?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2013
    From
    Bucaramanga, Colombia
    Posts
    2

    Re: Hard combinatorics question

    Yes, even though I was hoping for a more general formula.

    I know nothing about programming so you'll have to help me with that.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2008
    From
    Melbourne Australia
    Posts
    195
    Thanks
    13

    Re: Hard combinatorics question

    If you colour as follows:

    1. colour the lowest left corner
    2. colour the 3 squares around that corner
    3. colour the 5 squares around this new larger square
    etc.

    Then there are 5 ways of doing the first step.
    For each remaining step start at the lowest square and work counter clockwise. The first square to be coloured can be done in one of four ways, the highest rightmost (diagonal square) can be coloured in one of four ways all remaining squares can be coloured in one of three ways.

    So by my reconing there are 5*3^1*4^2*3^3*4^2*3^5*4^2*3^7*4^2*3^9*4^2*3^{11}*4  ^2*3^{13}*4^2=3^{49}4^{14}5

    Now I might have over counted because the board can be rotated through 90, 180 or 270 degrees and you may or may not want to cound boards with rotational symetry as being identical.
    Thanks from oveluus
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorics QUESTION 3-3
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 20th 2012, 05:30 PM
  2. Combinatorics question
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 29th 2011, 05:35 AM
  3. [SOLVED] Another hard combinatorics problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 17th 2011, 10:51 PM
  4. [SOLVED] Hard combinatorics problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 17th 2011, 05:06 PM
  5. Combinatorics question
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 24th 2011, 05:47 AM

Search Tags


/mathhelpforum @mathhelpforum