HMMT 十一月 2014 · 冲刺赛 · 第 23 题

HMMT November 2014 — Guts Round — Problem 23

[ 12 ] Seven little children sit in a circle. The teacher distributes pieces of candy to the children in such a way that the following conditions hold. • Every little child gets at least one piece of candy. • No two little children have the same number of pieces of candy. • The numbers of candy pieces given to any two adjacent little children have a common factor other than 1. • There is no prime dividing every little child’s number of candy pieces. What is the smallest number of pieces of candy that the teacher must have ready for the little children?

解析

[ 12 ] Seven little children sit in a circle. The teacher distributes pieces of candy to the children in such a way that the following conditions hold. • Every little child gets at least one piece of candy. • No two little children have the same number of pieces of candy. • The numbers of candy pieces given to any two adjacent little children have a common factor other than 1. • There is no prime dividing every little child’s number of candy pieces. What is the smallest number of pieces of candy that the teacher must have ready for the little children? Answer: 44 An optimal arrangement is 2-6-3-9-12-4-8. Note that at least two prime factors must appear. In addition, any prime factor that appears must appear in at least two non-prime powers unless it is not used as a common factor between any two adjacent little children. Thus with the distinctness condition we easily see that, if we are to beat 44, 5 and 7 cannot be included. More comparison shows that 12 or something higher cannot be avoided, so this is optimal. Guts Round