¿Por qué termina este procedimiento? ¿O hay números para los que no?

Question

Yo realmente no tienen una buena educación formal en matemáticas teóricas, así que por favor no se moleste si esta es la pregunta obvia, pero por otro lado no creo que yo soy el primero en pensar de tal problema. Así que vamos a p,q ser números Naturales p != 0 (vamos a pensar en ellos como un dividendo y el divisor de una fracción) y el procedimiento se ve más o menos así:

f(p,q): 
if (gcd(p,q) > 1) return f(p/gcd(p,q), q/gcd(p,q))
if (p/q > 1/3) then return f(p+1, q+4)
if (p/q < 1/3) then return f(p+1, q+1)
if (p/q == 1/3) then return WIN

para el caso de que se debe terminar en algún número infinito de pasos es intuitivo: cuando estamos de más de 1/3 de que el paso hacia 1/4 y si somos más pequeños, damos un paso hacia 1. La ejecución de un script determinado resultado que para todos los pares de números (hasta el 5 de dígitos decimales en tamaño) termina en algún momento, así que mi pregunta es "¿alguien Puede demostrar que este procedimiento termina después de algún número finito de pasos y no los bucles infinitamente para cualquiera de los números p y q, como se describe?"

Answer 1

Deje $(p_n, q_n)$ ser la consecuencia generada, y considerar la posibilidad de $d_n = 3p_n - q_n$.

Caso 1: Si $d_n = 0$ para algunos $n$ entonces $\frac{p_n}{q_n} = \frac 13$, es decir, la recursión termina después de más de un paso más.

Caso 2: Si $d_n < 0$ entonces $\frac{p_n}{q_n} < \frac 13$y $$ d_{n+1} = 3(p_n + 1) - (q_n + 1) = d_n + 2 > d_n $$ si $\gcd(p_n, q_n) = 1$, de lo contrario $$ d_{n+1} = \frac{d_n}{\gcd(p_n, q_n)} > d_n \, . $$ Así que mientras a $d_n < 0$, la secuencia de $(d_n)$ es estrictamente creciente secuencia de números enteros, lo que significa que eventualmente $d_n = 0$ o $d_n > 0$.

Caso 3: Si $d_n > 0$ entonces $\frac{p_n}{q_n} > \frac 13$y $$ d_{n+1} = 3(p_n + 1) - (q_n + 4) = d_n - 1 < d_n $$ si $\gcd(p_n, q_n) = 1$, de lo contrario $$ 0 < d_{n+1} = \frac{d_n}{\gcd(p_n, q_n)} < d_n \, . $$ Así que mientras a $d_n > 0$, la secuencia de $(d_n)$ es estrictamente decreciente, y el tiempo llega a cero. (Tenga en cuenta que $d_{n+1}$ no puede llegar a ser negativa.)

Así, en todos los casos $d_n = 0$ finalmente, lo que demuestra que la recursión termina siempre. Concretamente:

• Si $\frac pq = \frac 13$ , a continuación, la recursión termina después de más de un paso (dividiendo por el $\gcd$). Ejemplo: $$ (2, 6) \a (1, 3) $$
• Si $\frac pq < \frac 13$ , a continuación, la recursión termina después de que en la mayoría de los $$ \left\lceil \frac{p-3p}{2}\right\rceil + 2 $$ pasos: $\left\lceil \frac{q-3p}{2}\right\rceil$ pasos para alcanzar un estado con $\frac pq \ge \frac 13$, posiblemente un paso más para llegar a un estado con $\frac pq = \frac 13$, y, posiblemente, un paso más para dividir por la $\gcd$. Ejemplo: $$ (1, 6) \a (2, 7) \a (3, 8) \a (4, 12) \a (1, 3) $$
• Si $\frac pq > \frac 13$ , a continuación, la recursión termina después de que en la mayoría de los $$ 3p - q + 1 $$ pasos: $3p-q$ pasos para alcanzar un estado con $\frac pq = \frac 13$, y, posiblemente, un paso más para dividir por la $\gcd$. Ejemplo: $$ (3, 7) \a (4, 11) \a (5, 15) \a (1, 3) $$

Los ejemplos muestran que los límites son la mejor forma posible.

Answer 2

Vamos a caminar hacia atrás desde el final de resultado: $3x-y=0$ (ambos $x$ e $y$ son enteros).

A partir de cualquier $x$ e $y$ la lógica es la siguiente: cuando $3x - y <0$, añadimos un tanto $x$ e $y$ por lo que la convierte en la expresión de $3x+3-y-1=3x-y+2$. Aumento del $2$ hemos conseguido $0$ o de pasarse por $1$.

Cuando $3x-y>0$ añadir uno a $x$ y añadimos $4$ a $y$ por lo que la convierte en la expresión de $3x+3-y-4=3x-y-1$. Ahora es obvio que no podemos perder de cero como somos la disminución de la expresión por uno hasta llegar a cero.

La lógica que implica MCD sólo acelera el proceso a medida que se reduce el $p$ e $q$, usted realmente no necesita para conseguir la victoria.