A classic math puzzle! - Tilted Forum Project Discussion Community

KnifeMissile · 03-17-2004, 12:16 AM

I've wanted to post this puzzle for a while now but, first, let's say down some terminology.

A chessboard is what we all think of as a chessboard except that we are not concerned with the colour of the squares and it's dimensions needn't necessarily be 8 x 8. A triominoe is a piece that consists of three chessboard squares connected together in an L shape. Finally, a chessboard is said to be defective if it is missing exactly one square.

Now, prove that every 2^n x 2^n defective chessboard can be tiled with triominoes...

passthru · 03-17-2004, 04:22 AM

I'm confused.
If n=0, the board is 1 square and a triominoe can't fit.
If n=1, the board is 2x2 and a triominoe can't fit.
If n=2, the board is 4x4 and I'm not going to visualize the triominoes on it because 4x4 is 16 spaces but triominoes that take 3 spaces can't be added together to take 16 spaces since it's not a multiple of 3.

And damnit I'm tired cause I didn't read the "defective" part. I'll assume that the question excludes the case where n=0, and take a look tomorrow.

Kadath · 03-17-2004, 05:28 AM

Well, in the case where n=0, the board is 0 squares, so...
Hmm. I'm at 4x4 and I think I found a case where you can't do it, which is clearly wrong. Assuming piece (3,2) is missing, how do you tile it with triominoes?

rsl12 · 03-17-2004, 06:59 AM

interesting question. i will have to think about that one knifemissile.

Yakk · 03-17-2004, 07:43 AM

pass, in the n=0 case, there is exactly one defective chessboard.

The empty chessboard.

Which can have all of its squares covered with triominoes: you use 0 triominoes to cover all 0 squares.

Shpoop · 03-17-2004, 09:11 AM

i know this probably isnt a sufficient proof, but (2^n)(2^n) - 1 is always divisible by 3

and kadath, here u go:
[img]http://groups.msn.com/_Secure/0SgAAAKQWfl2Jq7ic8vj!w0HN!*LKCR1J77UA7yPkM6E2xDSO2XnDGh!IZU!kAl08E2Ho3jzYK0jfJtYs*UYL4gBoVFZwHd8MFwuNpItlR*rV!W*1Q9euKg/trinome.JPG?dc=4675464204921035879[/img]

Kadath · 03-17-2004, 09:19 AM

Oh, my. I feel extraordinarily stupid now.

KnifeMissile · 03-17-2004, 10:47 AM

Thank you, so much, Shpoop! That illustration was brilliant!

rsl12 · 03-17-2004, 02:22 PM

ok, i have a proof! it's recursive, i don't know if i can explain it without diagrams.

trivial case: 2x2 should be obvious.

4x4: a 4x4 is made up of 4 2x2 squares. Let's divide it into NW, NE, SW, SE quadrants. The defective square will be in one of those quadrants, let's say in the NW, and since we've already proved that a 2x2 defective square can be tiled, the NW quadrant can be completely tiled. For the remaining 3 quadrants, pretend that the 3 tiles closest to the center of the big 4x4 square are defective. Then you can tile the each of those quadrants, since they're all defective 2x2 squares. Finally, stick the final tile right in the center, in the three tiles you pretended were defective, and you're done!

8x8: Same logic. Divide into four 4x4 quadrants. Whichever quadrant has the defective square can be tiled (as proved above). Pretent the remaining center squares are defective, tile the other three quadrants. Put the final tile in the center.

Etc etc etc. Is there a better proof?

KnifeMissile · 03-17-2004, 03:26 PM

That's pretty much it! If you wanted to formalize the proof, use mathematical induction!

I believe this is the first time anyone has ever solved one of my posted puzzles...

rsl12 · 03-17-2004, 06:59 PM

that was a great puzzle knifemissile. i kept going in the wrong direction over and over again, because it reminds me of this puzzle:

Again we have a defective chessboard that needs tiling. In this case, the defective chessboard is formed by taking a NxN square and then adding one more row of N-2 squares, centering it. This time we're actually using dominoes (2x1 dominoes). Prove that for any NxN chessboard, you can only tile it if N is even.

EDITED! made a mistake 1st time i posted. sorry about that.

rsl12 · 03-17-2004, 07:11 PM

For example: if N = 4,

___XXXX___
___XXXX___
___XXXX___
___XXXX___
____XX____

KnifeMissile · 03-17-2004, 08:19 PM

Ooh, tricky. I'll need to think about this one...

KnifeMissile · 03-19-2004, 04:42 PM

Well, as usual, I was about to type in my proof (which I thought was elegant, considering) and my boss comes by to check up on me. We have a good relationship so I show him the problem and give him my proof, but then he thinks about it... and comes up with a better proof! I can't tell you how often this has happend...

