1
$\begingroup$

PLEASE NOTE! A different problem that uses the same ruleset (technically a subset of this one since i ask multiple questions here) that can be solved with brute force and pen-and-paper has been posted to puzzling.se, viewable HERE. I was unaware of the crossposting etiquette on stackexchange, my bad comrades! I have also edited the title of this question here on math.se to reflect the more math-technical nature of what I'm specifically asking the community here.

Game rules:

Click an empty grid square to place a $T1$ tile.

Line up three adjacent $T1$ tiles to create a $T2$ tile at the location of the most recently placed $T1$ tile.

Three $T2$ tiles can be aligned to create a $T3$ tile, etc.

My pal and I built a prototype out of these rules and both agree that it is not possible to create a tier 6 tile; $T5$ tiles are the highest you can make.

Consider which grid squares you click to create a $T2$ tile: there are only three clicks required, so your clicks will always form a tromino. To form a $T3$ tile (made from three $T2$ tiles, which themselves take three clicks to make), you need click at minimum 9 unique grid squares, but it's possible by clicking 5 unique grid squares: $$\;T2^1=(0,0)\;(1,0)\;(1,1);\quad T2^2=(1,0)\; (0,0)\;(0,1);\quad T2^3=(2,0)\;(1,0)\;(0,0)\quad =New\;T3\;at\;(0,0).$$ In this case the 5 unique grid squares clicked are $(0,0),\,(1,0),\,(1,1),\,(0,1),$ & $ (2,0)$, and together they form a P-shape pentomino aura around the newly created $T3$ tile (auras are defined here as the complete set of unique grid squares clicked to achieve a result). Because $T3,\,T4,\,$ and $T5$ tiles can have auras of different sizes, it becomes necessary to describe the auras as dense or loose to indicate whether they used the least amount of unique grid square clicks, the greatest, or somewhere inbetween.

What is the densest aura possible on a $T5$? The loosest? Is there some mathematical formula that can be applied to calculate the densest or loosest auras for $T4$ and $T5$ tiles ($T3$ and below are already solved)?

Important terms defined:

  • Grid square- The game is played on a grid of variable size. Grid squares are clickable.
  • $T1$ tile- When a grid square is clicked, a $T1$ tile is placed at that location.
  • $T_n$ tile- When three $T_n$ tiles are connected via touching sides (think Bejeweled, but including the L-shaped tromino as an additional valid match), a $T_{n+1}$ tile is formed at the location of the most recently placed $T_n$ tile. $T5$ is the highest tile achievable under this ruleset.
  • Aura- The shape created by counting all the unique grid squares that were used to create a given tile. $T2$ tiles always have an aura size of 3, $T3$ tiles always have an aura size of 5, 6, 7, 8 or 9. Discovering the possible aura size range for $T4$ & $T5$ tiles is the main purpose of this post!
  • Aura density- Used to describe how close to the lowest or highest bounds of its possible aura size range a given tile's aura is. A $T3$ tile with an aura of size 5 is defined as having the densest aura possible. A $T3$ tile with an aura size of 9 is defined as having the loosest aura possible.

I'm also interested in calculating the total number of possible auras for each tile, ignoring rotations, translations, and reflections.

When I set out to try and find the total amount of possible $T3$ auras, I used some techniques for defining possibility spaces I learned in a probability class:

Total amount of options in step 1 $\times$ Total amount of options in step 2 $\times$ Etc. $\ldots=$ Total number of possibilities.

  1. I figured there's 18 possible ways to create a $T2$ tile when you consider unique rotations, reflections, which tromino the aura is shaped as, and the location of the $T2$ within that tromino as important factors.
  2. Because creating that first $T2$ creates a square on the grid you can no longer click to place a $T1$, I then reasoned that there's 12 possible ways to place one of those 18 possible $T2$s such that it's adjacent to the $T2$ you already created (12 possible ways to connect the new one to a specific side of the older one, I didn't repeat for each side because of the point symmetry).
  3. You now have a domino of $T2$ tiles, you need one more to form a $T3$. In the last step I figured that there's 12 possible ways to connect to a specific side, but in the case of the domino there's 2 sides that we care about, one for each possible tromino. 24 possible ways to connect up in this step.

$$18\times12\times24=5,184$$

That's an overwhelming number (which I'm not entirely sure is correct: 2,592 and 62,208 are other numbers I came across trying to solve the same problem), and that's just for $T3$ tiles, whose min and max auras I've already solved! Because ascending to the next tile tier multiplies the amount of required clicks by 3, the mere idea of beginning to calculate the densest and loosest auras for $T4$ and $T5$ tiles is leaving me completely frozen. Please help,

