# Math Help - Combinational Logic

1. ## 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!

2. Originally Posted by Banana1
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.