주어진 $n$, 찾기 $2$ 양의 정수 $a,b$ 그런 $a+b=n$ 과 $LCM(a,b)$ 가능한 한 최소
이것은 이전 수학 / 코딩 콘테스트의 문제입니다.
나는 이것을 분해 $2$ 사례 : $n$ 짝수 또는 $n$이상하다. 언제$n$ 짝수, 즉 $a=b=n/2$, 직관적으로 $a < n/2$ (WLOG), 다음 $b > n/2$, 등 $LCM(a,b) \ge b > n/2$.
언제 $n$이상하다. 어떻게해야할지 모르겠다. 내가 생각 해낸 유일한 방법은$a$ (다시 WLOG) $1$ 까지 $n/2$, 그러나 이것은 너무 느립니다. $n$ 큽니다.
어떤 도움이라도 대단히 감사하겠습니다.
답변
정답은 $a=k, b=n-k$ 이상하게 $n>1$ 가장 큰 속성 (즉, $<n$) 제수 $k$ 의 $n$ 과 $a=b=n/2$ 심지어 $n$.
증명. 가정$n$ 이상하다 $k+(n-k)$ 분해는 $n$ 가장 작은 $LCM(k, n-k)$. 사례 1. 만약$k$ 분할 $n$ 그런 다음 분할 $n-k$ 그리고 $LCM$ 이다 $n-k$, 따라서이 경우에는 $k$ 가장 큰 적절한 제수 $n$. 사례 2. If$k$ 나누지 않는다 $n$, 그러면 분할되지 않습니다. $n-k$, 그래서 $LCM$ 이다 $k(n-k)/gcd(n,k)$. 허락하다$k/gcd(n,k)=m$. 허락하다$gcd(n,k)=d$. 그때$k=md$. 그러면 분해는$md+(n-2d)$ 그리고 $LCM$ 이다 $m(n-2d)=mn-2md$. 최소화하려면 우리는$mn-2md<n-d$, 그래서 $(m-1)n<(2m-1)d$, $d>((m-1)/(2m-1))n$. 하지만 그때부터$n$ 이상하고 나눌 수 있습니다 $d$ 그것은 의미 $n\ge 3d$, 그래서 $3(m-1)/(2m-1)<1$, $m<3$ 그래서 $m=2$, 이는 쉽게 모순으로 이어집니다. 따라서 최소 LCM은 다음과 같은 경우 사례 1에서 달성됩니다.$k$ 가장 큰 고유 ($\ne n$) 제수 $n$. $\Box$
나는 내 자신의 증거를 작성했습니다.
만약 $n$ 짝수, 대답은 분명히 $a = b = n/2$, 우리가 $a < n/2$ (WLOG), 즉 $b > n/2$, 등 $LCM(a,b) \ge b > n/2$.
만약 $n$ 이상하다, 대답은 $a = k$, $b = n-k$, 어디 $k$ 가장 큰 제수 $n$. 참고$k$ 같을 수 없다$n$, 그 이후로 우리는 $a = n$, $b = 0$, 그러나 질문은 $2$ 양의 정수.
또한 $k$ 기껏해야 $n/2$ 가장 큰 제수 ($n$). 이것은$n-k \ge n/2$.
자, 왜 $k$제수입니까? 글쎄요, 간단합니다 :
만약 $k|n$, 다음 $k|n-k$, 등 $LCM(k,n-k) = n-k < n$. 그러나 만약$k \nmid n$, 다음 $k \nmid n-k$, 등 $LCM(k, n-k) \ge 2(n-k) \ge 2 \frac{n}{2} \ge n$.
끝난.