Степан має 12 монет, кожна з яких важить різне ціле число грамів, та терези які показують три стани:
вага зліва дорівнює вазі справа
вага однієї шальки більше ніж другої, але не більше ніж у два рази
3 вага однієї шальки більше ніж другої в два або більше разів
якщо він покладе на обидві шальки терезів по дві монети, то завжди переважає та шалька, на якій лежить найважча з Цих монет, причому терези показують, що вага більше в два або більше разів. Потрібно знайти мінімальну можливу вагу найважчої монети.
Ответы
Ответ:
Пошаговое объяснение:
Запишемо всі можливі ваги монет в порядку зростання:
a1 < a2 < a3 < ... < a12
Далі, помітимо, що якщо вага однієї монети більше в два або більше разів від ваги іншої монети, то цю пару монет можна одразу відкинути, бо щоб перевірити, яка з них є найважчою, потрібно порівняти обидві монети із іншим набором монет, що неможливо.
Таким чином, в результаті відкидаємо можливі пари монет з різницею в дві та більше разів:
a1 < a2 < a3 < ... < a6 < 2*a1
a6*2 < a7 < a8 < ... < a12
Тепер додатково відкинемо комбінації монет, які не задовольняють умови, що вага однієї шальки більше ніж другої, але не більше ніж у два рази. Для цього покладемо на одну шальку терезів дві найлегші монети (a1 та a2), а на другу шальку покладемо такі монети, щоб вага однієї шальки була не менше у два рази від ваги іншої. Таким чином, терези мають показувати, що на одній шальці знаходяться монети a1 та a2, а на іншій - пара монет зі списку a3 ... a12.
Отримуємо такі комбінації монет:
a3 < a4 < a5 < 2*a2
a6*2 < a7 < a8 < ... < a12
Тепер додатково відкинемо комбінації монет, які не задовольняють умови, що вага однієї шальки більше ніж другої в два або більше разів. Для цього покладемо на одну шальку терезів дві найлегші монети з другого списку (a7 та a8), а на іншу шальку покладемо такі монети, щоб вага однієї шальки була не менше у два рази від ваги іншої. Таким чином, терези мають показувати, що на одній шальці знаходяться монети a7 та a8, а на іншій - пара монет зі списку a9 ... a12.
Отримуємо такі комбінації монет:
a3 < a4 < a5 < 2*a2
2*a8 < 2*a7 < a9 < ... < a12
Тепер залишилось знайти найбільшу монету зі списку a9 ... a12. Можна покласти на одну шальку терезів найлегшу монету з цього списку (a9), а на іншу шальку покласти найбільшу монету зі списку a3 ... a5 та монету a2 (так як ці три монети не можуть бути більш важкими за будь-яку монету зі списку a9 ... a12). Якщо переважить перша шалька - найважча монета знаходиться у списку a3 ... a5. Якщо переважить друга шалька - найважча монета знаходиться у списку a9 ... a12.
Отже, мінімальна можлива вага найважчої монети дорівнює максимальній вазі зі списку a3 ... a5 або a9 ... a12.