nxn grid, n even

[Ender]

You have an 16x16 grid of squares, where the bottom left and top right squares are removed. Is it possible to cover all the squares with 1x2 dominoes?

Update: Changed the problem and am doing it for a 16x16 grid of squares.

[Nate]

no...a 4 variable K-map with PoS of [(~A)+B+(~C)+D][A+(~B)+C+(~D)] would be an example of it not being possible.

[iago]

Counterexample: n = 2.

:)

[Ender]

Sorry. The wording to this question is probably confusing, though I believe the wording to be correct in a convoluted way.

When I ask "is it possible to cover all the squares" I don't ask is it "possible to not be able to cover all the squares for a certain n".  So if you think it is possible, find an even n and an algorithm that allows you to cover all the squares with 1x2 dominoes. If you think it is impossible, prove that for all even n you cannot cover the n^2 - 2 squares with 1x2 dominoes.

I will change the question to a certain n to make things less confusing. You can forget the paragraph above.

[Nate]

It is not possible...I can't mathematically prove it cause it is blatantly obvious.
1 0    1 1 1 0  1 1 1 1 1 0
0 1    1 1 1 1  1 1 1 1 1 1
        1 1 1 1  1 1 1 1 1 1
        0 1 1 1  1 1 1 1 1 1
                   1 1 1 1 1 1
                   0 1 1 1 1 1

are all clearly not possible.

[iago]

Yeah, I know it's not possible, because I remember having to prove it back in first year Discrete Math. But damned if I remember how the proof went. :)

[Nate]

I'd assume you could prove it with graph theory/connected components but its just not fun to proof.  And first year of discrete math? I only have to take one.

[iago]

Not the first year of Discrete Math. I only had to take one, but it was in my first year, which would be about 7 years ago now.

[Sidoh]

I'd assume you could prove it with graph theory/connected components but its just not fun to proof.  And first year of discrete math? I only have to take one.

Graph theory proofs are awesome!  I love proofs in general.  I talked to him at IM last night and pretty much got it, although I didn't present a rigorous solution.  The one he has in mind doesn't involve graph theory.

Anyway, Nate, this may not be your favorite subject, but you can't just say "It is because I know it is."  Even if it's intuitively obvious to you, you have to present a proof that will convince anyone who's able to understand it, otherwise you haven't done much.

[Nate]

For set N{0,1} with Arcs A{} there exists no connected components, therefore N=2 as no solution and N=(2n) is not true for all cases.

Kruskal's w/all elements of A having 0 weight proves it as well.

[Camel]

There's a fairly simple logical crutch that can be converted in to math I don't understand to prove it can't be done elegantly.

The first step is to read Nate's second post, which is true even though it isn't proof.

The second step is to assume that any solution worth looking in to requires mirroring the dominoes around the center of the cube - that is to say that for every piece you place, you place another one 180 degrees around the center of the cube from that tile.

Given this assumption, there are only two elegant ways to fill the cube: start in the center and work out - which gives you two large L shapes around the perimiter with an odd number of squares, and by starting in the center, which gives you Nate's first example.

Therefore, it's impossible to fill it elegantly :)

[Blaze]

This problem reminds me of this: http://en.wikipedia.org/wiki/Mutilated_chessboard_problem

[iago]

That's actually the exact same problem, just on a different scale. The black/white thing is pretty much the proof, anyways. :)

[Ender]

Yes, there's a fairly simple solution to this problem. And the challenge is the proof (specifically the checkerboard coloring), not the answer, as yes/no is a 50/50 after all.

Proof. Color the board black-and-white in the scheme of a checkerboard. We see WLOG that there are two more black squares than white squares. The dominoes establish a 1:1 correspondence between the white squares and the black squares, but since there is no bijection between the two sets it is impossible to cover the board with dominoes. QED.