दिया हुआ $n$, खोजें $2$ सकारात्मक आंकड़े $a,b$ ऐसा है कि $a+b=n$ तथा $LCM(a,b)$ यथासंभव न्यूनतम है
यह पिछले गणित / कोडिंग प्रतियोगिता में एक समस्या है।
मैंने इसमें सेंध लगाई $2$ मामले: $n$ या भी है $n$अजीब है। कब$n$ यहां तक कि, इसका मतलब है कि $a=b=n/2$, क्योंकि, सहज रूप से, अगर हम लेते हैं $a < n/2$ (डब्ल्यूएलओजी), तब $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. अगर$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$, जो आसानी से एक विरोधाभास की ओर जाता है। इसलिए केस 1 में न्यूनतम LCM प्राप्त किया जाता है$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$।
कर दी है।