У царя Гієрона є 11 металевих злитків, які не можна розрізнити на вигляд; цар
знає, що їх ваги (в деякому порядку) рівні 1, 2, . . . , 11 кг. Ще у нього є мішок, який
порветься, якщо в нього покласти більше 11 кг. Архімед дізнався ваги всіх злитків
і хоче довести Гієрону, що перший злиток має вагу 1 кг. За один крок він може
завантажити декілька злитків у мішок і продемонструвати Гієрону, що мішок не
порвався (рвати мішок не можна!). За яку найменшу кількість завантажень мішка
Архімед може добитися необхідного?
знає, що їх ваги (в деякому порядку) рівні 1, 2, . . . , 11 кг. Ще у нього є мішок, який
порветься, якщо в нього покласти більше 11 кг. Архімед дізнався ваги всіх злитків
і хоче довести Гієрону, що перший злиток має вагу 1 кг. За один крок він може
завантажити декілька злитків у мішок і продемонструвати Гієрону, що мішок не
порвався (рвати мішок не можна!). За яку найменшу кількість завантажень мішка
Архімед може добитися необхідного?
More Questions From This User See All
Answers & Comments
Ответ:
Оскільки Архімед знає ваги всіх злитків, то він може скласти таблицю ваг злитків від 1 до 11 кг. Тоді сума ваг перших k злитків дорівнює:
1 + 2 + ... + k = k(k+1)/2.
Для того, щоб довести, що перший злиток має вагу 1 кг, Архімед повинен визначити суму ваг деякої підмножини злитків. Якщо ця сума не перевищує 11 кг, то в першій злиток точно входить злиток вагою 1 кг. Якщо ж перевищує, то злиток вагою 1 кг знаходиться в залишку.
Можна скласти таку таблицю для підрахунку сум ваг(знизу фото)
З цієї таблиці видно, що сума ваг перших 5 злитків дорівнює 15, що не перевищує 11 + 1 = 12. Значить, Архімед може завантажити перші 5 злитків в мішок, а потім показати Гієрону, що мішок не порвався. Якщо в цих п'яти злитках немає злитка вагою 1 кг, то він знаходиться в залишку, тобто в інших 6 злитках. Тоді Архімед може завантажити в мішок 6 злитків, а потім показати, що мішок не порвався. Таким чином, Архімед може добитися того, що перший злиток має вагу 1 кг за два завантаження в мішок.