Results 1 to 2 of 2

Math Help - Combinational Logic

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    12

    Combinational Logic

    Hi guys,

    Just a couple of exercises Im struggling with, can you help me out?

    First one;

    An n-simplex is an analogue of a triangle in n dimensions: n = 1 corresponds to an interval, n = 2 to a triangle, n = 3 to a tetrahedron, etc. Suppose that the vertices of an n-simplex are labelled 1; 2; 3; .... ; n + 1.
    We then allow arbitrary subdivisions of this simplex, with the rule that any subdivided region has n + 1 vertices on its boundary. These vertices may be labelled according to the following rules: if they are on an edge (a1; a2) then they may be labelled a1 or a2, if they are on a face (a1; a2; a3) then they may be labelled a1, a2 or a3, while if they are in a d-dimensional region defined by vertices labelled (a1; a2; ... ; ad+1) then they may be labelled a1, a2, ... , ad+1. Spernerís lemma for an n-simplex states that for any choice of subdivision with vertices labelled according
    to the previously defined rules, the number of regions labelled (1; 2; 3; ... ; n + 1) must be an odd number. Prove this lemma via the floorplan lemma and the principle of induction.

    Second one;

    Prove that it is not possible to completely cover a 6x6 chessboard by
    tiles which have dimensions 1x4.

    Thanks in advance guys!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Banana1 View Post
    Hi guys,

    Just a couple of exercises Im struggling with, can you help me out?

    First one;

    An n-simplex is an analogue of a triangle in n dimensions: n = 1 corresponds to an interval, n = 2 to a triangle, n = 3 to a tetrahedron, etc. Suppose that the vertices of an n-simplex are labelled 1; 2; 3; .... ; n + 1.
    We then allow arbitrary subdivisions of this simplex, with the rule that any subdivided region has n + 1 vertices on its boundary. These vertices may be labelled according to the following rules: if they are on an edge (a1; a2) then they may be labelled a1 or a2, if they are on a face (a1; a2; a3) then they may be labelled a1, a2 or a3, while if they are in a d-dimensional region defined by vertices labelled (a1; a2; ... ; ad+1) then they may be labelled a1, a2, ... , ad+1. Spernerís lemma for an n-simplex states that for any choice of subdivision with vertices labelled according
    to the previously defined rules, the number of regions labelled (1; 2; 3; ... ; n + 1) must be an odd number. Prove this lemma via the floorplan lemma and the principle of induction.

    Second one;

    Prove that it is not possible to completely cover a 6x6 chessboard by
    tiles which have dimensions 1x4.

    Thanks in advance guys!
    First one: Sorry, can't help you with this, don't know the floorplan lemma.

    Second one:

    Number the chessboard's squares like this:
    Code:
    1 2 3 4 1 2
    2 3 4 1 2 3
    3 4 1 2 3 4
    4 1 2 3 4 1
    1 2 3 4 1 2
    2 3 4 1 2 3
    With this numbering, any 1 by 4 tile covers one 1, one 2, one 3, and one 4, regardless of where it is placed, horizontally or vertically. So any covering by 9 such tiles must cover 9 1's, 9 2's, 9 3's and 9 4's. But the chessboard contains 9 1's, 10 2's, 9 3's, and 8 4's. Conclusion: no such covering is possible.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Can someone check my logic (sentential logic)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 13th 2010, 03:30 AM
  2. Show equality by combinational argument
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 30th 2009, 05:46 PM
  3. combinational probability
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 11th 2007, 11:14 AM
  4. combinational test
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 11th 2007, 10:35 AM
  5. combinational puzzle
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 11th 2007, 10:29 AM

Search Tags


/mathhelpforum @mathhelpforum