Turbo's en route to visit each cell of the board

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Turbo's en route to visit each cell of the board

G H J

Reveal topic tags

turbo the snail

L

G H BBookmark kLocked kLocked NReply

Source: EGMO 2025 P5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

267 posts

#1 h Apr 14, 2025, 11:01 AM • 8 Y

Y by farhad.fritl, TeodorVonBurg, radian_51, dangerousliri, Gato_combinatorio, qlip, mathleticguyyy, ehuseyinyigit

Let $n > 1$ be an integer. In a configuration of an $n \times n$ board, each of the $n^2$ cells contains an arrow, either pointing up, down, left, or right. Given a starting configuration, Turbo the snail starts in one of the cells of the board and travels from cell to cell. In each move, Turbo moves one square unit in the direction indicated by the arrow in her cell (possibly leaving the board). After each move, the arrows in all of the cells rotate $90^{\circ}$ counterclockwise. We call a cell good if, starting from that cell, Turbo visits each cell of the board exactly once, without leaving the board, and returns to her initial cell at the end. Determine, in terms of $n$ , the maximum number of good cells over all possible starting configurations.

Proposed by Melek Güngör, Turkey

This post has been edited 1 time. Last edited by Lukaluce, Apr 14, 2025, 11:54 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

559 posts

#2 h Apr 14, 2025, 11:04 AM • 5 Y

Y by GuvercinciHoca, CT17, radian_51, Gato_combinatorio, qlip

Great problem!

(Should have been IMO P5 instead...)

This post has been edited 1 time. Last edited by BR1F1SZ, Apr 14, 2025, 11:08 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

122 posts

#3 h Apr 14, 2025, 11:37 AM • 35 Y

Y by bin_sherlo, egxa, Assassino9931, Lukaluce, NicoN9, Sadigly, BR1F1SZ, alexanderhamilton124, MuradSafarli, Rg230403, farhad.fritl, vangelis, AlperenINAN, MS_asdfgzxcvb, giangtruong13, AnSoLiN, aidan0626, EpicBird08, Sedro, Euclid9876, hakN, TeodorVonBurg, Fibonacci_11235, Steff9, agwwtl03, solidgreen, radian_51, mariairam, SatisfiedMagma, khina, poirasss, X.Allaberdiyev, zaidova, Yiyj1, ehuseyinyigit

Proposed by Melek Güngör, Turkey (my problem

). Hope you all like it!!! It is the first problem in EGMO which proposed by Turkey since 2015 p2.

This post has been edited 1 time. Last edited by GuvercinciHoca, Apr 14, 2025, 11:38 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7346 posts

DottedCaculator

#4 h Apr 14, 2025, 12:35 PM • 1 Y

Y by radian_51

If $n$ is odd, no cells can be good because there is no cycle visiting every cell once.

If $n$ is even, we claim the answer is $\frac{n^2}4$ . Each good cell has a corresponding cycle on the grid. Note that if a cell is good, then every fourth cell on that cycle is also good because it traces the same cycle. Thus, $\frac{n^2}4$ is easy to construct by taking one cycle. Now, we show two distinct cycles are impossible. Consider the moment Turbo reaches the top left corner. There are two possible next moves: right and down, so there are at most two possible cycles. If both cycles are possible, then they approach the corner in opposite directions. Then, considering the approach from the bottom, the corner must have the following configuration, up to rotation:
D(L/U)
U

Considering the approach from the right, the corner must have the following configuration, up to rotation:
LL
(U/L)

These are contradictory.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

708 posts

#5 h Apr 14, 2025, 1:11 PM • 1 Y

Y by radian_51

This proof is not detailed, kind of a sketch.
First notice that if $n$ is odd, then there is no such route which can be seen by chessboard colouring. Let's show that the maximum is $\frac{n^2}{4}$ for even $n'$ s.
Lower Bound: Pick any cyclic route, we see that if a square is good, the square reached after $4$ moves from that square must be also good. Thus, we get $\frac{n^2}{4}$ good squares.
Upper Bound: Let's start by presenting a lemma.

Lemma: Let $(i,j)$ be the square in $i.$ row $j.$ column and $A(i,j)$ be the arrow in that square. If there is a route passing through $A(1,2),A(1,1),A(2,1)$ in this order, then $A(1,2)=A(1,1)$ .
Proof. Working on $4$ cases give the result.

