Gold Bars 2
Your worker was very diligent, so you decided to reward him by offering him another month of work [31 days] and to pay him a huge gold bar, but only getting 1/31 of it a day. You are alone in your room with a butcher knife, trying to cut the gold bar so that you can pay the worker enough every day. You cannot pay him advance, for fear that he may cheat you, and you cannot not pay him his daily 1/31, as you have a great reputation in the community.
What is the least number of cuts you need to pay your worker every day? Remember, he is willing to return you some gold bars.
The answer is 4.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
Moderator note:
Hi Daniel Oh, we really like this problem as a Logic problem! We hope to see more good problems like these in the future! Thank you.
When cutting the gold bar, you want to cut to split the gold bars to powers of two. This will always work because 2^n+2^[n+1]=2^[n+2]-1. What does this mean? If we cut it, using change and the bigger gold bars, we can "stack up" small gold bars until the worker has all the gold bars smaller than the gold bar that is the next power of 2. The worker should have values of one less than this gold bar. Then, the next day he cashes all his gold bars in for the big one. And now you stack small, repeating the previous steps of saving up [except now he has a big bar to up his value] and eventually have one less than the next power of 2. Rinse and repeat.
Example:
Day 1: Pay him the 1/31
Day 2: Pay him the 2/31 and receive the 1/31 in change [note that these values are powers of 2]
Day 3: Pay him the 1/31
Day 4: Pay him the 4/31 and receive all bars worker owns in change.
Day 5: Pay him the 1/31
Day 6: Pay him the 2/31 and receive the 1/31 in change.
Day 7: Pay him 1/31
Day 8: Pay him the 8/31 bar.
Etc., etc. See how many steps repeat?