Suppose I had a little robot on the coordinate grid that moves according to the following rule. If it's at the point $(x,y)$, it can move to either $(x+y,y)$ or $(x,x+y)$. If the robot starts at the point $(6,21)$ and can make any number of moves, what points could the robot go to?
2
-
2$\begingroup$ For any particular destination point it is easy to check whether it can be reached, as explained in the answers to this stackoverflow post. $\endgroup$– Jaap ScherphuisFeb 22, 2021 at 8:02
-
5$\begingroup$ I’m voting to close this question because it is an ongoing contest. See spcsonlineapp.stanford.edu/apply/SUMAC/… $\endgroup$– WhatsUpFeb 26, 2021 at 15:22
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
From (6,21) the robot can either go to (27,21) or (6,27). Another turn after that, the robot will be at either (48,21), (27, 48), (33, 27) or (6, 33). Because these numbers have no way of ever decreasing, the robot can go to any point (6a+21b,6c+21d) where a, b, c and d are all positive integers, b and c being larger than 0. Hope this answers your question!
-
5$\begingroup$ It can't go to (27, 27), though (a=b=c=d=1) $\endgroup$– justhalfFeb 22, 2021 at 6:58
-
$\begingroup$ hmm, your right... i'll have to rethink what ive said. $\endgroup$ Feb 22, 2021 at 7:57
$\begingroup$
$\endgroup$
8
Since $x$ and $y$ are positive, $x+y$ is always greater than $x$ and $y$ - this means that undoing a move always involves decreasing the greater coordinate by some multiple of the lesser.
This should remind you of the Euclidean Algorithm. If the greatest common divisor of $x$ and $y$ is not $3$, you can't get there from $(6,21)$ because the algorithm always preserves GCD.
Consider the fraction $\frac{x}{y}$, and take its continued fraction expansion.
Our destination is $(6,21)$, which corresponds to $3+\frac{1}{2}$: if the second-last number in the continued fraction is less than 3* or the last number is greater than 2, the Euclidean Algorithm can't get us where we need to go.
*the beginning 3 merely has to be dominated since other paths can join $(6,21)$'s path from two directions - all further terms have to be matched exactly.
If the desired point was $(204,39) \leftrightarrow 5+\frac{1}{4+\frac{1}{3}}$ instead, $8+\frac{1}{4+\frac{1}{3}}$ would be a valid path but $5+\frac{1}{5+\frac{1}{3}}$ would not.
However, since the destination is not on the diagonal, order matters. The position of the greater coordinate changes at every level of the continued fraction, and we want the final $2$ to correspond to the $y$-coordinate. Therefore, for any pair that hasn't already been ruled out at this point, it can be reached from $(6,21)$ if and only if the fraction has odd length and the $x$-coordinate is larger of the fraction has even length and the $y$-coordinate is larger - otherwise, you'll reach $(21,6)$ instead.
In summary, the reachable points $(a,b)$ satisfy the following criteria:
- $\text{GCD}(a,b) = 3$.
- The continued fraction of $\frac{a}{b}$ ends in $\cdots+\frac{1}{3+x+\frac{1}{2}}$.
- (The continued fraction of $\frac{a}{b}$ has odd length) XOR $y>x$.
-
$\begingroup$ Your last sentence seems to suggest than any (x,y) with gcd 3 can be reached from either (6,21) or (21,6). Is that what you are saying? $\endgroup$– hexominoFeb 22, 2021 at 16:02
-
$\begingroup$ Apologies, I can see where "the above criterion" would cause some confusion: hopefully this works better. $\endgroup$ Feb 22, 2021 at 16:07
-
1$\begingroup$ Sorry, I'm still a little confused about the criteria. In the (204,39) example would you say that this is ruled out because the last number in the continued fraction expansion is greater than 2? $\endgroup$– hexominoFeb 22, 2021 at 16:21
-
$\begingroup$ Are you using (204,39) as an example of a potential destination point that we want to check is reachable from (6,21), or are you using it as a hypothetical different starting point instead of (6,21)? Calling (6,21) a destination is confusing. $\endgroup$ Feb 22, 2021 at 16:41
-
$\begingroup$ " This should remind you of the EA." I would go so far as to say it is the EA back-to-front. Also, I was wondering are you using CFs as anything more than a "summary of EA steps"? Are there any fancy CF properties that can be used? If not, what is gained over using EA directly (which has the advantage that gcd need not be registered separately)? Am I missing something? $\endgroup$ Feb 22, 2021 at 22:57