Question

Є 4 кавуни різної ваги. Як, користуючись терезами без гир, шляхом не більше 5 зважувань розмістити кавуни за збільшенням маси?

Answer 1

Відповідь:

1.Зважити два кавуни (назвемо їх А і Б) і два інших кавуни (назвемо їх В і Г). Запам’ятати, яка пара важча.

2.Зважити А і В. Якщо вони однакової маси, то розташувати їх поруч. Якщо А важчий за В, то поставити А праворуч від В. Якщо А легший за В, то поставити А ліворуч від В.

3.Зважити Б і Г. Якщо вони однакової маси, то розташувати їх поруч. Якщо Б важчий за Г, то поставити Б праворуч від Г. Якщо Б легший за Г, то поставити Б ліворуч від Г.

4.Зважити легший кавун з першої пари і важчий кавун з другої пари. Якщо вони однакової маси, то розташувати їх поруч між двома іншими кавунами. Якщо перший кавун важчий за другий, то поставити його праворуч від другого кавуна між двома іншими кавунами. Якщо перший кавун легший за другий, то поставити його ліворуч від другого кавуна між двома іншими кавунами.

5.Зважити два середніх кавуни (якщо вони не однакової маси). Якщо перший кавун важчий за другий, то поміняти їх місцями. Якщо перший кавун легший за другий, то залишити їх на своїх місцях.

Тепер чотири кавуни розташовані за збільшенням маси зліва направо.

Answer 2

Для розв'язання цієї задачі можна використати метод двійкового дерева.

1. Розташуємо кавуни в рядок випадковим чином.

2. Розділимо рядок на дві рівні частини. Перша половина кавунів буде зліва, друга - справа.

3. Зважуємо ліву і праву половини. Якщо вони мають однакову масу, то це означає, що всі кавуни мають однакову масу і ми закінчуємо.

4. Якщо ліва і права половини мають різну масу, то переходимо до наступного кроку.

5. Відбираємо ту половину, яка має більшу масу і повторюємо кроки 2-4 з відібраною половиною.

6. Продовжуємо цей процес до тих пір, поки не знайдемо кавун з найбільшою масою.

Таким чином, за допомогою не більше 5 зважувань ми зможемо розмістити кавуни за збільшенням маси.