48 blacksmiths need to shoe 60 horses. Each blacksmith spends 5 minutes on one horseshoe. What is the least amount of time they should spend on the work? (Note, a horse cannot stand on two legs.)

#
Note that it is impossible to shoe all the horses in less than 25 minutes. Why?

## Solution

Let's show how to proceed. First, 48 blacksmiths take 48 horses and shoe each one with one shoe, which takes 5 minutes. At this point, 48 horses have one shoe, and 12 have none. Then, 12 blacksmiths shoe the horses that still have no shoes, while the remaining 36 blacksmiths put the second shoes on 36 horses. This again takes 5 minutes, leaving 36 horses with two shoes and 24 with one. Now, 24 blacksmiths put the second shoes on, and 24 put the third shoes. Now, 24 horses have three shoes, and 36 have two. Next, 36 blacksmiths put the third shoes on 36 horses and 12 put the fourth shoes on 12 horses. Now, 48 horses have three shoes, and 12 have four. The final stage is for 48 blacksmiths to put the last shoes on 48 horses. Thus, in 5 stages, i.e., 25 minutes, all the horses are shod.

Let's show that it cannot be done in less than 25 minutes. We need to put on \(60 \times 4 = 240\) shoes. Each shoe takes 5 minutes, so in total, it takes no less than \(240 \times 5 = 1200\) minutes. But we have 48 blacksmiths, so it can be done in \(1200 \div 48 = 25\) minutes, but no less. We did it in 25 minutes.