Nice problem for my 500th post, but I had quite a tough time rewriting this. Tournament of Towns, Senior A-Level, Spring 2019, p7 wrote: Consider lattice paths of finite length, which start from $(0,0)$ and move only up and right, which we call $\textit{skeletons}$. For each skeleton, we define a $\textit{worm}$ consisting of all unit cells in the plane sharing at least one point with the skeleton. (For example, for the path from $(0,0)$ to $(1,0)$, the corresponding worm has six cells). Prove that for every integer $n > 2$, the number of worms which can be tiled by dominoes in exactly $n$ ways is equal to $\varphi(n)$. Let's set up some notations and observations. For a skeleton $A$, we define $n(A)$ as the number of ways we can tile worm with skeleton $A$ with dominoes. Observation 01. If $A \subseteq B$, then $n(A) \le n(B)$. This is quite obvious. We define a continuous zig-zag pattern (see the attachment), which is $C-D-E-F-G$ from the attachment as a $\textbf{stair}$. Furthermore, the two ends of any stair is an endpoint and an edge which is not perpendicular with the last edge from the stair. Now, we will define the relation $\sim$. We define $A \sim B$ for two skeletons $A$ and $B$ if and only if: 1. $A \subseteq B$. 2. $B$ is formed by attaching a stair of any length from skeleton $A$. Now, we define $A_k$ as the skeleton $B$ such that $A \sim B$, and the stair formed is of length $k$ (see the attachment for both $A$ and $A_5$). We now first prove that every skeleton $A$ has $n(A)$ that can be represent as sum of two integers. Notice the last two edge that skeleton $A$ has. We will now set a recursion formula for $A$. It eithers form an L or a straight line. $\textbf{Subclaim 01.}$ $n(A--) = n(A-) + n(A)$ $\textit{Proof.}$ This is just a simple recursion. We consider the rightest (most extreme) part of the worm, which can be tiled in either two ways, horizontally or vertically. If the last two edge forms a straight line, wlog a horizontal straight line, then if the extreme part of the worm is tiled vertically. Then, we could just delete the last vertex, and that works, which has the number of tiling of $n(A-)$. Now, otherwise, it must be tiled horizontally, and therefore the "cells" below it must be tiled horizontally as well, so this is equivalent to deleting the last two vertex, and that works, which has the number of riling of $n(A)$. Now, we consider the case where the last two edge forms an $L$, therefore, this skeleton must has a $\textbf{stair}$. Now, suppose that this skeleton $B = A_k$ for some skeleton $A$ and some integer $k \ge 2$. $\textbf{Subclaim 02.}$ $n(A_k) = n(A) + n(A_{k - 1})$. $\textit{Proof.}$ Hard to answer without any visual, but it's basically just the same way as the first one, and notice that stair somehow forces a unique tiling if one is tilted either horizontally or vertically, which forces it having $n(A)$ way of tiling, and $n(A_{k - 1})$ in the other way (deleting that vertex). $\textbf{Remark in Notation.}$ In here, one could notice that $n(A-) = n(A_1)$ as well, as the last edge is the foundation of a stair, by letting it becomes the base of the stair of length $1$. Thus, by the above two subclaims, we could somehow associate each skeleton $A$ to two pairs of integers $(n(i), n(j))$ where $n(i) + n(j) = n(A)$. Therefore, we want to establish a bijection between: The number of integers less than $n(A)$ relatively prime to $n(A)$, which is basically the number of pairs of positive integers $(a,b)$ such that $a + b = n(A)$ and the number of tiling with $n(A)$ partitions. The first one is obviously $\varphi(n)$ by definition, then we just need to establish such bijection. $\textbf{Claim 01.}$ For every skeleton $A$, we can associate it with a number $(i,j)$ such that $\gcd(i,j) = 1$. Notice that we associate it using the way we define it just now. Notice that every skeleton is associated with $(n(X), n(Y))$ where $X \sim Y$. It suffices to prove the following claim. $\textbf{Claim.}$ If $A \sim B$, then $\gcd(n(A), n(B)) = 1$. Now, notice that as we define stair, one of the ends must be connected straight with an other edge (or possibly empty, when the whole skeleton is a stair). Now, we define $A_{-1}$ during situation like this since $A_1$ is $X - - $ for some skeleton $X$, and we define $A_{-1} = X$, $A_0 = X - = A$, and $A_1 = X - - $. One can easily check by induction that $n(A_k) = k \cdot n(A_{-1}) + n(A_0)$. We'll prove this by induction on $n(A_{-1})$. It is easy to check $n(A_{-1})$ for smaller cases $\le k$. Notice that $B = A_k$ for some $k \ge 1$. Then, $\gcd(n(A_{-1}), n(A_k)) = \gcd(n(A_{-1}), k \cdot n(A_{-1}) + n(A_0)) =1$ by induction claim, so this works. $\textbf{Claim 02.}$ For every integer $a,b$ such that $\gcd(a,b) = 1$. There exists unique pairs of skeletons $X,Y$ such that $X \sim Y$ and $n(X) = a, n(Y) = b$. $\textit{Proof.}$ First, we will prove this for $a,b$ such that $a < b < 2a$, and $\gcd(a,b) = 1$, and as a matter of fact, we'll proved that there exists $X_{-1}, X_0$ such that $n(X_{-1}) = a, n(X_0) = b$. Define $\mathcal{S}(i)$ as the set of skeletons with $i$ number of tilings. We want to prove that $|\mathcal{S}(i)| = \varphi(i)$ for all $i \in \mathbb{N}$. Now, we want to biject each $(a,b)$ to $(X_{-1}, X_0)$. Notice that both of the set has cardinality $\varphi(a + b)$. Then, it suffices to prove that the map is surjective to imply that it is bijective. To prove this, notice that $(X_0, X_1)$ satisfies the condition and this gives us $(b, a + b)$. Then, by induction, we are done. Now, notice that by adding sufficient stairs, we can cover all $(X_{-1}, X_k)$ with gcd still 1 and reaches all $(a, ka + b)$. Therefore, induct on the value of $X_{-1}$ will gives us the condition we want. $\textbf{Claim 03.}$ If $X \sim Y$, then there exists a unique skeleton $Z$ such that $Z$ could be associated with $(n(X), n(Y))$. To prove this, if $Y = X-$, then $Z = X--$. Otherwise, just construct using stair since by the previous claim of $(X_{-1}, X_k)$.

