Announcement: Be excellent to each other.


Caravel Forum : Caravel Boards : General : Invariants of Tar Cutting (Or, Why Can't I Remove That Bloody Tar Blob)
Page 1 of 3
23
New Topic New Poll Post Reply
Poster Message
Watcher
Level: Smitemaster
Avatar
Rank Points: 902
Registered: 02-04-2003
IP: Logged

File: Invariants Demo.hold (1 KB)
Downloaded 161 times.
License: Other
From: Unspecified
icon Invariants of Tar Cutting (+8)  
One thing that I'm sure you will all know, is that some tar blobs cannot be removed entirely, but always leave something behind. The simplest example is of course the 2x2 tar blob, which is uncuttable, but there are other examples. One such example is any rectangular tar blob with an even number of squares along both sides. Such a blob can be reduced no further than to a 2x2 blob.

This post is intended to explain why this happens, and to provide a more general method for determining whether a tar blob can be removed entirely.

Attached is a one room hold, which I designed by using the ideas explained here. It's provided as an example of what you can use this for.

Now, I'll only consider what happens when Beethro cuts tar. In other words, I'll be looking only at tar blobs in rooms without tar mothers. Tar babies will also be ignored; if any tar babies are formed during cutting, the relevant squares of tar are simply considered to have disappeared. Also, I'll ignore the possibility of "double-stabbing" by Beethro and a mimic for now. Finally, it's possible to cut a tar blob into two separate blobs; in this case, the two new blobs will be considered part of the same blob.

Now consider the point right between four squares in DROD. I'll call such a point a corner. A corner is considered to be enclosed by tar if all the four squares next to it contain tar. Note that if there is no tar in a room, the room contains 0 enclosed corners. Also, since all tar squares must be adjacent to at least on enclosed corner (this is just a different way of stating the tar baby formation rules), there will be no tar in a room containing 0 enclosed corners.

Now suppose that a square of tar (call it X) is cuttable. This means that it is an edge square. Suppose further that the edge is on the south side of the square. This implies that the square just S of X does not contain tar. Further, the squares just W, NW, N, NE, and E of X must contain tar. The squares SW and SE of X may or may not contain tar. In any case, all this means that the SW and the SE corners of X will not be enclosed by tar, but the NW and NE corners will be. Even more important, if Beethro cuts square X, the NW and NE corners will no longer be enclosed. Further, no other corners will be affected by the cutting. (If they are enclosed, they will stay that way.) In other words, the number of enclosed corners in the blob is decreased by 2. Similar things happens if the edge of square X is on the west, north or east side.

The above can be summarised as: Whenever Beethro cuts a square of tar, the number of enclosed corners is decreased by 2. This implies that the parity of the number of enclosed corners is invariant. (For those unfamiliar with the terms: "Parity" means whether a number is even or odd. "Is invariant" is a fancy way of saying "does not change".) Since a room with no tar has 0 enclosed corners, a tar blob containing an odd number of enclosed corners cannot be removed! This is the reason that rectangular tar blobs with sides of even length cannot be removed; they contain an odd number of enclosed corners.

Now consider what happens when you checkerboard-color the corners. This means that every corner is assigned one of two colors (I'll just use black and white) in such a way that any two adjacent corners have different colors. (It's just the same as the way the floor squares in any DROD room is colored.) As was observed above, every time Beethro cuts tar, 2 corners enclosed by tar will no longer be enclosed. Now observe that the two corners must be adjacent, meaning that they will have different colors. So every time Beethro cuts tar, one black and one white corner will no longer be enclosed. This implies that the number of enclosed white corners minus the number of enclosed black corners is invariant! This number can be called the value of a tar blob. It should be noted that the number of corners enclosed by a tar blob can be reduced no further than its value (or minus its value, if the value is negative).

Now, about mimics. In most cases, it doesn't matter that Beethro and a mimic cut tar simultaneously. However, if Beethro and the mimic (or two mimics, for that matter) cut two squares of tar that share a corner, the cutting will remove 3 enclosed corners, thus changing the parity. Further, the corners removed will be either 2 white and 1 black, or 1 white and 2 black, thus changing the value as well. Therefore, neither the parity nor the value of a tar blob are invariant if a mimic is employed carefully. This is why it can be necessary to use a mimic in order to remove a tar blob.

Yeah, this was rather long, but I hope that some of you can use it for something.

____________________________
Today the refrigerator, tomorrow the world!
03-16-2004 at 08:51 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
DiMono
Level: Smitemaster
Avatar
Rank Points: 1181
Registered: 09-13-2003
IP: Logged
icon Re: Invariants of Tar Cutting (0)  
I have one question: Since Beethro moves, and then the mimic moves, how could they both cut tar in the way you suggest at the same time? Once Beethro has affected the tar, it's already been changed, and then the Mimic will interact with it as if it were Beethro on a second move.

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!
03-17-2004 at 02:44 AM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts This architect's holds Quote Reply
Schik
Level: Legendary Smitemaster
Avatar
Rank Points: 5381
Registered: 02-04-2003
IP: Logged
icon Re: Invariants of Tar Cutting (0)  
This is handled as a special case in the code, just to allow simultaneous stabbing.

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi
03-17-2004 at 02:53 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores Quote Reply
DiMono
Level: Smitemaster
Avatar
Rank Points: 1181
Registered: 09-13-2003
IP: Logged
icon Re: Invariants of Tar Cutting (0)  
Cool, you learn something new every day. Thanks for the new knowledge.

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!
03-17-2004 at 04:04 AM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts This architect's holds Quote Reply
TripleM
Level: Smitemaster
Rank Points: 1373
Registered: 02-05-2003
IP: Logged
icon Re: Invariants of Tar Cutting (0)  
Woah, thats brilliant work.. I think that may really help me with a couple of rooms in Ricky's Dungeon :D
03-17-2004 at 06:05 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
The_Red_Hawk
Level: Smitemaster
Rank Points: 783
Registered: 09-02-2003
IP: Logged
icon Re: Invariants of Tar Cutting (0)  
Yeah, this is an amazing breakthrough! It'll come in really helpful when (if) we get Black Gates!

____________________________
Slashing, whirling, diving, twirling,
Snapping, turning, rising, swirling,
Screeching, flipping, gliding, sliding,
The red hawk's dance of death.

.....the king of the skies.....
03-17-2004 at 05:19 PM
View Profile Send Private Message to User Send Email to User Show all user's posts This architect's holds Quote Reply
TripleM
Level: Smitemaster
Rank Points: 1373
Registered: 02-05-2003
IP: Logged
icon Re: Invariants of Tar Cutting (0)  
Any chance you can post the logic of working out your example room? That might make it a bit clearer how you're meant to exactly solve a room like that.
03-18-2004 at 07:43 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
Watcher
Level: Smitemaster
Avatar
Rank Points: 902
Registered: 02-04-2003
IP: Logged

File: Demo Explanation.JPG (28.4 KB)
Downloaded 306 times.
License: Other
From: Unspecified
icon Re: Invariants of Tar Cutting (+2)  
TripleM wrote:
Any chance you can post the logic of working out your example room? That might make it a bit clearer how you're meant to exactly solve a room like that.

Sure thing. Take a look at the attached picture, which shows part of the room. All the corners enclosed by the tar blob have been marked with dots. If you count them, you'll find that the blob has a value of 4, meaning that there are 4 extra white corners. Therefore, whatever you do, there must be 4 enclosed white corners left on the platform. Obviously, these corners cannot be adjacent to a trapdoor square, since the 2x2 tar blob would block off this square. On the other platform, I've marked the 4 white corners that are not adjacent to any trapdoor square. You need to leave 2x2 tar blobs around those corners, and no others. I've also marked off the 6 black corners that are not adjacent to any trapdoor square. These are red herrings, as leaving a 2x2 tar blob around them will force you to keep an extra white corner enclosed.

____________________________
Today the refrigerator, tomorrow the world!
03-18-2004 at 04:31 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
masonjason
Level: Smiter
Avatar
Rank Points: 349
Registered: 12-29-2003
IP: Logged
icon Re: Invariants of Tar Cutting (+4)  
This approach can also be used to solve a little problem I've been wondering about for a while: that is, how many tar babies can be made from an m * n rectangle of tar?
The number of tar babies made is obviously
a - b - c,
where a = area of the rectangle = mn,
b = number of cuts you need to make,
c = area of any uncuttable tar left over at the end.
In a rectangle of dimensions m * n, there are (m - 1)(n - 1) enclosed corners. Every time you make a cut in the tar, exactly two enclosed corners are freed, but tar is only converted completely into tar babies when there are no enclosed corners left. Thus, the number of cuts you need to make is equal to half the number of enclosed corners, i.e. b = (1/2)(m - 1)(n - 1). This is an integer as long as not both of m and n are even. I will consider the case where m and n are both even shortly. There will be no uncuttable tar left, so c = 0 and a - b - c = mn - (1/2)(m - 1)(n - 1).
However, if m and n are both even, then the number of enclosed corners is odd and there will be one enclosed corner that cannot be cut. In other words, the number of cuts that can be made is b = (1/2)((m - 1)(n - 1) - 1). Also, there will be 4 uncuttable tar squares left, so c = 4. So in this case, the number of tar babies = a - b - c = mn - (1/2)((m - 1)(n - 1) - 1) - 4.
In summary, the number of tar babies that can be created from a rectangle of tar of dimensions m * n is
mn - (1/2)((m - 1)(n - 1) - 1) - 4 (m and n both even)
mn - (1/2)(m - 1)(n - 1) (otherwise).




____________________________
Eighty people came to the bazaar.
03-29-2004 at 07:46 PM
View Profile Send Private Message to User Visit Homepage Show all user's posts This architect's holds Quote Reply
Drizzo
Level: Master Delver
Avatar
Rank Points: 179
Registered: 03-03-2004
IP: Logged
icon Re: Invariants of Tar Cutting (0)  
Interesting... I wonder how easy it would be to figure out how many you can keep alive as you carve this block of tar up... an interesting puzzle where you need to make ALL the tar babies possible from a block of tar survive, in order to kill a snake or something... hmmm... Although I guess with the proper room features they all could live, but I'm picturing a room where Beethro has to be constantly one step ahead of these tar babies as he carefully eliminates this tar block, as opposed to one where he can just put them in storage somewhere...

____________________________
"Disbelief in magic can force a poor soul into believing in government
and business." - Tom Robbins
03-29-2004 at 08:54 PM
View Profile Send Private Message to User Visit Homepage Show all user's posts Quote Reply
swann_88
Level: Delver
Avatar
Rank Points: 87
Registered: 06-29-2003
IP: Logged
icon Re: Invariants of Tar Cutting (0)  
maybe I am missing something
does this cover the case where beethro stabs the middle of a row of 3? xyx y is stabbed both x become tarbabies
03-31-2004 at 01:51 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
masonjason
Level: Smiter
Avatar
Rank Points: 349
Registered: 12-29-2003
IP: Logged
icon Re: Invariants of Tar Cutting (+1)  
swann_88 wrote:
maybe I am missing something
does this cover the case where beethro stabs the middle of a row of 3? xyx y is stabbed both x become tarbabies
Yes, it does, but a row of 3 tar squares cannot exist on its own. Apply the formula to a 3 * 1 rectangle and you get
3 * 1 - 1/2(2 * 0) = 3
and 3 tar babies is what a 3 * 1 rectangle of tar basically is.

____________________________
Eighty people came to the bazaar.
03-31-2004 at 07:52 PM
View Profile Send Private Message to User Visit Homepage Show all user's posts This architect's holds Quote Reply
Watcher
Level: Smitemaster
Avatar
Rank Points: 902
Registered: 02-04-2003
IP: Logged
icon Re: Invariants of Tar Cutting (+1)  
Very nice work, masonjason. :thumbsup Just one quick comment:

masonjason wrote:
In summary, the number of tar babies that can be created from a rectangle of tar of dimensions m * n is
mn - (1/2)((m - 1)(n - 1) - 1) - 4 (m and n both even)
mn - (1/2)(m - 1)(n - 1) (otherwise).

These two formulas can be simplified to
((m + 1)(n + 1) - 9)/2 (m and n both even)
((m + 1)(n + 1) - 2)/2 (otherwise)

____________________________
Today the refrigerator, tomorrow the world!
03-31-2004 at 08:45 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
masonjason
Level: Smiter
Avatar
Rank Points: 349
Registered: 12-29-2003
IP: Logged
icon Re: Invariants of Tar Cutting (0)  
Cool, I didn't bother to check whether they could be simplified. Thanks.

____________________________
Eighty people came to the bazaar.
03-31-2004 at 08:48 PM
View Profile Send Private Message to User Visit Homepage Show all user's posts This architect's holds Quote Reply
silver
Level: Smitemaster
Rank Points: 915
Registered: 01-18-2005
IP: Logged
icon Re: Invariants of Tar Cutting (+3)  
bit of a thread necromancy here, but:

I find sometimes with big chunks of randomly shaped tar, it's hard to compute the parity. so I wrote the little script I've attached. it's perl, so it should run for linux and mac osX people for free, and windows people if they have cygwin or ActiveState perl or similar.

edit: removed attachment, see my next reply.

(only secreted because it's long):
Click here to view the secret text



____________________________
:yinyang

[Last edited by silver at 09-16-2006 07:05 AM]
09-15-2006 at 02:24 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
Tahnan
Level: Smitemaster
Avatar
Rank Points: 2459
Registered: 11-14-2005
IP: Logged
icon Re: Invariants of Tar Cutting (0)  
Wow. And to think I just go into the editor, select a test hold of my own, and recreate the tar there. :-)
09-15-2006 at 04:47 PM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
silver
Level: Smitemaster
Rank Points: 915
Registered: 01-18-2005
IP: Logged

File: tar_check.pl (7.5 KB)
Downloaded 39 times.
License: Public Domain
icon Re: Invariants of Tar Cutting (+2)  
this is a more full-featured version. it detects tar clusters and removes impossible tar, and it computes the 'tar number' as it relates to solubility.

my computation of "tar number" is probably a little off from the description above, as I just sum the coordinates and call evens "white" and odds "black", and always do white-black as number. which means a blob with a tar number of 2 will have a tar number of -2 if you shift it left or right. but other than white/black being fixed outside of the tar, it's pretty much the same thing. Especially in that for this program, my only real concern is that the tar number is 0 - due to the demonstration in the first post that every tar cut removes one white and one black.

(only secreted because it's long):
Click here to view the secret text



____________________________
:yinyang

[Last edited by silver at 09-16-2006 09:38 PM]
09-16-2006 at 06:36 AM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
adS
Level: Master Delver
Avatar
Rank Points: 214
Registered: 05-02-2010
IP: Logged
icon Re: Invariants of Tar Cutting (+3)  
Basically to figure out if a tar blob is cuttable or not is the same as deciding if an "blob" of unit squares may be tiled with 1x2 dominoes.

There is a very interesting application of homotopy theory and combinatorial group theory.
It is easy to decide if a simply connected region consisting of unit squares in Z^2 is cuttable (may be tiled with dominoes) or not:

Link

Caution: Don't read unless you are a mathematician.

adS

Edit: Of course, the set of enclosed corners must be tileable by dominoes.

____________________________
pauca sed matura

[Last edited by adS at 05-14-2014 10:37 PM]
05-14-2014 at 08:54 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
Kargaros
Level: Delver
Rank Points: 58
Registered: 04-06-2010
IP: Logged
icon Re: Invariants of Tar Cutting (+1)  
adS wrote:
Link
Caution: Don't read unless you are a mathematician.
As a homotopical group theorist, I thank you highly for posting that link.
I now find myself thinking about domino-tiling/tar-cutting when I should be preparing a talk for next week. :P

____________________________
95th Skywatcher
05-14-2014 at 11:19 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts High Scores Quote Reply
adS
Level: Master Delver
Avatar
Rank Points: 214
Registered: 05-02-2010
IP: Logged
icon Re: Invariants of Tar Cutting (0)  
You should also have a look at this.

adS

____________________________
pauca sed matura
05-15-2014 at 09:39 AM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
Watcher
Level: Smitemaster
Avatar
Rank Points: 902
Registered: 02-04-2003
IP: Logged
icon Re: Invariants of Tar Cutting (+1)  
adS wrote:
There is a very interesting application of homotopy theory and combinatorial group theory.
It is easy to decide if a simply connected region consisting of unit squares in Z^2 is cuttable (may be tiled with dominoes) or not:

Link

Hm, interesting. So the approach here is to regard the underlying grid as the Cayley graph of a group, which you can then write as F/R where F is a free group and R is a subgroup generated by some relations. Then a path along the edges in the grid can be regarded as an element of F, and it is a loop if and only if it is contained in R. In the case of a square grid, F is generated by two elements a and b, and R is generated by the element aba^(-1)b^(-1) and all its conjugates.

Given a set of tiles, you can then define a subgroup T of R by letting T be generated by the boundaries of your tiles (and their conjugates in F). Then for any region that can actually be tiled by your set, its boundary must lie in T. In the case of dominoes, you have two essentially different generators in T: a^2ba^(-2)b^(-1) for the horizontal dominoes, and ab^2a^(-1)b^(-2) for the vertical ones. I fiddled with the groups for a bit, and found that R/T is then an infinite cyclic group, generated by the element aba^(-1)b^(-1). So we can think of it as the group of integers, Z. With a bit more work, I found out that for any closed bounded region in the plane, the image of its boundary in R/T is actually the difference between the number of white squares and the number of black squares in the region. So that gets you back the value invariant I described in the first post.

I'm rather intrigued by the algorithm for constructing a domino tiling, provided that one exists. In effect, it seems to iteratively pick out spots where you can put down a domino, but I don't really understand why it can't lead you into a dead end.

____________________________
Today the refrigerator, tomorrow the world!
05-16-2014 at 10:18 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
TripleM
Level: Smitemaster
Rank Points: 1373
Registered: 02-05-2003
IP: Logged
icon Re: Invariants of Tar Cutting (+1)  
I don't have access to that article, but a maximum-bipartite-matching approach is one method of construction.

Namely, start from any unmatched square and perform any depth/breadth first search. Move to any adjacent square; if already part of a domino, move to other half of the domino. When you reach another unmatched square (and you will always be able to, given it is tileable), the whole path you've travelled along can be tiled with dominoes, replacing any already there. You've now added one more domino. Repeat.
05-16-2014 at 11:53 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
Kargaros
Level: Delver
Rank Points: 58
Registered: 04-06-2010
IP: Logged
icon Re: Invariants of Tar Cutting (+2)  
I believe I have convinced myself:
First of all, Thurston's method only works for simply-connected/contracible regions, i.e. regions without interior "holes".

If we have a region R that we try to tile, then we make a directed graph on the edges in R where the edges around a black square is oriented counter-clockwise and the edges around white squares are oriented clockwise.
For the vertices v and w of the graph, we then have a distance function d(v,w) measuring the distance from v to w following the direction of the oriented edges.
The goal of Thurston's algorithm is then to construct a height function on all vertices/corners in R such that h(w) - h(v) <= d(v,w) for all vertex pairs v and w. (Note: The inequality sign in Thurston's paper is wrong at this spot.)

The height function is fixed (up to a constant) on the boundary of R by the requirement that it can only increase or decrease by 1 at each step. This corresponds to the fact that each edge on the boundary has to be a boundary edge of a domino. That the total change of height around the boundary is zero, is equivalent to the number of white and black squares being equal, as Watcher pointed out.
The additional claim is that the requirement h(w) - h(v) <= d(v,w) for v,w on the boundary is equivalent to the existence of a domino-tiling of R. The inequality has to be true if there is a domino-tiling of R.
Thurston then extends the function h to the interior vertices of R step by step along the oriented edges. If ever the height increases by more than 1 along an edge, the inequality h(w) - h(v) <= d(v,w) fails, and by tracing a path back to the boundary of R, the inequality must have failed already for the boundary vertices! (This is the critical point of why the algorithm doesn't break down.)

Once h has been extended to all vertices of R, it must satisfy h(w) - h(v) <= d(v,w) for all v,w in R, since otherwise the algorithm would have found an edge with an increase of more than 1. (Not entirely obvious but true.)
Applied to each square of R, h(w) - h(v) <= d(v,w) implies that each oriented edge either changes h by 1 or -3. Furthermore, each square has exactly 1 edge where the change is -3. Hence if we then delete the edges with -3, we have a tiling of R with dominoes.

The secret lies in the inequality h(w) - h(v) <= d(v,w) (which Thurston sadly wrote with >= instead of <=).

____________________________
95th Skywatcher

[Last edited by Kargaros at 05-17-2014 12:14 AM]
05-17-2014 at 12:10 AM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts High Scores Quote Reply
adS
Level: Master Delver
Avatar
Rank Points: 214
Registered: 05-02-2010
IP: Logged
icon Re: Invariants of Tar Cutting (+1)  
Regarding the non-simply connected case see here.

adS

____________________________
pauca sed matura
05-17-2014 at 03:04 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
coppro
Level: Smitemaster
Rank Points: 1308
Registered: 11-24-2005
IP: Logged
icon Re: Invariants of Tar Cutting (0)  
But the real question is: can we analyze gel?
05-17-2014 at 04:10 PM
View Profile Show all user's posts Quote Reply
adS
Level: Master Delver
Avatar
Rank Points: 214
Registered: 05-02-2010
IP: Logged
icon Re: Invariants of Tar Cutting (+1)  
coppro wrote:
But the real question is: can we analyze gel?

Well, somebody would have to analyze the tilings with


  X          X
  XX   and  X


adS

____________________________
pauca sed matura
05-17-2014 at 04:15 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
Pinnacle
Level: Smitemaster
Avatar
Rank Points: 1126
Registered: 06-10-2004
IP: Logged
icon Re: Invariants of Tar Cutting (+1)  
Does gel actually reduce to L-tromino tiling on the enclosed corners? From a bit of experimentation, it looks like it does, and we know that Golomb's proof applies to gel. The most basic cuttable tar shape fits a single domino, and the most basic cuttable gel shape fits a single L-tromino.

____________________________
Once (adv.): Enough.
Twice (adv.): Once too often.
~Ambrose Bierce, The Devil's Dictionary
05-17-2014 at 04:37 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
The spitemaster
Level: Smiter
Rank Points: 354
Registered: 06-09-2005
IP: Logged
icon Re: Invariants of Tar Cutting (+1)  
The problem is that the shape of gel is non-trivial. For instance:

__XXX
__XXX
XXXXX
XXXXX
XXXXX


While this shape can be completely destroyed, it is impossible to cut without outside assistance.

____________________________
Last night upon a stair
I met a man that wasn't there
He wasn't there again today
I wish that man would stay away

[Last edited by The spitemaster at 05-17-2014 05:00 PM]
05-17-2014 at 05:00 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts This architect's holds Quote Reply
tempestadept
Level: Master Delver
Rank Points: 141
Registered: 12-23-2010
IP: Logged
icon Re: Invariants of Tar Cutting (0)  
Pinnacle wrote:
Does gel actually reduce to L-tromino tiling on the enclosed corners? From a bit of experimentation, it looks like it does, and we know that Golomb's proof applies to gel. The most basic cuttable tar shape fits a single domino, and the most basic cuttable gel shape fits a single L-tromino.
Tiling itself tells nothing about reachability of cutting points. E.g. 2x3 rectangle is a union of two L-triominoes, but that doesn't correspond to a cutting sequence.
05-17-2014 at 05:21 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
Kargaros
Level: Delver
Rank Points: 58
Registered: 04-06-2010
IP: Logged
icon Re: Invariants of Tar Cutting (+1)  
Asking whether a Gel blob is removable, is more than just a tiling problem for L-shapes -- even when ignoring the Gel babies that form.

The following Gel blob
XXXX
XXXX
XXXX
has enclosed corners forming the shape
XXX
XXX
This shape can be tiled by two L's, but the original blob cannot be cut at all. The problem is that each L-shape is only cuttable at the interior corner, and in the given configuration the interior corner for each L is unreachable.

Tar does not have the same problem, because the domino shape is cuttable from both sides. Hence we are always able to cut at least one exterior domino.

Edit: Ahh, beat to it :)

____________________________
95th Skywatcher

[Last edited by Kargaros at 05-17-2014 05:28 PM]
05-17-2014 at 05:27 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts High Scores Quote Reply
Page 1 of 3
23
New Topic New Poll Post Reply
Caravel Forum : Caravel Boards : General : Invariants of Tar Cutting (Or, Why Can't I Remove That Bloody Tar Blob)
Surf To:


Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us | CaravelGames.com

Powered by: tForum tForumHacks Edition b0.98.8
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.