Question

В вершинах квадрата расставлены натуральные числа. Известно, что из двух чисел, стоящих концах любой стороны, одно делится на другое, а из двух чисел, стоящих в концах любой диагонали , ни одно не делится на другое. <br /> Какое наименьшее значение может принимать сумма всех этих чисел.​

Answer 1

Повернём квадрат так, чтобы наименьшее из записанных чисел оказалось в правом нижнем углу. Пусть оно равно x. Тогда в левом нижнем углу и правом верхнем углу должны быть записаны числа вида ax и bx, где a и b – некоторые натуральные числа, для определённости a > b, иначе можно отразить квадрат относительно диагонали. Число в левом верхнем углу не может делиться на x (иначе на диагонали будет пара, в которой одно число делится на другое), тогда это какой-то общий делитель чисел ax и bx, обозначим его как d.

Заметим, что x ≥ 2 (иначе будет делящаяся пара чисел на диагонали); d ≥ x + 1 (по предположению, x – наименьшее число, и d не делится на x); bx ≥ 2d ≥ 2x + 2 (bx делится на d и bx > d, иначе, если bx = d, d будет делиться на x); ax > bx ≥ 3d ≥ 3x + 3. Значит, сумма всех записанных чисел не меньше x + 6d = x + d + 2d + 3d ≥ x + (x + 1) + (2x + 2) + (3x + 3) = 7x + 6.

Если в квадрате расставлены числа 2, 6, 12 и 3, то такая расстановка удовлетворяет условию и сумма чисел равна 23. Если какая-то существует какая-то подходящая расстановка с не большей суммой чисел, то 7x + 6 ≤ 23, x ≤ 2 (отсюда x = 2) и x + 6d = 2 + 6d ≤ 23, d ≤ 3 (отсюда d = 3). При этом ax и bx должны одновременно делиться на x и d, то есть на 2 и 3, значит, они делятся на 2 • 3 = 6, откуда bx ≥ 6, ax ≥ 6 • 2 = 12, и сумма чисел не меньше 23.

Ответ. 23

Answer 2

Рассмотрим одну из сторон квадрата, на концах которой стоят числа $a$ и $b$ $(a<b)$. Так как одно из чисел делится на другое, то $b=ka$ для некоторого $k\geq2$.

Рассмотрим теперь диагональ квадрата, на концах которой стоят числа $a$ и $c$ $(a<c)$. Так как числа не делятся друг на друга, то $\gcd(a,c)=1$. Рассмотрим теперь диагональ, на концах которой стоят числа $b$ и $d$ $(b<d)$. Так как числа не делятся друг на друга, то $\gcd(b,d)=1$.

Рассмотрим теперь оставшиеся две стороны квадрата. Одна из них содержит число $c$, а другая -- число $d$. Можно предположить, что $c$ и $d$ находятся на разных сторонах квадрата (иначе, если $c$ и $d$ лежат на одной стороне, то можно уменьшить сумму, поменяв $c$ и $d$ местами). Без ограничения общности будем считать, что $c$ находится на стороне, на которой не находится $b$, а $d$ находится на стороне, на которой не находится $a$.

Тогда можно записать $c=ma$ и $d=nb$ для некоторых $m,n\geq2$. Из того, что $\gcd(a,c)=1$ и $b=ka$, следует, что $\gcd(a,m)=1$. Аналогично, из того, что $\gcd(b,d)=1$ и $c=ma$, следует, что $\gcd(b,n)=1$.

Теперь можно выразить $m$ и $n$ через $k$: $m=ck/a=c/k$ и $n=dk/b=d/k$. Таким образом, сумма всех чисел в квадрате равна $a+b+c+d=2a+2b+ma+nb=2a+2b+c(k+1/k)+d(k+1/k)=2a(1+k)+2b(1+1/k)+c(k+1/k)+d(k+1/k)=2a(1+k)+2b(1+1/k)+(c+d)(k+1/k)$.

Теперь заметим, что $k+1/k\geq2$, причем равенство достигается только при $k=2$. Поэтому наименьшее значение суммы всех чисел в квадрате достигается при $k=2$, т.е. когда $b=2a$ и $c=2a$, $d=4a$, и равно $2a(1+2)+2a(1+1/2)+2a(2+1/2)+4a(2+1/2)=21