The answer is 3.

Answer is 3. Pretty sure this works?

The answer is $\boxed{3}$. Consider the following walk on the graph depicted below: \begin{align*} A_1 &\to A_2 \to B_2 \to C_2 \to C_1 \to D_1 \\ &\to C_1 \to B_1 \to B_2 \to A_2 \to D_2 \\ &\to C_2 \to B_2 \to B_1 \to A_1, \end{align*}during which the junction $B_2$ is visited three times. [asy][asy] draw(circle((0,0), 1)^^circle((0,0), 2)); string[] names = {"$B_2$", "$B_1$", "$A_2$", "$A_2$", "$D_2$", "$D_1$", "$C_2$", "$C_1$"}; pair[] ll = {SE, E, NE, N, NW, W, SW, S}; for (int i=0; i<4; ++i) { draw(dir(90*i)--2*dir(90*i)); dot(names[2*i], dir(90*i), dir(ll[2*i])); dot(names[2*i+1], 2*dir(90*i), dir(ll[2*i+1])); } [/asy][/asy] We will now show that $3$ is the maximum, and we use the notation \[ X \stackrel{R}{\to} Y, \quad X \stackrel{L}{\to} Y \]to denote that the hiker took a right (resp. left) turn to enter junction $Y$ from $X$. Claim 1. It is impossible that $X \stackrel{R}{\to} Y$ (and similarly $X \stackrel{L}{\to} Y$) appear more than once during her hike. Proof. Suppose for the sake of contradiction that her hike could be infinite. Let $U$ be a junction, and let $V$ be the junction the hiker entered from $U$. Suppose the hiker took a right (resp. left) turn from $U$ to $V$. We say that $U$ is repeated if the hiker traversed $U \stackrel{R}{\to} V$ (resp. $U \stackrel{L}{\to} V$) for a second time later in the hike. There must exist a repeated junction based on our assumption that her hike is infinitely long. Let $X$ be the first repeated junction the hiker encountered. Clearly $X$ cannot be the junction at which the hiker started, since she terminates her hike as soon as she reaches her source junction for the second time. Therefore, there is a junction $J$ that the hiker visited immediately before $X$. Notice that given a structure of the form $X \stackrel{R}{\to} Y$, the junction from which the hiker entered $X$ is uniquely determined, implying that when $X \stackrel{R}{\to} Y$ appeared for the second time, $J$ came directly before $X$ then as well. Furthermore, the direction that the hiker took to reach $X$ through $J$ must be the same for both occurrences. Thus, $J$ is a repeated junction that came earlier than $X$. $\blacksquare$ Claim 2. It is impossible that both $X \stackrel{R}{\to} Y$ and $Y \stackrel{R}{\to} X$ occur during the hike. Of course, the same holds if $R$ is replaced with $L$. Proof. Suppose for the sake of contradiction that her hike looks like \[ \cdots \to \underbrace{X \stackrel{R}{\to} Y}_{\text{occurrence 1}} \to \cdots \to \underbrace{Y \stackrel{R}{\to} X}_{\text{occurrence 2}} \to \cdots, \]where $\cdots$ represents an unknown portion of the hike. The key is to realize that whichever junction the hiker visited from $Y$ directly after occurrence 1, call it $J_1$, must be the same junction from which the hiker entered $Y$ directly before occurrence 2 (one can easily check this). That is, the hike looks like \[ \cdots \to \underbrace{X \stackrel{R}{\to} Y}_{\text{occurrence 1}} \to J_1 \to \cdots \to J_1 \to \underbrace{Y \stackrel{R}{\to} X}_{\text{occurrence 2}} \to \cdots \]We may now replicate this line of reasoning repeatedly to deduce that the two portions of the hike stemming from the two occurrences and moving inward are mirror images of each other. The contradiction arises when they meet in the middle. There are two possibilities for how this can happen: \begin{align*} &\cdots \to J_{k-1} \to J_k \to J_{k-1} \to \cdots, \quad \text{or} \\ &\cdots \to J_{k-1} \to J_k \to J_k \to J_{k-1} \to \cdots \end{align*}But $J_{k-1} \to J_k \to J_{k-1}$ and $J_k \to J_k$ are impossible, and the claim follows. $\blacksquare$ Claims 1 and 2 are enough to show that no junction can be visited more than $3$ times. Suppose the hiker visits the junction $X$ at least $4$ times, and without loss of generality assume the following orientation of the neighbors $J_1,J_2,J_3$ of $X$: [asy][asy] pair X = (0, 0), J1 = dir(-90), J2 = dir(30), J3 = dir(150); draw(J2--X--J3^^X--J1); dot("$X$", X, dir(-30)); dot("$J_1$", J1, dir(J1)); dot("$J_2$", J2, dir(J2)); dot("$J_3$", J3, dir(J3)); [/asy][/asy] Then we have the following cases: $\boxed{J_1 \to X \cdots J_1 \to X \cdots J_2 \to X \cdots J_2 \to X}$. By Claim 1, one of the $J_1 \to X$ must be $J_1 \stackrel{R}{\to} X \stackrel{L}{\to} J_2$, and one of the $J_2 \to X$ must be $J_2 \stackrel{L}{\to} X$, which contradicts Claim 2. $\boxed{J_1 \to X \cdots J_1 \to X \cdots J_2 \to X \cdots J_3 \to X}$. Again by Claim 1, the two occurrences of $J_1 \to X$ must be \begin{align*} &J_1 \stackrel{L}{\to} X \stackrel{R}{\to} J_3 \\ &J_1 \stackrel{R}{\to} X \stackrel{L}{\to} J_2, \end{align*}so in order to avoid contradicting Claim 2, $J_2 \to X$ and $J_3 \to X$ must be \begin{align*} &J_3 \stackrel{L}{\to} X \stackrel{R}{\to} J_2 \\ &J_2 \stackrel{R}{\to} X \stackrel{L}{\to} J_3, \end{align*}however, this contradicts Claim 2 anyway. By Claim 1, no junction entering $X$ can be repeated $3$ or more times. Thus, we have established that the hiker cannot visit any junction at least $4$ times, which concludes the proof. $\square$