EDIT: Here is a YouTube video illustrating the components of this problem and the terms I use to describe them. Hopefully this helps if you're having trouble visualizing what I'm talking about! (Note that from 1:24 - 1:38 I mistakenly refer to T3s as T2s and a T4 as a T3. This is fixed in the closed captions and marked as a revision with an asterisk, similarly to how someone might correct a spelling error.)

$\endgroup$
  • $\begingroup$ -1 It is completely unclear what the $T_k$ are, or how they are created, or what an aura is, let alone what the density of an aura is. $\endgroup$ – Servaes May 2 at 10:14
  • $\begingroup$ @Servaes I made a video to help illustrate the components of the problem and the terms I use. (Link to YouTube video.) Note that from 1:24 - 1:38 I mistakenly refer to T3s as T2s and a T4 as a T3. This is fixed in the captions and marked as a revision with an asterisk, similarly to how someone might correct a spelling error. $\endgroup$ – jodediah holems May 2 at 13:35
  • $\begingroup$ And please include definitions of the terms "densest aura" and "loosest aura" in your post. It would be much more descriptive to phrase the questions as (for example): "What is the smallest playing field on which you can create a $T_n$-tile?" $\endgroup$ – Servaes May 2 at 14:04
  • $\begingroup$ And do you consider two aura's the same if they are just rotations and/or reflections of each other? $\endgroup$ – Servaes May 2 at 14:05
  • $\begingroup$ @Servaes I added a terms defined section! I also clarified that rotations, translations, and reflections of an aura should be ignored when looking for the total amount of possible auras for a given tile tier. Hopefully you have everything you need now! :- ) $\endgroup$ – jodediah holems May 2 at 14:48
0
$\begingroup$

This is only a partial answer; I don't have the minimum and maximum for $T_5$, and I haven't attempted to count the total numbers of auras for the $T_n$. Let $\min_n$ and $\max_n$ denote the minimum and maximum number of tiles to be used in the making of a $T_n$ tile. Here are three simple observations:

Observation 1: It is impossible to make a $T_6$ tile.

This just leaves the problem of finding $\min_n$ and $\max_n$ for $n\in\{1,2,3,4,5\}$.

Observation 2: To make a $T_{n+1}$ tile with the least possible number of tiles, we need to have two adjacent $T_n$ tiles and make an adjacent $T_n$ tile. This shows that $\min_{n+1}\geq\min_n+2$.

It is not hard to verify that for $n=1,2,3,4$ this lower bound is sharp.

Observation 2: The total number of clicks required to make a $T_n$ tile is $3^{n-1}$, so $\max_n\leq3^{n-1}$.

It is again not hard to verify that for $n=1,2,3,4$ this upper bound is sharp. This yields the following values:

$$\begin{array}{r|ccccc} n&1&2&3&4&5\\ \hline \text{min}_n&1&3&5&7&?\\ \text{max}_n&1&3&9&27&? \end{array}$$

That just leaves the minimum and maximum for the $T_5$ tile; we have $\min_5\geq9$ and $\max_5\leq81$. A bit of scribbling shows that $\min_5\leq13$ and $53\leq\max_5\leq79$, and it seems likely that $\max_5$ is closer to the lower bound than the upper bound. I would advise a computer search, certainly to find the total number of auras.