Suppose that two distinct cyclic routes exist. If these two routes are passing through $A(1,2),A(1,1),A(2,1)$ and $A(2,1),A(1,1),A(1,2)$ then $A(1,2)=A(1,1)=A(2,1)$ . However the route starting from $A(2,1)$ cannot exist in this case.
These routes must go in the same direction. WLOG let both of them follow the route as $A(1,2),A(1,1),A(2,1)$ . We have $A(1,2)=A(1,1)$ . But this implies that these route are the same. We get a contradiction as desired. $\blacksquare$

This post has been edited 1 time. Last edited by bin_sherlo, Apr 14, 2025, 1:12 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

64 posts

#6 h Apr 14, 2025, 1:44 PM • 2 Y

Y by GuvercinciHoca, radian_51

If $n$ is odd, then color the board in chessboard manner, then there are more black square than white square, vice versa. That is no cycle exists.
Hence, consider even positive integer $n$ .
We claim that the answer is $\frac{n^2}{4}$ .
The construction is to construct a board with arrows forming cycles, then pick a square to start and then reverse the rotation to satisfy the condition.
Since, in every $4$ moves, the arrows return to its initial orientation, there are $\frac{n^2}{4}$ squares to start with. That is $\frac{n^2}{4}$ good cells.

Now, we are left to show that no board with more than $\frac{n^2}{4}$ good cells exists.
Suppose there exist some board with more good cells than $\frac{n^2}{4}$ . Since, each cycle can gives us at most $\frac{n^2}{4}$ good cells, there exist another cycles in such squares. Call these $2$ cycle, $C_1$ and $C_2$ . Suppose the good cells from cycles $C_1$ and $C_2$ are in squares of the same colors. Note that if at least one arrows when it is in the same orientation in both cycles, then the rest of the arrows in both cycles are same. For any arrow $A$ , let $f(A)$ denote the number of moves done when the arrow $A$ is used in modulo $4$ . Also, for any arrow $A$ in cycle $C_1$ in square $S$ at some moment, denote $-A$ as an arrow in $C_2$ in square $S$ in the exact same moment.
Hence, note that $f(A) \neq f(-A)$ and since both cycle have good cells of the same colors, we have $2 \mid f(A) - f(-A)$ Hence, $| f(A) - f(-A)| = 2$ That is $-A$ is the reflection of $A$ . So, we run into contradiction, since the squares in the corner will point out of the grids.
Hence, good cells in $C_1$ and $C_2$ are different colors. This mean $2 \nmid f(A) - f(-A)$ .
In this case, there are no edge $E$ such that Turbo travel through $E$ in both cycles $C_1$ and $C_2$ (By parity arguments of arrows). Hence, contradiction since, the corner square have only $2$ edges, which is inevitably used as edges to get in and get out of the squares. Hence, we are done. $\blacksquare$

This post has been edited 1 time. Last edited by EeEeRUT, Apr 14, 2025, 1:45 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

17 posts

AleMM

#7 h Apr 14, 2025, 2:02 PM • 3 Y

Y by GuvercinciHoca, XAN4, radian_51

Notice that if $n$ is odd, we can color the board in a checkerboard pattern to get that no cycles visiting every cell once can exist (just by looking at a raw path, without rotating cells).

If $n$ is even, we can get at least $\dfrac{n^2}{4}$ good cells, just construct a simple cycle and go through it rotating the $t^{\text{th}}$ cell you walk through (supposing the good starting cell is $t=0$ ) $t$ times clockwise, so it can be in the desired direction when you get there. Thus we force a cycle to exist and a cell to be good, the key observation is that every fourth cell on that cycle is good as well, because we're ceasing to rotate it by a multiple of 4 (and since 4 rotations get you back to the initial state, we can just consider everything modulo 4), thus getting the desired $\dfrac{n^2}{4}$ good cells $\ \square$

