Kallor
Level: Master Delver
Rank Points: 277
Registered: 04-02-2007
IP: Logged

That question sounds super hard. The number of polyominoes grows exponentially fast with a base nobody knows, and in addition we should
1) rule out any shape with empty tile (orthogonally) pincered by two non-empty tiles,
2) allow diagonal adjacency.
How about just lower and upper bounds?

-Kallor

____________________________
Kallor

adS
Level: Master Delver

Rank Points: 214
Registered: 05-02-2010
IP: Logged

I have a much simpler "problem" for the non-professionals:

I played a bit with the editor to figure out which small tar blobs are cuttable.

By the way, shouldn't it be sliceable?

As all players - except complete beginners - know the smallest cuttable tar blob has 6 tiles;

6  XXX
   XXX

There are none with 7 or 8 tiles then we have 9, 10, 11, 12:

9  XXX
   XXX
   XXX

10 XXXXX
   XXXXX

11:    XXX
     XXXXX
     XXX

12:  XXXX
     XXXX
     XXXX

Now I wondered for which natural numbers n ≥ 9 there is a cuttable tar blob with n tiles.

Puzzle: Prove that there is a cuttable tar blob with n tiles for every n ≥ 9.

I propose that the professional mathematicians do not reply

adS


____________________________
pauca sed matura

brian_s
Level: Smitemaster

Rank Points: 587
Registered: 05-27-2004
IP: Logged

Prety simple proof actually. All 3xN rectangles of tar are cuttable. That takes care of 6,9,12,...

Add a 2x2 blob to the rectangle:

XXX
XXXYY
XXXYY

This takes care of 10,13,16,...

Add a 2x4 instead:

XXX
XXXYYYY
XXXYYYY

And that takes care of 14,17,20,...

Together those three families take care of all integers >=9 except for 11, which you already provided an example of.

Pinnacle
Level: Smitemaster

Rank Points: 1144
Registered: 06-10-2004
IP: Logged

1215, however, is uncuttable due to room size constraints.

EDIT: starting inside the tar may make it cuttable.

____________________________
Once (adv.): Enough.
Twice (adv.): Once too often.
~Ambrose Bierce, The Devil's Dictionary

---

[Last edited by Pinnacle at 05-26-2014 01:16 PM]

skell
Level: Legendary Smitemaster

Rank Points: 3880
Registered: 12-28-2004
IP: Logged

Which gives us a question:

Can tar be only cut on its edges, or could you cut it from inside if it was possible to make this kind of attack?

____________________________
My website

bwross
Level: Smiter
Rank Points: 376
Registered: 04-17-2005
IP: Logged

skell wrote:
Which gives us a question:

Can tar be only cut on its edges, or could you cut it from inside if it was possible to make this kind of attack?

Yes. I just finished a hold where Beethro is placed at the start of a level, surrounded by tar, and co-existing with tar in his square. He had to cut his way out, so he can cut an edge between tar and tar, just like how he can cut one between tar and air. But apparently (having just tested it again), it needs a tar/air interface on one edge of the tile cut... if that tile is surrounded by tar on the four edges, it doesn't cut.

---

[Last edited by bwross at 05-26-2014 02:17 PM]

skell
Level: Legendary Smitemaster

Rank Points: 3880
Registered: 12-28-2004
IP: Logged

Can you please link tell me which hold level and room?

____________________________
My website

bwross
Level: Smiter
Rank Points: 376
Registered: 04-17-2005
IP: Logged

skell wrote:
Can you please link tell me which hold level and room?

Chaco's hold, Level VI (the master level) entrance.

adS
Level: Master Delver

Rank Points: 214
Registered: 05-02-2010
IP: Logged

Next question:

Which numbers can occur as the number of tiles of a cuttable gel blob?

adS


____________________________
pauca sed matura

coppro
Level: Smitemaster
Rank Points: 1309
Registered: 11-24-2005
IP: Logged

adS wrote:
Erm, but for the purpose of players everything can be decided in O(1), since we have a board of constant size, right?

