Задача 88023

Темы:    [ Теория алгоритмов (прочее) ] [ Оценка + пример ]

Сложность: 3 Классы: 5,6,7,8

Условие

48 кузнецов должны подковать 60 лошадей. Каждый кузнец тратит на одну подкову 5 минут. Какое наименьшее время они должны потратят на работу? (Учтите, лошадь не может стоять на двух ногах.)

Подсказка

Обратите внимание, меньше чем за 25 мин подковать всех лошадей нельзя. Почему?

Решение

Покажем, как надо действовать. Сначала 48 кузнецов берут 48 лошадей и подковывают каждой одну ногу, на это уходит 5 минут, у 48ми лошадей одна подкова, у 12 ти  — ни одной. Затем 12 кузнецов подковывают тех лошадей, у которых ещё нет подков, а остальные 36 кузнецов ставят 36ти лошадям вторые подковы. На это опять уходит 5 минут, 36 лошадей с двумя подковами и 24  — с одной. Теперь 24 кузнеца ставят вторые подковы, и 24  — третьи. Теперь 24 лошади с тремя подковами и 36  — с двумя. Теперь 36 кузнецов ставят 36 третьих подков и 12  — 12 четвёртых. Теперь 48 лошадей с тремя подковами и 12  — с четыремя. Последний этап  — 48 кузнецов ставят последние подковы 48ми лошадям. Итак, за 5 этапов, т.е. за 25 минут, все лошади подкованы.

Покажем, что меньше чем за 25 минут это сделать нельзя. Нужно поставить 604 = 240 подков. На каждую подкову нужно 5 минут, значит, всего не меньше, чем 2405 = 1200 минут. Но у нас есть 48 кузнецов, значит, можно сделать это за  1200 : 48 = 25 минут, но никак не меньше. Мы и сделали за 25 минут.

Источники и прецеденты использования

книга
Автор	Козлова Е.Г.
Название	Сказки и подсказки
задача
Номер	91