Author Topic: nxn grid, n even  (Read 6939 times)

0 Members and 1 Guest are viewing this topic.

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2390
    • View Profile
nxn grid, n even
« on: April 12, 2008, 03:07:52 am »
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.
« Last Edit: April 12, 2008, 08:48:02 pm by Ender »

Offline Nate

  • Full Member
  • ***
  • Posts: 425
  • You all suck
    • View Profile
Re: nxn grid, n even
« Reply #1 on: April 12, 2008, 03:16:52 am »
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.

Offline iago

  • Leader
  • Administrator
  • Hero Member
  • *****
  • Posts: 17914
  • Fnord.
    • View Profile
    • SkullSecurity
Re: nxn grid, n even
« Reply #2 on: April 12, 2008, 07:02:23 pm »
Counterexample: n = 2.

:)

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2390
    • View Profile
Re: nxn grid, n even
« Reply #3 on: April 12, 2008, 08:45:23 pm »
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.
« Last Edit: April 12, 2008, 08:49:05 pm by Ender »

Offline Nate

  • Full Member
  • ***
  • Posts: 425
  • You all suck
    • View Profile
Re: nxn grid, n even
« Reply #4 on: April 13, 2008, 02:49:04 am »
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.

Offline iago

  • Leader
  • Administrator
  • Hero Member
  • *****
  • Posts: 17914
  • Fnord.
    • View Profile
    • SkullSecurity
Re: nxn grid, n even
« Reply #5 on: April 13, 2008, 09:14:21 am »
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. :)

Offline Nate

  • Full Member
  • ***
  • Posts: 425
  • You all suck
    • View Profile
Re: nxn grid, n even
« Reply #6 on: April 13, 2008, 10:18:20 am »
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.

Offline iago

  • Leader
  • Administrator
  • Hero Member
  • *****
  • Posts: 17914
  • Fnord.
    • View Profile
    • SkullSecurity
Re: nxn grid, n even
« Reply #7 on: April 13, 2008, 10:43:54 am »
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.

Offline Sidoh

  • Moderator
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: nxn grid, n even
« Reply #8 on: April 13, 2008, 12:52:02 pm »
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.

Offline Nate

  • Full Member
  • ***
  • Posts: 425
  • You all suck
    • View Profile
Re: nxn grid, n even
« Reply #9 on: April 13, 2008, 01:54:01 pm »
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.

Offline Camel

  • Hero Member
  • *****
  • Posts: 1703
    • View Profile
    • BNU Bot
Re: nxn grid, n even
« Reply #10 on: April 28, 2008, 02:54:34 pm »
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 :)

<Camel> i said what what
<Blaze> in the butt
<Camel> you want to do it in my butt?
<Blaze> in my butt
<Camel> let's do it in the butt
<Blaze> Okay!

Offline Blaze

  • x86
  • Hero Member
  • *****
  • Posts: 7136
  • Canadian
    • View Profile
    • Maide
Re: nxn grid, n even
« Reply #11 on: April 28, 2008, 03:01:04 pm »
And like a fool I believed myself, and thought I was somebody else...

Offline iago

  • Leader
  • Administrator
  • Hero Member
  • *****
  • Posts: 17914
  • Fnord.
    • View Profile
    • SkullSecurity
Re: nxn grid, n even
« Reply #12 on: April 28, 2008, 03:09:38 pm »
That's actually the exact same problem, just on a different scale. The black/white thing is pretty much the proof, anyways. :)

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2390
    • View Profile
Re: nxn grid, n even
« Reply #13 on: May 01, 2008, 04:54:33 pm »
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.