adS

Quiet you. Complexity theorists have no need for trivial, unenlightening, and useless observations such as this.

Nuntar
Level: Smitemaster

Rank Points: 5558
Registered: 02-20-2007
IP: Logged

adS wrote: Which numbers can occur as the number of tiles of a cuttable gel blob?

Taking the two basic shapes

 XX      XX
XXX     XXX
XX      XXX

and "chaining" them by overlapping the NE tile of one unit with the SW tile of another allows all numbers of the form 6x + 7y + 1 to occur. Since 6 and 7 have no common factors, all numbers (6 x 7) - 6 - 7 + 2 = 31 and above can be represented in this form.

These shapes

 XX       XX        XXXX
XXXX     XXX       XXXXX
XXXX     XXXXX     XXXX
 XX        XXX     XXX
           XXX     XX

contain 12, 16 and 18 tiles, and can be chained to construct shapes of 17, 23, 24 and 30 tiles. This accounts for all numbers except 1-6 and 9-11, which are clearly impossible.

____________________________
50th Skywatcher

---

[Last edited by Nuntar at 05-26-2014 04:53 PM]

adS
Level: Master Delver

Rank Points: 214
Registered: 05-02-2010
IP: Logged

Nuntar wrote:

adS wrote: Which numbers can occur as the number of tiles of a cuttable gel blob?

Taking the two basic shapes

 XX      XX
XXX     XXX
XX      XXX

and "chaining" them by overlapping the NE tile of one unit with the SW tile of another allows all numbers of the form 6x + 7y + 1 to occur. Since 6 and 7 have no common factors, all numbers (6 x 7) - 6 - 7 + 2 = 31 and above can be represented in this form.

These shapes

 XX       XX        XXXX
XXXX     XXX       XXXXX
XXXX     XXXXX     XXXX
 XX        XXX     XXX
           XXX     XX

contain 12, 16 and 18 tiles, and can be chained to construct shapes of 17, 23, 24 and 30 tiles. This accounts for all numbers except 1-6 and 9-11, which are clearly impossible.

Very nice!
My proof was a bit longer

By the way, I can't see how you want to get 17 from your patterns by chaining. Of course, there is a pattern with 17 tiles.

adS

____________________________
pauca sed matura

KevG
Level: Smiter

Rank Points: 333
Registered: 08-16-2004
IP: Logged

To get 17 chain two 12s. The z means an x and a y.:

  YY*
 ZZYY
XZZZY
XXZZ
 XX

FWIW, the * gives another way for 18.

---

[Last edited by KevG at 05-26-2014 06:57 PM]

brian_s
Level: Smitemaster

Rank Points: 587
Registered: 05-27-2004
IP: Logged

One thing about tar is that if you know it is clearable then the number of cuts needed to breakup the tar is invariant regardless of the strategy used. This is false for gel; there are gel shapes which can be cleared in different ways requiring different number of cuts.

This 23 tile gel blob has 12 enclosed corners:

   GG           X
 GGGGG        XXXX
 GGGGG        XXX
GGGGG        XXX
GGGG          X
 GG

Two completely different ways to clear it exist:

4 cuts   5 cuts
   X        X
 XXXX     XXXX
 XXX      XXX
XXX      XXX
 X        X

In this particular instance none of the cuts are the same.

adS
Level: Master Delver

Rank Points: 214
Registered: 05-02-2010
IP: Logged

KevG wrote:
To get 17 chain two 12s. The z means an x and a y.:

  YY
 ZZYY
XZZZY
XXZZ
 XX

In Nuntar's posting chaining means overlapping a single tile.

But it really doesn't matter.
The proof us very nice - using Sylvester's theorem



adS


____________________________
pauca sed matura

Syntax
Level: Smitemaster
Rank Points: 1218
Registered: 05-12-2005
IP: Logged

I'm not a theorist (yet I love theories and mathematical proofs).

The way I intuitively decide solvability with gel is to make sure that all internal + external cuttable nodes add up to an even number and that no square from which the gel is cuttable has an odd number of cuttable squares within 2 square distance

