# How did the king pay the worker? [duplicate]

A humorous king pays his worker with one inch gold bar everyday. He had a $$31$$ inches gold bar and he paid the worker $$31$$ days of a month cutting it in just $$4$$ places. How is this possible?

Taken from the book Neurone Abaro Onuronon by Muhammad Zafar Iqbal.

• Agree with @Anonymous. These are both king and gold puzzles. – WhatsUp May 7 at 11:22
• But there are some differences too (4 instead of 5) @Anonymous – F Nishat May 7 at 11:42
• The solution is directly equivalent to that for The Jeweler and the Five Rings, just framed differently, so I have voted to close as a duplicate. – Stiv May 7 at 11:50

He could do it as follows

Cut the bar of size 31 into segments of size 16|8|4|2|1
Clearly this can be achieved with just four cuts.
Then, for each day $$n$$, ensure the worker leaves with the gold bars which correspond to 1 in the binary representation of $$n$$.
For example, on day 21, the binary representation is 10101 so the worker must leave with the gold bars of size 16, 4 and 1.
This means that the worker will sometimes have to swap previous bars they've earnt. For example, on day 2, the worker will give back the gold bar of size 1 and receive the gold bar of size 2.

• "Clearly this can be achieved with just four cuts" i guess that makes it 5 cuts : 1st: 16, 2nd: 8, 3rd: 4, 4th: 2, 5th: 1 – imAProgrammer May 7 at 13:04
• @imAProgrammer cut 1: between 16&8, cut 2: between 8&4, cut 3: between 4&2, cut 4: between 2&1. This leaves 5 pieces from 4 cuts. – Mason May 7 at 13:11
• @imAProgrammer Programmers often do off-by-one errors. – trolley813 May 7 at 20:36
• @Mason what about cut between 32 & 16 ? this makes it 5 cuts i'm sure to cut a bar of size 32 to half until you get one single element, you'll end up with 5 cuts (C.F Dichotomy) – imAProgrammer May 10 at 14:48
• @imAProgrammer We are cutting the bar into five pieces and that needs four cuts. In general, to cut the bar into n pieces you need n-1 cuts. For example, cutting once divides it into two pieces. – hexomino May 10 at 14:52