HMMT 十一月 2023 · 团队赛 · 第 6 题

HMMT November 2023 — Team Round — Problem 6

[45] The pairwise greatest common divisors of five positive integers are 2 , 3 , 4 , 5 , 6 , 7 , 8 , p, q, r in some order, for some positive integers p, q, r . Compute the minimum possible value of p + q + r . ◦

解析

[45] The pairwise greatest common divisors of five positive integers are 2 , 3 , 4 , 5 , 6 , 7 , 8 , p, q, r in some order, for some positive integers p, q, r . Compute the minimum possible value of p + q + r . Proposed by: Arul Kolla Answer: 9 Solution: To see that 9 can be achieved, take the set { 6 , 12 , 40 , 56 , 105 } , which gives { p, q, r } = { 2 , 3 , 4 } . Now we show it’s impossible to get lower. m Notice that if m of the five numbers are even, then exactly of the gcd’s will be even. Since we’re 2 shown four even gcd’s and three odd gcd’s, the only possibility is m = 4. Hence exactly two of p, q, r are even. n Similarly, if n of the five numbers are divisible by 3, then exactly of the gcd’s will be divisible by 2