Solved with nukelauncher. Restrict our attention to broken lines that initially go to the right, i.e.\ that contain \((1,0)\). Let a staircase be a broken line such that each linear segment has length 1 and goes either up or to the right. Minimally divide each such broken line into staircases and label points \(A_0\), \(A_1\), \ldots, \(A_k\) between the staircases as shown in the example below. [asy][asy] size(6cm); defaultpen(fontsize(10pt)); pen pri=lightred+linewidth(1); pen sec=lightblue+linewidth(1); draw( (0,0)--(1,0)--(1,1)--(2,1)--(2,2)--(3,2), pri ); draw( (3,2)--(4,2), sec ); draw( (4,2)--(5,2)--(5,3)--(6,3), pri ); draw( (6,3)--(7,3), sec ); draw( (7,3)--(8,3)--(8,4), pri ); draw( (8,4)--(8,5)--(9,5)--(9,6), sec ); draw( (9,6)--(9,7)--(10,7), pri ); draw( (10,7)--(11,7)--(11,8), sec ); dot("\(A_0\)",(0,0),W); dot("\(A_1\)",(3,2),N); dot("\(A_2\)",(4,2),S); dot("\(A_3\)",(6,3),N); dot("\(A_4\)",(7,3),S); dot("\(A_5\)",(8,4),E); dot("\(A_6\)",(9,6),W); dot("\(A_7\)",(10,7),S); dot("\(A_8\)",(11,8),E); dot("\(A_8'\)",(11,7),SE); [/asy][/asy] For each point \(P\) on the broken line, let \(P'\) be the point immediately preceeding it. For illustration, \(A_8'\) is shown in the diagram above. For points \(P\), \(Q\) on the broken line, let \(|PQ|\) be the distance from \(P\) to \(Q\) along the broken line (i.e.\ the taxicab distance). For each point \(P\) on the broken line, let \(f(P)\) be the number of ways to domino-tile the worm corresponding to the portion of the broken line starting at \((0,0)\) and ending at \(P\). Claim: For any broken line, \(f(A_k)=f(A_k')+f(A_{k-1}')\) Proof. Assume without loss of generality the segment \(A_k'A_k\) is vertical. Then consider the orientation of the domino containing the top-right-most cell. If it is horizontal, then it suffices to domino-tile the worm of the broken line starting from \(A_0\) and ending at \(A_k'\). If it is vertical, then it uniquely determines several dominoes. In the example shown below, domino 1 implies 2 and 3, which in turn imply 4 and 5. Ultimately it suffices to domino-tile the worm of the broken line starting from \(A_0\) and ending at \(A_{k-1}'\). [asy][asy] size(5cm); defaultpen(fontsize(10pt)); pen pri=lightred+linewidth(1); pen sec=lightblue+linewidth(1); pen tri=heavygreen; pen tfil=invisible; pen qua=darkgreen; real t=0.2; void hori(pair P, string s) { filldraw( (P+(t,t))--(P+(2-t,t))--(P+(2-t,1-t))--(P+(t,1-t))--cycle, tfil,tri ); label(s,P+(1,.5),qua); } void vert(pair P, string s) { filldraw( (P+(t,t))--(P+(1-t,t))--(P+(1-t,2-t))--(P+(t,2-t))--cycle, tfil,tri ); label(s,P+(.5,1),qua); } vert( (11,7),"1"); vert( (10,7),"2"); hori( (10,6),"3"); vert( (9,6),"4"); hori( (9,5),"5"); draw( (7,5)--(8,5)--(8,6)--(9,6), pri ); draw( (9,6)--(10,6)--(10,7)--(11,7)--(11,8), sec ); dot("\(A_{k-2}\)",(7,5),W); dot("\(A_{k-1}'\)",(8,6),N); dot("\(A_{k-1}\)",(9,6),S); dot("\(A_k'\)",(11,7),E); dot("\(A_k\)",(11,8),N); [/asy][/asy] \(\blacksquare\) Claim: For any broken line, \begin{align*} f(A_{k-1}')&=f(A_k)-f(A_k')\\ f(A_{k-1})&=f(A_k)-|A_{k-1}A_k|\cdot f(A_{k-1}'). \end{align*} Proof. Repeatedly apply the first claim: note that \begin{align*} f(A_k)&=f(A_{k-1}')+f(A_k')\\ f(A_k')&=f(A_{k-1}')+f(A_k'')\\ f(A_k'')&=f(A_{k-1}')+f(A_k''')\\ &\;\vdots \end{align*}\(\blacksquare\) Now for positive integers \(m,n\ge2\), let \(g(m,n)\) be the number of broken lines \(\ell\) such that if the endpoints of \(\ell\) are \(A_0=(0,0)\) and \(A_k\) (here, \(k\) may vary), then \[f(A_k')=m\quad\text{and}\quad f(A_k)=n.\] Claim: For all \(m,n\ge2\), \[ g(m,n)= \begin{cases} 1&\text{if }n/2<m<n\text{ and }\gcd(m,n)=1,\\ 0&\text{otherwise}. \end{cases} \] Proof. It is easy to verify \(g(n-1,n)=1\) for all \(n\ge3\); they clearly represent broken lines with exactly one staircase. From the second claim, it is clear whenever \(n-m\ge2\) that \[g(m,n)=\sum_{c\ge1}g(n-m,n-c(n-m)).\]We will prove the claim by induction on \(m\), with base cases \(g(n-1,n)=1\) covered above. Evidently if \(m\ge n\), then \(g(m,n)=0\). Also if \(n/2\ge m\), then all terms on the right-hand side equal 0, so \(g(m,n)\ne0\) only if \(n/2<m<n\). Now if \(\gcd(m,n)\ne1\), then \(\gcd(n-m,n-c(n-m))=\gcd(m,n)\ne1\) for all \(c\), so \(g(m,n)=0\); if \(\gcd(m,n)=1\), then note that \[\frac{n-c(n-m)}2<n-m<n-c(n-m)\iff c+1<\frac n{n-m}<c+2\]occurs for exactly one positive integer \(c\), for which \(g(n-m,n-c(n-m))=1\) by the inductive hypothesis. Thus \(g(m,n)=1\). \(\blacksquare\) Finally, the number of broken lines that start to the right and whose worm can be domino-tiled in \(n\) ways is \[\sum_mg(m,n)=\frac{\varphi(n)}2.\]By symmetry, the number of broken lines that start in any direction whose worm can be domino-tiled in \(n\) ways is \(\varphi(n)\).

A hard but a super nice problem! Suppose WLOG that the last move was rightward. If we tile the $2 \times 2$ square which the last point is in it with a horizontal dominoe, by parity reasons there is an unique way to tile the largest staircase of the skeleton such that the last vertex is in it. $\qquad (\star)$ Otherwise, if we tile the $2 \times 2$ square containing the last vertex with a vertical dominoe, we may simply delete the last vertex and consider the remaining skeleton. $\qquad (\star \star)$ Thus, we get the recursion that for any skeleton $\mathcal{S}$, $$f(\mathcal{S})=f(A_{\mathcal{S}})+f(B_{\mathcal{S}}) \qquad (\spadesuit)$$where $A_{\mathcal{S}}$ is the remaining skeleton when we do $(\star)$, $B_{\mathcal{S}}$ is the remaining skeleton when we do $(\star \star)$, and $f(\mathcal{S})$ is the number of ways to tile any skeleton $\mathcal{S}$ with dominoes. Now, based on our recursion, we can draw the following tree (thanks SnowPanda for the code): [asy][asy] defaultpen(fontsize(11pt)); unitsize(0.9cm); pair P1 = (0, 0); void lp (string s, string a, pair P) { label(s, P); label(a, P, 1.5*dir(270)); } lp("$2$", "$ (1, 1 )$", P1); pair P2 = (-5, -1); pair P3 = (5, -1); lp("$3$", "$ (2, 1 )$", P2); lp("$3$", "$ (1, 2 )$", P3); pair P4 = (-7, -2); pair P5 = (-3, -2); pair P6 = (3, -2); pair P7 = (7, -2); lp("$5$", "$ (3, 2 )$", P4); lp("$4$", "$ (1, 3 )$", P5); lp("$4$", "$ (3, 1 )$", P6); lp("$5$", "$ (2, 3 )$", P7); pair P8 = (-8, -3); pair P9 = (-6, -3); pair P10 = (-4, -3); pair P11 = (-2, -3); pair P12 = (2, -3); pair P13 = (4, -3); pair P14 = (6, -3); pair P15 = (8, -3); lp("$8$", "$ (5, 3 )$", P8); lp("$7$", "$ (2, 5 )$", P9); lp("$5$", "$ (4, 1 )$", P10); lp("$7$", "$ (3, 4 )$", P11); lp("$7$", "$ (4, 3 )$", P12); lp("$5$", "$ (1, 4 )$", P13); lp("$7$", "$ (5, 2 )$", P14); lp("$8$", "$ (3, 5 )$", P15); draw(P2--P1--P3, gray); draw(P4--P2--P5, gray); draw(P6--P3--P7, gray); draw(P8--P4--P9, gray); draw(P10--P5--P11, gray); draw(P12--P6--P13, gray); draw(P14--P7--P15, gray); [/asy][/asy] where in the $k$-th row we have all the $2^k$ paths with size $k$, and for each skeleton $\mathcal{S}$, its left child is defined by being $\mathcal{S}+[\text{a single path rightwards}]$, and its right child is defined by being $\mathcal{S}+[\text{a single path upwards}]$. For each skeleton $\mathcal{S}$ on the tree, label it with $f(\mathcal{S})$. We want to prove that each integer $n$ appears exactly $\varphi (n)$ times on the tree. From $(\spadesuit)$, two neighbors on the tree are coprime $(\diamondsuit)$ (this can be easily proved via induction). Now, we prove the following claim: Claim: For each vertex labeled with $n$, its father is labeled with $m \in (\frac{n}{2},n)$ and $gcd(m,n)=1$. Proof: We use induction, the basecases are done. The $gcd$ condition is proved in $(\diamondsuit)$. From $(\spadesuit)$, $m<n \implies$ since $n-m$ comes before $m$ on the tree, $n-m<m \implies \frac{n}{2}<m$. $\qquad \square$ Observe that for each $m<n$ with $gcd(m,n)=1$, either $m$ or $n-m$ belongs to $(\frac{n}{2},n)$. This, there are exaclty $\frac{\varphi (n)}{2}$ numbers belonging to $(\frac{n}{2},n)$ which are coprime to $n$. Also, notice that for each $a \in \mathbb{N}$, there exist exactly $\frac{\varphi (a)}{2}$ positive integers $n$ such that $gcd(a,n)=1$ and $a \in (\frac{n}{2},n)$ $(\diamondsuit \diamondsuit)$, because either $a$ or $n-a<a$ satisfies the mentioned condition (both are coprime to $n$ by assumption). Now, we prove another claim: Claim: There aren't two pairs of neighbors on the same side of the tree that are equal. Proof: We use induction$^1$, the basecases are done. Suppose that we have two pairs of neighbors $(a_1,b_1)=(a_2,b_2)$, $a_1>b_1$, $a_2>b_2$. Note that the zigzag path starting form a vertex $v$ on the tree, labeled with $x$, it contains all the terms of the AP with initial term $x$ and ratio equals to the label of the father of $v$ $\qquad (\spadesuit \spadesuit)$. From the induction$^1$ hypothesis and $(\diamondsuit \diamondsuit)$, we can prove that the integers $m$ satisfying the induction$^1$ hypothesis also satisfie that its father is labeled with $m_0 \in (\frac{m}{2},m)$ and $gcd(m,m_0)=1$ (we prove it using the induction$^2$ hypothesis that claims that each father of a vertex $v$ labeled with $y$ is labeled with a number belonging to $(\frac{y}{2},y)$ and coprime to $y$). Thus, from the inductive$^2$ hypothesis, both $b_1$ and $b_2$ come from a zigzag path (otherwise $(b_1,c_1)=(b_2,c_2)$ (where $c_1,c_2$ are the father's label of $b_1,b_2$, respectively) or $\frac{a_1}{2}>a_1-b_1>\frac{a_1}{2}$, a contradiction), starting at some vertex $v_1,v_2$ with labels $l_1,l_2$, respectively. $\implies$ since $a_1=a_2$,$b_1=b_2$ and $a_1=b_1+l_1$, $a_2=b_2+l_2 \implies l_1=l_2 \implies$ due to $(\spadesuit \spadesuit)$, the fathers of $v_1,v_2$ have the same label, this contradicts the inductive$^1$ hypothesis. $\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \square$ Now, gathering the above claim with $(\diamondsuit \diamondsuit)$, we may prove that for each vertex $v$ labeled with $l$, its father is labeled with $l_0$ such that $gcd(l,l_0)=1$ and $l_0 \in (\frac{l}{2},l)$, and its children are labeled with $l_1,l_2$ such that $gcd(l,l_1)=gcd(l,l_2)=1$ and $l_1,l_2 \in (l,2l)$. We prove it via induction, the basecases are done. Assume that for all $n < N$, the inductive hypothesis holds and $n$ appears $\frac{\varphi (n)}{2}$ times on each side of the tree (another induction). Thus, consider $n_0 < N$ such that $n_0$ is coprime to $N$ and $n_0 \in (\frac{N}{2},N)$. From the inductive hypothesis, the children of all vertices labeled with $n_0$ on the same side of the tree belong to $(n_0,2n_0)$, and also $n \in (n_0,2n_0)$. From the previous claim and from $(\diamondsuit \diamondsuit)$, $n_0$ and $n$ must be neighbors exactly one time $(\heartsuit)$ $\qquad \implies N$ appears exactly $\frac{\varphi (N)}{2}$ times on each side of the tree and its fathers are all the $N_0 \in (\frac{N}{2},N)$ and $gcd(N,N_0)=1$. $\qquad \qquad \qquad \square$ Hence, using the above lemma and the same argument as in $(\heartsuit)$, we have that $n$ appears $\frac{\varphi (n)}{2}$ times on each side of the tree, totalizing $\varphi (n)$ on the whole tree, as desired. $\blacksquare$

