ให้ $n$, ค้นหา $2$ จำนวนเต็มบวก $a,b$ ดังนั้น $a+b=n$ และ $LCM(a,b)$ น้อยที่สุดเท่าที่จะทำได้

Aug 16 2020

นี่เป็นปัญหาในการแข่งขันคณิตศาสตร์ / การเข้ารหัสครั้งก่อน

ฉันทำลายสิ่งนี้ลงไป $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$ มีขนาดใหญ่

ความช่วยเหลือใด ๆ จะได้รับการชื่นชมมาก

คำตอบ

1 JCAA Aug 16 2020 at 02:01

คำตอบคือ $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$ซึ่งนำไปสู่ความขัดแย้งได้ง่าย ดังนั้น LCM ขั้นต่ำจะบรรลุในกรณีที่ 1 เมื่อ$k$ เป็นสิ่งที่เหมาะสมที่สุด ($\ne n$) ตัวหารของ $n$. $\Box$

skar90 Aug 16 2020 at 16:00

ฉันได้เขียนหลักฐานของตัวเอง:

ถ้า $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$.

เสร็จแล้ว