Joining five chains
You have five pieces of chain, each made of 3 links. Opening a link costs 1 dollar and welding it shut again costs 3 dollars.
What is the least cost, in dollars, to join all five pieces into one long chain (not a closed loop)?
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
The obvious plan opens one link at each of the four joints. Can you use fewer links?
Open every link of a single piece.
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. Every opened link costs 4 dollars, so use as few as possible. Opening all three links of one piece gives three connectors and removes that piece, leaving only four pieces to join.
Step 1: three links suffice. Open the 3 links of one piece. The four remaining pieces need 3 joints, one per opened link. Cost: dollars.
Step 2: two links do not. In the final chain, the opened links separate runs of unopened links. With opened links there are at most runs. With only 2 opened links, no piece has all of its 3 links opened, so the 5 pieces leave at least 5 runs, more than 3. So at least 3 links must be opened.
So the least cost is 12 dollars, against 16 for the obvious plan.