Kallor
Level: Master Delver
Rank Points: 277
Registered: 04-02-2007
IP: Logged

Sounds interesting but didn't exactly understand
At least that is a linear time algorithm so there has to exist counterexamples to your condition (or P = NP and we live in exciting times).

____________________________
Kallor

adS
Level: Master Delver

Rank Points: 214
Registered: 05-02-2010
IP: Logged

brian_s wrote:
One thing about tar is that if you know it is clearable then the number of cuts needed to breakup the tar is invariant regardless of the strategy used. This is false for gel; there are gel shapes which can be cleared in different ways requiring different number of cuts.
In this particular instance none of the cuts are the same.

adn the number of produced gel babies is different.
You have used this effect in a cleverly designed demonstration room.

adS

____________________________
pauca sed matura

Daneel
Level: Delver
Rank Points: 35
Registered: 04-12-2006
IP: Logged

Note: Gel destroyability (given appropriate access to tunnels at least) is NP-Complete. See: http://forum.caravelgames.com/viewtopic.php?TopicID=14898&page=1#179502

Kallor
Level: Master Delver
Rank Points: 277
Registered: 04-02-2007
IP: Logged

Oh I proved it earlier on this thread (reduction to 1-in-3-SAT, mimicing a proof on L-trominoes only), didn't realize it was done already

EDIT: Unfortunately I don't even understand your wire or wire-splitting. Wire crossing looks the same.

____________________________
Kallor

---

[Last edited by Kallor at 05-28-2014 07:33 AM]

Daneel
Level: Delver
Rank Points: 35
Registered: 04-12-2006
IP: Logged

Right. I guess I missed your post on that my first time through this thread.

First off, I should note that most of my thoughts about gel cutability were in terms of tracking which cells you cut rather than in terms of L-tilings of the internal squares. I kinda wonder what the dictionary between the two languages looks like.

In any case, (if I am reading my posts from 7 years ago correctly) my wire is just a 4xn block of gel. The value it carries is determined by the parity of the cells you cut along. Wire splitting was a pain. You would have a 4xn wire with another 4xn wire coming out of the side and one extra gel square at the intersection. This gave a "branch with error". In particular, the two wires along the same line had to carry the same value and the perpendicular wire carried either that value or a particular value specified by the extra gel square. From that primitive and OR predicates, it was possible to construct actual branching.

Kallor
Level: Master Delver
Rank Points: 277
Registered: 04-02-2007
IP: Logged

What an interesting idea! However, I'm not convinced.

A splits into A and A/1, meaning that if A/1 carries 0 then A must be 0. Note that even if A/1 carried 1 A could still be 0.
Now if (NOT(A/1) OR NOT(B/1)) carries 1 then A=0 or B=0. Similarly if (A/0 OR B/0) carries 1 then A=1 or B=1. Thus if both of these to wires carried 1 (an AND gate) we certainly have A=NOT(B). But if it so happens that one or both of these wires carried 0 we may deduce nothing. This is why I don't think the wire splitting of your proof works.

