By a $\emph{tile}$ we mean a polyomino (i.e. a finite edge-connected set of cells in the infinite grid). There are many ways to place a tile in the infinite table (rotation is allowed but we cannot flip the tile). We call a tile $\textbf{T}$ special if we can place a permutation of the positive integers on all cells of the infinite table in such a way that each number would be maximum between all the numbers that tile covers in at most one placement of the tile. 1. Prove that each square is a special tile. 2. Prove that each non-square rectangle is not a special tile. 3. Prove that tile $\textbf{T}$ is special if and only if it looks the same after $90^\circ$ rotation.
Problem
Source:
Tags: combinatorics, Tiling, polyomino
cadaeibf
09.08.2021 21:49
3) Assume the tile is different after $90$ degrees rotations. Consider the $2n^2$ translated by a vector $(a,b)$ with $0\leq a,b<n$ or rotated by $90$ degrees (wrt to a fixed point in the tile). For high enough $n$, the total area of the Union of these tiles is asymptotic to $n^2$. Since we have to choose $2n^2$ maxima among $\approx n^2$ tiles, it follows that some number must be the maximum of more than one translated/rotated tile. Assume the tile is rotationally symmetric. Then the following infinite table always works. In points with coordinates $(x,y)$ such that $max(x,y)=n$ place the numbers up to $(2n+1)^2$ that haven't already been put in the table. In particular start from the position $(n-1,n)$ and go in anticlockwise order. To see why this work, note that we may reduce the problem to a tile made of just of $4$ points (which may be disconnected), because a point is a point is a maximum of the entire tile only if it is the maximum of the reduced tile, and so it is sufficient to work with these. If a point is a maximum two times, this means that there must be a point $x$ and a vector $v$ such $f(x)>f(x+v)$ and $f(x)>f(x-v)$, where $f(x)$ is the number in point $x$, because of the four possible tiles that share that point, any two of them has a pair of points opposite wrt to the point. However the two inequalities can't both be satisfied. Assume wlog such a point has coordinates $x=(a,n)$ with $0\leq a\leq n$. If $v=(y,z)$ has $y\neq 0$, this means that at least one of $x+v$ and $x-v$ must land outside the square, and thus have a bigger value. If $y=0$, i.e. the two points are on the same side of the square, note that since the numbers increase on one side but decrease on the other we can't have the inequalities. The only special cases to check are $(n-1,n)$ which increases in both directions, and the four corners, for which at least one point must be outside of the square, and thus have a bigger value. Finally, since the problem is true for rotationally symmetric four squares tiles (plus the trivial single square tile) it must be true for all rotationally symmetric tiles.
quantam13
02.12.2024 16:28
Solved with NTguy
I directly show the third part which clearly establishes the first 2 parts too
For one direction, if a tile $\textbf{T}$ has rotational symmety after a $90^\circ$ rotation, then it can be checked a "spiral" works for a valid permutation
For the other direction, if $\textbf{T}$ is not invariant after a $90^\circ$ rotation, then it has atleast 2 different orientations but if we take $n\to\infty$ and consider a superpositipon of all the ways to place $\textbf{T}$ in an $n\times n$ grid, we get that there would be more than $n^2$ tiles in the super position so if we mark the maximum of every one of them, two of the maximums would collide by PHP and we would be done.
[\hide]