Натуральные числа взаимно простые, если они не имеют никаких общих делителей, кроме 1.
Обозначим N=(A+B)*(A+C)*(B+C)/(A*B*C), по условию это целое число. Перепишем (A+B)*(A+C)*(B+C) = N*A*B*C Если среди натуральных чисел А, В, С есть одинаковые, то можно принять, что А=В (нет никакой разницы, какую пару чисел считать равной). Но тогда наибольший общий делитель чисел А и В равен числу А, и равен 1. Т.е. А=В=1. Подставив эти значения в выражение (A+B)*(A+C)*(B+C) = N*A*B*C, получим: 2*(С+1)*(С+1) = N*C. Отсюда следует, что 2 делится на С; и следовательно, С=1 или С=2. Таким образом, имеем две тройки чисел: А=1, В=1, С=1 и А=1, В=1, С=2
Теперь рассматриваем случай, когда числа А, В и С попарно различны. Для однозначности будем считать, что А < B < C. Если два числа взаимно простые, то сумма этих чисел взаимно проста с каждым из них, поэтому из нашего выражения (A+B)*(A+C)*(B+C)=N*A*B*C следует, что А+В=M*С и А+С=К*В, где М и К - натуральные числа. Т.к. А+B < 2*C (см. выше, где мы приняли, что А <B < C), то М*С < 2*C, или M < 2, т.е. М=1, и следовательно, А+В=М*С=1*С=С. Выразим С из А+С=К*В и подставим в А+В=С: С=К*В-А А+В = К*В - А, откуда 2*А = (К-1)*В Т.к. А и В взаимно простые, то 2 делится на В. Учитывая, что 1 ≤ A < B, получаем, что B>1 и, значит, В=2. Тогда А=1 и С=3. Итак, ещё одна тройка чисел А=1, В=2, С=3
Поскольку весы именно чашечные, то задача нахождения фальшивой монеты из N сводится к бинарному поиску - мы каждый раз делим исходную кучку пополам (или на три части, если пополам не делится), определяем ту, которая легче, затем поступаем с ней аналогично. И т.д. пока сравнение не сведется к 2-м монетам - более легкая из них и есть искомая. При этом для N монет нам понадобится log2(N) взвешиваний. Если N не степень двойки, то округление идет до ближайшей СЛЕДУЮЩЕЙ. Т.о. в нашем примере log2(N) = 4. Откуда N = 2^4 = 16. 16 монет. мое предположение такое)
0,0(0 оценок)
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota
Оформи подписку
