MathDB

1

Part of 2024 CMIMC Theoretical Computer Science

Problems(1)

2024 TCS Problem 1

Source:

4/23/2024
Mellon Game Lab has come up with a concept for a new game: Square Finder. The premise is as follows. You are given an n×nn\times n grid of squares (for integer n≥2n\geq 2), each of which is either blank or has an arrow pointing up, down, left, or right. You are also given a 2×22\times 2 grid of squares that appears somewhere in this grid, possibly rotated. For example, see if you can find the following 2×22\times 2 grid inside the larger 4×44\times 4 grid.
[asy] size(2cm); defaultpen(fontsize(16pt)); string b = ""; string u = "↑\uparrow"; string d = "↓\downarrow"; string l = "←\leftarrow"; string r = "→\rightarrow"; // input should be n x n string[][] input = {{b,u},{r,l}}; int n = input.length; // draw table for (int i=0; i<=n; ++i) { draw((i,0)--(i,n)); draw((0,i)--(n,i)); } // fill table for (int i=1; i<=n; ++i) { for (int j=1; j<=n; ++j) { label(input[i-1][j-1], (j-0.5,n-i+0.5)); } } [/asy]
[asy] size(4cm); defaultpen(fontsize(16pt)); string b = ""; string u = "↑\uparrow"; string d = "↓\downarrow"; string l = "←\leftarrow"; string r = "→\rightarrow"; // input should be n x n string[][] input = {{u,b,b,r},{b,r,u,d},{d,b,u,b},{u,r,b,l}}; int n = input.length; // draw table for (int i=0; i<=n; ++i) { draw((i,0)--(i,n)); draw((0,i)--(n,i)); } // fill table for (int i=1; i<=n; ++i) { for (int j=1; j<=n; ++j) { label(input[i-1][j-1], (j-0.5,n-i+0.5)); } } [/asy]
Did you spot it? It's in the bottom left, rotated by 90∘90^\circ clockwise. To make the game as interesting as possible, Mellon Game Lab would like the grid to be as large as possible and for no 2×22\times 2 grid to appear more than once in the big grid. The grid above doesn't work, as the following 2×22\times 2 grid appears twice, once in the top left corner (rotated 90∘90^\circ counterclockwise) and once directly below it (overlapping).
[asy] size(2cm); defaultpen(fontsize(16pt)); string b = ""; string u = "↑\uparrow"; string d = "↓\downarrow"; string l = "←\leftarrow"; string r = "→\rightarrow"; // input should be n x n string[][] input = {{b,r},{d,b}}; int n = input.length; // draw table for (int i=0; i<=n; ++i) { draw((i,0)--(i,n)); draw((0,i)--(n,i)); } // fill table for (int i=1; i<=n; ++i) { for (int j=1; j<=n; ++j) { label(input[i-1][j-1], (j-0.5,n-i+0.5)); } } [/asy]
Let's call a grid that avoids such repeats a repeat-free grid. We are interested in finding out for which nn constructing an n×nn\times n repeat-free grid is possible. Here's what we know so far.
[*] Any 2×22\times 2 grid is repeat-free, as there is only one subgrid to worry about, and there can't possibly be any repeats. [*] If we can construct an n×nn\times n repeat-free grid, we can also construct a k×kk\times k repeat-free grid for any k≤nk\leq n by just taking the top left k×kk\times k of the original one we found. [*] By the previous observation, if it is impossible to construct such an n×nn\times n repeat-free grid, we cannot construct a k×kk\times k repeat-free grid for any k≥nk\geq n, as otherwise we could take the top left n×nn\times n to get one working for nn.
These three observations together tell us that either we can construct an n×nn\times n repeat-free grid for all n≥2n\geq 2, or there exists some upper limit N≥2N\geq 2 such that we can construct an n×nn\times n repeat-free grid for all n≤Nn\leq N but cannot construct one for any n>Nn> N. Your goal is to determine if such an NN exists, and if so, place bounds on its value.
More precisely, this problem consists of two parts: a lower bound and an upper bound. For the lower bound, to show that N≥nN\geq n for some nn, you need to construct an n×nn\times n repeat-free grid (you do not need to prove your construction works). For the upper bound, to show that NN is at most some value nn, you must prove that it is impossible to construct an (n+1)×(n+1)(n+1)\times (n+1) repeat-free grid.
Proposed by Connor Gordon and Eric Oh
Tcs