Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

USAMTS 6/2/22 states:

The roving rational robot rolls along the rational number line. On each turn, if the robot is at $\frac{p}{q}$, he selects a positive integer $n$ and rolls to $\frac{p+nq}{q+np}$. The robot begins at the rational number 2011. Can the roving rational robot ever reach the rational number 2?

Now, of course, I know it is true (I proved it and got the answer correct). However, I'm interested to see whether or not the robot can move from 2011 to 2 in four steps. I know it must move an even number of steps and cannot move in two steps, but that's as far as I was able to prove. I was able to find a set of six steps, so I know six is possible ($\displaystyle 2011 \rightarrow \frac{1}{671} \rightarrow 111 \rightarrow \frac{1}{23} \rightarrow 7 \rightarrow \frac{1}{3} \rightarrow 2$ works).

Is a set of four steps even possible? I figured out that for all $n > 2$, it is possible to move from $\frac{n-2}{2n-1}$ to 2 (with the robot using that same $n$). However, I have not been able to extend all the way from 2011 to that, even with a lot of time brute forcing in Mathematica.

share|improve this question
    
For sake of those who don't see the inner works of the six steps you took, can you post them in a clearer way, stating what $\frac{p}{q}$ you have chosen, and which $n$ did you choose at each step? (There is no mention whether or not $p,q$ are co-prime or just integers). –  Asaf Karagila Apr 22 '11 at 20:51
    
submissions.usamts.org/Year22/Round2/… This is the entirety of my round 2 solutions, so you want the last two pages. The first page of the solution is actually solving the problem, while the second page is proving that 2 steps is impossible. The first page will describe the method I used to get the six steps! –  Eugene Bulkin Apr 22 '11 at 20:53
2  
@Asaf, it doesn't matter, the thing is scale invariant. –  quanta Apr 22 '11 at 20:55
    
@quanta: Oh, right. The choice of $n$ still matters, I guess, and I do not see it right away (nor I feel like I will see it anytime soon due to lack of motivation and time to find those numbers by myself) –  Asaf Karagila Apr 22 '11 at 20:59
1  
@Michael it doesn't matter. If $p$ and $q$ share a factor, it would be factored out of the movement anyway. For the ease of computation, you can work with $p$ and $q$ relatively prime. –  Eugene Bulkin Apr 22 '11 at 21:27
show 2 more comments

2 Answers 2

up vote 21 down vote accepted

The roving rotation requires $6$ robotic ruminations. Here's why:

The operation

$$\frac{p}{q}\to\frac{p+qn}{q+pn}$$

acts linearly on the numerator and denominator, so we can write it like this:

$$\left(p \atop q\right)\to\left(\begin{array}{cc}1&n\\n&1\end{array}\right)\left(p\atop q\right)\;.$$

The eigenvectors of this transformation are independent of $n$; they correspond to the sum and difference of $p$ and $q$:

$$\left(p+q \atop p-q\right)\to\left(\begin{array}{cc}n+1&0\\0&1-n\end{array}\right)\left(p+q\atop p-q\right)\;.$$

Thus, we can simultaneously diagonalize all the transformations by working in this eigensystem. (By the way, that explains the commutativity that Ross noted.) For the initial state, $p+q=2012$ and $p-q=2010$, and for the final state, $p+q=3k$ and $p-q=k$ for some $k\in\mathbb N$. Thus, we are looking for $n_1, n_2, n_3, n_4$ and $k$ such that

$$\prod_{i=1}^4\left(\begin{array}{cc}n_i+1&0\\0&n_i-1\end{array}\right)\left(2012\atop2010\right)=k\left(3\atop1\right)\;.$$

Forming the quotient of the top and bottom row yields

$$\prod_{i=1}^4\frac{n_i+1}{n_i-1}=3\cdot\frac{2010}{2012}\;.$$

This implies $n_i>2$, since $(2+1)/(2-1)=3$ alone would make the product come out too large. Further, if the four factors on the left are to form the product on the right, at least one of them has to be greater or equal to the fourth root of the right-hand side. Without loss of generality, we can assume $n_1\le n_2\le n_3\le n_4$, so we have $(n_1+1)/(n_1-1)\ge\sqrt[4]{3\cdot2010/2012}\approx1.32$, leading to $n_1<8$. That leaves only five values of $n_1$ to be tested. Repeating the same considerations for $n_2$ and $n_3$ (taking cubic and square roots, respectively, of the remaining factor to bound them), we obtain an efficient way to test all possibilities by computer. This only requires a triple loop, since in the end we can solve for $n_4$ without looping. The inner loops may require more iterations than the outer one, since low values of $n_1$ bring the product close to the target and thus raise the bounds for $n_2$ and $n_3$, but the highest number that ever needs to be tested for $n_3$ is $58$, and in total the innermost check for $n_4$ only has to be performed $183$ times. No solutions are found, and so the shortest solution must use $6$ steps. (Of course this approach also provides an efficient way to search for solutions in $6$ steps, of which there are hundreds of inequivalent ones.)