Colour the defective chessboard with a chess colouring (one of two colours, no square has the same colour as it's adjacent square). If the shape is tiled with dominoes, then there must be an equal number of black and white squares on the board. However, because the width of the chessboard is odd, two squares of the same colour have been removed. Therefore, the board cannot be tiled with dominoes.
QED

rsl12 · 03-19-2004, 09:06 PM

knifemissile, that's the proof i would give too. what was your other one?

KnifeMissile · 03-19-2004, 09:20 PM

It was a constructive proof.

Basically, the defective row forces a partition of the next row because it has a run of odd length starting from an odd column. I called this a class D row.

The next row is partitioned into two runs of odd length, both starting from even columns. Because both runs are odd length, this forces the next row to be partitioned by two dominoes. Because both runs start from even columns, the next row must have a run of odd length starting from an odd column. I called this a class P row.

As you can see, all P rows are followed by D rows, while all D rows are followed by P rows. Couple this with the fact that both rows must have, at least, one domino jutting up from them, this shows that no tiling of this shape exists...
QED

rsl12 · 03-25-2004, 11:53 AM

not sure that proof is right--it assumes that dominoes you can have only one or two 'partitions'. it proves that you can't tile it if you tile it in that particular way, but not if you put three or more partitions in a given row. glad you found the other proof though.

KnifeMissile · 03-25-2004, 10:50 PM

The proof is fine. I just gave an overview of it to give you an idea of how it worked. Typing out the whole proof with all it's rigour would have been annoying. Besides, I figured you could figure it out. I guess I'm not used to such an adversarial attitude...

For instance, it's not that you can only have one or two "partitions," it's that you are forced to have, at least, one or two partitions. The addition of extra partitions doesn't remove the properties of the first few partitions that the proof was relying on.

rsl12 · 03-26-2004, 10:28 AM

sorry, i guess i just didn't understand it fully then.

03-29-2004, 05:31 PM

thanks for making me feel dumb

cowudders14 · 04-04-2004, 04:59 AM

Must brush up on my maths...
I have a degree in Civil Engineering and was pondering those! Grr...

03-17-2004, 12:16 AM	#1 (permalink)
KnifeMissile Location: Waterloo, Ontario	A classic math puzzle! I've wanted to post this puzzle for a while now but, first, let's say down some terminology. A chessboard is what we all think of as a chessboard except that we are not concerned with the colour of the squares and it's dimensions needn't necessarily be 8 x 8. A triominoe is a piece that consists of three chessboard squares connected together in an L shape. Finally, a chessboard is said to be defective if it is missing exactly one square. Now, prove that every 2^n x 2^n defective chessboard can be tiled with triominoes...

03-17-2004, 05:28 AM	#3 (permalink)
Kadath Muffled Location: Camazotz	Well, in the case where n=0, the board is 0 squares, so... Hmm. I'm at 4x4 and I think I found a case where you can't do it, which is clearly wrong. Assuming piece (3,2) is missing, how do you tile it with triominoes? __________________ it's quiet in here

03-17-2004, 06:59 AM	#4 (permalink)
rsl12 On the lam Location: northern va	interesting question. i will have to think about that one knifemissile. __________________ oh baby oh baby, i like gravy.

03-17-2004, 07:43 AM	#5 (permalink)
Yakk Wehret Den Anfängen! Location: Ontario, Canada	pass, in the n=0 case, there is exactly one defective chessboard. The empty chessboard. Which can have all of its squares covered with triominoes: you use 0 triominoes to cover all 0 squares. __________________ Last edited by JHVH : 10-29-4004 BC at 09:00 PM. Reason: Time for a rest.

03-17-2004, 09:19 AM	#7 (permalink)
Kadath Muffled Location: Camazotz	Oh, my. I feel extraordinarily stupid now. __________________ it's quiet in here

03-17-2004, 04:22 AM	#2 (permalink)
passthru Addict Location: Portland, OR	I'm confused. If n=0, the board is 1 square and a triominoe can't fit. If n=1, the board is 2x2 and a triominoe can't fit. If n=2, the board is 4x4 and I'm not going to visualize the triominoes on it because 4x4 is 16 spaces but triominoes that take 3 spaces can't be added together to take 16 spaces since it's not a multiple of 3. And damnit I'm tired cause I didn't read the "defective" part. I'll assume that the question excludes the case where n=0, and take a look tomorrow.

03-17-2004, 09:11 AM	#6 (permalink)
Shpoop Curious Location: NJ (but just for college)	i know this probably isnt a sufficient proof, but (2^n)(2^n) - 1 is always divisible by 3 and kadath, here u go: [img]http://groups.msn.com/_Secure/0SgAAAKQWfl2Jq7ic8vj!w0HN!LKCR1J77UA7yPkM6E2xDSO2XnDGh!IZU!kAl08E2Ho3jzYK0jfJtYsUYL4gBoVFZwHd8MFwuNpItlRrV!W1Q9euKg/trinome.JPG?dc=4675464204921035879[/img]

03-17-2004, 10:47 AM	#8 (permalink)
KnifeMissile Location: Waterloo, Ontario	Thank you, so much, Shpoop! That illustration was brilliant!

03-17-2004, 02:22 PM	#9 (permalink)
rsl12 On the lam Location: northern va	ok, i have a proof! it's recursive, i don't know if i can explain it without diagrams. trivial case: 2x2 should be obvious. 4x4: a 4x4 is made up of 4 2x2 squares. Let's divide it into NW, NE, SW, SE quadrants. The defective square will be in one of those quadrants, let's say in the NW, and since we've already proved that a 2x2 defective square can be tiled, the NW quadrant can be completely tiled. For the remaining 3 quadrants, pretend that the 3 tiles closest to the center of the big 4x4 square are defective. Then you can tile the each of those quadrants, since they're all defective 2x2 squares. Finally, stick the final tile right in the center, in the three tiles you pretended were defective, and you're done! 8x8: Same logic. Divide into four 4x4 quadrants. Whichever quadrant has the defective square can be tiled (as proved above). Pretent the remaining center squares are defective, tile the other three quadrants. Put the final tile in the center. Etc etc etc. Is there a better proof? __________________ oh baby oh baby, i like gravy.

03-17-2004, 03:26 PM	#10 (permalink)
KnifeMissile Location: Waterloo, Ontario	That's pretty much it! If you wanted to formalize the proof, use mathematical induction! I believe this is the first time anyone has ever solved one of my posted puzzles...

03-17-2004, 06:59 PM	#11 (permalink)
rsl12 On the lam Location: northern va	that was a great puzzle knifemissile. i kept going in the wrong direction over and over again, because it reminds me of this puzzle: Again we have a defective chessboard that needs tiling. In this case, the defective chessboard is formed by taking a NxN square and then adding one more row of N-2 squares, centering it. This time we're actually using dominoes (2x1 dominoes). Prove that for any NxN chessboard, you can only tile it if N is even. EDITED! made a mistake 1st time i posted. sorry about that. __________________ oh baby oh baby, i like gravy. Last edited by rsl12; 03-17-2004 at 07:10 PM..

03-17-2004, 07:11 PM	#12 (permalink)
rsl12 On the lam Location: northern va	For example: if N = 4, ___XXXX___ ___XXXX___ ___XXXX___ ___XXXX___ ____XX____ __________________ oh baby oh baby, i like gravy.

03-17-2004, 08:19 PM	#13 (permalink)
KnifeMissile Location: Waterloo, Ontario	Ooh, tricky. I'll need to think about this one... Last edited by KnifeMissile; 03-17-2004 at 08:26 PM..

03-19-2004, 04:42 PM	#14 (permalink)
KnifeMissile Location: Waterloo, Ontario	Well, as usual, I was about to type in my proof (which I thought was elegant, considering) and my boss comes by to check up on me. We have a good relationship so I show him the problem and give him my proof, but then he thinks about it... and comes up with a better proof! I can't tell you how often this has happend... Colour the defective chessboard with a chess colouring (one of two colours, no square has the same colour as it's adjacent square). If the shape is tiled with dominoes, then there must be an equal number of black and white squares on the board. However, because the width of the chessboard is odd, two squares of the same colour have been removed. Therefore, the board cannot be tiled with dominoes. QED

