Paying With a Gold Bar

Question

A contractor works for you for 7 days and must be paid exactly frac17 of a gold bar at the end of each day, no advance, no arrears. Pieces you've already paid can be taken back as change. What is the minimum number of cuts, and where?

Accepted Answer

Two cuts, producing pieces of frac17, frac27, frac47, the binary weights. | Day | Contractor holds | Move | |---|---|---| | 1 | 1 | give 1 | | 2 | 2 | give 2, take back 1 | | 3 | 1+2 | give 1 | | 4 | 4 | give 4, take back 1 and 2 | | 5 | 4+1 | give 1 | | 6 | 4+2 | give 2, take back 1 | | 7 | 4+2+1 | give 1 | Every value 1–7 is a subset sum of 1, 2, 4, that's binary representation, and exchange converts "pay one more seventh" into "hand over the right subset." Optimality: c cuts make c+1 pieces, whose nonempty subsets number 2^c+1 - 1. You need 7 distinct cumulative holdings, so 2^c+1 - 1 ge 7 Rightarrow c ge 2. Two cuts is tight precisely because binary wastes nothing, each piece doubles the reachable set. The general pattern: n days needs pieces 1, 2, 4, dots → lceil log_2(n+1) rceil pieces.

Paying With a Gold Bar

Problem

Your answer

Hints