Thursday, August 11, 2011

Minimum number of cuts to the bar of gold that will allow you to pay to worker 1/7th each day ?

A worker is to perform work for you for seven straight days. In return for his work, you will pay him 1/7th of a bar of gold per day. The worker requires a daily payment of 1/7th of the bar of gold. What and where are the fewest number of cuts to the bar of gold that will allow you to pay him 1/7th each day?

Solution
Gold bar need minimum two cuts. It should be divided in powers of two.
e.g. for i=0 to k where 2^k is nearly equals to N length of gold piece. 1 ,2 , 4........assuming 7 parts which is divided into a total of 1,2,4.

first day : 1 ---(1)
second day: take back one and give 2----(2)
third day : give back one----(1,2)
fourth day : take back 2,1 and give 4 ----(4)
fifth day : give back 1------(1,4)
sixth day : give 2 and take back 1-----(4,2)
sevent day : give back one-------(1,2,4)

No comments: