El itinerante de rotación requiere de $6$ robótica cavilaciones. He aquí por qué:
La operación
$$\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$ para evitar que el equipo de búsqueda (cada factor en el lado derecho debe ocurrir en algún factor en el lado izquierdo, y cada factor en el lado izquierdo que no ocurre en el lado derecho debe ser cancelado por algún factor en la otra fila), pero yo no llegué a ningún lado.
En una nota final, esto pone de relieve Qiaochu del dictamen que uno debe tratar de reducir las cosas al álgebra lineal porque álgebra lineal es más fácil que la mayoría de las otras cosas.
Aquí está el código de Java. Utiliza números enteros de 64 bits y comprueba el desbordamiento, pero resulta que el mayor número formado nunca encajaría en 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);
}
}
