lviii. Gold Chain

Problem. A worker is paid one link of a 7-link gold chain per day for 7 days, at the end of each day. Cutting a link is expensive. What is the minimum number of cuts? (Change may be given back: on day $d$ the worker must hold pieces totalling exactly $d$ links.)

Answer. One cut, at the third link, leaving pieces $1,2,4$: day 1 give the single link; day 2 give 2 and take 1 back; day 3 give 1; day 4 give 4 and take back 1 and 2; and so on, binary counting.

Variant	Best
gold bar of $n$ units, cut into pieces (each cut makes one more piece)	$c$ cuts give pieces $1,2,4,\dots$: pays up to $2^{c+1}-1$ days
chain of $n$ links, a cut opens one link (it becomes a single piece and splits the chain)	$k$ cuts pay up to $(k+1)2^{k+1}-1$ days: $7,23,63,159,383,\dots$
pieces for $k$ cuts	$k$ single links and segments $(k+1),2(k+1),4(k+1),\dots ,2^k(k+1)$
general principle	a multiset of piece sizes pays every amount $\mathrm{1..}S$ iff, sorted, each piece is at most $1+$ the sum of the smaller ones

int goldChainCuts(ll n) {                            // fewest cut links so that a chain of n links pays 1..n
    int k = 0;
    while (((ll)(k + 1) << (k + 1)) - 1 < n) k++;
    return k;
}
 
vector<ll> goldChainCutPositions(ll n) {             // 1-based positions of the links to cut
    int k = goldChainCuts(n); vector<ll> seg, cuts;
    ll rem = n - k;                                  // links left after the k cut links
    for (int i = 0; i <= k; i++) { seg.push_back(min((ll)(k + 1) << i, rem)); rem -= seg.back(); }   // capped doubling
    ll pos = 0;
    for (int i = 0; i < k; i++) { pos += seg[i] + 1; cuts.push_back(pos); }
    return cuts;
}
 
bool paysAll(vector<ll> pieces) {                    // every amount 1..sum is a sub-multiset sum
    sort(all(pieces)); ll reach = 0;
    for (ll p : pieces) { if (p > reach + 1) return false; reach += p; }
    return true;
}

Proof: the completeness criterion and the optimal number of cuts

Criterion. Sort the pieces $a_1\le a_2\le \dots$ and let $S_i=a_1+\cdots +a_i$. If $a_{i+1}>S_i+1$, the amount $S_i+1$ cannot be paid: pieces $a_{i+1},\dots$ are each too large and the smaller ones total only $S_i$. Conversely, if $a_{i+1}\le S_i+1$ and every amount in $[0,S_i]$ is payable from the first $i$ pieces, then every amount in $[0,S_{i+1}]$ is: amounts up to $S_i$ directly, larger ones as $a_{i+1}$ plus an amount in $[0,S_i]$. Day by day the worker can return pieces, so paying “a total of $d$ on day $d$” for all $d$ is exactly this condition.

Upper bound. With $k$ cut links the pieces $1$ ($k$ times), $(k+1),2(k+1),\dots ,2^k(k+1)$ satisfy the criterion: after the singles $S=k$, and each segment $2^i(k+1)=1+k+(k+1)(2^i-1)$ equals $S+1$. Their total is $k+(k+1)(2^{k+1}-1)=(k+1)2^{k+1}-1$; for a shorter chain cap the segments in order at the links that remain (a capped segment is still at most $S+1$, and later ones become empty), which keeps the criterion. The positions follow by laying the segments left to right with a cut link between consecutive ones.

Lower bound. $k$ cuts produce $k$ single links and at most $k+1$ segments. Sorted, the first $k$ pieces are ones ($S_k=k$), and the criterion gives $S_{i+1}\le 2S_i+1$, i.e. $S_i+1$ at most doubles with each further piece. After at most $k+1$ more pieces, $S+1\le (k+1)2^{k+1}$. So a chain longer than $(k+1)2^{k+1}-1$ needs more than $k$ cuts. For a bar the same doubling with no singles gives $2^{c+1}-1$. Checked against brute force over all sets of cut positions for every $n\le 40$.

Related notes

• Bit Tricks and XOR (binary representations)
• Bachet’s Weights (the same idea with a balance: powers of 3)
• Greedy and Exchange Arguments (the “smallest unreachable sum” greedy)