Dado $n$, encontrar $2$ inteiros positivos $a,b$ de tal modo que $a+b=n$ e $LCM(a,b)$ é o mínimo possível

Aug 16 2020

Este é um problema em um concurso de matemática / codificação anterior.

Eu dividi isso em $2$ casos: $n$ é par ou $n$é estranho. Quando$n$ é mesmo, isso significa que $a=b=n/2$, porque, intuitivamente, se tomarmos $a < n/2$ (WLOG), então $b > n/2$, e entao $LCM(a,b) \ge b > n/2$.

Quando $n$é estranho, não consegui descobrir como fazer. A única maneira que encontrei foi usando a força bruta de todos os valores de$a$ (novamente, WLOG) de $1$ até $n/2$, mas isso é muito lento quando $n$ é grande.

Qualquer ajuda seria muito apreciada.

Respostas

1 JCAA Aug 16 2020 at 02:01

A resposta é $a=k, b=n-k$ para estranho $n>1$ e o maior próprio (ou seja, $<n$) divisor $k$ do $n$ e $a=b=n/2$ para mesmo $n$.

Prova. Suponha$n$ é estranho, $k+(n-k)$ é a decomposição de $n$ com o menor $LCM(k, n-k)$. Caso 1. Se$k$ divide $n$ então ele divide $n-k$ e a $LCM$ é $n-k$, então, neste caso, é melhor levar $k$ para ser o maior divisor adequado de $n$. Caso 2. Se$k$ não divide $n$, então não divide $n-k$, então o $LCM$ é $k(n-k)/gcd(n,k)$. Deixei$k/gcd(n,k)=m$. Deixei$gcd(n,k)=d$. Então$k=md$. Então a decomposição é$md+(n-2d)$ e a $LCM$ é $m(n-2d)=mn-2md$. Para ser mínimo, devemos ter$mn-2md<n-d$, assim $(m-1)n<(2m-1)d$, $d>((m-1)/(2m-1))n$. Mas desde$n$ é estranho e divisível por $d$ isso implica $n\ge 3d$, assim $3(m-1)/(2m-1)<1$, $m<3$ assim $m=2$, o que facilmente leva a uma contradição. Portanto, o LCM mínimo é atingido no Caso 1, quando$k$ é o maior propriamente dito ($\ne n$) divisor de $n$. $\Box$

skar90 Aug 16 2020 at 16:00

Eu escrevi minha própria prova:

E se $n$ é par, a resposta é obviamente $a = b = n/2$, já que se tomarmos $a < n/2$ (WLOG), isso significa que $b > n/2$, e entao $LCM(a,b) \ge b > n/2$.

E se $n$ é estranho, a resposta é $a = k$, $b = n-k$, Onde $k$ é o maior divisor de $n$. Observe que$k$ não pode ser igual a$n$, desde então teríamos $a = n$, $b = 0$, mas a pergunta pede $2$ inteiros positivos .

Observe também que $k$ pode ser no máximo $n/2$ depois de isolar o maior divisor ($n$) Isso implica que$n-k \ge n/2$.

Agora, por que deveria $k$ser um divisor? Bem, é simples:

E se $k|n$, então $k|n-k$, e entao $LCM(k,n-k) = n-k < n$. Mas se$k \nmid n$, então $k \nmid n-k$, e entao $LCM(k, n-k) \ge 2(n-k) \ge 2 \frac{n}{2} \ge n$.

Feito.