$\endgroup$
  • 1
    $\begingroup$ this is thorough af and also has taught me a few intimidating math symbols that i did not previously know, thank you so much! even though it's only a partial answer, i think im going to mark this as The Answer (hopefully that isn't against some stackexchange rule), and take the question of how to write a brute force program for those t5 unknowns to stackoverflow. thanks again! your name is going in the credits of this game if it ever gets completed 😊❤️ $\endgroup$ – jodediah holems May 3 at 13:31
  • $\begingroup$ Maybe I missed something... was there a proof that $T_6$ is impossible? $\endgroup$ – antkam May 3 at 14:00
  • $\begingroup$ @antkam Not provided, as OP indicates that he has shown this himself. The idea is that to make a $T_n$ tile, a clicked square must upgrade from a $T_1$ to a $T_n$ tile by being adjacent to the appropriate tiles. As any square is adjacent to at most $4$ squares, it can upgrade at most $4$ times. $\endgroup$ – Servaes May 3 at 14:30
  • $\begingroup$ OP indicated that he and his pal both "agree" $T_6$ is impossible, but that's not a proof. :) And I don't understand your last line. After upgrading to $T_5$, all adjacent tiles are now back to clickable (which I think of as $T_0$) so that's not an a-priori argument why there is no path to $T_6$... or am I missing something obvious? $\endgroup$ – antkam May 3 at 14:35
  • 1
    $\begingroup$ Oh! you mean: the final click to form T5 must happen on a square that is surrounded by: T1, T2, T3, and T4, so that a proper "chain reaction" can occur? If that's what you mean then yes it's obvious T6 cannot be done. Sorry for wasting everyone's time! (Must finish that coffee...) $\endgroup$ – antkam May 3 at 15:21
2
$\begingroup$

UPDATE: a new solution to make $T_5$ using a grid of $\color{red}{11}$ cells (a $3 \times 4$ array minus a corner).

Lemma: If a chain of $5$ cells $C_1 C_2 C_3 C_4 C_5$ are such that $C_i$ and $C_{i+1}$ share an edge, and all $5$ cells start as empty (clickable), then it is possible to put a $T_3$ at $C_3$. After the $T_3$ is created, the other $4$ cells become empty again.

Proof: Clicking $C_3, C_2, C_1$ in that order puts $T_2$ at $C_1$. Clicking $C_4, C_3, C_2$ puts $T_2$ at $C_2$. Clicking $C_5, C_4, C_3$ puts $T_2$ at $C_3$, which then auto-upgrades to $T_3$.

This lemma turns out to be the visualization aid I need. The following diagrams successively place $T_3$ cells, including auto-upgrades to $T_4$ cells. It is easy to visually ascertain that there exists such a length-$5$ chain (e.g. marked with x) with its center being the newest $T_3$ cell (incl. auto-upgrades).

  . . x      . x .      x . .
. . . x    . . x .    x x . .
. x x 3    x x 3 3    x 4 . .

  3 x x      3 3 x      . . .
x x . .    . x x x    x 4 x x
. 4 . .    . 4 . .    x 4 . .

  x x 3      . x 3      x x .
. 4 . x    . 4 x 3    . . 5 .
. 4 . x    . 4 x x    . . x x
$\endgroup$
  • $\begingroup$ this is an awesome and understandable response to this problem, thank you! I probably should have shared this information as I discovered it (although the matrix in @Servaes 's answer covers most of this info): a t3 can be made in a minimum of 5 unique clicks, the pentomino formed by these clicks is always P-shaped, and there are three possible locations the t3 can end up in. a t4 tile can be made minimum 7 unique clicks, and there are only 2 possible ways to do that: a heptomino that looks like a middle finger, and a very similar heptomino with that lone square translated by 1 grid space. $\endgroup$ – jodediah holems May 3 at 23:02
  • $\begingroup$ continued, sorry, character limits: i too have found the 12 click solution for a t5! check out this puzzling stack exchange link and look for Kruga's answer to the problem: puzzling.stackexchange.com/questions/83557/… \\ Kruga theorizes that the minimum is between 10 and 12. What are your thoughts? Is it possible to go lower than 12? $\endgroup$ – jodediah holems May 3 at 23:05
  • $\begingroup$ you are new here so i presume you didnt know this etiquette, but it's not nice to cross-post without telling everyone involved. it wastes everyone's effort, fragments the knowledge base, etc. the usual etiquette is you post somewhere and let that community have a crack at it first, before cross-posting, and even then you clearly tell everyone involved. so pls update BOTH MAIN POSTS to point out the cross-posting. are there >2 sites involved? anyway, back to guessing: i would be very surprised if $11$ is doable, but i havent figured out an impossibility proof. will let you know if i find one. $\endgroup$ – antkam May 3 at 23:41
  • $\begingroup$ BTW, if you like my answer, it's also common practice to upvote. you can only accept (green checkmark) one answer but you can upvote any number of answers. $\endgroup$ – antkam May 3 at 23:48
  • $\begingroup$ well! i surprised myself. :) $11$ is doable after all. i would be SHOCKED if $10$ is doable, but i still have no proof... $\endgroup$ – antkam May 4 at 2:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.