Weighing problem

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

t1mm01994
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Weighing problem

I don´t think this has been posted, if it has, please link the thread, and lock this one

Say, you have N blocks (n geq 3), each with a different weight, and a balance, which can compare the weight of 2 blocks, so 1 block on each side. In how many times can you figure out which 2 weights are heaviest? I myself get the row
Spoiler:
For 3, you need 2.
For every value K you need the value of (K-1) + 1, except when K is writeable as 2^m-1, with m being a natural number. This can be achieved by the knock-out system, and then by comparing any weights you haven't excluded from being top 2 yet.

Any thoughts on this would be appreciated.

Godskalken
Posts: 159
Joined: Wed May 14, 2008 3:29 pm UTC

Re: Weighing problem

Could you explain your solution a bit more detailed?
If I understand you correctly,
Spoiler:
You do this recursively, that is, when you want to find the top two of N blocks, you first find the top two of N-1 blocks. Then you claim you can find the top two of the N blocks by one extra weighing, but if this is what you are saying then you are wrong. True, you can find whether the new block is among the top two by comparing it to the lightest of the previous top two, but that means you have to know which one is the lighter one. Even if you do, you won't necessarily know which is the lighter of the top two of the N after just one weighing.
If you want to make sure you always know which is the lighter of the top two, then you might have to use two extra weighings for each added block. This means 2*N-1 weighings in the worst case, but still N-1 weighings in the best case.

Also, I don't understand what you are saying about the knock-out. The knock-out would require N-1 weighings just to find the heaviest one, so if you really had a method for finding the top two in N-1 weighings from before, this can only make it worse.

Edit; an algorithm that may be optimal:
Spoiler:
This might be similar to what you had in mind for the knock-out thingy, but since I'm not sure what you meant I'll post it anyway.

Divide the blocks into two groups of equal size (or of sizes floor(N/2) and ceil(N/2) if N is odd). Do one pass of bubble sort on each group, to find the maximum element in each group. This takes N-2 comparisons. Compare the heaviest blocks in each group. Insert the lightest one into the group of the heavyest one and perform another pass of bubble sort on this group, for a maximum of ceil(N/2)-1 comparisons (assuming the heaviest one was removed from the group). This last step finds the second heaviest block. Total comparisons: N+ceil(N/2)-2 or approximately 3N/2.

I can't prove that this is optimal, but I would be surprised if you can do much better. Since finding the heavyest block requires at least N-1 comparisons, and sorting them all requires at least ~N log2(N) comparisons, I would be surprised if it is not the case that, to find the K heaviest blocks, you need at least $\sum_{i=0}^{K-1} \frac{N}{2^i}$
comparisons, plus minus a small constant.

t1mm01994
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Re: Weighing problem

Alright, I'll try and explain some more.
Spoiler:
First of all, a little adjustment; it's not for each 2^(m)-1, it's for each 2^(m)+2.
It gives a value of about N, actually, for extremely big N, it almost becomes N; some 1/3 better than yours. My idea is almost the same as yours though: See below.
Let's say we take N to be 13. First, we look at N when N is 16 (the first power of 2 above N). Using the knock-out system, you get the following scheme (I assume the first one wins, but it works the same if the other block is heavier):
1v2 3v4 5v6 7v8 9v10 11v12 13v14 15v16
1v3 5v7 9v11 13v15
1v5 9v13
1v9
1
Which makes 1 the heaviest of all. For the second heaviest, we can exclude all blocks that have 2 or more heavier weights. Since every weight, except for 1 has 1 as heavier weight, I will note the other heavier weight between brackets, derivable from the above schedule. This way, 4(3), 6(5), 7(5), 8(7), 10(9), 11(9), 12(11), 13(9), 14(13), 15(13), and 16(15) are excluded, which leaves us with 4 weights in for 2nd place: 2,3,5,9. We already have used 15 weighings, and now we just need to find the heaviest of those. This can be done in 3 turns, which gives us a total of 18 weighings.
If we now want 13 instead of 16, we simply don't look at all weighings involving 14,15 and 16. This leaves us with 3 weighings less, 13v14, 15v16, and 13v15 aren't needed now. So, for 13, we need 15 weighings.
Also to this, there is one little exception, if we have 2^(m)+1, you don't look at the one above, you look at 2^m instead of 2^(m+1). Then, using the last scheme, instead of 2,3,5 and 9, you compare 2,3,5,9 and 17, which takes 4 weighings, giving a total of 19 times.
For every power of 2, let's say 2^m, the amount of weighings you need using this scheme is 2^(m) + m - 2. You need 2^(m) - 1 to find out which is heaviest, then m-1 to find out which is the second heaviest (see also example). If we now write N as 2^(m) - a, 0 <=a<2^(m-1), the amount of weighings needed is 2^(m)+m-2-a, except when it is an exception given above.