get out of my head get out of my head get out of my head get out of my head

^ this is legendary

A bit easy for p2? If we say the intent $\in \{R,L \}$ is the direction in which she will turn at the next intersection, then we can never travel a road twice with the same intent, otherwise the previous move would have been like that too (so for instance considering the first time this happens gives a contradiction). This means if we let the roads entering some junction be $A,B,C$ in counterclockwise order, the actions "enter through $A$ with intent R" and "enter through $B$ with intent L" cannot both happen. With other symmetric statements, we see what we can only enter a junction 3 times; construction is shown below, starting from F and going to E (D is entered 3 times). [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(8cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -13.63548, xmax = 15.00764, ymin = -7.00099, ymax = 9.71637; /* image dimensions */ /* draw figures */ draw((-5.74672,0.76996)--(-5.64024,-1.1733), linewidth(2)); draw((-5.64024,-1.1733)--(-3.88,-2.46), linewidth(2)); draw((-3.88,-2.46)--(-2.36598,-1.25316), linewidth(2)); draw((-2.36598,-1.25316)--(-0.68892,-2.47768), linewidth(2)); draw((-0.68892,-2.47768)--(0.96152,-1.33302), linewidth(2)); draw((0.96152,-1.33302)--(0.98814,1.06278), linewidth(2)); draw((-2.47246,0.92968)--(-0.84864,2.39378), linewidth(2)); draw((-0.84864,2.39378)--(0.98814,1.06278), linewidth(2)); draw((-5.74672,0.76996)--(-4.06966,2.26068), linewidth(2)); draw((-4.06966,2.26068)--(-2.47246,0.92968), linewidth(2)); draw((-4.06966,2.26068)--(-4.17614,4.47014), linewidth(2)); draw((-4.17614,4.47014)--(-2.71204,6.20044), linewidth(2)); draw((-2.71204,6.20044)--(-0.95512,4.57662), linewidth(2)); draw((-0.95512,4.57662)--(-0.84864,2.39378), linewidth(2)); draw((-2.47246,0.92968)--(-2.36598,-1.25316), linewidth(2)); draw((-5.74672,0.76996)--(-3.88,-2.46), linewidth(2)); draw((-0.68892,-2.47768)--(0.98814,1.06278), linewidth(2)); draw((-4.17614,4.47014)--(-0.95512,4.57662), linewidth(2)); draw(shift((-2.2404643543550478,2.8345266866580547))*xscale(5.255582669030052)*yscale(5.255582669030052)*arc((0,0),1,95.73103377466899,229.69258808875026), linewidth(2)); draw(shift((-2.2404643543550478,2.8345266866580547))*xscale(5.255582669030051)*yscale(5.255582669030051)*arc((0,0),1,-52.46442379037466,95.73103377466899), linewidth(2)); draw((-2.71204,6.20044)--(-2.76528,8.06384), linewidth(2)); /* dots and labels */ dot((-5.74672,0.76996),dotstyle); label("$A$", (-5.64948,1.03825), NE * labelscalefactor); dot((-5.64024,-1.1733),dotstyle); label("$B$", (-5.543,-0.90501), NE * labelscalefactor); dot((-4.06966,2.26068),dotstyle); label("$C$", (-3.97242,2.52897), NE * labelscalefactor); dot((-2.47246,0.92968),dotstyle); label("$D$", (-2.37522,1.19797), NE * labelscalefactor); dot((-2.36598,-1.25316),dotstyle); label("$E$", (-2.26874,-0.98487), NE * labelscalefactor); dot((-3.88,-2.46),dotstyle); label("$F$", (-3.78608,-2.18277), NE * labelscalefactor); dot((0.98814,1.06278),dotstyle); label("$G$", (1.08538,1.33107), NE * labelscalefactor); dot((0.96152,-1.33302),dotstyle); label("$H$", (1.05876,-1.06473), NE * labelscalefactor); dot((-0.68892,-2.47768),dotstyle); label("$I$", (-0.59168,-2.20939), NE * labelscalefactor); dot((-4.17614,4.47014),dotstyle); label("$J$", (-4.0789,4.73843), NE * labelscalefactor); dot((-0.95512,4.57662),dotstyle); label("$K$", (-0.85788,4.84491), NE * labelscalefactor); dot((-2.71204,6.20044),dotstyle); label("$L$", (-2.6148,6.46873), NE * labelscalefactor); dot((-0.84864,2.39378),dotstyle); label("$M$", (-0.7514,2.66207), NE * labelscalefactor); dot((-2.76528,8.06384),dotstyle); label("$N$", (-2.66804,8.33213), NE * labelscalefactor); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy]

Nothing.

Had a somewhat funny construction

$3 $

How much points would proving the walk is of finite length get?

@above that's infinite pigeonhole right? probably <= 1 if any... although i'm not a grader so don't ask me

I got 3 also. My proof wasn't super thorough, but I showed that 3 is attainable if the graph is of a pentagonal (or any other $4k+1$ gon) prism and your first move is going from one base to the other

I showed $a\rightarrow b\rightarrow c$ twice is impossible, and provided a correct construction for $n=3$ even though I said the answer is $6$. How many points would that give? (Sadge I crossed out $a\rightarrow b\rightarrow c$, $c\rightarrow b\rightarrow a$)

ikr they should give 7 points to everyone

Emathmaster wrote: How much points would proving the walk is of finite length get? But that's not true... Consider, for example, a park which is three infinite binary trees extending from the same root. Start at the root and travel in any direction initially. You will never get back to where you started.

How does one solve this problem? Draw 20 different convoluted graphs on a paper, and stare. You'll be able to hopefully find the answer. We claim the answer is 3. Surprisingly, the harder part is construction. To show the answer is at most 3, consider any junction $\phi$, and its neighbors $\chi$, $\psi$, and $\pi$ (no these are totally not chosen because they sound the exact same). Then, we note that first there are at most 3 distinct routes from one of these into and out of $\phi$, as if you enter from, without loss of generality, $\chi$, you must have turned in direction left (or right) and then must turn right (or left) in this junction. We now prove it is impossible to go over $\chi\to\phi\to\pi$ twice. We note we can never get stuck in a cycle, since all moves are "uniquely reversible". Thus, if we get to $\chi\to\phi\to\pi$ twice, we essentially reach a contradiction as we are in a cycle. Here's what an example with 3 looks like: [asy][asy] size(20cm); draw((0,0)--(-1,-1)--(-1,-3)); draw((0,0)--(1,-1)--(0,-2)--(1,-3)--(0,-4)--(-1,-3)); draw((1,-1)--(2,-2)); draw((0,-2)--(-1,-3)); draw((2,-3)--(2,-4)); draw((2,-2)--(2,-3)); draw((2,-3)--(1,-4)); draw((-1,-1)--(0,-1)); draw((0,-4)--(0,-3)); draw((0,-4)--(0,-3)); draw((2,-2)--(1,-2)); draw((1,-4)--(1,-3)); draw((1,-4)--(1.5,-3)); draw((0,-0.1)--(1,-1.1)--(0.1,-2)--(1.1,-3)--(0,-4.1)--(-1.1,-3)--(1,-0.9)--(2.1,-2)--(2.1,-3)--(0.9,-4.2)--(0.9,-3)--(0,-2.1)--(-0.9,-3)--(-0.9,-1)--cycle,red); real w=linewidth(); dot((0,0),blue+linewidth(12w)); dot((-1,-1)); dot((1,-1)); dot((0,-2),purple+linewidth(12w)); dot((2,-2)); dot((1,-3)); dot((-1,-3)); dot((0,-4)); dot((1,-4)); dot((2,-3)); label("$\lambda$",(0,-1),E); label("$\lambda$",(0,-3),N); label("$\lambda$",(1.5,-3),N); label("$\lambda$",(1,-2),W); label("$\lambda$",(2,-4),S); [/asy][/asy] where each $\lambda$ refers to the following graph: [asy][asy] draw((0,0)--(-1,-1)--(-1,-2)--(1,-2)--(1,-1)--cycle); draw((-1,-1)--(1,-2)); draw((1,-1)--(-1,-2)); dot((0,0)); dot((-1,-1)); dot((1,-1)); dot((-1,-2)); dot((1,-2)); label("$\lambda$",(0,0),N); [/asy][/asy] The visitor starts at the blue dot, and follows the path parallel to the red path. He passes through the purple dot three times, as desired. The sole purpose of $\lambda$ is to make sure every vertex has degree 3.

Thank you Pluto1708 for helping me out in asy.

THIS PROBLEM CHANGED MY LIFE Well, let me tell you the story. I was experiencing internet cut-off and my friend sent me this problem via SMS. When I tried to solve this, my lady stuck inside the national park in a loop. So, I thought the answer was "$\infty$" and asked my friend to check AoPS to see if this was a troll problem. He replied that NO ONE WAS TALKING ABOUT IT. I was like that is sooo weird... and I'm $100\%$ certain that my construction was right, which is the one below. Let the lady walk from $A$ to $B$ and she will be stuck in the loop $B, C, D, E, B, C, \dotsc$. (If you are confused, just continue reading). [asy][asy] pair A = (0, -1); pair B = (0, 1); pair C = (-1, 0); pair D = (0, 3); pair E = (1, 0); pair P = (-0.5, 0); pair Q = (0.5, 3); pair R = (1.5, 0); draw(A--B--C--D--E--B); draw(C--P); draw(D--Q); draw(E--R); dot("$A$", A, dir(270)); dot("$B$", B, dir(90)); dot("$C$", C, dir(270)); dot("$D$", D, dir(90)); dot("$E$", E, dir(270)); [/asy][/asy] Figure 1 Well, we cannot send figures via SMS, so I had to like.... send him the coordinates as if he were an asymptote renderer, lol. Anyway, after arguing for about 30 minutes, we finally found what went wrong. THE WAY I DEFINE LEFT AND RIGHT IS DIFFERENT FROM "STANDARD" ONE. OKay, so here is how I see left and right. Suppose you stand at point $A$ and walk towards point $X$ which is the junction of three roads (rays) $XA, XB$ and $XC$. To know which one of $XB$ or $XC$ is to the left/right of me, the way I define this is as follows: Quote: First, let $A'$ be reflection of $A$ at $X$. Then, I rotate the ray $XA'$ anticlockwise, the first of $XB$ or $XC$ that my rotating ray coincides is called the road on the left. Analogously, the first of $XB$ or $XC$ that my ray finds when rotating clockwise is called the road on the right. [asy][asy] size(3cm); pair A = (0, -1); pair X = (0, 0); pair B = (-1, 1); pair C = (1, 1); draw(X--A); draw(X--B); draw(X--C); dot("$X$", X, dir(210)); label("$A$", A, dir(270)); label("$B$", B, dir(135)); label("$C$", C, dir(45)); [/asy][/asy] Figure 2 With this definition, you can easily check that the lady does stuck in a loop as I said above (pls check this because things are about to get crazier). I was mind-blown... I used google maps and followed directions around the town for YEARS! How have I never come to contradict with google maps??? Well, apparently, the rest of the world uses the following definition to describe left or right, $X, A, B$ and $C$ have the same meaning as the above definition. Quote: Rotate the ray $XA$ clockwise, and the first of $XB$ or $XC$ that this rotating ray coincides is called the road on the left. Analogously, the road on the right is defined by rotating anticlockwise. Welp, the left and right choices we see in real life are just like those in figure 2, and these two definitions coincide for this case. Is this crazy enough? Nope, we asked another person on how they define left or right, and..... now we get a new definition again: Quote: Consider the interior angle bisector ray of $\angle BXC$. Now, rotate this ray anticlockwise, and the first of $XB$ and $XC$ you find is the road to the left. That with clockwise rotation is the road to the right. These all seem to be the same definitions on figure 2, but look at this: [asy][asy] pair X = (0, 0); pair P = 3*dir(270); pair Q = 3*dir(120); pair R = 3*dir(60); pair S = 3*dir(0); pair T = 3*dir(225); pair U = 3*dir(315); pair v = (-4,0); pair X1 = X+v; pair A1 = P+v; pair B1 = Q+v; pair C1 = R+v; draw(X1--A1); draw(X1--B1); draw(X1--C1); label("$A$", A1, dir(270)); label("$B$", B1, dir(120)); label("$C$", C1, dir(60)); pair X2 = X; pair A2 = P; pair B2 = R; pair C2 = S; draw(X2--A2); draw(X2--B2); draw(X2--C2); label("$A$", A2, dir(270)); label("$B$", B2, dir(60)); label("$C$", C2, dir(0)); pair X3 = X-2*v; pair A3 = P-2*v; pair B3 = T-2*v; pair C3 = U-2*v; draw(X3--A3); draw(X3--B3); draw(X3--C3); label("$A$", A3, dir(270)); label("$B$", B3, dir(225)); label("$C$", C3, dir(315)); [/asy][/asy] Figure 3 In these figures, all three definitions agree at the first figure. For the second figure, the world's and 3rd person's definitions agree while my definition is different. For the third figure, me and the world's definitions agree while 3rd person's definition is different. Well, this was an interesting experience for me... I was actually amazed how everyone taking USAMO had equivalent definitions for this problem. I'm sorry if this post has memey-vibes to it and not related to the problem. This was so mind-blowing to me that I had to share this story, lol.

First, we claim the answer is finite. Indeed, notice that the visitor can have 6 distinct states at each vertex (which edge she will walk through next and the handedness of the next vertex gives $3 \times 2$ possible states) and the state at each vertex is uniquely determined by the state on the last vertex. To say, if $S$ is the set of states and $f: S \to S$ is the function that takes the traveler from one state to the next state, then $f$ is bijective. Let $I$ be the initial state and assume some state $P$ is achieved twice without $I$ appearing between them. This is a contradiction since rolling back $P$ will always get $I$ back in a fixed number of steps. Now, we claim the visitor cannot visit a vertex more than thrice. Indeed, we say states $A$ and $A^{-1}$ at the same vertex $V$ are inverses if they have opposite handedness at the next vertex, and if the traveler will next walk along edge $e$ if $A$ occurs then the traveler walks into $V$ from $e$ if $A^{-1}$ occurs. We claim that at any vertex, the traveler can never have been in inverse states on the same walk. Indeed, assume the contrary holds. Suppose that the traveler first reaches some state $A_1$ then some other state $B_1=A_{1}^{-1}$. If $A_2$ is the state directly after $A_1$ and $B_2$ is the state directly before $B_1$, it is easy to see that $B_2=A_{2}^{-1}$. Repeating this inductively yields $B_n=A_{n}^{-1}$ for some $A_n$ and $B_n$ where $B_n$ occurs directly after $A_n$. But this is a contradiction since it implies that the traveler will get to some vertex and go back through the same edge it came in on. Each of the $6$ states has one inverse, giving at most $3$ states. For construction, refer to previous posts. remark: My primary motivation for this solution was rubik's cubes lmao

Nice problem. My construction was REALLY messy, but it worked

Uhhh same solution as above ones but whatever We claim that answer is $3$. For the sake of contradiction, assume that the answer is. $x>3$. Let the visited vertex be $X$ and its neighbours be $A,B,C$. Then let the walk as $B \rightarrow X \rightarrow A$ etc.By our assumption, we must use at least one walk or its reverse walk $2$ or more times, Hence it motivates us to prove our claims: Claim1. any sequence$A \rightarrow X \rightarrow B$ can't be used second time. Since the start and finish of path $...\rightarrow A \rightarrow X \rightarrow B \rightarrow..$ is uniquely determined, we will already pass from our main junction after $1$ time, which means $2$ or more time gives that our path is infinite. $\square$ Claim 2. any reverse sequence of $A \rightarrow X \rightarrow B$ can't be used if the original one is used. Since the end part of sequence $...A \rightarrow X \rightarrow B...$ is the same as the start part of $... B \rightarrow X \rightarrow A$, Naming these parts $Y_1,Y_2,...$ etc, in the middle part of the path we have either $Y_i \rightarrow Y_i$ or $Y_i \rightarrow Y_{i+1} \rightarrow Y_i$ which is absurd. $\square$ Since we have proven our claims, we have contradiction to our original claim, hence $x=3$ $\ \blacksquare$ I am confused on construction part, why should we show a construction? Since we don't know how many junctions there are, we must have a generalized construction but it doesn't seem possible for me, can someone explain please?

@above: to show that the maximum isn't lower

Need to add a pair of points E1 and E2 on the diagram. ppanther wrote: The answer is $\boxed{3}$. Consider the following walk on the graph depicted below: \begin{align*} A_1 &\to A_2 \to B_2 \to C_2 \to C_1 \to D_1 \\ &\to C_1 \to B_1 \to B_2 \to A_2 \to D_2 \\ &\to C_2 \to B_2 \to B_1 \to A_1, \end{align*}during which the junction $B_2$ is visited three times. [asy][asy] draw(circle((0,0), 1)^^circle((0,0), 2)); string[] names = {"$B_2$", "$B_1$", "$A_2$", "$A_2$", "$D_2$", "$D_1$", "$C_2$", "$C_1$"}; pair[] ll = {SE, E, NE, N, NW, W, SW, S}; for (int i=0; i<4; ++i) { draw(dir(90*i)--2*dir(90*i)); dot(names[2*i], dir(90*i), dir(ll[2*i])); dot(names[2*i+1], 2*dir(90*i), dir(ll[2*i+1])); } [/asy][/asy] We will now show that $3$ is the maximum, and we use the notation \[ X \stackrel{R}{\to} Y, \quad X \stackrel{L}{\to} Y \]to denote that the hiker took a right (resp. left) turn to enter junction $Y$ from $X$. Claim 1. It is impossible that $X \stackrel{R}{\to} Y$ (and similarly $X \stackrel{L}{\to} Y$) appear more than once during her hike. Proof. Suppose for the sake of contradiction that her hike could be infinite. Let $U$ be a junction, and let $V$ be the junction the hiker entered from $U$. Suppose the hiker took a right (resp. left) turn from $U$ to $V$. We say that $U$ is repeated if the hiker traversed $U \stackrel{R}{\to} V$ (resp. $U \stackrel{L}{\to} V$) for a second time later in the hike. There must exist a repeated junction based on our assumption that her hike is infinitely long. Let $X$ be the first repeated junction the hiker encountered. Clearly $X$ cannot be the junction at which the hiker started, since she terminates her hike as soon as she reaches her source junction for the second time. Therefore, there is a junction $J$ that the hiker visited immediately before $X$. Notice that given a structure of the form $X \stackrel{R}{\to} Y$, the junction from which the hiker entered $X$ is uniquely determined, implying that when $X \stackrel{R}{\to} Y$ appeared for the second time, $J$ came directly before $X$ then as well. Furthermore, the direction that the hiker took to reach $X$ through $J$ must be the same for both occurrences. Thus, $J$ is a repeated junction that came earlier than $X$. $\blacksquare$ Claim 2. It is impossible that both $X \stackrel{R}{\to} Y$ and $Y \stackrel{R}{\to} X$ occur during the hike. Of course, the same holds if $R$ is replaced with $L$. Proof. Suppose for the sake of contradiction that her hike looks like \[ \cdots \to \underbrace{X \stackrel{R}{\to} Y}_{\text{occurrence 1}} \to \cdots \to \underbrace{Y \stackrel{R}{\to} X}_{\text{occurrence 2}} \to \cdots, \]where $\cdots$ represents an unknown portion of the hike. The key is to realize that whichever junction the hiker visited from $Y$ directly after occurrence 1, call it $J_1$, must be the same junction from which the hiker entered $Y$ directly before occurrence 2 (one can easily check this). That is, the hike looks like \[ \cdots \to \underbrace{X \stackrel{R}{\to} Y}_{\text{occurrence 1}} \to J_1 \to \cdots \to J_1 \to \underbrace{Y \stackrel{R}{\to} X}_{\text{occurrence 2}} \to \cdots \]We may now replicate this line of reasoning repeatedly to deduce that the two portions of the hike stemming from the two occurrences and moving inward are mirror images of each other. The contradiction arises when they meet in the middle. There are two possibilities for how this can happen: \begin{align*} &\cdots \to J_{k-1} \to J_k \to J_{k-1} \to \cdots, \quad \text{or} \\ &\cdots \to J_{k-1} \to J_k \to J_k \to J_{k-1} \to \cdots \end{align*}But $J_{k-1} \to J_k \to J_{k-1}$ and $J_k \to J_k$ are impossible, and the claim follows. $\blacksquare$ Claims 1 and 2 are enough to show that no junction can be visited more than $3$ times. Suppose the hiker visits the junction $X$ at least $4$ times, and without loss of generality assume the following orientation of the neighbors $J_1,J_2,J_3$ of $X$: [asy][asy] pair X = (0, 0), J1 = dir(-90), J2 = dir(30), J3 = dir(150); draw(J2--X--J3^^X--J1); dot("$X$", X, dir(-30)); dot("$J_1$", J1, dir(J1)); dot("$J_2$", J2, dir(J2)); dot("$J_3$", J3, dir(J3)); [/asy][/asy] Then we have the following cases: $\boxed{J_1 \to X \cdots J_1 \to X \cdots J_2 \to X \cdots J_2 \to X}$. By Claim 1, one of the $J_1 \to X$ must be $J_1 \stackrel{R}{\to} X \stackrel{L}{\to} J_2$, and one of the $J_2 \to X$ must be $J_2 \stackrel{L}{\to} X$, which contradicts Claim 2. $\boxed{J_1 \to X \cdots J_1 \to X \cdots J_2 \to X \cdots J_3 \to X}$. Again by Claim 1, the two occurrences of $J_1 \to X$ must be \begin{align*} &J_1 \stackrel{L}{\to} X \stackrel{R}{\to} J_3 \\ &J_1 \stackrel{R}{\to} X \stackrel{L}{\to} J_2, \end{align*}so in order to avoid contradicting Claim 2, $J_2 \to X$ and $J_3 \to X$ must be \begin{align*} &J_3 \stackrel{L}{\to} X \stackrel{R}{\to} J_2 \\ &J_2 \stackrel{R}{\to} X \stackrel{L}{\to} J_3, \end{align*}however, this contradicts Claim 2 anyway. By Claim 1, no junction entering $X$ can be repeated $3$ or more times. Thus, we have established that the hiker cannot visit any junction at least $4$ times, which concludes the proof. $\square$

We first give a construction for $n = 3$. Take the following design with the bottom copied, and start from the dot and go up. [asy][asy] size(5cm); import geometry; point a, b, c, d, e, f, g, h; a = (0, 0); b = (-2, 1); c = (0, 1); d = (2, 1); e = (-1, 2); f = (1, 2); g = (-1, 3); h = (1, 3); draw(a--c--b--e--f--d--c); draw(b--g--h--d); draw(g--e); draw(h--f); dot(a); [/asy][/asy] Claim: The visitor's walk has no cycles with respect to her parity. Proof. Follows since the path can be determined backwards. $\blacksquare$ Claim: The visitor's walk does not trace back on itself in the opposite state. Proof. FTSOC suppose not. Then the path before the tracing back and the path after the traced over are the same, which eventually implies the path tracing back, which is illegal. $\blacksquare$ As such, there are at most $3 \cdot 2$ ways to enter a vertex, which must all be distinct. Furthermore, these ways are incompatible with their inverses, so there are at most $3$ total entrances.

Snark_Graphique wrote: THIS PROBLEM CHANGED MY LIFE Well, let me tell you the story. I was experiencing internet cut-off and my friend sent me this problem via SMS. When I tried to solve this, my lady stuck inside the national park in a loop. So, I thought the answer was "$\infty$" and asked my friend to check AoPS to see if this was a troll problem. He replied that NO ONE WAS TALKING ABOUT IT. I was like that is sooo weird... and I'm $100\%$ certain that my construction was right, which is the one below. Let the lady walk from $A$ to $B$ and she will be stuck in the loop $B, C, D, E, B, C, \dotsc$. (If you are confused, just continue reading). [asy][asy] pair A = (0, -1); pair B = (0, 1); pair C = (-1, 0); pair D = (0, 3); pair E = (1, 0); pair P = (-0.5, 0); pair Q = (0.5, 3); pair R = (1.5, 0); draw(A--B--C--D--E--B); draw(C--P); draw(D--Q); draw(E--R); dot("$A$", A, dir(270)); dot("$B$", B, dir(90)); dot("$C$", C, dir(270)); dot("$D$", D, dir(90)); dot("$E$", E, dir(270)); [/asy][/asy] Figure 1 Well, we cannot send figures via SMS, so I had to like.... send him the coordinates as if he were an asymptote renderer, lol. Anyway, after arguing for about 30 minutes, we finally found what went wrong. THE WAY I DEFINE LEFT AND RIGHT IS DIFFERENT FROM "STANDARD" ONE. OKay, so here is how I see left and right. Suppose you stand at point $A$ and walk towards point $X$ which is the junction of three roads (rays) $XA, XB$ and $XC$. To know which one of $XB$ or $XC$ is to the left/right of me, the way I define this is as follows: Quote: First, let $A'$ be reflection of $A$ at $X$. Then, I rotate the ray $XA'$ anticlockwise, the first of $XB$ or $XC$ that my rotating ray coincides is called the road on the left. Analogously, the first of $XB$ or $XC$ that my ray finds when rotating clockwise is called the road on the right. [asy][asy] size(3cm); pair A = (0, -1); pair X = (0, 0); pair B = (-1, 1); pair C = (1, 1); draw(X--A); draw(X--B); draw(X--C); dot("$X$", X, dir(210)); label("$A$", A, dir(270)); label("$B$", B, dir(135)); label("$C$", C, dir(45)); [/asy][/asy] Figure 2 With this definition, you can easily check that the lady does stuck in a loop as I said above (pls check this because things are about to get crazier). I was mind-blown... I used google maps and followed directions around the town for YEARS! How have I never come to contradict with google maps??? Well, apparently, the rest of the world uses the following definition to describe left or right, $X, A, B$ and $C$ have the same meaning as the above definition. Quote: Rotate the ray $XA$ clockwise, and the first of $XB$ or $XC$ that this rotating ray coincides is called the road on the left. Analogously, the road on the right is defined by rotating anticlockwise. Welp, the left and right choices we see in real life are just like those in figure 2, and these two definitions coincide for this case. Is this crazy enough? Nope, we asked another person on how they define left or right, and..... now we get a new definition again: Quote: Consider the interior angle bisector ray of $\angle BXC$. Now, rotate this ray anticlockwise, and the first of $XB$ and $XC$ you find is the road to the left. That with clockwise rotation is the road to the right. These all seem to be the same definitions on figure 2, but look at this: [asy][asy] pair X = (0, 0); pair P = 3*dir(270); pair Q = 3*dir(120); pair R = 3*dir(60); pair S = 3*dir(0); pair T = 3*dir(225); pair U = 3*dir(315); pair v = (-4,0); pair X1 = X+v; pair A1 = P+v; pair B1 = Q+v; pair C1 = R+v; draw(X1--A1); draw(X1--B1); draw(X1--C1); label("$A$", A1, dir(270)); label("$B$", B1, dir(120)); label("$C$", C1, dir(60)); pair X2 = X; pair A2 = P; pair B2 = R; pair C2 = S; draw(X2--A2); draw(X2--B2); draw(X2--C2); label("$A$", A2, dir(270)); label("$B$", B2, dir(60)); label("$C$", C2, dir(0)); pair X3 = X-2*v; pair A3 = P-2*v; pair B3 = T-2*v; pair C3 = U-2*v; draw(X3--A3); draw(X3--B3); draw(X3--C3); label("$A$", A3, dir(270)); label("$B$", B3, dir(225)); label("$C$", C3, dir(315)); [/asy][/asy] Figure 3 In these figures, all three definitions agree at the first figure. For the second figure, the world's and 3rd person's definitions agree while my definition is different. For the third figure, me and the world's definitions agree while 3rd person's definition is different. Well, this was an interesting experience for me... I was actually amazed how everyone taking USAMO had equivalent definitions for this problem. I'm sorry if this post has memey-vibes to it and not related to the problem. This was so mind-blowing to me that I had to share this story, lol. I was confused by "left" and "right" as well. Tbh, I don't think that is your issue, MAA should explain more. Especially in a graph theory problem where we can potentially twist the edges. Any unclear statement may destroy some groups of students.

KI_HG wrote: I was confused by "left" and "right" as well. Tbh, I don't think that is your issue, MAA should explain more. Especially in a graph theory problem where we can potentially twist the edges. Any unclear statement may destroy some groups of students. I was the chief editor for USAMO 2021, so please blame any issues with clarity of problem statements on me rather than on the MAA staff. Give credit where credit is due. I am sorry that apparently some people would think turning left would mean going along $C$ in Figure 3. When editing the statements, it would have never occurred to me that “left” and “right” were terms that students may not know, and it did not occur to any of the other editors either. Happily, as far as I can tell from also having graded this problem, I did not recall seeing any students who actually used a wrong definition of “left” or “right” during the exam.

Apparently I never posted my write-up, so here it is: The answer is $3$. We consider the trajectory of the visitor as an ordered sequence of turns. A turn is defined by specifying a vertex, the incoming edge, and the outgoing edge. Hence there are six possible turns for each vertex. Claim: Given one turn in the sequence, one can reconstruct the entire sequence of turns. Proof. This is clear from the process's definition: given a turn $t$, one can compute the turn after it and the turn before it. $\blacksquare$ This implies already that the trajectory of the visitor, when extended to an infinite sequence, is totally periodic (not just eventually periodic), because there are finitely many possible turns, so some turn must be repeated. So, any turn appears at most once in the period of the sequence, giving a na\"{\i}ve bound of $6$ for the original problem. However, the following claim improves the bound to $3$. Claim: It is impossible for both of the turns $a \to b \to c$ and $c \to b \to a$ to occur in the same trajectory. Proof. If so, then extending the path, we get $a \to b \to c \to d \to e \to \dotsb$ and $\dots \to e \to d \to c \to b \to a$, as illustrated below in red and blue respectively. [asy][asy] defaultpen(fontsize(11pt)); dotfactor *= 1.8; pair A = (0,0); pair B = (1,1); pair C = (0,2); pair D = (1,3); pair E = (0,4); draw(A--B--C--D--E--(0.5,4.5), black+1.3); draw( (0.5,4.5)--(0.8,4.8), black+1.3+dotted ); draw((1,-1)--A--(-1,0), grey); draw(B--(2,1), grey); draw(C--(-1,2), grey); draw(D--(2,3), grey); draw(E--(-1,4), grey); dot("$a$", A, -dir(B-A), deepgreen); dot("$b$", B, -dir(C-B), deepgreen); dot("$c$", C, -dir(D-C), deepgreen); dot("$d$", D, -dir(E-D), deepgreen); dot("$e$", E, dir(90), deepgreen); draw( (1,0.2)..(1.4,1)..(1,1.8), red+1.8, EndArrow(TeXHead)); draw( (1,2.2)..(1.4,3)..(1,3.8), lightred+1, EndArrow(TeXHead)); draw( (0.8,1.6)..(0.4,2)..(0.8,2.4), lightred+1, EndArrow(TeXHead)); draw( (0.8,3.6)..(0.4,4)..(0.8,4.4), lightred+1, EndArrow(TeXHead)); draw( (0.2,1.4)..(0.6,1)..(0.2,0.6), blue+1.8, EndArrow(TeXHead)); draw( (0.2,3.4)..(0.6,3)..(0.2,2.6), lightblue+1, EndArrow(TeXHead)); draw( (0,2.8)..(-0.4,2)..(0,1.2), lightblue+1, EndArrow(TeXHead)); draw( (0,4.8)..(-0.4,4)..(0,3.2), lightblue+1, EndArrow(TeXHead)); [/asy][/asy] However, we assumed for contradiction the red and blue paths were part of the same trajectory, yet they clearly never meet. $\blacksquare$ It remains to give a construction showing $3$ can be achieved. There are many, many valid constructions. One construction due to Danielle Wang is given here, who provided the following motivation: ``I was lying in bed and drew the first thing I could think of''. The path is $CAHIFGDBAHEFGJBAC$ which visits $A$ three times. [asy][asy] size(10cm); defaultpen(fontsize(11pt)); pair A = (-2,2); pair B = (2,2); pair C = (-1,1); pair D = (1,1); pair E = (-1,-1); pair F = (0,-1); pair G = (1,-1); pair H = (-2,-2); pair I = (0,-2); pair J = (2,-2); pen gr = fontsize(14pt) + deepgreen; draw(A--H, blue); label("$2,9$", A--H, gr); draw(A--C, blue); label("$16$", A--C, gr); draw(A--B, blue); draw(B--D, blue); draw(B--J, blue); draw(B--A, blue); label("$8,15$", B--A, gr); draw(C--E, blue); draw(C--D, blue); draw(C--A, blue); label("$1$", C--A, gr); draw(D--C, blue); draw(D--G, blue); draw(D--B, blue); label("$7$", D--B, gr); draw(E--H, blue); draw(E--F, blue); label("$11$", E--F, gr); draw(E--C, blue); draw(F--I, blue); draw(F--G, blue); label("$5,12$", F--G, gr); draw(F--E, blue); draw(G--F, blue); draw(G--J, blue); label("$13$", G--J, gr); draw(G--D, blue); label("$6$", G--D, gr); draw(H--I, blue); label("$3$", H--I, gr); draw(H--E, blue); label("$10$", H--E, gr); draw(H--A, blue); draw(I--H, blue); draw(I--J, blue); draw(I--F, blue); label("$4$", I--F, gr); draw(J--B, blue); label("$14$", J--B, gr); draw(J--G, blue); draw(J--I, blue); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$C$", C, -dir(C)); dot("$D$", D, -dir(D)); dot("$E$", E, -dir(E)); dot("$F$", F, -dir(F)); dot("$G$", G, -dir(G)); dot("$H$", H, dir(H)); dot("$I$", I, dir(I)); dot("$J$", J, dir(J)); margin m = Margin(3,3); pair[] trajectory = {C,A,H,I,F,G,D,B,A,H,E,F,G,J,B,A,C}; for (int i=0; i<trajectory.length-1; ++i) { draw(trajectory[i]--trajectory[i+1], red+1.4, m); draw(trajectory[i]--trajectory[i+1], red, EndArrow, m); } [/asy][/asy] Remark: As the above example shows it is possible to transverse an edge more than once even in the same direction, as in edge $AH$ above.