Сможет кто решить?
царь сиракуз гиерон имел 6 золотых слитков. на взгляд слитки похожи, но массы у них разные (одинаковых по массе нет). архимеду выдали весы со стрелкой и бирки с номерами от 1 до n. гиерон приказал архимеду взвесить эти слитки и на каждой приклеить бирку так, чтобы номера шли по возрастанию масс. при этом архимеду слитки по одному и сразу после взвешивания и наклеивания бирки слиток забирают (то есть поменять бирку уже нельзя). при этом разрешается чтобы номера шли не по порядку: например, можна чтобы наименьший имел номер 3, а другой пл массе - 8 и т. д.для какого минимального n архимед может быть уверен, что сможет справиться с ?

ScourgeTheCat ScourgeTheCat    1   18.08.2019 15:17    0

Ответы
dvolzhenkov dvolzhenkov  05.10.2020 03:13

Докажем методом Математической Индукции, что для распределения по весу k слитков потребуется как минимум 2^k - 1 бирок.

База (k = 1) очевидна.

Переход (от k к k+1):

Пусть для того, чтобы распределить по весу k слитков требуется 2^k - 1 бирка. Докажем, что для k+1 слитка требуется 2^(k+1) - 1 бирок.

Пусть бирок не более 2^(k+1) - 2. Рассмотрим самый первый слиток. Если Архимед выдаст ему бирку с номером меньше 2^k, сделаем его самым тяжёлым (и тогда осталось не более 2^k - 2 бирок на k слитков, чего не хватит по предположению индукции), а если выдаст бирку с номером не меньше 2^k, сделаем его самым лёгким (аналогично). Но тогда на первый слиток нельзя повесить ни одну из бирок, следовательно, бирок должно быть не менее 2^(k+1) - 1.

Докажем теперь, что  2^(k+1) - 1 бирки хватит. Отложим временно 2^k бирок с нечётными номерами. Все слитки, кроме последнего, пронумеруем исключительно бирками с чётными номерами. Бирок хватит, так как их ровно 2^k - 1 (на k слитков). Последний слиток находится по весу между какими-то двумя (возможно, только одним) слитками. Между бирками с их весами есть хотя бы одна незанятая бирка (так как оба их номера чётны). Её можно поставить на последний слиток.

Переход доказан.

Для k = 6 получаем ответ 63.

ответ: 63 бирки.

ПОКАЗАТЬ ОТВЕТЫ
Другие вопросы по теме Математика