Математикадан Эйлер олимпиадасы, 2015-2016 оқу жылы, Дистанциялық кезеңнің 2-ші туры

Вася алты $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, мы не сможем отличить набор из двойки и тройки от набора из единицы и шестёрки.