03-19-2004, 09:06 PM	#15 (permalink)
rsl12 On the lam Location: northern va	knifemissile, that's the proof i would give too. what was your other one? __________________ oh baby oh baby, i like gravy.

03-19-2004, 09:20 PM	#16 (permalink)
KnifeMissile Location: Waterloo, Ontario	It was a constructive proof. Basically, the defective row forces a partition of the next row because it has a run of odd length starting from an odd column. I called this a class D row. The next row is partitioned into two runs of odd length, both starting from even columns. Because both runs are odd length, this forces the next row to be partitioned by two dominoes. Because both runs start from even columns, the next row must have a run of odd length starting from an odd column. I called this a class P row. As you can see, all P rows are followed by D rows, while all D rows are followed by P rows. Couple this with the fact that both rows must have, at least, one domino jutting up from them, this shows that no tiling of this shape exists... QED

03-25-2004, 11:53 AM	#17 (permalink)
rsl12 On the lam Location: northern va	not sure that proof is right--it assumes that dominoes you can have only one or two 'partitions'. it proves that you can't tile it if you tile it in that particular way, but not if you put three or more partitions in a given row. glad you found the other proof though. __________________ oh baby oh baby, i like gravy.

03-25-2004, 10:50 PM	#18 (permalink)
KnifeMissile Location: Waterloo, Ontario	The proof is fine. I just gave an overview of it to give you an idea of how it worked. Typing out the whole proof with all it's rigour would have been annoying. Besides, I figured you could figure it out. I guess I'm not used to such an adversarial attitude... For instance, it's not that you can only have one or two "partitions," it's that you are forced to have, at least, one or two partitions. The addition of extra partitions doesn't remove the properties of the first few partitions that the proof was relying on.

03-26-2004, 10:28 AM	#19 (permalink)
rsl12 On the lam Location: northern va	sorry, i guess i just didn't understand it fully then. __________________ oh baby oh baby, i like gravy.

03-29-2004, 05:31 PM	#20 (permalink)
mciprepaid Guest	thanks for making me feel dumb

04-04-2004, 04:59 AM	#21 (permalink)
cowudders14 Bringer of good Moos... Location: Midlands, UK	Must brush up on my maths... I have a degree in Civil Engineering and was pondering those! Grr... __________________ Moo! I'm mooey!