Dado $n$, encontrar $2$ enteros positivos $a,b$ tal que $a+b=n$ y $LCM(a,b)$ es lo mínimo posible

Aug 16 2020

Este es un problema en un concurso anterior de matemáticas / codificación.

Rompí esto en $2$ casos: $n$ es par o $n$es impar. Cuando$n$ es par, eso significa que $a=b=n/2$, porque, intuitivamente, si tomamos $a < n/2$ (WLOG), luego $b > n/2$, y entonces $LCM(a,b) \ge b > n/2$.

Cuando $n$es extraño, no pude averiguar cómo hacerlo. La única forma que se me ocurrió fue aplicar la fuerza bruta a todos los valores de$a$ (nuevamente, WLOG) de $1$ hasta $n/2$, pero esto es demasiado lento cuando $n$ es largo.

Cualquier ayuda será muy apreciada.

Respuestas

1 JCAA Aug 16 2020 at 02:01

La respuesta es $a=k, b=n-k$ por extraño $n>1$ y el más grande propio (es decir, $<n$) divisor $k$ de $n$ y $a=b=n/2$ incluso para $n$.

Prueba. Suponer$n$ es impar, $k+(n-k)$ es la descomposición de $n$ con los mas pequeños $LCM(k, n-k)$. Caso 1. Si$k$ divide $n$ luego se divide $n-k$ y el $LCM$ es $n-k$, entonces en este caso es mejor tomar $k$ ser el divisor propio más grande de $n$. Caso 2. Si$k$ no divide $n$, entonces no divide $n-k$, entonces el $LCM$ es $k(n-k)/gcd(n,k)$. Dejar$k/gcd(n,k)=m$. Dejar$gcd(n,k)=d$. Entonces$k=md$. Entonces la descomposición es$md+(n-2d)$ y el $LCM$ es $m(n-2d)=mn-2md$. Para ser mínimos deberíamos tener$mn-2md<n-d$, entonces $(m-1)n<(2m-1)d$, $d>((m-1)/(2m-1))n$. Pero desde$n$ es impar y divisible por $d$ eso implica $n\ge 3d$, entonces $3(m-1)/(2m-1)<1$, $m<3$ entonces $m=2$, que conduce fácilmente a una contradicción. Por lo tanto, el LCM mínimo se alcanza en el Caso 1 cuando$k$ es el más grande adecuado$\ne n$) divisor de $n$. $\Box$

skar90 Aug 16 2020 at 16:00

He escrito mi propia prueba:

Si $n$ es par, la respuesta es obviamente $a = b = n/2$, ya que si tomamos $a < n/2$ (WLOG), eso significa que $b > n/2$, y entonces $LCM(a,b) \ge b > n/2$.

Si $n$ es extraño, la respuesta es $a = k$, $b = n-k$, dónde $k$ es el mayor divisor de $n$. Tenga en cuenta que$k$ no puede ser igual a$n$, desde entonces tendríamos $a = n$, $b = 0$, pero la pregunta pide $2$ enteros positivos .

También tenga en cuenta que $k$ puede ser como máximo $n/2$ después de aislar el divisor más grande ($n$). Esto implica que$n-k \ge n/2$.

Ahora, ¿por qué debería $k$ser un divisor? Bueno, es simple:

Si $k|n$, entonces $k|n-k$, y entonces $LCM(k,n-k) = n-k < n$. Pero si$k \nmid n$, entonces $k \nmid n-k$, y entonces $LCM(k, n-k) \ge 2(n-k) \ge 2 \frac{n}{2} \ge n$.

Hecho.