Спирина, М.С. Дискретная математика

4. Из 27 монет одна более легкая. Как при помощи 3 взвешива­ ний определить ее? 5. Из 81 монеты одна более легкая. Показать, что 4 взвешива­ ний достаточно, чтобы ее определить. 6. Из 82 монет одна более легкая. Какое наименьшее число взве­ шиваний необходимо для определения этой монеты? 7. Из т одинаковых по виду монет одна фальшивая (более лег­ кая). Указать наименьшее число взвешиваний, необходимых для определения фальшивой монеты. 2.12. Решите задачи, используя графы (рис. 2.31). 1. Винни-Пух вышел на прогулку, взяв с собой карту (рис. 2.31, а). Числа на рисунке обозначают время движения (в минутах) от пункта до пункта. Помогите Винни-Пуху найти кратчайший путь от своего дома в пункте А до дома Пятачка в пункте К. Перечис­ лите пункты, через которые должен пройти Винни-Пух, и под­ считайте время, которое он затратит на весь путь. 2. Атос поскакал в гости к Портосу, взяв с собой карту (рис. 2.31, б). Числа на рисунке обозначают время движения (в часах) от пункта до пункта. Помогите Атосу найти кратчайший путь от своего поместья в пункте Е до поместья Портоса в пункте Д. П е ­ речислите пункты, через которые должен проехать Атос, и под­ считайте время, которое он затратит на весь путь. 3. Рыцарь, находясь в пункте А, узнал, что Прекрасной Даме, в пункте О, ровно через сутки может грозить опасность. Взяв с собой карту (рис. 2.31, в), он немедленно выехал на помощь. Ч и с ­ ла на рисунке обозначают время движения (в часах) от пункта до пункта. Успеет ли рыцарь спасти Прекрасную Даму? Обоснуйте ответ, указав кратчайший маршрут. 4. Рыцарь, находясь в пункте А, узнал, что Прекрасной Даме, в пункте К, через 14 часов может грозить опасность. Взяв с собой карту (рис. 2.31, г), он немедленно выехал на помощь. Числа на рисунке обозначают время движения (в часах) от пункта до пун ­ кта. Успеет ли рыцарь спасти Прекрасную Даму? Обоснуйте ответ, указав кратчайший маршрут. 5. Перед вами —карта (рис. 2.31, д). Числа на карте обозначают время движения (в часах) от пункта до пункта. Можно ли успеть доехать из пункта А в пункт О за 22 часа? В случае положительного ответа укажите маршрут, в случае отрицательного ответа обоснуйте его. 6. Придумайте и решите аналогичную задачу.