Gegeben $n$, finden $2$ positive ganze Zahlen $a,b$ so dass $a+b=n$ und $LCM(a,b)$ ist so minimal wie möglich

Aug 16 2020

Dies ist ein Problem in einem früheren Mathematik- / Codierungswettbewerb.

Ich habe das aufgeschlüsselt $2$ Fälle: $n$ ist gerade oder $n$ist ungerade. Wann$n$ ist gerade, das heißt das $a=b=n/2$, weil intuitiv, wenn wir nehmen $a < n/2$ (WLOG) also $b > n/2$, und so $LCM(a,b) \ge b > n/2$.

Wann $n$ist seltsam, ich konnte nicht herausfinden, wie es geht. Der einzige Weg, den ich mir ausgedacht habe, war, alle Werte von brutal zu erzwingen$a$ (wieder WLOG) von $1$ bis zu $n/2$, aber das ist viel zu langsam wenn $n$ ist groß.

Jede Hilfe wäre sehr dankbar.

Antworten

1 JCAA Aug 16 2020 at 02:01

Die Antwort ist $a=k, b=n-k$ für ungerade $n>1$ und das größte richtige (dh $<n$) Teiler $k$ von $n$ und $a=b=n/2$ für gerade $n$.

Beweis. Annehmen$n$ ist ungerade, $k+(n-k)$ ist die Zersetzung von $n$ mit dem kleinsten $LCM(k, n-k)$. Fall 1. Wenn$k$ teilt $n$ dann teilt es sich $n-k$ und der $LCM$ ist $n-k$In diesem Fall ist es also besser zu nehmen $k$ der größte richtige Teiler von zu sein $n$. Fall 2. Wenn$k$ teilt sich nicht $n$dann teilt es sich nicht $n-k$, so die $LCM$ ist $k(n-k)/gcd(n,k)$. Lassen$k/gcd(n,k)=m$. Lassen$gcd(n,k)=d$. Dann$k=md$. Dann ist die Zersetzung$md+(n-2d)$ und der $LCM$ ist $m(n-2d)=mn-2md$. Um minimal zu sein, sollten wir haben$mn-2md<n-d$, so $(m-1)n<(2m-1)d$, $d>((m-1)/(2m-1))n$. Aber seit$n$ ist ungerade und teilbar durch $d$ es impliziert $n\ge 3d$, so $3(m-1)/(2m-1)<1$, $m<3$ so $m=2$, was leicht zu einem Widerspruch führt. Daher wird das minimale LCM in Fall 1 erreicht, wenn$k$ ist das größte richtige ($\ne n$) Teiler von $n$. $\Box$

skar90 Aug 16 2020 at 16:00

Ich habe meinen eigenen Beweis geschrieben:

Wenn $n$ ist gerade, die Antwort ist offensichtlich $a = b = n/2$, denn wenn wir nehmen $a < n/2$ (WLOG), das heißt das $b > n/2$, und so $LCM(a,b) \ge b > n/2$.

Wenn $n$ ist seltsam, die Antwort ist $a = k$, $b = n-k$, wo $k$ ist der größte Teiler von $n$. Beachten Sie, dass$k$ kann nicht gleich sein$n$, seitdem hätten wir $a = n$, $b = 0$, aber die Frage fragt nach $2$ positive ganze Zahlen.

Beachten Sie auch das $k$ kann höchstens sein $n/2$ nach dem Isolieren des größten Teilers ($n$). Dies impliziert das$n-k \ge n/2$.

Nun, warum sollte $k$ein Teiler sein? Nun, es ist einfach:

Wenn $k|n$, dann $k|n-k$, und so $LCM(k,n-k) = n-k < n$. Aber wenn$k \nmid n$, dann $k \nmid n-k$, und so $LCM(k, n-k) \ge 2(n-k) \ge 2 \frac{n}{2} \ge n$.

Erledigt.