We refer to the lattice path as the skeleton of the worm, which is composed of several bones (segments of length $1$). A limb of the skeleton refers to maximal contiguous segment of bones, i.e.\ the parts between the ``turns'' of the worms. This proof is divided into three parts. First we describe how to count the number of domino tilings of a given worm recursively in terms of the skeleton. Secondly, we use this to generate a infinite binary tree containing the data of the number of partitions. In the third part we extract the answer $\varphi(n)$. Part I: worm recursion. Consider the last segment in the skeleton, and WLOG it is upwards (by symmetry). Let $s$ denote the upper-rightmost square of the worm. We consider cases based on how $s$ is covered. [asy][asy] size(6cm); path skel = (0,0)--(3,0)--(3,1)--(7,1)--(7,2)--(8,2)--(8,3); pair p; pen wormfill = lightgrey; pen wormbound = lightblue; for (int i=0; i<=11; ++i) { p = relpoint(skel, i/arclength(skel)); filldraw(shift(p)*unitsquare, wormfill, wormbound); filldraw(shift(p)*shift(0,-1)*unitsquare, wormfill, wormbound); filldraw(shift(p)*shift(-1,0)*unitsquare, wormfill, wormbound); filldraw(shift(p)*shift(-1,-1)*unitsquare, wormfill, wormbound); } dotfactor *= 1.5; for (int i=0; i<=11; ++i) { p = relpoint(skel, i/arclength(skel)); dot(p); } draw(skel, black+1.5); label(scale(1.4)*"$s$", (8.5, 3.5), red); [/asy][/asy] If $s$ is covered by a horizontal domino, then the resulting shape is the worm whose skeleton merely has the last bone deleted. [asy][asy] size(6cm); filldraw(shift(8,3)*unitsquare, palered, red); filldraw(shift(7,3)*unitsquare, palered, red); path skel = (0,0)--(3,0)--(3,1)--(7,1)--(7,2)--(8,2); pair p; pen wormfill = lightgrey; pen wormbound = lightblue; for (int i=0; i<=10; ++i) { p = relpoint(skel, i/arclength(skel)); filldraw(shift(p)*unitsquare, wormfill, wormbound); filldraw(shift(p)*shift(0,-1)*unitsquare, wormfill, wormbound); filldraw(shift(p)*shift(-1,0)*unitsquare, wormfill, wormbound); filldraw(shift(p)*shift(-1,-1)*unitsquare, wormfill, wormbound); } dotfactor *= 1.5; for (int i=0; i<=10; ++i) { p = relpoint(skel, i/arclength(skel)); dot(p); } draw(skel, black+1.5); [/asy][/asy] Now suppose $s$ is covered by a vertical domino instead, the situation is more complex. When this occurs, certain dominoes are automatically ``forced''. After all such forced dominoes are placed, we get another worm. Its skeleton is obtained by first deleting every limb of length $1$ from the end until we reach a limb of length more than $1$ (there may be none), and then deleting two more bones from that limb. (If all limbs have length $1$, then the entire skeleton is destroyed.) An example is shown below where five dominoes are forced after the first (red) one is placed, and the resulting skeleton loses four bones. [asy][asy] size(6cm); filldraw(shift(8,3)*unitsquare, palered, red); filldraw(shift(8,2)*unitsquare, palered, red); filldraw(shift(7,3)*unitsquare, paleyellow, red); filldraw(shift(7,2)*unitsquare, paleyellow, red); filldraw(shift(6,2)*unitsquare, palegreen, red); filldraw(shift(6,1)*unitsquare, palegreen, red); filldraw(shift(7,1)*unitsquare, palecyan, red); filldraw(shift(8,1)*unitsquare, palecyan, red); filldraw(shift(6,0)*unitsquare, paleblue, red); filldraw(shift(7,0)*unitsquare, paleblue, red); path skel = (0,0)--(3,0)--(3,1)--(5,1); pair p; pen wormfill = lightgrey; pen wormbound = lightblue; for (int i=0; i<=6; ++i) { p = relpoint(skel, i/arclength(skel)); filldraw(shift(p)*unitsquare, wormfill, wormbound); filldraw(shift(p)*shift(0,-1)*unitsquare, wormfill, wormbound); filldraw(shift(p)*shift(-1,0)*unitsquare, wormfill, wormbound); filldraw(shift(p)*shift(-1,-1)*unitsquare, wormfill, wormbound); } dotfactor *= 1.5; for (int i=0; i<=6; ++i) { p = relpoint(skel, i/arclength(skel)); dot(p); } draw(skel, black+1.5); [/asy][/asy] In this way we can get a complete recursion which lets us effectively compute the number of domino tilings of each worm. Part II: the infinite tree. We now construct an infinite binary tree corresponding in the obvious way to choices of skeletons. The $0$th level has the trivial skeleton with zero bones; the $i$th level contains skeletons with $i$ bones. Going left in the tree corresponds to adding an ``right'' bone while going right in the tree corresponds to adding a ``up'' bone. The value of each vertex is the number of domino tilings of the corresponding worm. Now, given an edge $a \to b$ we annotate the edge with $b-a$. The left half of the tree is shown below (the right half is symmetric, thus omitted by ellipsis). [asy][asy] size(14cm); int[] vals = {3,5,4,8,7,5,7,13,11,9,12,9,6,10,11, 21,18,14,19,16,11,17,19,14,13,7,11,17,13,15,18}; int m; pair pos(int i) { if (i == 0) { return (0,0); } m = floor(log(i+1)/log(2)); return (2**(5-m)*(i-(2**m-1)*1.5), -3*m); } int j, l, d; for (int i=1; i<31; ++i) { m = floor(log(i+1)/log(2)); j = floor((i-1) / 2); draw(pos(i)--pos(j), dir(90), lightblue); d = vals[i] - vals[j]; if (i==2*j+1) { label("$"+(string) d+"$", midpoint(pos(i)--pos(j)), dir(135), lightred+fontsize(9pt)); } else { label("$"+(string) d+"$", midpoint(pos(i)--pos(j)), dir(45), lightred+fontsize(9pt)); } } for (int i=0; i<31; ++i) { if (i<=14) { dot("$"+(string)vals[i]+"$", pos(i), dir(90), blue); } else { dot("$"+(string)vals[i]+"$", pos(i), dir(-90), blue); } } pair O = (8,4); draw(O--pos(0), lightblue); label("$1$", O--pos(0), dir(135), lightred); pair P = (16, 0); draw(O--P, lightblue); label("$1$", O--P, dir(45), lightred); label("$\ddots$", P, dir(-45), blue); dot("$2$", O, dir(90), blue); pen wormfill = lightgrey; pen wormbound = lightblue; picture worm(path skel, int ind) { picture pic; pair p; for (int i=0; i<=arclength(skel); ++i) { p = relpoint(skel, i/arclength(skel)); filldraw(pic, shift(p)*unitsquare, wormfill, wormbound); filldraw(pic, shift(p)*shift(0,-1)*unitsquare, wormfill, wormbound); filldraw(pic, shift(p)*shift(-1,0)*unitsquare, wormfill, wormbound); filldraw(pic, shift(p)*shift(-1,-1)*unitsquare, wormfill, wormbound); } for (int i=0; i<=arclength(skel); ++i) { p = relpoint(skel, i/arclength(skel)); dot(pic, p); } draw(pic, skel, black+1.5); return shift(pos(ind))*scale(0.4)*pic; } add(shift(0.8,0.4)*worm( (0,0)--(2,0)--(2,1), 4 )); add(shift(-1.7,0.4)*worm( (0,0)--(1,0)--(1,1)--(2,1), 5 )); add(shift(-2.5,0.5)*worm( (0,0)--(4,0), 7 )); add(shift(-1.9,0.5)*worm( (0,0)--(1,0)--(1,1)--(3,1), 11 )); add(shift(-1.2,0.5)*worm( (0,0)--(1,0)--(1,2)--(2,2), 13 )); [/asy][/asy] Given a vertex $v$ other than the root, define its signature is the ordered pair $(a,b)$ where $b$ is the value of its parent and $a$ is the value of the ordered pair joining it. The signature of the root vertex is considered to be $(1,1)$. Then, if we translate our work from Part I, we find that the recursion rewrites in the following way. Claim: Let $v$ be a vertex with signature $(a,b)$ and value $n = a+b$. If the parent of $v$ was to its left, then The left child of $v$ has value $n+a$, hence has signature $(a,a+b)$. The right child of $v$ is $n+b$, hence has signature $(b,a+b)$. The bullets are swapped if $v$ had parent to its right. Part III: answer extraction. Now that we have the tree, we note that the Euclidean algorithm appears in the form $(a,b) \mapsto (a,a+b)$ and $(a,b) \mapsto (b,a+b)$. So the previous claim can be rephrased as saying: Claim: Whenever $a \le b$ and $\gcd(a,b) = 1$, exactly one vertex in the left half of the tree has signature $(a,b)$. In particular, $n$ appears $\varphi(n)$ times for $n > 2$, since the value at each vertex is the sum of labels. Remark: The recursion may initially seem quite uncompelling given that is yielding Fibonacci numbers, which seem unrelated to the Euler phi $\varphi$ other than using the same Greek letter. The binary tree helps a lot for better visualizing what is going on. The first hint comes when one finds the chain $1 \to 2 \to 3 \to \dots$ and $1 \to 3 \to 5 \to \dots$ which respectively get all integers and all odd integers; one continues to work from there.

