A positive integer is written on each corner of a square such that numbers on opposite vertices are relatively prime while numbers on adjacent vertices are not relatively prime. What is the smallest possible value of the sum of these 4 numbers?
Solution
Two opposite vertices are relatively prime, but they both share a factor with their common neighbor. So that common neighbor must have two prime factors. So each of the 4 numbers has two prime factors, which are not shared with the opposite vertex. Moreover, it suffices to choose the vertices to be the numbers ab, bc, cd, da for some prime numbers a, b, c, d. It's clear that we should choose them to be the smallest primes 2,3,5,7 in some order. The order that minimizes the sum of all of the numbers gives 14,10,15,21 for a sum of 60.
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.