Weighing problems
These problems was posed to me by friends at NBHM Nurture Programme 2007 at IMSc Chennai
Problem 1:
A shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1,3 and 4 only. How many minimum weights and name the weights you will need to measure all weights from 1 to 1000.
Solution 1:
Highlight the part between the * symbols for the answer.
*The numbers 1,2,4,8,16... This is optimal as each number has exactly one binary representation. So for making 1000 kg we need up to 1, 2, 4, 8, 16, 32, 64, 128, 512. :) *
------------------------------------------------------------------------------
Problem 2:
Same as the first problem with the condition of placing weights on only side of the common balance being removed. You can place weights on both side and you need to measure all weights between 1 and 1000. For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2, by placing 3 on one side and 1 on the side which contain the substance to be weighed. How many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg.
Solution 2:
Highlight the part between the * symbols for the answer.
* The numbers 1,3,9,27,81,243,729. This is true because each number now has exactly one ternary representation. Any 2*3^i can always be represented as 3^(i+1) - 3^i. So, there is a unique way of representing a number in the form of sigma s_i*3^i where s_i belongs to {0, 1, -1}. So, this is optimal. *
------------------------------------------------------------------------------
Problem 3:
This is the most difficult one. You have to make 125 packets of sugar with first one weighing 1 kg, second 2 kg, third 3 kg etc ...and 125th one weighing 125kg.You can only use one pan of the common balance for measurement for weighing sugar, the other pan had to be used for weights i.e. weights should be used for each weighing.
It has come into notice that moving weights into and out of the pan of the balance takes time and this time depends on the number on the number of weights that are moved. For example - If we need to measure 4 kg using weights 1 and 3 only, it will take twice as much time needed to measure 1 kg. Lets say we want to make sugar packets of weights 1,3,4 using weights 1 and 3 only. For this first we measure 1 kg, with 1 unit of time, we place 3 kg along with 1 kg and measure 4kg with again 1 unit of time, and finally we move 1kg out of pan to measure 3kg in 1 unit of time. So in 3 units of time we could measure 1,3 and 4kg using weights 1 and 3 only.
Now you have to make sugar packets of all weights from 1 to 125 in minimum time, in other words in minimum movement of weights. The question here is to find out the minimum number of weighs needed and the weight of each the weights used and the strategy to be followed for the creation of 125 packets of sugar.
Solution:
Highlight the part between the * symbols for the answer.
* This is a problem to be solved by Gray code.
A naive method was taking ~ 2^7*7/2 = 448 shifts :) *
Problem 1:
A shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1,3 and 4 only. How many minimum weights and name the weights you will need to measure all weights from 1 to 1000.
Solution 1:
Highlight the part between the * symbols for the answer.
*The numbers 1,2,4,8,16... This is optimal as each number has exactly one binary representation. So for making 1000 kg we need up to 1, 2, 4, 8, 16, 32, 64, 128, 512. :) *
------------------------------------------------------------------------------
Problem 2:
Same as the first problem with the condition of placing weights on only side of the common balance being removed. You can place weights on both side and you need to measure all weights between 1 and 1000. For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2, by placing 3 on one side and 1 on the side which contain the substance to be weighed. How many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg.
Solution 2:
Highlight the part between the * symbols for the answer.
* The numbers 1,3,9,27,81,243,729. This is true because each number now has exactly one ternary representation. Any 2*3^i can always be represented as 3^(i+1) - 3^i. So, there is a unique way of representing a number in the form of sigma s_i*3^i where s_i belongs to {0, 1, -1}. So, this is optimal. *
------------------------------------------------------------------------------
Problem 3:
This is the most difficult one. You have to make 125 packets of sugar with first one weighing 1 kg, second 2 kg, third 3 kg etc ...and 125th one weighing 125kg.You can only use one pan of the common balance for measurement for weighing sugar, the other pan had to be used for weights i.e. weights should be used for each weighing.
It has come into notice that moving weights into and out of the pan of the balance takes time and this time depends on the number on the number of weights that are moved. For example - If we need to measure 4 kg using weights 1 and 3 only, it will take twice as much time needed to measure 1 kg. Lets say we want to make sugar packets of weights 1,3,4 using weights 1 and 3 only. For this first we measure 1 kg, with 1 unit of time, we place 3 kg along with 1 kg and measure 4kg with again 1 unit of time, and finally we move 1kg out of pan to measure 3kg in 1 unit of time. So in 3 units of time we could measure 1,3 and 4kg using weights 1 and 3 only.
Now you have to make sugar packets of all weights from 1 to 125 in minimum time, in other words in minimum movement of weights. The question here is to find out the minimum number of weighs needed and the weight of each the weights used and the strategy to be followed for the creation of 125 packets of sugar.
Solution:
Highlight the part between the * symbols for the answer.
* This is a problem to be solved by Gray code.
A Gray code represents each number in the sequence of integers {0...2^N-1} as a binary string of length N in an order such that adjacent integers have Gray code representations that differ in only one bit position. Marching through the integer sequence therefore requires flipping just one bit at a time.
For this answer we need as many blocks as per Solution to Problem 1. For easy understanding let me describe the case where the packets range from 1 to 7 which can be easily extended to 1 - 125 range.
Now if we want to make packets of all weights from 1 to & we will do the following
001 We measure 1kg,using 1kg block.
011 We measure 3kg by placing 2 kg block also
010 We remove 1kg block and measure 2 kg.
110 We add 4kg weight and measure 6kg weight
and so on
Now we can see answer to our problem is Gray code of 7 bits. Now our range is 1 to 125 and not 1 to 127.This can be solved by using appropriate Gray code making the following numbers falling to the end of the sequence you are starting with
1111 110
1111 111
So, it means that I can weigh all packets from 1 to 125 with only 125 shifts
Problem 1 : The solution is correct but there is a slight correction need. 256 has been missed out. A similar problem is http://gurmeet.net/puzzles/poisoned-wine-barrels/index.html
ReplyDeleteweights of 1 and 3 allow us to get to 4. We now need to cater for 5 and this can be done (optimally) with a weight of 9 since the 4 can be used for subtraction. Also by subtraction we can get 6,7 and 8. Moving on from 9, the 1 and 3 allow to get to 13, and the next weight we need to worry about is 14.
ReplyDeleteUsing the subtraction method again, we can get 14 using a weight of 27, (27 in one pan and 1+3+9=13 in the other), and since all weights from 1 to 13 are already available, the other weights from 15 to 26 can be formed. That takes us upto 40, 1+3+9+27=40.
To get 41 a weight of 81 wiil do, (81 in one pan and 40 in the other), and the intervening weights will be covered also.
It seems fairly clear now that we are going up through the powers of 3, in which case in addition to 1, 3, 9, 27 and 81, we need 243 and 729.