First, we introduce relevant notation. For a skeleton $S$, let $f(S)$ be the number of tilings of its worm. Additionally, let $S'$ be the largest sub-skeleton of $S$ that ends with a segment in a different direction that for $S$. Let $s$ be the endpoint of $S$. Let the point $t$ of $S$ be defined as the point that precedes $s$ if $S$ ends with two segments of the same direction, and the point 1 unit left and 1 unit down of $s$ if $S$ ends with two segments of different directions. Let $S''$ be the portion of $S$ starting at $(0, 0)$ and ending at $t$. WLOG, suppose that the last segment of the skeleton is rightwards. Consider the $2 \times 2$ square whose center is the endpoint of the skeleton. We consider the orientation of the domino tiling for this square. Now we do casework on the possible tilings of the square in order to find a useful recurrence for $f$. If the long sides of the dominoes are vertical, then this contributes $f(S')$ tilings. If the long sides of the dominoes are horizontal, then this contributes $f(S'')$ tilings. Thus we have the recurrence $f(S) = f(S')+f(S'')$. Now construct an infinite binary tree with root $(1, 1)$ so that node $(a, b)$ has children $(a+b, b)$ and $(a, a+b)$, thus generating all coprime pairs of positive integers. Define the skeleton $S_u$ for a node $u$ of the tree as follows: Let $S_{(1, 1)}$ denote the skeleton induced by the point $(0, 0)$. Let $S_{(a+b, b)}$ be the skeleton induced by adding a horizontal segment to $S_{(a, b)}$. Let $S_{(a, a+b)}$ be the skeleton induced by adding a vertical segment to $S_{(a, b)}$. Label each node $u$ with $f(S_u)$, and note that $(1, 1)$ is labeled with $2$. By induction, it follows that $(a, b)$ is labeled with $a+b$, as the inductive step follows from the tiling recursion. Thus it suffices to show that the number of solutions in positive integers to $a+b=n$ where $\gcd(a, b)=1$ is $\varphi(n)$, but this is clear since this is equivalent to enumerating $0<a \leq n$ such that $\gcd(a, n)=1$, and we are done.