1
$\begingroup$

Given an 8x8 Mboard ( top left piece missing), as given below in the image, and 21 trominoes, how can we proof that there exists a configuration where there will be no overlap after all trominoes are placed.

enter image description here

What I tried doing was - a 8x8 Mboard will have 63 squares, now $63 / 21 = 3$, ie. it is divisble. But recall a tromino is L-shaped, so just show that the total number of squares is divisble with the total number of trominoes really isnt telling much. I mean how do you account for the shape of the tromino in that case.

I actually manually plotted out a configuration but could only get up 20 trominoes to fit. I have no idea how 21 fits in, and how we can say that there will be no overlap.

enter image description here

The red squares are the squares that were blank. There are 3 of them, but how can we rearrange the configuration to included 21 trominoes. And more than that how can we say that there will be no overlap?

$\endgroup$

marked as duplicate by Jyrki Lahtonen, Arthur, Cesareo, Paul Frost, cmk Jul 18 at 13:31

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ If you use 20 trominoes, you should have $(8 \cdot 8 - 1) - (20 \cdot 3) = 63 - 60 = 3$ red tiles. Indeed, in your second figure, the bottom left square should be colored red. $\endgroup$ – parsiad Jul 18 at 8:08
  • $\begingroup$ @parsiad edited it. $\endgroup$ – ng.newbie Jul 18 at 8:14
  • $\begingroup$ Another obligatory link. $\endgroup$ – Jyrki Lahtonen Jul 18 at 8:27
  • 2
    $\begingroup$ Fun fact: There are exactly 30355 ways to tile the chessboard with one corner missing. 15178 solutions if we consider mirror images as the same solution. This means that there's only one solution that has mirror symmetry! $\endgroup$ – John Dvorak Jul 18 at 8:32
  • 1
    $\begingroup$ @ng.newbie Presumably by just doing it. Tell a computer to try every way, and have it count them. It's possible that there is some other, really clever way to do it, but I doubt it. It seems like a mess to count by hand. $\endgroup$ – Arthur Jul 18 at 8:38
6
$\begingroup$

Instead of filling in row-by-row, go layer-by-layer. First tackle the $2\times 2$ with one corner missing. This is trivial. Now tackle the $4\times 4$, by first covering the top $2\times 2$ the way you did.

Here is the kicker: The way you placed your trominoes in this last step makes them one large tromino! (They cover the $4\times4$ board except the top $2\times2$.) Now you can tackle the $8\times8$ by first taking the top $2\times2$, then the top $4\times4$, then take the rest of the board using your large tromino piece. This makes this last step identical to the $4\times 4$ covering, only scaled up.

$\endgroup$
  • $\begingroup$ tell me given the total number of squares and the number trominoes, is it possible to tell whether there will be any overlap or not ? If so how is that possible ? I guess thats what I am really asking. $\endgroup$ – ng.newbie Jul 18 at 8:20
  • $\begingroup$ So Arthur proves that the task is possible irrespective of which of the 64 squares is missing. This is a classic puzzle. We may have covered it earlier. IIRC I've seen the 3D version with a $2^n\times 2^n\times 2^n$ cube with a single $1\times1\times1$ prefilled to be filled it with blocks of $2\times2\times2$ minus one corner. But +1 anyway. $\endgroup$ – Jyrki Lahtonen Jul 18 at 8:24
  • 2
    $\begingroup$ @ng.newbie Yes, it's possible to tell. If it's possible, then a proof will consist of giving an example of it being done. If it's impossible, then a proof will consist of some reason it just can't be done. For instance, it's impossible by using $20$ trominoes, because the number of squares doesn't match up. It's impossible using any number of dominoes because the board has an odd number of squares. That kind of argument will show impossibility. But there is no good, general way to show that it is possible except just doing it. $\endgroup$ – Arthur Jul 18 at 8:25
  • $\begingroup$ Not surprisingly this has been done at least twice before. In addition to my suggested duplicate target see also here. $\endgroup$ – Jyrki Lahtonen Jul 18 at 8:28
  • $\begingroup$ Oh, you had a slightly different recursion in mind. Sorry about jumping the gun a bit. Many ways to do this. $\endgroup$ – Jyrki Lahtonen Jul 18 at 8:32
3
$\begingroup$

      enter image description here

$\endgroup$
  • $\begingroup$ @parisad Any intution for this? because I can't undertsand why this works. Any mathematical proof for this exists ? $\endgroup$ – ng.newbie Jul 18 at 8:16
  • $\begingroup$ This is a mathematical proof. As for intuition, you could try breaking up the board into smaller chunks and cover each chunk separately. $\endgroup$ – parsiad Jul 18 at 8:17
  • $\begingroup$ @parisad Ok just tell me given the total number of squares and the number trominoes, is it possible to tell whether there will be any overlap or not ? If so how is that possible ? I guess thats what I am really asking. $\endgroup$ – ng.newbie Jul 18 at 8:19
  • $\begingroup$ See @Arthur's answer. $\endgroup$ – parsiad Jul 18 at 8:21
  • $\begingroup$ @parisad Also could you help me out and tell me which branch of mathematics this falls under. Is it a tiling problem? If so I will study them to gain more insight. $\endgroup$ – ng.newbie Jul 18 at 8:21
3
$\begingroup$

This picture shows how you can build up the solution, exactly as Arthur describes in his answer. enter image description here

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.