The Weights' Problem Part II - 02/04/2013

[showmyiq]

This puzzle was proposed by Sergey Sokolov via Facebook

What is the minimum number of weights needed to measure every object with total weight of 1gr, 2gr, .. ,120 gr, but this time using scale?

Can you find universal formula describing the same algorithm for object with total weight of 1gr, 2gr, …, Xgr -
again using scale?

You are allowed to use only one unknown object per measurement!

[showmyiq]

Now when you state that we are dealing with scale, the things are really different (and I was really interested how the algorithm behaves).

Now, let’s start!

Again, let’s define such set A_i, which holds such weights that can generate all the unknown object weights from 1 to I (but this time using scales, not weight – single scale). Ok, so we are looking for A_120 = ?.

Let’s see first what is going on with A_1. It’s obvious that A_1 = {1} (there can be infinite solutions again, but we were looking for the minimum ones).

What about A_2? Well, one possible solution is A_2 = {1,1). Since, we are dealing with scales this time, not weight – I want to push the things further now and find such set A_2, that it’s not only a minimum one, but on the same time holds the maximum value of the elements it holds. In other words, such A_2 = {x,y}, so x and y to be with maximum values. I can choose A-2={3,2} and A_2={3,1}. Since, A_2={3,2} will crash to generate an object with weight of 4 gr, I avoid it. Therefore the best approach and value for A_2 is A_2 = {3,1}, because we can generate not only 1 and 2, but 3 and 4 too. Therefore A_4 = {3,1}
Now, because I want to push all to the limits, I want to find such Z, so A_5 = {Z,3,1}, to be maximum. Therefore, Z-3-1 = 5, so Z = 9. The minimum A_5 = {9,3,1}. Since {3,1} can generate us all the values from 1 to 4, therefore {9,3,1} can generate us all the values from 1 to 13. So A_13 = {9,3,1}. Again pushing the limits and choosing the next element to be Z – 9 – 3 – 1 = 14. Therefore Z = 27.

Therefore, A_14 = {27,9,3,1}. This can generate all the unknown objects up to 27+9+3+1 = 40.
Therefore A_40 = {27,9,3,1} too. Again pushing the limits, therefore Z = 81.
Therefore A_41 = {81,27,9,3,1}. This can generate all the unknown objects up to 81+27+9+3+1= 121.
Therefore A_121 = A_120 = {81,27,9,3,1}.

Conclusions?

1st – excellent puzzle!
2nd – We can deduct that all the elements of this set will be powers of 3.

Answer?

Well, we saw that (in my previous solution) if we are dealing with weight, not scale – the solution is behaving around the powers of 2. We just saw that if we are dealing with scale, the solution is behaving around the powers of 3. My answer is – can you think up of physical measuring device, which in the given problem will behave around the powers of 4?

Extra information:

I have made this simple PHP script, which is pushing the limits for optimized solution. Just another way to calculate powers of 3, haha.

Code: Select all

<?php
$initiate = 0;
for ($temp=1;$temp<=10;$temp++)
{
 $require = $initiate+1;
 $nextelem = $require + $initiate;
 echo $nextelem. "<br />";
 $initiate = $nextelem + $initiate;
}

Results:

1
3
9
27
81
243
729
2187
6561
19683

[showmyiq]

Puzzle is solved by shashank201090!