Олимпиада имени Леонарда Эйлера2015-2016 учебный год, II тур дистанционного этапа

Вася задумал шесть натуральных чисел: $a$, $b$, $c$, $d$, $e$, $f$. За рубль можно указать любые два из них и узнать их произведение. Пете известно, что любые два из задуманных чисел взаимно просты (то есть не имеют общих делителей, больших 1). За какую наименьшую сумму он сможет узнать все задуманные числа?

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. За 4 рубля.
Покажем, как обойтись четырьмя рублями. Сначала узнаем произведения $ab$ и $bc$. Так как у чисел $a$ и $c$ нет общих простых делителей, наибольший общий делитель этих произведений равен $b$. Таким образом мы узнаём число $b$, а с ним и числа $a = ab/b$ и $c = bc/b$. Аналогично за два вопроса узнаем числа $d$, $e$ и $f$.
Покажем, что трёх рублей не хватит. Пусть мы знаем только три произведения. Тогда в них должны входить все шесть чисел, иначе про одно из них мы не будем знать вообще ничего. Но в таком случае каждое число входит ровно в одно произведение, и если, например, одно из произведений равно 6, мы не сможем отличить набор из двойки и тройки от набора из единицы и шестёрки.