Given a $32 \times 32$ table, we put a mouse (facing up) at the bottom left cell and a piece of cheese at several other cells. The mouse then starts moving. It moves forward except that when it reaches a piece of cheese, it eats a part of it, turns right, and continues moving forward. We say that a subset of cells containing cheese is good if, during this process, the mouse tastes each piece of cheese exactly once and then falls off the table. Show that: (a) No good subset consists of 888 cells. (b) There exists a good subset consisting of at least 666 cells.
Problem
Source: APMO 2021 Problem 4
Tags: combinatorics, APMO
InternetPerson10
09.06.2021 09:30
The problems are now on the site! Discussion can begin Anyway yeah I really liked this one.
What I did was show that there are at most $\dfrac{13}{16}\times 32^2$ pieces of cheese by tiling the grid into a bunch of $4 \times 4$ smaller squares, and showing that there must be at most $13$ pieces of cheese in each one. You can do this with a bunch of casework, based on the number of empty squares on the border of each grid. This gives that the number of cells with cheese is at most $\dfrac{13}{16} \times 32^2 = 832 < 888$, as desired.
The basic idea is to induct $2^i \times 2^i$ grids.
Here's a construction for a $2 \times 2$ grid; it has $3$ pieces of cheese.
[asy][asy]
size(2.5cm);
for(int i = 0; i <= 2; ++i) {
draw((i,0)--(i,2));
draw((0,i)--(2,i));
}
dot((1.5, 0.5));
dot((1.5, 1.5));
dot((0.5, 1.5));
[/asy][/asy]
Now put four copies of this grid, and orient them so that you can "recurse" on the $2^i \times 2^i$ four times; additionally, remove the bottom left square's cheese when you do this. Here are constructions for the $4 \times 4$ and $8 \times 8$ grids.
[asy][asy]
size(5cm, 0);
for(int i = 0; i <= 4; ++i) {
draw((i,0)--(i,4));
draw((0,i)--(4,i));
}
dot((1.5, 0.5));
dot((2.5, 0.5));
dot((3.5, 0.5));
dot((3.5, 1.5));
dot((3.5, 2.5));
dot((3.5, 3.5));
dot((2.5, 3.5));
dot((1.5, 3.5));
dot((0.5, 3.5));
dot((0.5, 2.5));
dot((0.5, 1.5));
[/asy][/asy]
[asy][asy]
size(5cm, 0);
for(int i = 0; i <= 8; ++i) {
draw((i,0)--(i,8));
draw((0,i)--(8,i));
}
dot((1.5, 0.5));
dot((2.5, 0.5));
dot((3.5, 0.5));
dot((3.5, 1.5));
dot((3.5, 2.5));
dot((2.5, 3.5));
dot((1.5, 3.5));
dot((0.5, 3.5));
dot((0.5, 2.5));
dot((0.5, 1.5));
dot((4.5, 2.5));
dot((4.5, 1.5));
dot((4.5, 0.5));
dot((5.5, 0.5));
dot((6.5, 0.5));
dot((7.5, 0.5));
dot((7.5, 1.5));
dot((7.5, 2.5));
dot((7.5, 3.5));
dot((6.5, 3.5));
dot((5.5, 3.5));
dot((4.5, 2.5));
dot((5.5, 4.5));
dot((6.5, 4.5));
dot((7.5, 4.5));
dot((7.5, 5.5));
dot((7.5, 6.5));
dot((7.5, 7.5));
dot((6.5, 7.5));
dot((5.5, 7.5));
dot((4.5, 7.5));
dot((4.5, 6.5));
dot((4.5, 5.5));
dot((7.5, 4.5));
dot((7.5, 4.5));
dot((7.5, 4.5));
dot((2.5, 4.5));
dot((1.5, 4.5));
dot((0.5, 4.5));
dot((0.5, 5.5));
dot((0.5, 6.5));
dot((0.5, 7.5));
dot((1.5, 7.5));
dot((2.5, 7.5));
dot((3.5, 7.5));
dot((3.5, 6.5));
dot((3.5, 5.5));
[/asy][/asy]
Then if $G(i)$ is the number of cells with cheese in this construction for a $2^i \times 2^i$ grid, we get $$G(i) = 4G(i-1) - 1$$giving
$$\begin{tabular}{c|c c c c c}
i & 1 & 2 & 3 & 4 & 5 \\ \hline
G(i) & 3 & 11 & 43 & 171 & 683
\end{tabular}$$so the number of cells with cheese is $G(5) = 683 \geq 666$, as desired. Yay!
ABCDE
09.06.2021 10:33
The bound in part (a) can be improved to $820$, corresponding to a cheese density of $\frac45$ for any rectangular grid. Suppose there are $C$ pieces of cheese. After the mouse falls off the table, have the mouse walk back to its original position along the outside of the table, following the same rules as before (only going forward and turning right allowed) so that its path back does not intersect itself. It is easy to see that its path will have $4\left\lfloor\frac{C+5}4\right\rfloor$ corners. Furthermore, all self-intersections of the mouse's path occur at a cell in the table in which there is no cheese. On the other hand, by this, the mouse's path intersects itself at least $\left\lfloor\frac{C+1}4\right\rfloor$ times. It follows that $C+\left\lfloor\frac{C+1}4\right\rfloor\le1024\implies C\le819$.
alexiaslexia
09.06.2021 10:59
It's almost over when the optimal config is found: but writing the solution's completeness takes a lot of work. $\color{green} \rule{7.8cm}{2pt}$ $\color{green} \clubsuit$ $\boxed{\textbf{Basic Definitions and Slight Removal.}}$ $\color{green} \clubsuit$ $\color{green} \rule{7.8cm}{2pt}$ Let the cheese signify a one-time use of a right turn; denote each of them to be of type $UR, RD, DL, LU$ if the mouse moves at the direction up-right, right-down and so on. Now instead of considering the $\text{path}$ of the mouse; which follows the structure \[ \text{start point} \; - C_1 - C_2 - \ldots - C_k \](big $C_i$ denoting cheese and dash representing a straight path) we will consider $\textit{Hamiltionian cycles}$. Define a $\textit{closed circuit}$ to be a series of $\textit{straightaways}$ and $\textit{turns}$ the mouse travel through, where all cheeses are part of the circuit exactly once (meaning the straightaways do not have cheese in the middle), and the start and end points are equal, and the endpoint can be put a cheese to complete the circuit (in other words, if the start direction is up, the end direction $\textbf{must}$ be right.) We close this little definition Section by the claim that
$\color{blue} \boxed{\textbf{Bijection Verification Finishing.}}$ It remains to prove that in each intersection cell, there are at most two direct shots. Note that for each matched intersection cell, for example with $C_k - C_{k+1}$ (also WLOG in the right direction), it must be the intersection of (somewhat) consecutive straightaways in the form of $C_{k-2}-C_{k-1}$ and $C_{k+1}-C_{k+2}$ if the closer cheese is $C_{k-1}$, or $C_{k-1}-C_k$ and $C_{k+2}-C_{k+3}$ if the closer cheese is $C_{k+2}$. However, if there exists $l \ne k-1,k$ so that $C_l-C_{l+1}$ so that it has the same matched cell with $C_k-C_{k+1}$, we will consider the sets of straightaways before/after $C_l-C_{l+1}$ as before. By the process in $\color{red} \spadesuit$ $\color{red} \boxed{\textbf{Proof}}$ $\color{red} \spadesuit$, we know that the segments that form the intersection cell $\{(C_{l-2},C_{l-1}), (C_{l+1},C_{l+2})\}$ and $\{(C_{k-2},C_{k-1}), (C_{k+1},C_{k+2})\}$ if $C_l-C_{l+1}$ is of the $\textbf{First Type}$, or $\{(C_{l-1},C_{l}), (C_{l+2},C_{l+3})\}$ and $\{(C_{k-2},C_{k-1}), (C_{k+1},C_{k+2})\}$ if $C_l-C_{l+1}$ is of the $\textbf{Second Type}$ are equal. This is a no-brainer --- $l$ must be either $k$ or $k-1$. So, as there exists more than $\dfrac{2}{5}x$ direct shots and fewer than $\dfrac{1}{5}x$ vacant cells (fewer intersection cells, at that), we have a contradiction. We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$
Replace the whole entire Section of $\color{red} \clubsuit$ $\color{red} \boxed{\textbf{Upper Bound}}$ $\color{red}\clubsuit$ and $\color{red} \spadesuit$ $\color{red} \boxed{\textbf{Proof}}$ $\color{red} \spadesuit$ with the following observation:
\[\begin{tabular}{p{12cm}}
$\color{red} \boxed{\textbf{Observation.}}$ No 3 consecutive straightaways may be $\color{red} \textit{direct shots.}$
\end{tabular} \\ \]Let the number of cheeses be $N$ and total cells be $M$. Now, it's easily computed that the total path length is at most $N+2(M-N) = 2M-N$ with $N-1$ total straightaways.
Dividing the straightaways into groups of three consecutive ones, we get that each group's total length is $4$ or more (by the $\color{red} \boxed{\textbf{Observation}}$) --- so we get the total length is at least $\dfrac{4}{3}$ times $N-3$; the number of segments which $\textbf{must belong to a group.}$
Putting it all together,
\[ 2M-N \geq \dfrac{4}{3} (N-3) \Rightarrow 6M-3N \geq 4N-12 \]so the total number of cheese must not exceed $\dfrac{6M+12}{7} \sim 878\dfrac{3}{7}$ (phew, still hit the mark, even if it's much scarier!)
We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$
$\color{green} \rule{25cm}{2pt}$
$\color{red} \text{Section 1: Construction.}$
From what I recall on the ideas that led me to the construction, it was to deeply analyze and eliminate bad contenders for the construction as follows:
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=1.2]
\begin{scope}[xshift=0cm,yshift=4.25cm]
\foreach \i in {0,0.5,1,1.5} \draw[blue,thick] (\i,0)--(\i,1.5); \foreach \i in {0,0.5,1,1.5} \draw[blue,thick] (0,\i)--(1.5,\i); \draw[green,thick] (0.25,0.25)--(0.25,0.75)--(1.25,0.75)--(1.25,0.25)--(0.75,0.25)--(0.75,1.25)--(1.25,1.25); \foreach \i/\j in {0.25/0.75,1.25/0.75,1.25/0.25,0.75/0.25,0.75/1.25} \draw[fill] (\i,\j) circle (0.75pt);
\end{scope}
\begin{scope}[xshift=2.5cm,yshift=4cm]
\foreach \i in {0,0.5,1,1.5,2} \draw[blue,thick] (\i,0)--(\i,2); \foreach \i in {0,0.5,1,1.5,2} \draw[blue,thick] (0,\i)--(2,\i); \draw[green,thick] (0.25,0.25)--(0.25,0.75)--(1.25,0.75)--(1.25,0.25)--(0.75,0.25)--(0.75,1.25); \foreach \i/\j in {0.25/0.75,1.25/0.75,1.25/0.25,0.75/0.25} \draw[fill] (\i,\j) circle (0.75pt);
\end{scope}
\begin{scope}[xshift=5.5cm,yshift=4cm]
\foreach \i in {0,0.5,1,1.5,2} \draw[blue,thick] (\i,0)--(\i,2); \foreach \i in {0,0.5,1,1.5,2} \draw[blue,thick] (0,\i)--(2,\i); \draw[green,thick] (0.25,0.25)--(0.25,1.25)--(1.25,1.25)--(1.25,0.75)--(0.75,0.75)--(0.75,1.75)--(1.75,1.75)--(1.75,0.25); \foreach \i/\j in {0.25/1.25,1.25/1.25,1.25/0.75,0.75/0.75,0.75/1.75,1.75/1.75} \draw[fill] (\i,\j) circle (0.75pt);
\end{scope}
\begin{scope}[xshift=2.5cm,yshift=1cm]
\draw[blue,thick] (0,0)--(2,0)--(2,2)--(0,2)--cycle;
\draw[green,thick] (0.25,0.25)--(0.25,1.75)--(1.75,1.75)--(1.75,0.25)--(0.75,0.25)--(0.75,1.25)--(1.25,1.25)--(1.25,0.75)--(1,0.75); \foreach \i/\j in {0.25/1.75,1.75/1.75,1.75/0.25,0.75/0.25,0.75/1.25,1.25/1.25,1.25/0.75} \draw[fill] (\i,\j) circle (0.75pt);
\end{scope}
\begin{scope}[xshift=5.5cm,yshift=1cm]
\draw[blue,thick] (0,0)--(2,0)--(2,2)--(0,2)--cycle;
\draw[green,thick] (0.25,0.25)--(0.25,0.75)--(1.75,0.75)--(1.75,0.25)--(1.25,0.25)--(1.25,1.75)--(1.75,1.75)--(1.75,1.25)--(0.25,1.25)--(0.25,1.75)--(0.75,1.75)--(0.75,0.25)--(0.5,0.25);
\foreach \i/\j in {0.25/0.75,1.75/0.75,1.75/0.25,1.25/0.25,1.25/1.75,1.75/1.75,1.75/1.25,0.25/1.25,0.25/1.75,0.75/1.75,0.75/0.25} \draw[fill] (\i,\j) circle (0.75pt);
\end{scope}
\begin{large}
\node[orange] at (0.75,3.5) {Fig 6.01}; \node[orange] at (3.5,3.5) {Fig 6.11}; \node[orange] at (6.5,3.5) {Fig 6.12}; \node[orange] at (3.5,0.5) {Fig 6.13}; \node[orange] at (6.5,0.5) {Fig 6.14};
\end{large}
\end{tikzpicture}");[/asy][/asy]
And here I only fixed (i.e. considered) the first two moves of going up and directly right afterwards, and finding the optimal path given that I do not change the first two.
In order, they are
$6.11$ illustrates the initial step of going up $1$ and right $2$; since there's almost no other option but to go down, left $1$ and pierce through the intersection cell by $2$ steps, this is just back to the method used for $6.01$ --- since any path through the last column will inevitably fall.
$6.12$ is similar to $6.11$ --- while the mouse can circle through the intersection cell of (row 2, column 3) instead of (row 3, column 2) from the bottom right corner, it seems plausible to let the mouse travel as far as possible.
$6.13$ is even worse, after going up $3$ times, the board essentially becomes a $3 \times 4$ board, which is very much a hindrance.
Sooner or later, $6.14$ will be found by going up only once, but turning right three times makes room for two intersections in the (row 2, column 2) and (row 2, column 3) cells.
So what can we get from this? What I immediately noticed is the curious property of $6.14$ --- how could it be almost full with four whole copies of $n = 2$ configuration, with an addition of a bridge which connects them in the middle?
Aside from that, I knew that the construction $\textbf{will not be linear}$; as the given bound is not very strong at any regards, but this is contrasted with the fact that $\textbf{almost all spaces in there is actually filled!}$ More precisely, each cell either function as a $\textit{cheese-cell}$, or $\textit{intersection-cell}$ or $\textit{starting point}$!
Notes.Note 1: I shuddered after seeing the strange P5, so seeing that my best bets are to completely annihilate a C problem to get a 7 instead of gambling in a (possibly wild and Pell-type) obscure NT FE, I returned to this with a sad but empowered feeling ...
In the terminology of $\color{red} \clubsuit$ $\color{red} \boxed{\textbf{Central Claim part a}}$ $\color{red} \clubsuit$, every vacant cell must have a path of length $2$ --- no horizontal or vertical cells are in there! So, the way to complete the $n = 4$ configuration to be perfect is to add an $\textit{auxiliary cheese}$ to the starting point and form a Hamiltonian cycle, and remove a corner with cheese for the finishing!
Long story short, after finishing all this, the idea to consider $32$ not linearly, but inductively/exponentially yielded the construction after making sure that $\textbf{all four corners}$ are filled with cheese --- making the induction seem easy and weak.
Note: Eight semi-corners are found at the junction between the (top-right corner of the top-left $n = 2^{k-1}$ config) and (top-left corner of the top-right $n = 2^{k-1}$ config); and so on.
$\color{green} \rule{25cm}{2pt}$
$\color{red} \text{Section 2: Anti-Construction, Cluster Style.}$
At first, I wanted to prove that the middle set of four cheeses are removed $\textbf{for a reason}$; what if I were to claim that no $2 \times 2$ cells are populated?
Unfortunately, claiming that the maximum cheese is $\dfrac{3}{4}$ of the $1024$ grids just don't cut it, things such as that will not work, given the $\textbf{ample extra lives we've got!}$ This is what initially derailed me to do $\#5$ first; if a large collection (i.e. more than $888- \dfrac{3}{4} \cdot 1024 = 120$) of full $2 \times 2$ grids won't cut it, then what will?
After giving up on considering one particular/special $2 \times 2$ grid, I expanded my vision from considering some middle $2 \times 2$ cluster to the area surrounding it; if we were to have a $2 \times 2$ full-cheese-populated-grid, how would the path of the mouse behave?
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.85]
\begin{scope}[xshift=0cm,yshift=0cm]
\draw[blue,thick](0,0)--(0,5)--(3,5)--(3,0)--cycle; \draw[blue,thick,dashed](0,2.5)--(3,2.5);
\draw[thick] (0.5,1.5)--(0.5,3.5)--(2.5,3.5)--(2.5,1.5)--cycle; \foreach \i/\j in {1/2,1/3,2/3,2/2} \draw[fill] (\i,\j) circle (1pt); \draw[green,thick,->](1,1)--(1,1.8); \draw[green,thick,->](1.2,2)--(1.8,2); \draw[green,thick,->](2,1.8)--(2,1);
\draw[green,thick,->](2,4)--(2,3.2); \draw[green,thick,->](1.8,3)--(1.2,3); \draw[green,thick,->](1,3.2)--(1,4);
\end{scope}
\begin{scope}[xshift=3.5cm,yshift=0cm]
\draw[blue,thick](0,0)--(0,5)--(3,5)--(3,0)--cycle; \draw[blue,thick,dashed](0,2.5)--(3,2.5); \draw[blue,thick,dashed] (1.5,2.5)--(1.5,5);
\draw[thick] (0.5,1.5)--(0.5,3.5)--(2.5,3.5)--(2.5,1.5)--cycle; \foreach \i/\j in {1/2,1/3,2/3,2/2} \draw[fill] (\i,\j) circle (1pt); \draw[green,thick,->](1,1)--(1,1.8); \draw[green,thick,->](1.2,2)--(1.8,2); \draw[green,thick,->](2,1.8)--(2,1);
\draw[green,thick,->] (2.75,3)--(2.2,3); \draw[green,thick,->] (0.8,3)--(0.25,3);
\draw[green,thick,->] (2,3.2)--(2,4); \draw[green,thick,->] (1,4)--(1,3.2);
\end{scope}
\draw[red,thick,<->] (6.8,2.1)--(6.8,2.9); \node[right,red] at (6.8,2.5) {missing};
\node at (3.25,-0.4) {Fig 7: Clusters?};
\end{tikzpicture}");[/asy][/asy]
Seeing that something like Figure 7 will form, it clearly suggests some sort of length argument; can we prove that the total length of paths in one column be $32$ or less? If so, then the $2 \times 2$ grids should be spaced out; as we are missing one path indicated in the picture!
$\color{green} \rule{25cm}{2pt}$
$\color{red} \text{Section 3: Anti-Construction, Double Counting Style.}$
This question strengthens the length-argment to be true; can a long-unending path be formed in one column? Assuming this is so, I would assume that the total path length is at most $888+ 2 \cdot (1024-888) = 1160$, which must make the cheese easy to double-count!
This Double Count also reminded me of the figure of (going right 2, down 1, left 1, up 2) since these are the densest thing in all the $n = 2^k$ configs; a lot of them naturally form by config duplication.
So, can we be sure of deriving a contradiction --- seeing that we only have $1024-888=136$ $\textit{vacant}$ (i.e. non-cheese) cells to boot, much less intersection cells to contribute (presumably) for 3-in-a-row cheeses?
By this point, I realized that I was missing the most important ingredient for this; $\textit{the Long-Unending Path Claim itself.}$ So, I conjured the Claim and proved it using (actually the double-consideration of) a particular cell; that alone took 10-15 minutes to convince myself that no cell can be a part of two horizontal straightaways.
$\color{green} \rule{25cm}{2pt}$
$\color{red} \text{Section 4: Anti-Construction, Bijection Style.}$
Now, the main drive for me to consider the final strats were to combine established ideas into one cohesive sequence:
First was to consider the actual single-length-ed straightedges instead of plain cheese was the (already mentioned) anomaly that $887$ segments (or more) supposedly has a total length of $1160$ or less; prompting around $600$ of them to be exactly of single length (as in the start of $\color{red} \text{Section 3: Double Counting Style.}$)
Another primary drive to consider the segments $\textit{near}$ to $C_i-C_{i+1}$, (i.e. $(C_{k-1}-C_k), (C_{k+1},C_{k+2})$) was the abundace of the $\textit{specific moves}$ of:
\[\begin{tabular}{p{12cm}}
down, down, left, up, right, right, right, down, left, up, up; which is a (nondisjoint) union (with one common edge) of the two sequences \\
\\
(down, down, left, up, right, $\color{red} \text{right}$) and \\
\\
($\color{red} \text{right}$, right, down, left, up, up)
\end{tabular} \\ \]An example in the config of $n = 2^3$ would be the one starting from the cell (row 3, column 6).
The idea is newly discovered here, but it somewhat relies on the construction (for inspiration) and rough ideas from $\color{red} \text{Section 2: Cluster Style}$ where small clustered things will be likely to contradict itself.
$\color{green} \rule{25cm}{0.4pt}$
This led me to consider every edge and prove that every intersection cell will be mapped to two direct shots; but not every intersection cell is the intersection of $C_a - C_{a+1}$ and $C_{a+3}-C_{a+4}$ as our ideally mapped one.
To combat that, I considered the other way, so that every direct shot will have its pair by the extremal principle, and no other direct shot other than its pair will have their intersection cell (which is uniquely identified as an intersection of two segments) shared with other direct shots.
So the counting falsifies itself and I was done; so I could move on to try $\#3$ and $\#5$.
More Notes.Note 2: Direct shots got its name from how direct the turns are; let $C_k - C_{k+1}$ be a direct shot to the right, so the segments $C_{k-1} - C_k$ and the other supporting segment will have directly met if one were to curve towards the other (and it will; there are no other directions it may curve).
Note 3: The post-contest idea to consider specifically three-in-a-row direct shots was inspired by explicitly stating the straightaways in order: they go as in $1,3,1,1,3,3,3,1,1,3,1,1,3,1,1,3, \ldots$ (and then it continues to the top-right $n = 2^{k-1}$ config.) If you look closely, large blocks of $3$s do occur, but they are rare.
Since our main idea was to consider the density of $1$s, why not consider what would happen if $1$s are located next to each other in $\textit{bundles}$? This is an easy way out (albeit with a fairly weaker bound) with no repercussions: even if the $3$s were to be changed to $2$s, the overly many lives we're getting is enough to guarantee 3 direct shots in a row.
As it turns out, shallow inspection yields the result $\textit{\textbf{directly.}}$ (pun absolutely intended)
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \blacksquare \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]
VicKmath7
09.06.2021 22:00
Great problem, I really enjoyed it. Here's my solution to a) (same approach as the official one, though I will post it). We have the following two claims: Claim 1: Each non-cheese cell is visited at most twice, one time max from each direction. Proof: Suppose FTSoC that we have visited a cell twice from the horizontal direction. Then, the second time when we come to this cell, we will have to turn once on the row of that cell, but we should have visited that cheese-cell the first time, so this cell is visited twice, absurd. Claim 2: We can't visit 4 cheese cells consecutively. Proof: Pretty obvious, if it is so, we have turned four times, so a cell from those is visited twice, absurd. Now view the path of mouse as a string of $C$ and $N$ (cheese and non-cheese) with $888$ $C$. We consider the blocks of C's. They are max $888/3=296$ (claim 2), so at least $295$ strings of $N$'s between them, and thus at least $295$ $N$'s at all. But claim 1 gives at least $148$ actual empty cells, so we calculate that the cells are too much: $888+148=1036>1024=32^2$, so a) is done.
MellowMelon
10.06.2021 00:01
The C and N model in Vick's post can be used to obtain some very good bounds for (a). I used T and S for turn and straight, so T=C and S=N. Here's a proof that there are at most 768 pieces of cheese.
Model the mouse's path as a sequence of Ts and Ss. Let the count of Ts and Ss in the string be $t$ and $s$. We have (1) $t + s/2 \leq 1024$ since each cheese is visited once and empty squares can be visited at most twice.
Notice that if the string begins or ends with a T, then $t \leq 2$. So we assume it begins and ends with S.
For each S, label it with the total number of Ts in the run right before it and the run right after it. Let the sum of the labels we put on each S be $\ell$. Because the string begins and ends with S, the sum of all the labels equals two times the number of Ts, i.e. (2) $\ell = 2t$.
The following substrings are forbidden in the mouse path: TTTT, TTSTT. This means that the only way an S gets a label of 4 or more is ...STTTSTS... or its reverse. We cannot get a label higher than four. Therefore, (3) $\ell \leq 4s$. With just (1), (2), (3), we get the 4096/5 bound that other posts have shown.
But we can do better and show that (4) $\ell \leq 3s$. The following substrings are also forbidden: TTTSTSTT, TTSTSTTT, TTSTSTST, TSTSTSTT. Take any S labelled 4. Using the previous paragraph, WLOG it is the middle S in ...STTTSTS... . The S that comes after has label at most 2, because TTTSTSTT is forbidden. Moreover, we also can't have TTTSTSTSTTT, so the labels can't be 4-2-4. This means that we can pair our S labelled 4 with the S that comes after (or before, if it's STSTTTS instead) to get two labels with average at most 3, and none of the pairs will overlap. Therefore, $\ell \leq 3s$.
Combining (1), (2), (4) gives $s \leq 512$ and $t \leq 768$.
pepat
10.06.2021 03:08
MellowMelon wrote: The C and N model in Vick's post can be used to obtain some very good bounds for (a). I used T and S for turn and straight, so T=C and S=N. Here's a proof that there are at most 768 pieces of cheese.
Model the mouse's path as a sequence of Ts and Ss. Let the count of Ts and Ss in the string be $t$ and $s$. We have (1) $t + s/2 \leq 1024$ since each cheese is visited once and empty squares can be visited at most twice.
Notice that if the string begins or ends with a T, then $t \leq 2$. So we assume it begins and ends with S.
For each S, label it with the total number of Ts in the run right before it and the run right after it. Let the sum of the labels we put on each S be $\ell$. Because the string begins and ends with S, the sum of all the labels equals two times the number of Ts, i.e. (2) $\ell = 2t$.
The following substrings are forbidden in the mouse path: TTTT, TTSTT. This means that the only way an S gets a label of 4 or more is ...STTTSTS... or its reverse. We cannot get a label higher than four. Therefore, (3) $\ell \leq 4s$. With just (1), (2), (3), we get the 4096/5 bound that other posts have shown.
But we can do better and show that (4) $\ell \leq 3s$. The following substrings are also forbidden: TTTSTSTT, TTSTSTTT, TTSTSTST, TSTSTSTT. Take any S labelled 4. Using the previous paragraph, WLOG it is the middle S in ...STTTSTS... . The S that comes after has label at most 2, because TTTSTSTT is forbidden. Moreover, we also can't have TTTSTSTSTTT, so the labels can't be 4-2-4. This means that we can pair our S labelled 4 with the S that comes after (or before, if it's STSTTTS instead) to get two labels with average at most 3, and none of the pairs will overlap. Therefore, $\ell \leq 3s$.
Combining (1), (2), (4) gives $s \leq 512$ and $t \leq 768$.
Another way to get the 768 upper bound is by showing that one can partition the string of visited cells into blocks such that, in each block, the cheese-cells make up at most 3/5 of the block's length. (One can argue that such a partitioning is possible by a casework on forbidden substrings, similar to what MellowMelon did: S is a good block, TS is good, TTSS is good, TTSTS is good, TTSTT is impossible, $\dots$) Once verified, this gives an upper bound of 3/4 on the density of cheese-cells in the table -- at least for large boards, where the little overhead due to the beginning/end is negligible. When Morteza Saghafian and I (Josef Tkadlec) came up with the problem, we thought we could push this idea (through a more annoying casework) down to density 5/9 within blocks, which would then give an upper bound of (roughly) 5/7 on the density of cheese-cells. But even if this 5/7 upper bound works out, the construction from (b) for a large $2^n\times 2^n$ board has density only (roughly) 2/3. Can anyone close the gap?
renrenthehamster
18.06.2021 11:53
This is a really fun problem! Did a video covering the solution: https://www.youtube.com/watch?v=nIQVbtch4k8
mathleticguyyy
23.06.2021 01:05
Claim: the mouse can go through each non-cheese cell at most twice.
Proof: If it goes through a non-cheese cell 3 times, two of these occasions must be in the same orientation, which implies that a piece of cheese in that orientation will have been hit twice.
Claim: the mouse can never go through four consecutive cheese cells.
Proof: It will get stuck in a loop.
Let $x$ denote the number of non-cheese cells and $y$ denote the number of cheese cells; we have that the mouse can go through at most $2x+y$ and at least $\frac{4y}{3}$ cells, giving us that $2x+y\ge\frac{4y}{3}\rightarrow x\ge\frac{y}{6}$, which means that there are at least $\frac{1024}{7}>1024-888$ empty cells.
508669
30.06.2021 08:21
InternetPerson10 wrote: Given a $32 \times 32$ table, we put a mouse (facing up) at the bottom left cell and a piece of cheese at several other cells. The mouse then starts moving. It moves forward except that when it reaches a piece of cheese, it eats a part of it, turns right, and continues moving forward. We say that a subset of cells containing cheese is good if, during this process, the mouse tastes each piece of cheese exactly once and then falls off the table. Show that: (a) No good subset consists of 888 cells. (b) There exists a good subset consisting of at least 666 cells. Part a) We call a cell 'good' if it contains a cheese block, and 'bad' otherwise. It can be seen that each bad block is visited at most twice. We define a sequence $S$ of letters $G$ and $B$ such that the letter at the $i^{\text{th}}$ position tells us whether the mouse was on a good $(G)$ or bad $(B)$ cell during the $i^{th}$ step. We observe that a block of four consecutive $C$ letters cannot occur in $S$, else, the mouse will be stuck in a cyclic loop. We see that if the maximum number of cheese blocks on the board possible is $x$, then there are at least $\frac{x}{3}$ continuous blocks of $G$ in the sequence $S$. But all these continuous $G$ blocks must be separated by blocks of $S$, which means that there must be at least $\frac{x}{3}-1$ blocks of $B$, which means that there are at least $\frac{\frac{x}{3}-1}{2}$ bad cells on the board. This means that there are at least $x + \dfrac{\frac{x}{3}-1}{2} \leq 1024$ cells on the board, which bounds $x \leq \dfrac{6147}{7} < \dfrac{6216}{7} = 888$ cells, which means that there cannot exist a good subset with $888$ cells. Although this bound is weaker than $820$ or $768$, it is quick and easy to reciprocate in exam conditions Part b) We induction on $n$ to prove: For all positive integers $n$, there exists a good subset of size $\dfrac{2^{2n+1}+1}{3}$ on the board of size $2^n$ units. Let us say that for all positive integers $k \leq n$, there exists a good subset of the aforesaid size on the board of size $2^k$. Divide the $2^{n+1}$ by $2^{n+1}$ unit dimensions square board into $4$ congruent square boards of size $2^n$ each. Then replicate the pattern similar to what Internet Person did (I cannot draw using asymptote like that ) then observe that we get a good subset on the square board of dimensions $2^{n+1}$ by $2^{n+1}$ units with size $4 \cdot \dfrac{2^{2n+1}+1}{3} - 1 = \dfrac{2^{2(n+1)+1}+4-3}{3} = \dfrac{2^{2(n+1)+1}+1}{3}$ as desired. Plugging in $n=5$ gives there exists a good subset of size $683 > 666$ on the $32$ by $32$ square board which is the desired conclusion.
mastermind.hk16
15.10.2021 04:03
Call a cell good if it contains cheese and is traversed once.
Claim 1: In every $3\times 3$ square, there are at most $8$ good cells.
Proof: If not, then all $9$ cells are good. Hence the center cell is good, but then you get an infinite cycle in one of the $2 \times 2$ sub-squares.
Claim 2: In every edge $3 \times 3$ square, there are at most $7$ good cells.
Proof: There are four $2 \times 2$ subsquares. To prevent an infinite cycle in any one of them, each of them must have $1$ bad cell. So if this is not the center cell of the $3 \times 3$ then we're done. Hence assume the center is bad. WLOG, the edge of the table is on the bottom of this $3 \times 3$ square. Since the center is bad AFSOC every other cell is good. Consider the middle bottom cell of the $3 \times 3$. Since it's good there are only two possible symmetric choices for a path going through. Assume it's any one of them. But then, the continuation of this path into the future and the past (within the $3 \times 3$) is uniquely determined. Continuing this path, you get that the mouse reaches the middle bottom cell twice. Contradiction.
So now what's left is to partition our table into $3\times 3$ squares. Partition the grid into $3 \times 3$ squares, but align the edge squares with edges of the table as much as possible. (i.e. the partition is not tight and has gaps.) Also, in the $3$ leftmost columns, skip the bottommost row, and then start the partitioning from the second bottommost row. So now our partition has $36$ edge $3 \times 3$ squares and $64$ non-edge $3 \times 3$ squares. Also, it is easy to see that the leftmost bottommost cell must be bad (if it were good then the mouse would fall off the table in at most $32$ steps.) Hence there are at least $2\times 36 +64+1 =137$ bad cells. Hence there are at most $1024-137 = 887$ good cells.
jj_ca888
30.11.2021 06:42
a) Consider a good subset with $T$ pieces of cheese. The mouse hits each piece of cheese, and it cannot hit any $4$ pieces of cheese consecutively (else it cycles infinitely), so in the mouse's path, he has to go through $\geq \tfrac{T}{3}$ non-cheese squares, not necessarily distinct. However, we do know he cannot enter a non-cheese block more than twice, else he hits some two cheese blocks in that row twice. Thus, the mouse must pass through $\geq \tfrac{T}{6}$ $\textit{distinct}$ non cheese blocks, hence\[1024 \geq T + \frac{T}{6} \implies T \leq \frac{1024 \times 6}{7} < 888\]as desired. b) bah
yu_dty5631
01.01.2023 08:50
pepat wrote: MellowMelon wrote: The C and N model in Vick's post can be used to obtain some very good bounds for (a). I used T and S for turn and straight, so T=C and S=N. Here's a proof that there are at most 768 pieces of cheese.
Model the mouse's path as a sequence of Ts and Ss. Let the count of Ts and Ss in the string be $t$ and $s$. We have (1) $t + s/2 \leq 1024$ since each cheese is visited once and empty squares can be visited at most twice.
Notice that if the string begins or ends with a T, then $t \leq 2$. So we assume it begins and ends with S.
For each S, label it with the total number of Ts in the run right before it and the run right after it. Let the sum of the labels we put on each S be $\ell$. Because the string begins and ends with S, the sum of all the labels equals two times the number of Ts, i.e. (2) $\ell = 2t$.
The following substrings are forbidden in the mouse path: TTTT, TTSTT. This means that the only way an S gets a label of 4 or more is ...STTTSTS... or its reverse. We cannot get a label higher than four. Therefore, (3) $\ell \leq 4s$. With just (1), (2), (3), we get the 4096/5 bound that other posts have shown.
But we can do better and show that (4) $\ell \leq 3s$. The following substrings are also forbidden: TTTSTSTT, TTSTSTTT, TTSTSTST, TSTSTSTT. Take any S labelled 4. Using the previous paragraph, WLOG it is the middle S in ...STTTSTS... . The S that comes after has label at most 2, because TTTSTSTT is forbidden. Moreover, we also can't have TTTSTSTSTTT, so the labels can't be 4-2-4. This means that we can pair our S labelled 4 with the S that comes after (or before, if it's STSTTTS instead) to get two labels with average at most 3, and none of the pairs will overlap. Therefore, $\ell \leq 3s$.
Combining (1), (2), (4) gives $s \leq 512$ and $t \leq 768$.
Another way to get the 768 upper bound is by showing that one can partition the string of visited cells into blocks such that, in each block, the cheese-cells make up at most 3/5 of the block's length. (One can argue that such a partitioning is possible by a casework on forbidden substrings, similar to what MellowMelon did: S is a good block, TS is good, TTSS is good, TTSTS is good, TTSTT is impossible, $\dots$) Once verified, this gives an upper bound of 3/4 on the density of cheese-cells in the table -- at least for large boards, where the little overhead due to the beginning/end is negligible. When Morteza Saghafian and I (Josef Tkadlec) came up with the problem, we thought we could push this idea (through a more annoying casework) down to density 5/9 within blocks, which would then give an upper bound of (roughly) 5/7 on the density of cheese-cells. But even if this 5/7 upper bound works out, the construction from (b) for a large $2^n\times 2^n$ board has density only (roughly) 2/3. Can anyone close the gap? I've been working on this, but I just couldn't figure out how you reached the density of 5/7. I'm actually a senior high student, can you explain it to me? Thank you~
Inconsistent
05.03.2023 19:49
For part a, note that the configuration: OOO .O. OOO Is illegal in both rotations, so each empty point we can say contributes a badness factor of $1$ to its diagonal neighbors and $\frac{1}{2}$ to its edge-adjacent neighbors, then each point in the diagram must have badness at least $1$ (edges of diagram work as well). Therefore by double counting badness, if $E$ is the number of empty points, $7E \geq 32^2$ so $E \geq \frac{1024}{7} \geq 146$ so the number of cheese is at most $878$, giving contradiction. For part b, note that we can make a fractal pattern: Take grid $A$, duplicate it four times, place them rotated, and remove an entry corner. For instance: OO .O OOOO O..O O..O .OOO OOOOOOOO O..OO..O O..OO..O OOO..OOO OOO..OOO O..OO..O O..OO..O .OOOOOOO And so on. This gives a construction with $671$ points, which is at least $666$, finishing.
IAmTheHazard
04.12.2023 02:37
Am I the only person who misinterpreted the problem as allowing the mouse to visit the same cheese cell more than once, but then only count the number of cheese cells visited once? I'm pretty sure that (surprising) part (a) is still provable under this assumption with a more convoluted version of the original proof, but it makes everything so much harder (and more time-consuming...) Bad/unclear wording really seems to be a common theme in APMO problems... unfortunate.
polishedhardwoodtable
10.03.2024 12:21
IAmTheHazard wrote: Am I the only person who misinterpreted the problem as allowing the mouse to visit the same cheese cell more than once, but then only count the number of cheese cells visited once? I'm pretty sure that (surprising) part (a) is still provable under this assumption with a more convoluted version of the original proof, but it makes everything so much harder (and more time-consuming...) Bad/unclear wording really seems to be a common theme in APMO problems... unfortunate. I just spent the last 2 days trying to solve the problem assuming that each piece of cheese disappears after the mouse eats it which makes the problem so much harder and I'm not even sure if 888 is impossible like that...