Results 1 to 3 of 3

Math Help - Coloring problem

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    2

    Post Coloring problem

    I'm not sure how to approach the following problem. Any help would be appreciated!

    An nxn square is divided into n^2 unit squares. Each of the (n+1)^2 vertices is to be colored either red or blue. How many different colorings are there such that each unit square has exactly two red vertices?

    Note: Two colorings are considered different if at least one vertex is colored differently in the two schemes.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2006
    Posts
    244
    Quote Originally Posted by Lighterning View Post
    I'm not sure how to approach the following problem. Any help would be appreciated!

    An nxn square is divided into n^2 unit squares. Each of the (n+1)^2 vertices is to be colored either red or blue. How many different colorings are there such that each unit square has exactly two red vertices?

    Note: Two colorings are considered different if at least one vertex is colored differently in the two schemes.
    How many colorings would there be if exactly one vertex was to be colored red?

    .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Lighterning View Post
    I'm not sure how to approach the following problem. Any help would be appreciated!

    An nxn square is divided into n^2 unit squares. Each of the (n+1)^2 vertices is to be colored either red or blue. How many different colorings are there such that each unit square has exactly two red vertices?

    Note: Two colorings are considered different if at least one vertex is colored differently in the two schemes.
    This is an interesting problem. My suggestion would be to look at the first column, and to wonder if the positions of the red vertices in this column force the positions of the red vertices in the second column. (For instance, if the first two vertices of the first column are red, the first two vertices of the second column have to be blue)

    It seems to me that all the configurations of the first column except two are such that the other columns are forced. So that, in most cases, the configuration is entirely given by the first column, and counting configurations boils down to counting configurations of the first column (with a special treatment for the above mentioned two special configurations)

    I let you think about it (draw plenty of sketches). This proof scheme would work for a rectangle with m columns and n rows.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph coloring
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 2nd 2010, 12:49 PM
  2. Coloring K10
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 15th 2009, 11:42 AM
  3. 4 Coloring Problems
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 22nd 2009, 08:32 PM
  4. Chromatic Coloring
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 11th 2009, 11:25 AM
  5. Coloring of a Cube
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 9th 2008, 04:01 PM

Search Tags


/mathhelpforum @mathhelpforum