$\Theta \rho ϵ\eta \Pi \alpha \tau \pi$

Let ${𝚜𝚕𝚘𝚠\mathrm{𝟷}}_k$ be the value of $𝚜𝚕𝚘𝚠\mathrm{𝟷}$ at the end of the $k$-th iteration of the while loop. Observe that $g_k={𝚜𝚕𝚘𝚠\mathrm{𝟷}}_t$, this holds true for $k=0$ as well where we have $g_0=0={𝚜𝚕𝚘𝚠\mathrm{𝟷}}_0$, note that the equality holds true as each iteration of the while loop directly pertains the recursive definition of $g_{i+1}$, moreover note that ${𝚏𝚊𝚜𝚝}_k=g_{2k}$ which can be verified in a similar manner. Note that this means that $𝚏𝚊𝚜𝚝$'s movement sequence is a subsequence of $𝚜𝚕𝚘𝚠\mathrm{𝟷}$'s denote this subsequence $\text{ 𝐬 }:=(s_0,s_1,s_2,\dots )$ where $s_i=g_{2i}$ then we know that ${𝚏𝚊𝚜𝚝}_k=s_k$.

Let $G$ be the index array graph of $A$, we know that it has a cycle that it gets stuck in forever, and suppose that the elements of the cycle are given by $C=(c_0,c_1,\dots ,c_k)$, where $c_0$ is the meet value.

Consider the smallest index $x$ where $g_x$ and $s_x$ are both in $C$ for the first time. Since the start of the cycle is the meet value, then we know that $g_x=c_0$ whereas $s_x=c_i$ where $i\in {\mathbb{N}}_0$

Since $C$ is a cycle of length $k+1$ and $𝚏𝚊𝚜𝚝$ traverses $C$ at twice the speed of $𝚜𝚕𝚘𝚠\mathrm{𝟷}$, (which is to say that $g_{x+y}=c_{(0+y)\%k+1}$ and $s_{x+y}=c_{(y+2y)\%k+1}$) in tandem with the fact that all elements in the cycle are distinct and thus we know that $c_a=c_b$ if and only if $a\%(k+1)=b\%(k+1)$, we conclude that $g_{x+y}=s_{x+y}$ when $y\equiv i+2y(\mathrm{mod}k+1)$, where $y$ is the $y$-th iteration after $𝚜𝚕𝚘𝚠\mathrm{𝟷}$ and $𝚏𝚊𝚜𝚝$ are both in $C$ for the first time.

Rearranging shows $y\equiv -i(\mathrm{mod}k+1)$, if $i=0$, then this is satisfied by $y=0$ which means that when both $𝚜𝚕𝚘𝚠\mathrm{𝟷}=c_0=𝚏𝚊𝚜𝚝$ when they enter the cycle for the first time. On the other hand if $i>0$ then $y=k+1-i$ satisfies the equation. Note that there are infinitely other non-negative solutions, but these two solutions are the smallest ones, thus the while loop will encounter these first before any larger ones and terminate, thus $y\in \{0,\dots ,k\}$.

Assume the first while loop terminates after $t$ iterations.

Let $G$ be the index array graph of $A$. By Corollary: All Index Array Graphs have A Cycle Continuing Forever, $G$ has a cycle $C=(c_0,c_1,\dots ,c_k)$. Without a loss of generality, assume $c_0=g_x$. Let $\text{𝐠}=(g_0,g_1,g_2,\dots )$ be the movement sequence of $G$. Now, let $y\in {\mathbb{N}}_0$ be the smallest number such that $g_{x+y}={𝚜𝚕𝚘𝚠\mathrm{𝟷}}_t$ at iteration $t$ (i.e., termination) of the first while loop. Finally, let $z\in {\mathbb{N}}_0$ be the smallest number such that $g_{x+y+z}=c_0$. It is worth noting that $y+z=k+1$, thus $y+z$ is the length of $C$.

