yet another wieghing problem

[phil1882]

you have a balance scale with an unknown weight, known to be less than 365. to find the wieght, you have the 6 known wieghts 1,3,9,27,81, and 243.

you have the following allowed moves:

1) place a wieght on one side of the scale or the other.

2) move a wieght from one side of the scale to the other.

3) remove a wieght.

assuming you want to minimize the number of moves, what's the most moves required to find any weight? (that is; what's the worst case scenario for minimizing the number of moves?)

[superprismatic]

9.

I retract my answer (in the spoiler above). I must have had a brain fog when I replied. I hope this didn't keep anyone from working on this problem.

[superprismatic]

369. Using a Gray code on the 364 necessary configurations of weights on the scale, I can go through all of them by changing only one weight from configuration to configuration except for 5 breaks, where I had to change two. So, my worst case is 369.

[CaptainEd]

Even if I start with the unknown in one pan, it takes me 5 moves to find any number from 1 to 14. When you said it takes 9 to do 365, I was, as always when I read your stuff, AWED.

[CaptainEd]

Looking at SP's answer, I think we are working on different problems. I think I am trying to find the minimax number of moves needed to find any given unknown weight. "minimax" means we need to minimize the maximum over all weights.

for 1,3, weights 1 to 5, 2 moves is enough

for 1,3,9, weights 1 to 14, 5 moves is enough

for 1,3,9,27, weights 1 to 41, 8 moves is enough I'll show the entire protocol later

Using a linear extrapolation (with NO JUSTIFICATION), I'm guessing we can do 1,3,9,27,81,243, weights 1 to 365, 14 moves might be enough

Edited June 17, 2012 by CaptainEd

[superprismatic]

Looking at SP's answer, I think we are working on different problems. I think I am trying to find the minimax number of moves needed to find any given unknown weight. "minimax" means we need to minimize the maximum over all weights.

for 1,3, weights 1 to 5, 2 moves is enough

for 1,3,9, weights 1 to 14, 5 moves is enough

for 1,3,9,27, weights 1 to 41, 8 moves is enough I'll show the entire protocol later

Using a linear extrapolation (with NO JUSTIFICATION), I'm guessing we can do 1,3,9,27,81,243, weights 1 to 365, 14 moves might be enough

Actually, we are working on the same problem. But since nobody posted anything for a day and a half, I thought I would throw out some

gray code thoughts. So, I can go through the gray code scheme mindlessly and am able to determine any weight in at most 369 moves.

The average time is about half of that. The gray code is much too restrictive, however, because it counts moving a weight from one pan

to another as two moves (the OP has it as one). I was going to try other things along a modified gray code line when I get some time in

a day or two. I may be barking up the wrong tree, but it's fun to play with this stuff. It's good to see that the Captain is working on this

and I suspect that he'll get to the bottom of this one before I do.

[plasmid]

Edit: realized I didn't consider an important case

Edited June 18, 2012 by plasmid

[CaptainEd]

Plasmid, that is an elegant answer! Assuming Philip will allow us to preset all the weights before the first move. If not, you're up to 17. And you've proved it!

[plasmid]

I think I'm reading the problem fundamentally differently than superprismatic. I can get it in 13. Fewer might be possible.

