We are given a bag of sugar, a two-pan balance, and a weight of $1$ gram. How do we obtain $1$ kilogram of sugar in the smallest possible number of weighings?
Problem
Source:
Tags: combinatorics, algorithm, IMO Shortlist, IMO Longlist
khan.academy
24.03.2019 17:26
Anyone here? Should we take some geometric sum? I am so confused.
MathPassionForever
24.03.2019 20:52
Just one doubt: is it necessary that the sugar can't be kept at any place other than the pan and the bag?
RudraRockstar
24.03.2019 21:01
I’m getting 10 weighings with the condition @above stated( that is sugar obtained at different times can be kept separate).
khan.academy
24.03.2019 21:06
I have thought about this 512+ 256+ 128+64+32+8
RudraRockstar
24.03.2019 21:21
I think my method requires lesser weighings than yours. 1st weigh: We get 1g of sugar from the bag against the 1g wt. 2nd weigh: we put 1g of sugar we got and 1g weigh on one pan. So we can get 2g of sugar more. Therefore total 3g. 3rd: 3g sugar and 1g weight on 1 side, so we get 4g more. So total 7g. Like this on the nth weighing we get 2^n-1 g sugar. Therefore on 10th weigh we have 1kg 23g. Since we kept sugar obtained separately we remove the 15g , 7g and 1g to get 1kg in 10 weighings
RudraRockstar
24.03.2019 21:21
Pls someone say whether this is correct or not
khan.academy
24.03.2019 21:24
RudraRockstar wrote: Pls someone say whether this is correct or not I think process is correct but still that is 11 steps. There might be less too. This question is aso vague.
Rinocyrus
24.09.2020 05:35
Is this correct?
Let us define 2 operations that use one weighing:
A - transfer all the sugar already on the 2 pans to one of the pans, then put in enough sugar on the other pan to balance it.
B - transfer all the sugar already on the 2 pans to one of the pans then add the 1g weight on the same side then put in enough sugar on the other pan to balance it.
Operation A doubles the amount of sugar in the 2 pans, while operation B doubles it then adds one more gram.
Operation A is equivalent to 'adding' a 0 to the end of a binary number, which would double the value of the number, while operation B is equivalent to 'adding' a 1 to the end of a binary number.
Therefore, to get N grams of sugar we get N in binary, then for each digit:
If the digit is 0, apply operation A.
If the digit is 1, apply operation B.
1000 is 1111101000 which is 10 digits long, so there are 10 weighings.
superagh
24.09.2020 05:42
Just keep moving everything to one side to get $10$ weighings.