About time to post the solution for the
covering problem from last time. I though I had come up with a good way to post pictures in blogger, but I apparently forgot what it was, so I don't think I'll bother, the solution is easy enough to describe anyway.
Picture a horizontal line of four squares, numbered 1,2,3,4. Add a square we will call 5 above square 2, and a square we will call 6 below square 3.
It is clear this cannot be tiled, as both 1 and 5 only touch 2 (as well as 4 and 6 only touching 3), but if we add a 2x1 block below 1 and 2, this gives a new option for 1 and 6 to connect, and the tiling works.
Easy enough solution, and it got me thinking, is there an easy way we can check when a tiling is possible or impossible? The general problem is that we have two equally sized groups of things (in this case white and black squares) and you want to have a 1-1 matching between group 1 and group 2, but there are restrictions on what may match with what. In my solution example, we have squares 1,3,5 in group 1 and 2,4,6 in group 2. 1 and 5 may match to 2, and 3 may match to any of 2,4,6. Clearly in this case a matching is impossible, since we will not be able to match different things to 1 and 5, also on the other side we won't be able to match 4 and 6.
We can see a necessary condition here:
For each subset S of group 1, the set of things that subset can match with needs to have at least as many elements as S.
So in our example, the set S can be {1,5} and the set of things they match to is {2} and so it violates this condition. Of course, I could have put group 2 instead of group 1, but as it turns out I don't need to, as we will see.
I spent some time wondering if it was possible to satisfy this condition and still not have a possible matching, but I wasn't able to find anything, I started to suspect that this condition was not just necessary, but also sufficient. Then somebody pointed me to the
Hall marriage theorem which proves that this statement is in fact sufficient, and also having this statement proves the equivalent statement on group 2.
Anyway, neat stuff, and a new theorem I didn't know. Thats all for now.
