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.
- 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.
- 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).
- 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.)
Best Answer
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).