I tried reasoning about the prime factorizations of $n-1$ and $n+1$ to avoid the computer search (every factor on the right-hand side must occur in some factor on the left-hand side, and every factor on the left-hand side that doesn't occur on the right-hand side must be canceled by some factor in the other row), but I didn't get anywhere.

On a final note, this underscores Qiaochu's dictum that one should try to reduce things to linear algebra because linear algebra is easier than most other things.

Here's the Java code. It uses 64-bit integers and checks for overflow, but it turns out the highest number ever formed would fit into 32 bits.

public class RovingRotationalRobot {
    static int count = 0;
    static long maxOperand;
    static long maxProduct;
    static long maxTested;

    public static void main (String [] args) {
        recurse (3 * 2010,2012,4,0);
        System.out.println (count + " tests performed");
        System.out.println ("maximal value   : " + maxTested);
        System.out.println ("maximal operand : " + Long.toHexString (maxOperand));
        System.out.println ("maximal product : " + Long.toHexString (maxProduct));
    }

    private static void recurse (long num,long den,int depth,long lim) {
        long min = (num + den) / (num - den) + 1;

        checkOverflow (min+1,den);
        checkOverflow (min-1,num);

        boolean between = 
            (min - 1) * num > (min + 1) * den &&
            (min - 2) * num < (min + 0) * den;

        if (!between)
            throw new Error (depth == 1 ? "hit" : "error");

        if (depth == 1) {
            count++;
            return;
        }

        double root = Math.pow (num / (double) den,1./depth);
        long max = (long) ((root + 1) / (root - 1));
        maxTested = Math.max (maxTested,max);

        min = Math.max (min,lim); // don't have to test numbers below the earlier ones

        // double-check with integer arithmetic that the next integer would make the product too small
        long next = max + 1;
        long succ = next + 1;
        long pred = next - 1;
        long s = 1;
        long p = 1;
        for (int i = 0;i < depth;i++) {
            checkOverflow (s,succ);
            checkOverflow (p,pred);
            s *= succ;
            p *= pred;
        }
        checkOverflow (s,den);
        checkOverflow (p,num);

        if (s * den >= p * num)
            throw new Error ("rounding error");

        for (long n = min;n <= max;n++) {
            checkOverflow (num,n-1);
            checkOverflow (den,n+1);
            long newNum = num * (n - 1);
            long newDen = den * (n + 1);
            long gcd = gcd (newNum,newDen);
            recurse (newNum / gcd,newDen / gcd,depth - 1,n);
        }
    }

    public static long gcd (long p,long q) {
        if (p < q) {
            long tmp = p;
            p = q;
            q = tmp;
        }

        for (;;) {
            long r = p % q;
            if (r == 0)
                return q;
            p = q;
            q = r;
        }
    }

    static void checkOverflow (long a,long b) {
        maxOperand = Math.max (maxOperand,a);
        maxOperand = Math.max (maxOperand,b);
        maxProduct = Math.max (maxProduct,a*b);
    }
}
share|improve this answer
4  
Such a good answer!! cool! –  quanta Apr 23 '11 at 13:44
    
AWESOME solution. if only I understood the workings of the problem well enough to come to that linear algebra conclusion! –  Eugene Bulkin Apr 23 '11 at 21:03
    
This is a model answer. –  The Chaz 2.0 Apr 20 '13 at 23:56
add comment

Not an answer, but maybe some help. It turns out your steps commute. That is, instead of using $(1007,133,29,10,5,5)$ you use $(5,5,10,29,133,1007)$ (or any other order) you get to $2$ as well. If the integers you use are $(n_1,n_2,n_3,n_4),$ after the four iterations you are at $\frac{2011(1+e_2+e_4)+(e_1+e_3)}{(1+e_2+e_4)+(e_1+e_3)2011}$, where $e_i$ is the $i^{\text{th}}$ degree symmetric polynomial. For example, $e_2=n_1n_2+n_1n_3+n_1n_4+n_2n_3+n_2n_4+n_3n_4$ Setting this equal to $2$ gives $2009(1+e_2+e_4)=4021(e_1+e_3)$. This will allow you to set bounds on the search-if the $n$'s are too large, $e_4$ will be too much larger than $e_3$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.