Sorry for my english not being so great, I'm not english, and not grown up as well. Does anyone see any flaws in this, or an other, more optimal solution?

FCN
Posts: 120
Joined: Wed May 28, 2008 7:47 am UTC

Re: Weighing problem

I got an answer without reading any of the spoilers, and after reading t1mm01994's last post I think I was slightly off:
Spoiler:
I had n-2 + ceiling(log2(n)), but now I think it's n-2 + ceiling(log2(n-1)). Either way, it's on the order of n + log2(n)

My original reasoning:
Spoiler:
It takes n-1 weighings to find the heaviest, since each non-heaviest has to lose one weighing. The only candidates for second-heaviest are the ones that lost directly to the champion (heaviest) block. To minimize the worst case scenario for the number of candidates, you can set up the weighings like a single elimination tournament (like the NCAA college basketball tournament) with brackets and rounds; this requires ceiling(log2(n)) rounds, with some blocks getting a "bye" in the first round if n is not a power of 2. There will be either floor(log2(n)) or ceiling(log2(n)) candidates for second-heaviest (depending on whether the champion had a bye or not), and it takes that many minus 1 weighings to figure out which is the heaviest of the candidates. So n-1 weighings to find the heaviest, and then up to ceiling(log2(n)) - 1 weighings to find the second-heaviest, for n-2 + ceiling(log2(n)) total weighings.

But can you ever do better than this? After reading t1mm01994's latest post I realized that sometimes you can:
Spoiler:
You don't necessarily need to know which is heaviest and which is second-heaviest, just which two are the two heaviest. This can sometimes save you one weighing - but only (as far as I can tell) in the special case where n is one more than a power of 2, n = 2^m + 1. In that case, you can run a tournament of n-1 blocks (taking m rounds). Then winner of the tournament is one of the two heaviest, and the only candidates for being the other one of the two heaviest are the blocks that the winner beat directly plus the one block that didn't enter the tournament (although if the unentered block is heavier than the other candidates, you won't know if it's the heaviest or second-heaviest overall). That saves a weighing in the tournament, and it doesn't alter the worst-case scenario for the number of candidates. Consider n = 9. My old method would've had you run a 4-round tournament, with the first round containing only one matchup. It would've taken 8 weighings to find the heaviest, and then there would have been 3 or 4 candidates for second-heaviest (depending if the winner played in the first round game). That gives you 10 or 11 weighings total. The new method is to set one block aside and run a three-round (8-block) tournament (taking 7 weighings), and then there will always be 4 candidates for the other top-2 block (the 3 that lost to the champion plus the one that was set aside). Take 3 more weighings to find which of the 4 candidates is heaviest, and that's 10 weighings total for the new method, vs. up to 11 for the old. The new method takes one less weighing when n = 2^m + 1, and you can account for that by changing the equation to take the log2 of (n-1) instead of n.
Spoiler:
LuNatic wrote:
Dear FCN,
You are:
a) Terrible, but in an awesome way.
or
b) Awesome, but in a terrible way.
I'm having difficulty deciding which.

t1mm01994
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Re: Weighing problem

FCN: That was my approach sas well, I just don't have the formal mathematical knowledge to express it that way. I got the same number, I believe.. the "m" I was talking about is your log2(n), I had the minus 2, and N.. so I believe we got to the same answer.