Được $n$, tìm thấy $2$ những số nguyên dương $a,b$ như vậy mà $a+b=n$ và $LCM(a,b)$ là tối thiểu nhất có thể
Đây là một vấn đề trong một cuộc thi toán học / mã hóa trước đây.
Tôi đã chia nhỏ điều này thành $2$ các trường hợp: $n$ là thậm chí hoặc $n$là số lẻ. Khi nào$n$ thậm chí, điều đó có nghĩa là $a=b=n/2$, bởi vì, theo trực giác, nếu chúng ta lấy $a < n/2$ (WLOG), sau đó $b > n/2$, và vì thế $LCM(a,b) \ge b > n/2$.
Khi nào $n$thật kỳ lạ, tôi không thể tìm ra cách làm điều đó. Cách duy nhất tôi nghĩ ra là buộc tất cả các giá trị của$a$ (một lần nữa, WLOG) từ $1$ lên cho đến khi $n/2$, nhưng cách này quá chậm khi $n$ là lớn.
Bất kì sự trợ giúp nào đều được đánh giá cao.
Trả lời
Câu trả lời là $a=k, b=n-k$ cho lẻ $n>1$ và thích hợp lớn nhất (tức là, $<n$) số chia $k$ của $n$ và $a=b=n/2$ cho dù $n$.
Bằng chứng. Giả sử$n$ là số lẻ, $k+(n-k)$ là sự phân hủy của $n$ với cái nhỏ nhất $LCM(k, n-k)$. Trường hợp 1. Nếu$k$ phân chia $n$ sau đó nó phân chia $n-k$ và $LCM$ Là $n-k$, vì vậy trong trường hợp này tốt hơn là nên lấy $k$ là ước số thích hợp lớn nhất của $n$. Trường hợp 2. Nếu$k$ không phân chia $n$, sau đó nó không phân chia $n-k$, nên $LCM$ Là $k(n-k)/gcd(n,k)$. Để cho$k/gcd(n,k)=m$. Để cho$gcd(n,k)=d$. Sau đó$k=md$. Sau đó, sự phân hủy là$md+(n-2d)$ và $LCM$ Là $m(n-2d)=mn-2md$. Để tối thiểu chúng ta nên có$mn-2md<n-d$, vì thế $(m-1)n<(2m-1)d$, $d>((m-1)/(2m-1))n$. Nhưng kể từ khi$n$ là số lẻ và chia hết cho $d$ nó ngụ ý $n\ge 3d$, vì thế $3(m-1)/(2m-1)<1$, $m<3$ vì thế $m=2$, dễ dẫn đến mâu thuẫn. Do đó, LCM tối thiểu đạt được trong Trường hợp 1 khi$k$ là quyền lớn nhất ($\ne n$) ước số của $n$. $\Box$
Tôi đã viết bằng chứng của riêng mình:
Nếu $n$ thậm chí, câu trả lời rõ ràng là $a = b = n/2$, vì nếu chúng ta lấy $a < n/2$ (WLOG), có nghĩa là $b > n/2$, và vì thế $LCM(a,b) \ge b > n/2$.
Nếu $n$ thật kỳ quặc, câu trả lời là $a = k$, $b = n-k$, Ở đâu $k$ là ước số lớn nhất của $n$. Lưu ý rằng$k$ không thể bằng$n$, kể từ đó chúng tôi sẽ có $a = n$, $b = 0$, nhưng câu hỏi yêu cầu $2$ tích cực số nguyên.
Cũng lưu ý rằng $k$ có thể là nhiều nhất $n/2$ sau khi cô lập ước số lớn nhất ($n$). Điều này ngụ ý rằng$n-k \ge n/2$.
Bây giờ, tại sao nên $k$là một số chia? Vâng, nó đơn giản:
Nếu $k|n$, sau đó $k|n-k$, và vì thế $LCM(k,n-k) = n-k < n$. Nhưng nếu$k \nmid n$, sau đó $k \nmid n-k$, và vì thế $LCM(k, n-k) \ge 2(n-k) \ge 2 \frac{n}{2} \ge n$.
Làm xong.