|
|
TheDeath
Responsible
Undefeatable Hero
with serious business
|
posted November 12, 2008 07:21 PM |
|
|
@Celfious: (6x2)-8+9x1 (order of operations, the blue multiplication is executed first right?)
@JollyJoker:Quote:
FOUR lines and 9 rows (3x3)
I think you meant columns right? Otherwise it makes no sense (lines is the same as row). 
____________
The above post is subject to SIRIOUSness.
No jokes were harmed during the making of this signature.
|
|
JollyJoker
Honorable
Undefeatable Hero
|
|
posted November 12, 2008 07:56 PM |
|
|
Quote:
Excellent reasoning JJ!  Ironically, while I thought my reasoning about the number 13 was rather clever, it led me down the exact wrong path. 
I fell for your clever reasoning as well. 
@ TheDeath
Lol, yes, of course, I changed that. 
|
|
Ecoris
Promising
Supreme Hero
|
|
posted November 13, 2008 11:37 AM |
|
Edited by Ecoris at 11:39, 13 Nov 2008.
|
Is it possible to cover a 6x6 board with 9 pieces of the following shape:
X
XXX
(the Tetris "L")
You may rotate and flip the pieces.
____________
|
|
JollyJoker
Honorable
Undefeatable Hero
|
|
posted November 13, 2008 12:19 PM |
|
|
Nope. I've difficulties to really prove it mathematically, though.
You'll need 9 of them Ls to cover the 6x6 area. For the 9th L you'll have either a 2x2 or a 4x1 space left. Triple shapes are possible, but these will look
XX
XX
XX
XXX
XXX
And again there is no way to fit more than two into the square. In the end this will leave 2 2x1 spaces.
How do you prove those things?
|
|
Ecoris
Promising
Supreme Hero
|
|
posted November 13, 2008 03:30 PM |
|
|
Quote:
How do you prove those things?
That's the problem. If the answer was "yes" one would just have to give an example of how to solve the puzzle; that wouldn't be difficult.
____________
|
|
Gnoll_Mage
Responsible
Supreme Hero
|
|
posted November 13, 2008 07:42 PM |
|
|
|
Asheera
Honorable
Undefeatable Hero
Elite Assassin
|
|
posted November 13, 2008 07:47 PM |
|
|
|
Gnoll_Mage
Responsible
Supreme Hero
|
|
posted November 13, 2008 08:02 PM |
|
|
Heh, sorry, I realised and tried to edit it but because JavaScript is disabled for anti-virus reasons I can't log in.
Anyway, can I have a clue on the quadrominoes? It sounds like an interesting problem. Perhaps it has something to do with dividing up the board or the set of quadrominoes, or starting by assuming that it's possible...
I also have a similar problem, can I post it at the moment?
|
|
Ecoris
Promising
Supreme Hero
|
|
posted November 13, 2008 10:08 PM |
|
|
Quote:
Anyway, can I have a clue on the quadrominoes?
Not yet. And we're only working with the L quadromino.
Quote:
I also have a similar problem, can I post it at the moment?
Certainly.
____________
|
|
dimis
Responsible
Supreme Hero
Digitally signed by FoG
|
posted November 14, 2008 05:39 AM |
|
Edited by dimis at 21:21, 14 Nov 2008.
|
My approach
Math-QP  to Ecoris for his very interesting problem on tiling. 
Ok, I have much work these days, but whenever I have a break, this problem is knocking on my "head-door". Anyway, here is my approach, which is still incomplete for the general case, but it should do for this specific case.
The general idea is to decompose the grid that you want to cover in smaller sub-grids (i.e. this forces parallelograms = boxes). These other smaller sub-grids will be called prime (or irreducible - I haven't decided yet). The idea is, just like numbers can be factored into primes, I want the grid that you give to be factored into prime tilings, where factorization here comes in terms of summing plane-surfaces.
Hence, all I need is those prime tilings and then I want to express the grid that you give as a linear combination of some of the prime tilings. Probably the orientation of the prime-tilings has to be taken into account in order to form the required equations.
For example (I haven't checked thoroughly the following, but I hope you get my idea),
X X X X
X X X X
is a prime tiling because it can not be decomposed further by Tetris-L's.
With 3 L's you can not have such a prime tiling.
With 4 L's you have 2 trivial sums of 2-prime-tilings, namely the 4x4
X X X X
X X X X
X X X X
X X X X
and the 2x8
X X X X X X X X
X X X X X X X X
but these are reducible to 2-prime-tilings, so I won't count them.
Then, you start playing Tetris on a piece of paper.
For example, you can create a parallelogram with one side = 3, with 6 L's:
X X X
X X X
X X X
X X X
X X X
X X X
X X X
X X X
and so on ...
In this case however, if you use more ( > ) than 4 Tetris-L's, you use at least 5x4=20 squares of the plane. Hence, a parallelogram with one side less than or equal to 3 requires the other one to be more than 6, and hence you can not use it anyway since the grid you want to cover is 6x6. So you only care among possible prime tilings with both sides in the range 2-6. I guess it shouldn't be difficult to show that apart from
X X X X
X X X X
and the similar (if we take orientation into account)
X X
X X
X X
X X
there are no other prime tilings with this property and the given restrictions.
And this also explains why someone ends up with 1x4 or 2x2 regions which of course can not be covered by Tetris-L's.
Of course, even if there are others, still, there are no integer solutions in the equations which they imply. I haven't said anything about those equations yet, but, ... I really have other things to do atm. For sure I'll come back to this problem. In any case though, prime tilings composed by at most 5 Tetris-L's should do the trick in our problem.
Thanks for sharing.
edit: What I didn't write down of course, is that the 6x6 is still a potential prime tiling, which reduces to your initial question; that ("prime" tilings) I had in mind to do by brute force.
Another thing is, that it is tempting to try different partitions of the plane which are not boxes (like the "primes" that I want) and then glue them together, but, allow a few unit squares in the perimeter. However, such a divide and conquer approach will eventually have to deal with placements of single Tetris-L's, and at least from high-level it doesn't seem to be different than brute-force search on L's directly.
____________
The empty set
|
|
Ecoris
Promising
Supreme Hero
|
|
posted November 15, 2008 01:48 PM |
|
Edited by Ecoris at 13:56, 15 Nov 2008.
|
@dimis
So you introduce a formalism like this:
For natural numbers m and n we consider a block with m rows and n columns. Such a block is called tilable if it can be covered by L-tiles (with no overlapping tiles), i.e. by m*n/4 tiles. If it cannot be covered it is called untilable.
If a tilable block can be "built" from two or more tilable blocks we say that the block can be decomposed. Otherwise we will call it a prime block. (I prefer to use the word block instead of tiling since being prime is a property of the board/block we wish to cover with tiles and not of a particular tiling).
As one may expect, introducing such a formalism usually does not help one solve the problem at hand; it just serves as a precise language in which we can speak of the problem. In addition it may give a better overview of the problem or perhaps it becomes possible to reformulate the problem in this language.
In this case it may be possible to rule out that a 6x6 block can be decomposed (you seem to have done that). But as you mentioned we don't know whether it is a prime block or not. It may be possible to show that if a 6x6 block is tilable it can't be prime. (That would solve the problem).
_________________________________________________
I'll pose a somewhat easier problem:
Consider an 8x8 board with two diagonally opposite corners removed. Can such a board be covered by 1x2 tiles (with no overlaps). I.e can you cover
. X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X .
with tiles of the form
X
X and XX
?
____________
|
|
Asheera
Honorable
Undefeatable Hero
Elite Assassin
|
|
posted November 15, 2008 01:53 PM |
|
|
I tried a lot of possibilities with those Ls and I always end up needing a 2x2 square.
____________
|
|
TheDeath
Responsible
Undefeatable Hero
with serious business
|
|
posted November 15, 2008 02:03 PM |
|
|
Hmm I tried a pattern that goes from the exterior to the middle and I couldn't get the core (2x2 center tile) correctly with such 1x2 tiles (I needed a diagonal).
Not sure how to do it mathematically though.
____________
The above post is subject to SIRIOUSness.
No jokes were harmed during the making of this signature.
|
|
Ecoris
Promising
Supreme Hero
|
|
posted November 15, 2008 02:20 PM |
|
|
I think the problem is a classic. I have seen it several times. I will give a hint later if no one solves it.
____________
|
|
Asheera
Honorable
Undefeatable Hero
Elite Assassin
|
|
posted November 15, 2008 02:21 PM |
|
|
Which one? The one with Ls or the last one?
____________
|
|
JollyJoker
Honorable
Undefeatable Hero
|
|
posted November 15, 2008 02:52 PM |
|
|
No you cannot.
Make the board like a chess board (with squares that are alternating black and white. A tile like XX will always cover one black and one white tile. The two diagonally opposite corners are of equal color, though, which would mean, that instead of 2*32 squares you have 30 + 32 now. After 30 b/w tiles you cannot place the last ones, since you'll keep 2 equally colored squares.
|
|
TheDeath
Responsible
Undefeatable Hero
with serious business
|
|
posted November 15, 2008 02:56 PM |
|
|
Yes that is what I thought as well
____________
The above post is subject to SIRIOUSness.
No jokes were harmed during the making of this signature.
|
|
Ecoris
Promising
Supreme Hero
|
|
posted November 15, 2008 06:05 PM |
|
|
Quote:
Which one? The one with Ls or the last one?
The last one with the chess board.
Now that you have solved that one, can you solve the one with the Ls?
____________
|
|
SwampLord
Supreme Hero
Lord of the Swamp
|
|
posted November 15, 2008 06:58 PM |
|
|
Oh math, how I despise you.
I so look forward to the day when math and I walk separate paths...I just hate this subject.
|
|
TheDeath
Responsible
Undefeatable Hero
with serious business
|
|
posted November 15, 2008 07:18 PM |
|
|
Math is cool It's about thinking for problems.
But I get what you say if you refer to school math, which mostly sucks, since it's based on memorizing formulas. 
____________
The above post is subject to SIRIOUSness.
No jokes were harmed during the making of this signature.
|
|
|
|
This thread is pages long: 