Now, let's prove that the only good cells are each fourth cell of a fixed cycle, so the number of good cells is at most $\dfrac{n^2}{4}$ . Suppose there exist a good cell, otherwise it would be 0, and look at the cycle $\mathcal{C}$ that it would form starting on that cell. Label the cells accordingly to the cycle by walking through it starting on 0 from the good cell (all the way up to $n^2-1$ ), so if we pick a cell labeled $k$ , we saw that if $k\equiv 0 \pmod{4}$ , the cycle would preserve and that cell would also be good. Now, let's take a cell $k\not\equiv 0 \pmod{4}$ , if at some point we arrive in a cell pointing to the same direction as in $\mathcal{C}$ , we know that we're going to go to the same next cell as in $\mathcal{C}$ and the rotation will be the same (since for it to happen we need to be in the same time $t$ modulo 4 as in the original walk) and we can extend this reasoning to show that the entire cycle would have to be equal to $\mathcal{C}$ , but since $k\not\equiv 0 \pmod{4}$ we have that the cell labeled $k$ will have arrows pointing to different directions, contradiction (because it wouldn't be the same exact cycle)! But then, look at the top right corner. Draw the arrows according to the final path of $\mathcal{C}$ and of $\mathcal{P}$ (the sencond cycle we're assuming to exist), we know that they don't match in any arrow, so the top right corner wouldn't as well. So, by looking at the top right most arrow, we know that they would have to be different, but there are only two possible options (otherwise Turbo would leave the board):

WLOG the $\color{green} \mathcal{C}$ path:

$[asy] usepackage("mathdots"); size(2cm, 2cm); int rows = 3; int cols = 3; pen gridPen = black + 0.5bp; // Draw the grid for (int i = 0; i <= rows; ++i) { draw((0, i)--(cols, i), gridPen); } for (int j = 0; j <= cols; ++j) { draw((j, 0)--(j, rows), gridPen); } label("A", (1.5, 2.5), green); label("B", (1.5, 1.5), green); label("C", (2.5, 1.5), green); label("$\downarrow$", (2.5, 2.5), green); label("$\cdots$", (0.5, 2.5)); label("$\iddots$", (0.5, 0.7)); label("$\vdots$", (2.5, 0.7)); [/asy]$

The $\color{red} \mathcal{P}$ path:

$[asy] usepackage("mathdots"); size(2cm, 2cm); int rows = 3; int cols = 3; pen gridPen = black + 0.5bp; // Draw the grid for (int i = 0; i <= rows; ++i) { draw((0, i)--(cols, i), gridPen); } for (int j = 0; j <= cols; ++j) { draw((j, 0)--(j, rows), gridPen); } label("X", (1.5, 2.5), red); label("Y", (1.5, 1.5), red); label("Z", (2.5, 1.5), red); label("$\leftarrow$", (2.5, 2.5), red); label("$\cdots$", (0.5, 2.5)); label("$\iddots$", (0.5, 0.7)); label("$\vdots$", (2.5, 0.7)); [/asy]$

Now notice that $\color{green} A$ has to be $\color{green} \rightarrow$ (because Turbo has to visit the $\color{green} \downarrow$ ), but from $\color{green} A$ to $\color{green} \downarrow$ , it has rotated only once counterclockwise, so before Turbo leaving $\color{green} A$ it should be:

$[asy] usepackage("mathdots"); size(2cm, 2cm); int rows = 3; int cols = 3; pen gridPen = black + 0.5bp; fill((1, 2)--(2, 2)--(2, 3)--(1, 3)--cycle, palegrey+opacity(0.5)); // Draw the grid for (int i = 0; i <= rows; ++i) { draw((0, i)--(cols, i), gridPen); } for (int j = 0; j <= cols; ++j) { draw((j, 0)--(j, rows), gridPen); } label("$\rightarrow$", (1.5, 2.5), green); label("B", (1.5, 1.5), green); label("C", (2.5, 1.5), green); label("$\leftarrow$", (2.5, 2.5), green); label("$\cdots$", (0.5, 2.5)); label("$\iddots$", (0.5, 0.7)); label("$\vdots$", (2.5, 0.7)); [/asy]$

So $\color{green} A$ and $\color{green} \downarrow$ have to be a $180^{\circ}$ rotation apart from each other, which means that so do $\color{red} X$ and $\color{red} \leftarrow$ . But from $\color{red} \leftarrow$ we go to $\color{red} X$ (so we rotate counterclockwise once to get to $\color{red} X$ ), which means that when we're on $\color{red} \leftarrow$ , the $\color{red} \mathcal{P}$ looks like:

$[asy] usepackage("mathdots"); size(2cm, 2cm); int rows = 3; int cols = 3; pen gridPen = black + 0.5bp; fill((2, 2)--(3, 2)--(3, 3)--(2, 3)--cycle, palegrey+opacity(0.5)); // Draw the grid for (int i = 0; i <= rows; ++i) { draw((0, i)--(cols, i), gridPen); } for (int j = 0; j <= cols; ++j) { draw((j, 0)--(j, rows), gridPen); } label("$\rightarrow$", (1.5, 2.5), red); label("Y", (1.5, 1.5), red); label("Z", (2.5, 1.5), red); label("$\leftarrow$", (2.5, 2.5), red); label("$\cdots$", (0.5, 2.5)); label("$\iddots$", (0.5, 0.7)); label("$\vdots$", (2.5, 0.7)); [/asy]$

So then, after we arrive at $\color{red} X$ , there should be a $90^{\circ}$ rotation counterclockwise, so on the final $\color{red} \mathcal{P}$ path it will be:

$[asy] usepackage("mathdots"); size(2cm, 2cm); int rows = 3; int cols = 3; pen gridPen = black + 0.5bp; // Draw the grid for (int i = 0; i <= rows; ++i) { draw((0, i)--(cols, i), gridPen); } for (int j = 0; j <= cols; ++j) { draw((j, 0)--(j, rows), gridPen); } label("$\uparrow$", (1.5, 2.5), red); label("Y", (1.5, 1.5), red); label("Z", (2.5, 1.5), red); label("$\leftarrow$", (2.5, 2.5), red); label("$\cdots$", (0.5, 2.5)); label("$\iddots$", (0.5, 0.7)); label("$\vdots$", (2.5, 0.7)); [/asy]$

So Turbo would leave the board in one of the two cycles if there were to exist two of them, so there has to be at most one cycle $\ \square$

This post has been edited 1 time. Last edited by AleMM, Apr 14, 2025, 2:21 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1529 posts

#8 h Apr 14, 2025, 3:49 PM • 1 Y

Y by radian_51

For odd $n$ , this is evidently impossible regardless of turning.

For even $n$ , we claim the answer is $\frac{n^2}{4}$ , which can be obtained by taking any Hamiltonian path and rotating squares in it so every fourth square in the path works.

Now, we prove this is optimal. Fix this Hamiltonian path $\mathcal{P}$ which is created by some good cell $c$ and index it so that the good squares are $0 \pmod{4}$ . Suppose some non $0 \pmod{4}$ cell $c'$ worked. Note that if $c'$ ever ends up in the same cell $c$ does at the same parity, then it traces the rest of $c$ 's path, which gives a contradiction as it implies the paths are the same.

Thus, if we consider the top left corner, the path that $g$ takes and the path $c'$ take must be flipped. We can check this is always impossible.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

559 posts

#9 h Apr 14, 2025, 3:56 PM • 2 Y

Y by GuvercinciHoca, radian_51

GuvercinciHoca wrote:

Proposed by Melek Güngör, Turkey (my problem

). Hope you all like it!!! It is the first problem in EGMO which proposed by Turkey since 2015 p2.

Congrats!

My answer

This post has been edited 2 times. Last edited by BR1F1SZ, Apr 14, 2025, 4:03 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

446 posts

#10 h Apr 14, 2025, 4:45 PM

Y by

solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2 posts

#11 h Apr 14, 2025, 5:35 PM • 6 Y

Y by Davud29_09, farhad.fritl, Yunis019, ChessFM, Ismayil_Orucov, turann

Lukaluce wrote:

Let $n > 1$ be an integer. In a configuration of an $n \times n$ board, each of the $n^2$ cells contains an arrow, either pointing up, down, left, or right. Given a starting configuration, Turbo the snail starts in one of the cells of the board and travels from cell to cell. In each move, Turbo moves one square unit in the direction indicated by the arrow in her cell (possibly leaving the board). After each move, the arrows in all of the cells rotate $90^{\circ}$ counterclockwise. We call a cell good if, starting from that cell, Turbo visits each cell of the board exactly once, without leaving the board, and returns to her initial cell at the end. Determine, in terms of $n$ , the maximum number of good cells over all possible starting configurations.

Proposed by Melek Güngör, Turkey

Türkiye

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

20 posts

#12 h Apr 14, 2025, 5:40 PM • 10 Y

Y by TeodorVonBurg, farhad.fritl, Yunis019, ChessFM, Ismayil_Orucov, Frd_19_Hsnzde, Nuran2010, MuradSafarli, Omerking, Sadigly

Lukaluce wrote:

Let $n > 1$ be an integer. In a configuration of an $n \times n$ board, each of the $n^2$ cells contains an arrow, either pointing up, down, left, or right. Given a starting configuration, Turbo the snail starts in one of the cells of the board and travels from cell to cell. In each move, Turbo moves one square unit in the direction indicated by the arrow in her cell (possibly leaving the board). After each move, the arrows in all of the cells rotate $90^{\circ}$ counterclockwise. We call a cell good if, starting from that cell, Turbo visits each cell of the board exactly once, without leaving the board, and returns to her initial cell at the end. Determine, in terms of $n$ , the maximum number of good cells over all possible starting configurations.

Proposed by Melek Güngör, Turkey

Türkiye

This post has been edited 1 time. Last edited by Davud29_09, Apr 14, 2025, 5:40 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1893 posts

#13 h Apr 14, 2025, 6:54 PM • 1 Y

Y by radian_51

The answer is $0$ for $n$ odd and $\frac{n^2}{4}$ for $n$ even. $n$ odd is obvious and $n$ even construction is just taking your favorite Hamiltonian cycle then rotating arrows along the path accordingly.

For $n$ even bound, the important idea is that something on the border, if it is pointing perpendicularly to that border when Turbo arrives, must be pointing away from the border. Thus corners get two of these constraints. So if two good cells have the same checkerboard parity, they'll run into a corner at the same configuration, so they must be part of the same cycle. If they have opposite checkerboard parity, local analysis on a corner will work (done on paper, way too lazy to type up here). $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1501 posts

#14 h Apr 15, 2025, 4:26 AM • 1 Y

Y by radian_51

Trivially for $n$ odd there is no cycle by parity therefore we will only consider $n$ even.
For $n$ even we claim the answer is $\frac{n^2}{4}$ , the construction is fairly simple, just oick a cool Hamiltonian cycle and assing the arrows acordingly, then here we can see from a starting point the next 4 steps will also serve as a starting point and so on which by counting gives what we wanted.
Now to prove there won't be more cells satisfying that if we start the cycle is completed after the whole process is finished, we suppose FTSOC one that is not 4-step with one of the $\frac{n^2}{4}$ chosen cells, if it reincorporated back into the cycle in some way, it would've skipped the next cell on the cycle so when it goes back it will go through this cell a second time before hitting it, thus reaching a contradiction.
So now the other alternative is that this new starting point develops a 2nd cycle with the same arrow setup, so suppose it did exist, then consider whenever it reaches a corner of the board, say top-left then in from directional checking we can see from whatever direction it came from, the cell before reaching the corner itself shares the same arrow direction, clearly this should imply that both cycles have the same entrance to the corner as else we would have these 3 cells with the same arrow direction and that just wouldn't work because both cycles are suppose to show two different ways to enter but due to the arrow equality there's only one that can be chosen. And to finish if they did have the same entrance direction there is 4 cells we are guaranteed to enter either way so this shows in fact both of the cycles were the same one this whole time which is a contradiction!, thus we are done :cool:

:cool:

.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

14 posts

#15 h Apr 15, 2025, 2:10 PM • 1 Y

Y by GuvercinciHoca

Cute problem! Congratulations to the proposer!

Define "walkable cycle" as a sequence of cells $c_1-c_2-\dots-c_{n^2}-c_1$ for which $c_i$ and $c_{i+1}$ are adjacent, $\forall 1\leq i \leq n^2$ (indices taken modulo $n^2$ ) and in which each cell besides $c_1$ appears exactly once. Easily, by coloring the board like a chessboard, we may see that for odd $n$ there is no walkable cycle, so we will only consider the case where $n$ is even. If $n=2k, k \in \mathbb{N}$ , we will prove the answer is $k^2$ .

Proof of bound: Fix a good cell, denote it $c_1$ and then label the other cells $c_2, c_3, \dots c_{4k^2}$ , such that $c_i$ is the $i$ -th cell in the walkable cycle starting and ending in $c_1$ . Suppose FTSoC that there could be more than $k^2$ good cells.
Claim: The cells $c_5, c_9 \dots c_{4k^2-3}$ are good.
Proof: Notice that, after $4$ moves, the arrangement of arrows on the board is the same as the initial arrangement of arrows. This initial arrangement of arrows was designed in such a way that $c_1-c_2-\dots-c_{4k^2}-c_1$ is a walkable cycle, if Turbo is initially on $c_1$ . So, by periodicity modulo $4$ the claim is proved. $\square$
If there are more than $k^2$ good cells, we may pick $c_i$ a good cell such that $i$ isn't $1$ (mod $4$ ).

We now look at the top left corner of the board. Turbo can either enter it from the right and leave it to go in the cell under it at the next move, in which case the arrow in the top left corner and the one next to it should be pointing "west" when Turbo moves to the top left corner, or she can enter it from below and leave it to go in the cell next to it at the next move, in which case the arrow under the top left corner should be pointing "north" and the arrow in the top left corner should be pointing "south" when Turbo moves to the top left corner.
If the placements of these two arrows are different when we walk the cycles from $c_i$ and $c_1$ we have a contradiction, because the way these two arrows point at eachother is invariant with respect to rotation. But, because $i$ isn't $1$ (mod $4$ ), these two arrows will be in different orientation than the ones in the walkable path starting in $c_1$ , therefore we either exit the board or never arrive in the top left corner, contradiction.

An example is easy to find, by just considering a cycle and arranging the arrows modulo $4$ accordingly, therefore the proof is complete. $\blacksquare$

This post has been edited 2 times. Last edited by ravengsd, Apr 16, 2025, 11:59 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

103 posts

#16 h Apr 15, 2025, 5:28 PM • 2 Y

Y by farhad.fritl, GuvercinciHoca

GuvercinciHoca wrote:

Proposed by Melek Güngör, Turkey (my problem

). Hope you all like it!!! It is the first problem in EGMO which proposed by Turkey since 2015 p2.

Congrats, you fulfilled the dream of most IMO 2024 contestants by making the answer depend on n (you wrote that the IMO 2024 P5 was the biggest disappointment, so you came up with this??). Cute problem, and more interesting than IMO 2024 P5!
My solution similar to #7, so I won’t post it.

This post has been edited 3 times. Last edited by X.Allaberdiyev, Apr 15, 2025, 5:38 PM
Reason: .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1252 posts

#17 h Apr 16, 2025, 1:13 AM

Y by

Turbo again made a show and coordinations finished at around 2 AM! The reason for prolonging is that there were thorough verifications for whether a student's argument really uses that the table has even length sides or works a bit by luck here, but not for a $(2i+1) \times (4j+2)$ table where some intermediate conclusions could be false - if the latter, then the solution was treated as incomplete. Moreover, 6 points were not attainable unless the only error in the solution is for the very easy case of $n$ being odd.

This post has been edited 2 times. Last edited by Assassino9931, Apr 16, 2025, 1:19 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Gato_combinatorio

15 posts

Gato_combinatorio

#18 h Apr 16, 2025, 3:30 AM

Y by

Turbo the snail is back!!!

We'll work all numbers in subscripts at mod 4.
By chess coloring we can notice that the answer for $n$ odd is 0.
Now, let's see $n$ even: $n=2k$ .
Let's call arrows to the arrows defined in the problem.
If Turbo makes his way to complete a cycle $Q$ on the board, then that's a directed graph, so let's call the edges "Q-arrows" (not normal arrows).
The board has 4 states of the normal arrows, let's call them $S_0, S_1, S_2, S_3$ , where $S_0$ is the initial state.
We write a number $Q_x$ in the cell $c$ if Turbo can start in the cell $c$ at the state $S_x$ to complete the $Q$ cycle.
Note that if $c_1 \rightarrow c_2$ then $Q_x$ being written on $c_1$ implies $c_2$ has $Q_{x+1}$ written in it $...(\alpha)$

We can draw any cycle $Q$ containing all the cells.
Then Turbo can start in the corner and we can help him to complete the cycle by adding arrows as it's convenient to get $Q$ .
By $(\alpha)$ , one of each four cells has a $Q_0$ written in it, so we get an example with exactly $k^2$ good cells.

If it were possible to get more good cells than that, we would need another cycle $P$ .
Note that the sets of Q-arrows and P-arrows are disjoint because otherwise the cycles would be constructed equally.
By chess coloring and $(\alpha)$ we can notice that for some $w$ : $Q_w$ and $Q_{w+2}$ are written on exactly $k^2$ black cells each one,
and $Q_{w+1}$ and $Q_{w+3}$ are written on exactly $k^2$ white cells each one. Same thing happens with $P$ .
The Q-arrow and P-arrow that come out from the corner are differentiated by an odd number of rotations.
So $w$ has different parity in $Q$ and $P$ : for every cell $c$ , the difference between the P-arrow and the Q-arrow that come out from $c$ is an odd number of rotations.
So, if $c$ is in the left column of the board, either the P-arrow or the Q-arrow will be a right arrow.
By the Pigeonhole Principle, either exactly one between $P$ or $Q$ will have at least $k$ right (P or Q)-arrows leaving the left column.
This is only possible when exactly $k$ are coming out of the left column and exactly $k$ are coming into the left column and they intercalate.
So same thing will happen with P and Q there (intercaling so that they don't coincide right P-arrows with Q-arrows)
We can apply the same logic in the four sides of the board but the P-arrows will not coincide in the corners, contradiction

So the maximum possible for $n=2k$ is $k^2$ . Sorry for the long solution :oops:

:oops:

This post has been edited 1 time. Last edited by Gato_combinatorio, Apr 16, 2025, 3:38 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

478 posts

#20 h Apr 18, 2025, 12:25 PM • 2 Y

Y by alexanderhamilton124, SilverBlaze_SY

Solved with SilverBlaze_SY.

We solve for $n$ odd first.

$n$ is odd: Color the board in chessboard pattern. Then note that if Turbo is able to travel via all the cells of the board and return back to the initial cell, then it must have traversed $n^2$ many cells. Note that each time it moves from one cell to another, the color of the cell alternates.

But as Turbo is supposed to end at the initial cell, the number of color changes is supposed to be even, whereas $n^2$ is clearly odd. This implies that there are no good cells for an odd $n$ .
$n$ is even: We focus on the cell in the bottom-right corner. Note that Turbo can enter the bottom-right corner either from the cell to its left, or from the cell above it.

Note that if Turbo enters the cell from its left, then the configuration of the cells while Turbo is on the cell adjacent to the corner cell should be as shown in the diagram in order to ensure that Turbo does not get kicked out of the board.

Again, if Turbo enters from the cell above, the configuration should be as shown below.

Now note that these two configurations are not interchangeable by rotation of arrows because the relative direction of the arrows always stays the same. For the first case, the arrows in the cells along the bottom edge are in the same direction whereas in the second case, they are not.

So depending upon the initial configuration of the board, Turbo can enter the bottom-right cell only from one of its adjacent cells.

WLOG assume Turbo enters the bottom-right corner from its left. Denote the cell to the left of the bottom-right corner as $P$ . Then note that when Turbo is on $P$ then the arrow of this cell must be pointing towards the right.

Now note that if $G$ is a good cell, after going through the entire board along its arrows, Turbo comes back to $G$ . Then while going through the path, when Turbo lands on $P$ it points towards right. Following this path starting from $P$ , we return to the cell where we started from. Then again from this cell, we can go to $P$ .

This means that $P$ is a good cell. Now note that after every fourth move, the entire board returns to its original configuration. Consider the path that is formed when we start from $P$ . This means that every fourth cell on the path starting from $P$ is good.

Now we show that none of the other cells are going to be good. FTSOC assume one of them is good which is not at a distance of $\equiv 0\pmod 4$ from $P$ along the path.

Call this cell $Q$ . Then as we start from $Q$ , we must pass through $P$ at some point. Now we show that there is only one path from $Q$ to $P$ . In order to show this, call the path from $Q$ back to itself via the cells as $\ell_1$ . Also, call the path from $P$ back to itself as $\ell_2$ . While Turbo goes through the path $\ell_1$ , note that at some point it must land on $P$ . From this point on, the paths $\ell_1$ and $\ell_2$ become identical as in both cases, the arrow in $P$ points towards the right when Turbo reaches $P$ . Now after Turbo completes one trip around the entire board, it is supposed to follow the same path again. So we can conclude that the sub-path $Q\to P$ when Turbo starts at $Q$ is same as the sub-path $Q\to P$ when Turbo starts at $P$ .

But since the distance of $Q$ from $P$ along this path is not $\equiv 0\pmod 4$ . When Turbo comes to $P$ , the arrow is no longer pointing towards its right and Turbo fails to complete its trip.

So the maximum number of good cells in a board is at most $\frac{n^2}{4}$ .

Now we give the construction.

Note that the given construction can easily be generalized and we are done.

This post has been edited 5 times. Last edited by kamatadu, Apr 18, 2025, 12:33 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6876 posts

#21 h Apr 19, 2025, 1:05 AM

Y by

Solution from Twitch Solves ISL:

Odd $n$ . When $n > 1$ is odd, there's no way to navigate loop through the board at all visiting every cell exactly once, and hence good cells cannot exist at all. The answer is $0$ in that case.

Even $n$ . For even $n$ , we claim that the answer is $n^2/4$ . In fact, we prove something more strong: if there are any good cells at all, then there are exactly $n^2/4$ good cells.
We assume henceforth that there is some good cell and hence that there is at least one valid loop (and indeed for even $n$ there are valid directed Hamiltonian cycles of an $n \times n$ board so this case can occur). The number of steps in the loop is $n^2$ and hence divisible by $4$ : thus it's easy to see that that every fourth cell along the loop is also good, because the same loop will be traced out. This gives $n^2/4$ good cells.
To prove that there can't be more good cells, it's sufficient to focus on the northwest corner.
Claim: There are only four methods for Turbo to pass through that corner, which we illustrate below. The subscript number indicates the order the cells are visited in relative to each other. $\begin{bmatrix} \downarrow_2 & \uparrow_3 \\ \uparrow_1 \end{bmatrix} \qquad \begin{bmatrix} \downarrow_2 & \leftarrow_3 \\ \uparrow_1 \end{bmatrix} \qquad \begin{bmatrix} \leftarrow_2 & \leftarrow_1 \\ \leftarrow_3 \end{bmatrix} \qquad \begin{bmatrix} \leftarrow_2 & \leftarrow_1 \\ \uparrow_3 \end{bmatrix}$ Proof. Clear. $\blacksquare$
From now on, we say two boards are rotations if one can be obtained from the other by rotating all the arrows the same amount (i.e.\ each board has four possible rotations).
The final observation is that in the four methods in the claim, none of the boards are rotations of each other. Hence for a given starting board, given a Hamiltonian cycle, the time modulo $4$ that Turbo passes through the northwest corner is uniquely determined. Then, by simply tracing out Turbo's trajectory from there, the entire directed Hamiltonian cycle is uniquely determined too, i.e.\ for every cell we know exactly which cell Turbo goes to next and the time modulo $4$ that Turbo visited the cell. This shows the good cells we asserted above are the only ones.
d

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

68 posts

#22 h Apr 23, 2025, 2:48 AM

Y by

My proof that starting from any cell $c_i \equiv 1,2,3(mod4)$ would result in the same path as of ur intial cycle $C$ ,
FTSOC, assume that a new path $d_{1 - d_2 - \ldots - d_k - d_1}$
does exists then we know that $d_{4p}-d{4p+1}$ this segment must lie in the direction of our cycle path, because after a multiple of "four" moves everything comes to its original position ,so now look at the top right corner where the cycle path has started from. WLOG, assume
in cycle $C$ it moved down ,but we know one thing that either $P \perp C$ or $P$ COINCIDES WITH $C$ ,so it is clear that this path " $d_{4p}-d{4p+1}$ " must be there on the down arrow, hence we must have the $C$ path to come down at least one step down again ,because if not then we would have " $d_{4p}-d{4p+1}$ " and " $d_{4p+1}-d{4p+2}$ " coincides with cycle $C$ ,but which generates contradiction, so on the square just below the top right corner would have two initial configuration> " $\rightarrow$ ":To satisfy cycle $C$
" $\downarrow$ " because starting from that cell $c_i$ and taking $1(Mod4)$ to make left move would result in the " $\downarrow$ " : To satisfy path $P$
Hence we again arrive at a contradiction .And the rest answer is explained above and easy for obvious reasons

This post has been edited 2 times. Last edited by Mathgloggers, Apr 23, 2025, 2:53 AM
Reason: n

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

14 posts

#23 h Apr 23, 2025, 10:01 AM

Y by

(Livesolved on YouTube: Art of Olympiad Mathematics)

Answer: $0$ if $n$ is odd, and $\frac{n^2}{4}$ otherwise.

First, let's show that for odd $n$ it is impossible to have any $good$ cells. The reason is quite simple - colour the board into chessboard colouring. Then every path on the board is a change in colours - black, white, black, ... . Then, a closed loop is of even length, which means that it is impossible to have a path through all the cells.

Now, we start off by noting that if we have one $good$ cell, then we have $\frac{n^2}{4}$ good cells, because every fourth cell keeps the orientations in such a way, that the path Turbo visits is the same. Now, we clearly have an example for $\frac{n^2}{4}$ (just take a random Hamiltonian cycle and direct arrows in the way we need). However, if we now look at the right-up corner of the board, then there is only two ways we can pass through it ( right then down or up and then left). This means that there are at most two orientations of all arrows (keeping the orientations in between the same) that work. However, if we had an arrow that goes to the right and then moves down, then both of the arrows should be of opposite direction. This means that the cells adjacent to the corner have the same direction opposite to the arrow in the cell of the corner, and an obvious contradiction is yielded just by checking where we go after going into the second cell adjacent to the corner. So, we are done.

This post has been edited 1 time. Last edited by zRevenant, Apr 23, 2025, 10:02 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a