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?
Solution
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.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.