Just Another Scale Puzzle - 23/03/2013

[showmyiq]

I am sure lots of you have already solved different scale puzzles, involving minimum procedures to determine the fake coin, gold piece or some other random object. I recently found another niche of thinking involving scales and I am sure a great pattern can be extracted from there. Imagine you have an ordinary scale and exactly 4 weights – 1gr, 3gr, 6gr and 9gr. The question is simple – how many different objects with unknown weight can be measured with the given scale and the given four weights, when you are allowed to put on the scale one unknown object per measurement only?

Just Another Scale Puzzle

Scale-Puzzle.gif (10.67 KiB) Viewed 41978 times

[showmyiq]

The answer is 19 objects.

Puzzle was cracked by Sergey Sokolov (via facebook).

I am going to later describe all the possible solutions.

Puzzle is closed.

[DArk0n3]

I should have published my solution last night when I came up with it. Very good puzzle!

[showmyiq]

As a matter of fact I found one easier version of this puzzle with 2 weights only in a math textbook for 8th grade. A lot of patterns can be extracted I think when the weights are going more and more. If you already write down some solution or algorithm – feel free to publish it! I will take a cup of coffee and after a while will start to describe for the other users the complete solution.

[DArk0n3]

Well, my solution is pretty simple - the first object weighs 1 kg. You can easily see how it will be measured. The second object weighs 2 kg - you measure it by putting it on one side of the scales with the 1 kg weight and on the other side - the 3 kg weight. Then for the third object - it weighs 3 kg and is measured with the 3kg weight. The fourth object weighs 4 kg and is put against the two weights - 1 kg and 3 kg - on the other side of the scales. Then we have more or less the same manipulations for all the other objects until we reach the last, which weighs 19 kg. Now, I think that if we already use the objects that we have already weighed we can go into infinitely measuring new objects and using them to measure more and more objects.

[showmyiq]

Yes, you are absolutely right! To tell you the truth I didn’t attack the problem with this approach (your approach is more flexible than mine). I wanted to analyze all the possible weight rearrangements and to make my conclusions of the unknown objects by deduction. I just want to add that if we were allowed to put 2 or more unknown objects on the scale, theoretically is possible to measure all the integer values of random weights of the unknown objects (using one weight only if 1 gr).

Imagine we have a weight of 1 gr and we can put 2 or more unknown objects on the scale. We can measure an object of 1 gr instantly. Then with the object and the weight of 1 gr – we can measure 2 gr objects. Following this scheme we can measure X gr object, for any X integer. In our task though, we can put only 1 unknown object on the scale. So the solutions will be not infinite, because we are not going to add more elements to the possible set of elements (in our case the possible set of elements is based on the permutations of the 4 weights and their position – left or right). Anyway, let’s analyze the puzzle manually – so we can feel the patterns and extract some schemes and statistics.

Let’s start analyze the cases.

1 case – We can instantly measure unknown objects with 1,3,6 or 9 gr (using only one weight on the one of the scales, and the unknown object situated on the other). You can see an example of measuring a 6gr object on the diagram below.

Case 1

Case-1.gif (9.34 KiB) Viewed 41960 times

That complete and fulfill the first case of our scenarios.

2 case – Now what if two weights are situated on one of the scales and the unknown object on the other scale? We can combine 2 weights by 6 possible ways. Those who are familiar with Combinatorics, can calculate the possible rearrangements of 4 objects on pairs with Newton Binomial Coefficient. In this case we have 4 above 2, or 4!/2!2! which is equal to 12/2= 6.

The possible pairs are:

1+3 = 4
1+6 = 7
1+9 = 10
3+6 = 9
3+9 = 12
6+9 = 15

So the possible weights of the unknown object could be: 4,7,9,10,12,15. We can see that 9 gr is duplicated from the first case, so we can exclude it and we can conclude that the possible solutions so far are 9 solutions - 1,3,4,6,7,9,10,12,15.

In the diagram below for example we measured an object with 15 gr.

Case 2

Case-2.gif (9.6 KiB) Viewed 41960 times

3 case – Ok, now let’s analyze 3 weights on one of the scales. We have 4 sub cases
1+3+6 = 10
1+6+9 = 16
1+3+9 = 13
3+6+9 = 18

We can see that 10 is already appeared on the second case, so we will add 3 new solutions to the set of the solutions. So far 12 solutions - 1,3,4,6,7,9,10,12,13,15,16,18.

In the diagram below for example we measured an object with 18 gr.

Case 3

Case-3.gif (9.63 KiB) Viewed 41960 times

4 case - Now about the fourth case we have only one possible solution. Add all the weights on one of the scale and the unknown object to the other. The object should be 19 gr. We can add that solution to the set of solutions and so far 13 solutions - 1,3,4,6,7,9,10,12,13,15,16,18,19.

Case 4

Case-4.gif (9.9 KiB) Viewed 41960 times

5 case - Now the more interesting cases are starting to appear. What if we add the unknown object with one known weight? Imagine you have (1 known weight, object) V.S. 1 known weight. Let’s count the possible solutions:
X+1 can be equal to 3,6,9. So the possible measurements of X are 2,5,8.
X+3 can be equal to 1,6,9. You can see by yourself that if we have X+3 on one of the scales and 1 gr to the other, it appears that the object should weight -2 gr. So the gravity should pull it upwards, instead backwards. That’s interesting philosophy subject by the way – is it possible an object to weight negative value? This way or another – we count such cases as impossible (at least on the boundaries of planet Earth).So the possible measurements of X are 3,6.
X+6 can be equal to 1,3,9. Again we exclude 1 and 3 (because of gravity laws) and we receive only 3 as possible measurement.
X+9 is impossible.