We know that there is some orientation of weights such that you can have the unknown weight on the left balance pan and the other weights on either the left pan, the right pan, or off the balance completely in which the scale will be balanced. (Hopefully that's already obvious.)

If you can start of with any starting orientation you wish without having that count as a move, then start off with

Left pan: unknown, 1, 3, 9, 27, 81

Right pan: 243

This would be balanced if the unknown weighs exactly 243-81-27-9-3-1 = 122. Importantly, if the unknown weighs less than 122 (CASE A) then you know that the final solution has the 243 weight off the balance completely and you should remove it; if the unknown weighs more than 122 (CASE B) then the final solution has the 243 weight on the right pan. (Again, I hope this is obvious without proof.)

In the case where the right pan is heavier (CASE A, meaning 243 belongs off the balance) then you should move 243 off the balance completely and all the remaining weights will be on the left pan. You will also know that the solution state does not have 81 on the left pan. Next, move 81 to the right pan. If the right pan is now heavier (meaning unknown < 81-27-9-3-1 = 41), then you know 81 must be off the balance completely and you should remove it. If the left pan is heavier (meaning 41 < unknown < 122) then you know that 81 belongs on the right pan and you should leave it there. Importantly, in the worst case scenario, you will know that you have the 243 and the 81 in the correct position after at most three moves.

In the case where the left pan is heavier (CASE B, meaning 243 belongs on the right pan): The next step will be to move the 81 weight from the left pan off the balance. If the right pan is now heavier (meaning 122 < unknown < 243-27-9-3-1 = 203), you will know that the solution state has 81 on the left pan and you will put it back on the left pan and proceed. If the left pan is still heavier after you remove 81 (meaning 203 < unknown), then put 81 on the right pan. If the right pan is heavier after you move the 81 to the right pan (meaning 203 < unknown < 243+81-27-9-3-1 = 284), then you know that 81 must be off the balance in the solution state and you should remove it; if the left pan is still heavier after you move 81 to the right pan (meaning 284 < unknown), then you know that 81 must be on the right pan in the solution state and you should leave it there. Importantly, in the worst case scenario, you will know that you have the 243 and the 81 in the right position after at most three moves.

Whether you've gone through CASE A or CASE B, you've now got both the 243 weight and the 81 weight in the position where they need to be after at most three moves. Now, depending on whether the left pan is heavier or the right pan is heavier, you can go through the CASE A and CASE B scenarios again but move the 27 weight instead of the 81 weight, and you will get the 27 weight in the correct position after at most three more moves for a total of six moves. Then you can similarly get 9 in the correct position after a total of nine moves, and get 3 in the correct position after a total of twelve moves.

Once you know that 3, 9, 27, 81, and 243 are all in the correct position and you still have 1 sitting on the left pan, if you haven't found a balanced state already, you can make the thirteenth move be to move the 1 from the left pan to the right pan. If it's balanced, then you have the answer. If it's not balanced, you know that the solution state has the 1 off the scale completely (because you've already got all the other weights in the correct position and you've already tried the 1 on the left pan and the right pan), so you've figured out the unknown weight without needing to make a fourteenth move to reach balance.

[phil1882]

nicely done plasmid. :-)

[bhramarraj]

I have solved the case when the weights given are 1,3,&9; and we have to find max. moves of weights to find out exact value of an unknown weight known to be less than 14.

CASE-A

Move-1a: W=3. But if W<3, then

Move-2a: W+1=3, i.e. W=2. But If W<2, then W=1, since W cannot be 0 .

CASE-B

Move-1b: W>3, then

Move-2b: W=9+3 i.e. W=12. But if W>12, then W=13 (as from condition given in OP W<14). But if W<12, then

Move-3b: W=9 But if W>9, then

Move-4b: W=9+1 i.e. W=10. But if W>10, & since from Move-2b W<12, therefore W=11.

CASE-C

Move-1c: W>3,

Move-2c: W<9+3 i.e. W<12

Move-3c: W<9

Move-4c: W+3=9 i.e. W=6, But if W>6, then

Move-5c: W+3=9+1 i.e. W=7 But if W>7, & since from Move-3c W<9, therefore W=8.

CASE-D

Move-1d: W>3,

Move-2d: W<9+3 i.e. W<12

Move-3d: W<9 Move-4d: W+3<9 i.e. W<6,

Move-5d: W+3+1=9, i.e. W=5. But if W<5 & since from Move-1d W>3, therefore W=4.

Thus we need maximum 5 movements of given weights, in order to know exact value of unknown weight which is known to be less than 14.

Now for 1,3,9,27,81 & 243, I have to work out.

[CaptainEd]

N weights Wi of weight 3^i, i = 0 ... N-1

Two pans, L and R

Start with all weights in left pan, with Unknown. That's wasteful of one move, but it makes it easier for me to express the algorithm:

Let V = reportable value under construction

Set V = - (sum of the weights)

For i = n-1 down to 0

----move Wi from L to R; V = V + 2 * 3^i

----if L is light,

--------remove Wi from R; V = V - 3^i

--------if L is still light,

------------move Wi to L; V = V - 3^i

----if L balances R, declare V and EXIT

if i = 0 if L is light, declare V-1 else declare V+1

[CaptainEd]

So Plasmid's beautiful algorithm guarantees a maximum number of moves when the weights, expressed in an odd ternary notation, are

RLLLLR

That is, the 243 and the 1 are in the Right pan, while the U and all other weights are in the Left pan. In this case, there are 4 triple moves (move from Left to right, remove same weight, move same weight back to Left) and 2 single moves (Left to Right). Actually, since Plasmid starts with RLLLLL, there's only one single move.

So this algorithm has a maximum number of moves of 3n-5, where n is the number of weights.

The algorithm is so clear, and solves such an important problem, I'm happy to declare that as a solution.

So, my next question is: what is the algorithm and max moves from a LeMans start--empty pans?