Diberikan $n$, Temukan $2$ bilangan bulat positif $a,b$ seperti yang $a+b=n$ dan $LCM(a,b)$ seminimal mungkin

Question

Ini adalah masalah dalam kontes matematika / pengkodean sebelumnya.

Saya memecah ini menjadi $2$ kasus: $n$ adalah genap atau $n$aneh. Kapan$n$ adalah genap, itu artinya $a=b=n/2$Karena, secara intuitif, jika kita mengambil $a < n/2$ (WLOG), lalu $b > n/2$, sehingga $LCM(a,b) \ge b > n/2$.

Kapan $n$aneh, saya tidak tahu bagaimana melakukannya. Satu-satunya cara yang saya temukan adalah dengan kekerasan terhadap semua nilai$a$ (sekali lagi, WLOG) dari $1$ sampai $n/2$, tapi ini terlalu lambat $n$ besar.

Bantuan apa pun akan sangat dihargai.

Answer 1

Jawabannya adalah $a=k, b=n-k$ untuk aneh $n>1$ dan properti terbesar (yaitu, $<n$) pembagi $k$ dari $n$ dan $a=b=n/2$ untuk genap $n$.

Bukti. Seharusnya$n$ aneh, $k+(n-k)$ adalah dekomposisi $n$ dengan yang terkecil $LCM(k, n-k)$. Kasus 1. Jika$k$ membagi $n$ lalu itu membelah $n-k$ dan $LCM$ aku s $n-k$, jadi dalam hal ini lebih baik mengambil $k$ menjadi pembagi terbesar dari $n$. Kasus 2. Jika$k$ tidak membelah $n$, maka itu tidak membelah $n-k$, sehingga $LCM$ aku s $k(n-k)/gcd(n,k)$. Membiarkan$k/gcd(n,k)=m$. Membiarkan$gcd(n,k)=d$. Kemudian$k=md$. Kemudian dekomposisinya$md+(n-2d)$ dan $LCM$ aku s $m(n-2d)=mn-2md$. Minimal kita harus punya$mn-2md<n-d$, jadi $(m-1)n<(2m-1)d$, $d>((m-1)/(2m-1))n$. Tapi sejak$n$ ganjil dan habis dibagi $d$ itu menyiratkan $n\ge 3d$, jadi $3(m-1)/(2m-1)<1$, $m<3$ begitu $m=2$, yang dengan mudah mengarah pada kontradiksi. Oleh karena itu, KPK minimum dicapai dalam Kasus 1 saat$k$ adalah properti terbesar ($\ne n$) pembagi dari $n$. $\Box$

Answer 2

Saya telah menulis bukti saya sendiri:

Jika $n$ adalah genap, jawabannya jelas $a = b = n/2$, karena jika kita mengambil $a < n/2$ (WLOG), itu artinya $b > n/2$, sehingga $LCM(a,b) \ge b > n/2$.

Jika $n$ aneh, jawabannya adalah $a = k$, $b = n-k$, dimana $k$ adalah pembagi terbesar dari $n$. Catat itu$k$ tidak bisa sama dengan$n$, sejak itu kami akan melakukannya $a = n$, $b = 0$, tapi pertanyaannya menanyakan $2$ bilangan bulat positif .

Perhatikan juga itu $k$ bisa maksimal $n/2$ setelah mengisolasi pembagi terbesar ($n$). Ini menyiratkan itu$n-k \ge n/2$.

Sekarang, kenapa harus $k$menjadi pembagi? Nah, itu sederhana:

Jika $k|n$, kemudian $k|n-k$, sehingga $LCM(k,n-k) = n-k < n$. Tapi jika$k \nmid n$, kemudian $k \nmid n-k$, sehingga $LCM(k, n-k) \ge 2(n-k) \ge 2 \frac{n}{2} \ge n$.

Selesai.