I also have to disagree with schep who claimed that this branhing with error is in fact an IF-THEN (->) gate (if it was you don't even need to invent your OR gate, which was amazing by the way). This is because we only have 3 possibilities (A=0 and A/1=0, A=0 and A/1=1, A=1 and A/1=1) so no matter which wire we choose as the output wire we don't get any proper gate.

By the way the reason I'm being such a huge nerd about this is not that I'm looking for errors in your proof but the fact that I genuinely find this stuff interesting even though it's not really my field (or because of it)

-Kallor

____________________________
Kallor

Daneel
Level: Delver
Rank Points: 35
Registered: 04-12-2006
IP: Logged

Fair enough. Being huge nerds is how we all got started on this conversation in the first place.

First off, my construction is probably better to think of in terms of predicates than gates. In this terminology the branch with error is an IF->THEN predicate (i.e. a configuration of inputs is valid if whenever A=1 then A/1 is also 1). [Note: my OR "gates" are also really OR predicates in that they can be filled in iff at least one of their inputs takes a 1].

The point is I build two predicates
(NOT (A/1)) OR (NOT (B/1)) and
A/0 OR B/0

The first guarantees that A=0 or B=0, the latter that A=1 or B=1. Together they imply that A = NOT B.

Kallor
Level: Master Delver
Rank Points: 277
Registered: 04-02-2007
IP: Logged

File: crossing.png (18.1 KB)
Downloaded 65 times.
License: Public Domain

Now I get it and it really works. What I did not understand is that you can force the output of
(NOT(A/1) OR NOT(B/1)) AND (A/1 OR B/1)
to be 1 by simply attaching

.........
*******..
*******..
******...  EDIT: fixed the error Daneel pointed out
******...
.........

to the end of the wire. If we now put a variable node

......
..**..
.****.
.****.
.****.
.****.
.****.

at the start of the wire B the only way to destroy the whole gel blob will be choosing B to be different than A. The whole gadget can be constructed without wire crossings (picture). Nice!

What I still don't get though is how we can interpret the wire crossing gadget as IF-THEN gate (or predicate) when it only accepts three of the totality of four inputs? In any case this is not really needed for the construction and I'm now convinced.

-Kallor

____________________________
Kallor

---

[Last edited by Kallor at 06-05-2014 10:03 AM]

Daneel
Level: Delver
Rank Points: 35
Registered: 04-12-2006
IP: Logged

I think that there still might be some confusion here. I do not have any gates in the traditional sense. In particular I do not have an OR gate. By which I mean a 3-input junction that can be completed if and only if the inputs, A,B,C satisfy C = A OR B. What I have is an OR predicate. A 4-input junction that can be completed if and only if at least one of the four inputs A,B,C or D is 1. (i.e. If A OR B OR C OR D holds). The IF-THEN makes sense in this way. It is a 3-input junction that can be properly cut if and only if its three inputs A,B, and C satisfy A=C (which is why we think of it as really only 2-input) and A => B (as in the logical A => B meaning that either A=0 or B=1).

We can also produce 2-input OR predicates by forcing some of the inputs to be 0 in a way similar to the one you mentioned. (Though I think your construction cannot actually be cut and you need to use this one instead:

.............
..***********
..***********
.************
.************
.............

)

---

[Last edited by Daneel at 06-05-2014 08:39 AM]

Kallor
Level: Master Delver
Rank Points: 277
Registered: 04-02-2007
IP: Logged

Okay I was careless when reading how the OR-thing works. Maybe I finally understand the construction:

So assuming they work, the OR-clauses require at least 1 positive input and have no outputs. They are used as end clauses when reducting the problem to 3-SAT, as well as inside the wire splitting gadgets to make them work. The NOT-gates needed (we need to be able to make end clauses of the form (A OR (NOT B) OR C) etc.) can be made from the (unfinished) wire splitting gadgets. There is no circular logic involved because the only NOT-gates in a wire splitting gadget occur as the inputs of a common OR-clause and can therefore be realized by moving the clause by 1 tile. Shifting a wire sideways can also be made with the wire splitting gadget. Crossing the wires is also dealt with.

As there was no wire turning device, the OR-clause should have all (three) inputs to the same direction (the end clauses) or all (two) inputs to the opposite directions (the auxiliary clauses inside the wire splitting device). Your example had four inputs to all four directions but that sound like a minor issue.

____________________________
Kallor

Kallor
Level: Master Delver
Rank Points: 277
Registered: 04-02-2007
IP: Logged

File: turning.png (24.4 KB)
Downloaded 85 times.
License: Public Domain

Actually your 4-directional OR-clause (assuming it works, it is quite big ) along with branching with error are of course enough to make a turning device (pictured) so there are no problems.

-Kallor

____________________________
Kallor

xitvono
Level: Delver
Rank Points: 55
Registered: 09-15-2012
IP: Logged

 XX 
XXX 
XXXX  
  XX

11 is clearly possible