So we just added 3 more possible solutions to the set of the solutions. Now we have 16 solutions - 1,2,3,4,5,6,7,8,9,10,12,13,15,16,18,19.

In the diagram below you can see the measurement of 8 grams.

Case 5

Case-5.gif (9.62 KiB) Viewed 41960 times

6 case – Now let’s analyze the case (1 known weight, object) V.S. 2 known weights.
X+1 can be equal to (3+6),(3+9) and (6+9). Or can be equal to 9,12,15. So X can be 8,11,14. Good, we just added 2 more possible solutions to the set of the solutions – 11 and 14.
X+3 can be equal to (1+6),(1+9),(6+9). Or can be equal to 7,10,15. So X can be 4,7,12 – all duplicated solutions, so nothing new to add.
X+6 can be equal to (1+3),(1+9),(3+9). So X can be equal to 4 or 6 – again duplicates.
X+9 is not possible arrangement.
So we just added 2 more possible solutions to the set of the solutions - Now we have 18 solutions - 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,19.

In the diagram below you can see the measurement of 14 gr` object.

Case 6

Case-6.gif (9.61 KiB) Viewed 41960 times

7 case - (1 known weight, object) V.S. 3 known weights.
X+1 = 3+6+9, so X should be equal to 17. Aha, another solution!
X+3 = 1+6+9, so X = 12, duplicate.
X+6 = 1+3+9, so X = 7, duplicate.
X+9 = 1+3+6, so X =1, duplicate.
So we just added 1 more possible solution to the set of the solutions - Now we have 19 solutions - 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19.

In the diagram below you can see the measurement of 17 gr` object.

Case 7

Case-7.gif (9.77 KiB) Viewed 41960 times

8 case - (2 known weight, object) V.S. 1 known weights.
This case we can easily pass, because we already had all the possible values in the set of the solutions from 1 to 19. So what we will receive – will be only duplicates! But to complete the thoroughly examination of this puzzle, I am going to describe the possible subcases anyway.
X + 1 + 3 can be equal to 6 or 9. So solutions are 2 or 5.Duplicates!
X + 1 + 6 can be equal to 3 or 9. Only 2 as solution – duplicate!
X + 1 + 9 can be equal to 3 or 6. Not possible.
X + 3 + 6 can be equal to 1 or 9. Not possible (but another interesting part here – maybe an object with 0 gr exists)?
X + 3 + 9 can be equal to 1 or 6. Not possible.
X + 6 + 9 can be equal to 1 or 3.Not possible.

9 case - (2 known weight, object) V.S. 2 known weights.
Again we are going to receive only duplicates. But let’s write down the possible subcases:
X + 1 + 3 can be equal to 6+9. So solution is 11.Duplicate!
X + 1 + 6 can be equal to 3+9. So solution is 5.Duplicate!
X + 1 + 9 can be equal to 3+6. Not possible.
X + 3 + 6 can be equal to 1+9. So solution is 1.Duplicate!
X + 3 + 9 can be equal to 1+6. Not possible.
X + 6 + 9 can be equal to 1+3.Not possible.

10 case - (3 known weight, object) V.S. 1 known weights.
Here all of the sub cases would be not possible ones. But let’s write them down:
X + 1 + 3 + 6 should be equal to 9.Not possible!
X + 1 + 3 + 9 should be equal to 6.Not possible!
X + 1 + 6 + 9 should be equal to 3.Not possible!
X + 3 + 6 + 9 should be equal to 1.Not possible!

With this final case we complete the thoroughly examination of this puzzle. The complete answer is 19 solutions - 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19.

Now let’s analyze the answer. We can see that we can generate all the possible integers from 1 to 19 included. The total weight of the four weights is 1+3+6+9 = 19. Is this a coincidence or a pattern? Can we state that if we have 4 different weights with total weight of 19 grams, can generate all the possible integer values from 1 to 19? What is the limitation of the weight counts? The puzzle itself is a tiny and easy to crack, but it reveals a vast yet undiscovered plane of the unknown.

This topic would stay open for further examinations.

[DArk0n3]

First of all you congratulations on your, as per usual, excellent explanation. Now to the questions you pose. The answer to the first question is for sure No. As the for the second question - what do you mean by weight counts? You mean what are the values that each of the weights might take?

[showmyiq]

Thank you for the kind words and I am happy you are interested to analyse the theory further. By weight counts (which should be weight’s count) I defined the number/the count of all the weights needed (sorry for my English, sometimes I am feeling difficulties to express myself correctly).

I just wandered about this scenario: imagine you have X different weights (but by different I define different physical objects, not different grams each). So the weight’s count is X now. Let’s define the weights as A1,A2, … , AX. Let’s define the sum of all A’s as S.

If we are allowed to put and arrange the A’s as we want, can we always measure objects in the interval (1,S)?
Can we find such weights B1,B2,…,BY, such that we can measure objects in the interval (1,S) again, but for such Y<X?
If so, what is the limitation of Y (I wanted to implement that as idea, when I used the wrong expression you asked me about)?
Even if always such Y exists, it can’t be descending forever, so what is the minimum?

This week I will try to find some time to script a source code, which is going to calculate all the possible scale arrangements for a given X.
I am just curious to see how it’s going to behave …