Dany $n$, odnaleźć $2$ liczby naturalne $a,b$ takie że $a+b=n$ i $LCM(a,b)$ jest jak najmniejsza
To jest problem z poprzedniego konkursu matematycznego / kodowania.
Zepsułem to na $2$ przypadki: $n$ jest równa lub $n$to jest dziwne. Kiedy$n$ jest równy, to znaczy, że $a=b=n/2$, bo intuicyjnie, jeśli bierzemy $a < n/2$ (WLOG) $b > n/2$, a więc $LCM(a,b) \ge b > n/2$.
Kiedy $n$to dziwne, nie mogłem wymyślić, jak to zrobić. Jedyny sposób, na jaki wpadłem, to brutalne wymuszenie wszystkich wartości$a$ (znowu WLOG) od $1$ aż do $n/2$, ale kiedy to jest o wiele za wolne $n$ jest wielki.
Każda pomoc byłaby mile widziana.
Odpowiedzi
Odpowiedź to $a=k, b=n-k$ za dziwne $n>1$ i największy właściwy (tj. $<n$) dzielnik $k$ z $n$ i $a=b=n/2$ nawet $n$.
Dowód. Przypuszczać$n$ to jest dziwne, $k+(n-k)$ jest rozkładem $n$ z najmniejszym $LCM(k, n-k)$. Przypadek 1. Jeśli$k$ dzieli $n$ potem dzieli $n-k$ i $LCM$ jest $n-k$, więc w tym przypadku lepiej jest wziąć $k$ być największym właściwym dzielnikiem $n$. Przypadek 2. Jeśli$k$ nie dzieli $n$, to nie dzieli $n-k$, więc $LCM$ jest $k(n-k)/gcd(n,k)$. Pozwolić$k/gcd(n,k)=m$. Pozwolić$gcd(n,k)=d$. Następnie$k=md$. Wtedy następuje rozkład$md+(n-2d)$ i $LCM$ jest $m(n-2d)=mn-2md$. Aby być minimalnym, powinniśmy$mn-2md<n-d$, więc $(m-1)n<(2m-1)d$, $d>((m-1)/(2m-1))n$. Lecz odkąd$n$ jest dziwne i podzielne przez $d$ to oznacza $n\ge 3d$, więc $3(m-1)/(2m-1)<1$, $m<3$ więc $m=2$, co łatwo prowadzi do sprzeczności. Stąd minimalne LCM jest osiągane w przypadku 1, kiedy$k$ jest największym właściwym ($\ne n$) dzielnik $n$. $\Box$
Napisałem swój własny dowód:
Jeśli $n$ jest równa, odpowiedź brzmi oczywiście $a = b = n/2$, ponieważ jeśli weźmiemy $a < n/2$ (WLOG), to znaczy, że $b > n/2$, a więc $LCM(a,b) \ge b > n/2$.
Jeśli $n$ jest dziwne, odpowiedź brzmi $a = k$, $b = n-k$, gdzie $k$ jest największym dzielnikiem $n$. Zwróć na to uwagę$k$ nie może się równać$n$, od tego czasu będziemy mieć $a = n$, $b = 0$, ale pytanie brzmi $2$ dodatnie liczby całkowite.
Zwróć też na to uwagę $k$ może być najwyżej $n/2$ po wyodrębnieniu największego dzielnika ($n$). To daje do zrozumienia ze$n-k \ge n/2$.
Teraz, dlaczego powinien $k$być dzielnikiem? Cóż, to proste:
Jeśli $k|n$, następnie $k|n-k$, a więc $LCM(k,n-k) = n-k < n$. Ale jeśli$k \nmid n$, następnie $k \nmid n-k$, a więc $LCM(k, n-k) \ge 2(n-k) \ge 2 \frac{n}{2} \ge n$.
Gotowe.