We know that the first while loop terminates at iteration $t=x+y$ . Since ${𝚏𝚊𝚜𝚝}_t={𝚜𝚕𝚘𝚠\mathrm{𝟷}}_{2t}$ at iteration $t$, we know ${𝚏𝚊𝚜𝚝}_{x+y}={𝚜𝚕𝚘𝚠\mathrm{𝟷}}_{2(x+y)}=g_{2(x+y)}$. Therefore, we can say that upon termination of the first while loop, $𝚏𝚊𝚜𝚝$ has travelled $2(x+y)$ nodes into $\text{𝐠}$.

For an alternative but equivalent statement of this fact, assume $𝚏𝚊𝚜𝚝$ completes $n$ full cycles around $C$ by iteration $t$. Then, ${𝚏𝚊𝚜𝚝}_t=g_{x+n(k+1)+y}=g_{x+n(y+z)+y}$. Hence, we can also say that upon termination of the first while loop, $𝚏𝚊𝚜𝚝$ has travelled $x+n(y+z)+y$ nodes into $\text{𝐠}$.

These two equivalent statements brings us to the following result. $$\begin{array}{cc}2(x+y)& =x+n(y+z)+y\\ 2x+2y& =x+(n+1)y+nz\\ x& =(n-1)y+nz\\ x& =(n-1)(y+z)+z\\ x& =(n-1)(k+1)+z\end{array}$$ Therefore, travelling $x$ nodes into $\text{𝐠}$ is equivalent to completing $n-1$ complete cycles around $C$ and travelling another $z$ nodes.

Now consider the second while loop. On iteration 0, $𝚜𝚕𝚘𝚠\mathrm{𝟷}=g_{x+y}$ and $𝚜𝚕𝚘𝚠\mathrm{𝟸}=g_0$. Now consider iteration $x$. On iteration $x$, $𝚜𝚕𝚘𝚠\mathrm{𝟷}=g_{x+y+x}$. $$\begin{array}{cc}{g}_{x+y+x}& =g_{x+y+(n-1)(k+1)+z}\\ & =g_{x+(y+z)+(n-1)(k+1)}\\ & =g_{x+(k+1)+(n-1)(k+1)}\\ & =g_{x+n(k+1)}\end{array}$$ Given $g_x$ is in $C$, $g_{x+y+x}$ is just $n$ complete cycles around $C$ from $g_x$. Therefore, $g_{x+y+x}=g_x$. On iteration $x$, we also trivially know $𝚜𝚕𝚘𝚠\mathrm{𝟸}=g_x$. Hence, $𝚜𝚕𝚘𝚠\mathrm{𝟷}=𝚜𝚕𝚘𝚠\mathrm{𝟸}$ so the second while loop terminates, and upon termination, $𝚜𝚕𝚘𝚠\mathrm{𝟷}=g_x$.

By definition of the meet value, it is encountered twice in the movement sequence $\text{ 𝐠 }:=(g_0,g_1,g_2,\dots )$ on it's first encounter, we have some index $i$ such that $g_i=m$ by the definition of the movement sequence this means that $A\left[g_{i-1}\right]=m$ so that $g_{i-1}$ is the index of $m$ in $A$

On the second encounter of $m$ in the movement sequence we have some $j$ where $(j>i)$ such that $g_j=m$ so also that $A\left[g_{j-1}\right]=m$. Now note that with respect to the movement sequence, we have the following subsequence $g_{i-1},m,\dots ,g_{j-1},m$, if $g_{i-1}=g_{j-1}$ then we get contradiction because by the definition of the meet value $g_j=m$ it's assumed that $j$ was the smallest value such that $(g_0,\dots ,g_m)$ has a duplicated value, but under the assumption that $g_{i-1}=g_{j-1}$ then $j-1$ would be a smaller value such that $(g_0,\dots ,g_{j-1})$ has a repeated value, therefore we must have that $g_{i-1}\ne g_{j-1}$.

Recall that $A\left[g_{i-1}\right]=A\left[g_{j-1}\right]=m$ therefore $m$ is duplicated in $A$ . Since $A$ contains exactly one duplicated element, then we must conclude that $d=m$.