Two gold nugget puzzle

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

DataGenetics
Posts: 24
Joined: Sat Jan 01, 2011 1:12 am UTC
Location: Seattle

Two gold nugget puzzle

On a table infront of you are sixteen gold nuggets.

You have been told that you can take any two of them as a gift.

As is human nature, you wish to take the two heaviest nuggets.

The nuggets are all random natural shapes. You are not skilled enough to estimate their individual weights, nor are you able, by hand, to determine their relative masses. Even though each of the nuggets is pure gold, they contain voids and holes so that you can't judge their weights by volume or shape. You will have to go by weight alone.

All is not lost, however, because you possess a pair of perfect balance scales. These scales will indicate which is the more massive of any items placed in the pans in opposite sides. How can you use these scales, and only these scales, to identify the two heaviest nuggets?

What is the smallest number of weighings needed to be able to identify the two heaviest nuggets (and what is your strategy)?

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Two gold nugget puzzle

I can do it in eighteen weighings, but I don't have a proof that that's optimal. I also can't determine whether it could beneficial to weigh more than one nugget on a side in any cases.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Two gold nugget puzzle

Spoiler:
First I test 8 different pairs using all 16 nuggets. Then I compare the winners, then I compare the winners, then I compare the winners=> 8 4 2 1=15 for The heaviest like comparing it with everyone individually.

This also results in a match tree (leaving out the first layer of 16)

Code: Select all

`Round 1 1 1 1 1 1 1 1 1Round 2  1    1    1   1Round 3    1         1Round 4         1`

The losing one (A) in round 4 is heavier than all nuggets on it's half of the tree, leaving 7 that could be heavier. Comparing it against the one that lost against the best one (B) removes 4 more. 1 test against the one that lost against B in round 2 removes 2 more. And one last test for the last one.

so 15+3 tests.

jmose
Posts: 7
Joined: Sat Feb 20, 2016 3:22 am UTC

Re: Two gold nugget puzzle

PeteP,

But you can't guarantee you have the heaviest in any of your tests. Since you are weighing 2 at a time to start, you could miss the heaviest one right away:

6+1 < 4+4

So you'd throw out the 6# one.

I'm still mulling this over to have my own answer.

jmose
Posts: 7
Joined: Sat Feb 20, 2016 3:22 am UTC

Re: Two gold nugget puzzle

OK, the simplest answer is that it is a single-elimination tournament, like the NCAAs, so we need 15 measurements.

Compare any 2 nuggets.
The heavier gets compared to the next nugget, and the lighter gets ignored.
Repeat another 14 times.

Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Two gold nugget puzzle

Note theoretical minimum number of weighings is 5.
16 choose 2 = 120. Each weighing can give 3 distinct results. Logbase3(120) = ~4.36

Spoiler:
Weight half of the nuggets against the other half.
- If both halves are equal, then perform the heavy coin method on each half.
- If one half is heavier, remove the lighter half and recurse on the heavier half.

Heavy coin method has been done many times. Basically split the group into groups of roughly N/3. Weigh two groups against each other. Take the heavier one. If equal, take the group not weighed. Recurse.

I think the worst case is 6 weighings.
8 vs 8 finds a heavier group
4 vs 4 finds both groups equal
two additional steps are needed to identify the heavy nugget in each group of 4.
This is a block of text that can be added to posts you make. There is a 300 character limit.

PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Two gold nugget puzzle

jmose wrote:PeteP,

But you can't guarantee you have the heaviest in any of your tests. Since you are weighing 2 at a time to start, you could miss the heaviest one right away:

6+1 < 4+4

So you'd throw out the 6# one.

I'm still mulling this over to have my own answer.

Hmm? No I mean I test two against each other, I never test two at once.

Edit:
Cradarc wrote:Note theoretical minimum number of weighings is 5.
16 choose 2 = 120. Each weighing can give 3 distinct results. Logbase3(120) = ~4.36

Spoiler:
Weight half of the nuggets against the other half.
- If both halves are equal, then perform the heavy coin method on each half.
- If one half is heavier, remove the lighter half and recurse on the heavier half.

Heavy coin method has been done many times. Basically split the group into groups of roughly N/3. Weigh two groups against each other. Take the heavier one. If equal, take the group not weighed. Recurse.

I think the worst case is 6 weighings.
8 vs 8 finds a heavier group
4 vs 4 finds both groups equal
two additional steps are needed to identify the heavy nugget in each group of 4.

I don't quite understand how that works with nuggets of arbitrary weight. Why can you discard the lighter half, the heaviest could be in it mixed with light ones?

jmose
Posts: 7
Joined: Sat Feb 20, 2016 3:22 am UTC

Re: Two gold nugget puzzle

I hadn't had my coffee yet, and missed that they want the top 2 nuggets.
Jim

Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Two gold nugget puzzle

Good catch, PeteP. I misunderstood the problem.
In that case, the minimum value should be around O(n) = ~16 since you're basically creating a max heap out of an unsorted array. (After you have the heap, it is trivial to remove the two highest elements).
This is a block of text that can be added to posts you make. There is a 300 character limit.

Elvish Pillager
Posts: 1009
Joined: Mon Aug 04, 2008 9:58 pm UTC
Location: Everywhere you think, nowhere you can possibly imagine.
Contact:

Re: Two gold nugget puzzle

Most well-known lower bounds for sorting are based on comparisons between just 2 elements, so they don't necessarily apply to this situation.

Since the nuggets could easily be such that no measurement would be equally balanced, a better lower bound than 6 is ceiling(log2(16 choose 2)) = 8 weighings.

I doubt it can be done in 8, but I'll have to think about it more.
Also known as Eli Dupree. Check out elidupree.com for my comics, games, and other work.

GENERATION A(g64, g64): Social experiment. Take the busy beaver function of the generation number and add it to your signature.

jaap
Posts: 2090
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Two gold nugget puzzle

I can do it in 12.
Spoiler:
If you split it into 4 piles, it is possible to eliminate the lightest two piles using four weighings.
Label the piles A, B, C, D, then weigh A vs B, and C vs D. Let's assume that B and D were the lighter ones (which we can do without loss of generality - swap labels if they weren't.)
A>B, C>D
Then weigh B vs D. Let assume D was the lightest (again no loss of generality - swap labels AB with CD if it wasn't)
A>B, C>D, B>D
This eliminates D, since it is definitely the lightest of all.
A>B
Now just compare B and C, and eliminate the lightest.

So for this puzzle, split 16 into 4 piles of 4, and eliminate 2 piles with 4 weighings.
Split the remaining 8 into 4 piles of 2, and eliminate 2 piles with 4 further weighings.
You now have 4 left - eliminate 2 with 4 final weighings.

Edit:
Never mind - that is wrong. The heaviest nugget can be in the lightest pile if the other nuggets in that pile are light enough.

Edit 2:
It would take 28 weighings if you use this method properly.
Spoiler:
Split into 4 piles of 4. Eliminate the two lightest in each pile using 4x4 weighings.
You now have 8 left. Split into 2 piles of 4. Eliminate the two lightest in each pile using 2x4 weighings.
You now have 4 left. Eliminate the two lightest using 4 weighings.
Total 7x4=28 weigings.

Edit 3: Actually splitting onto piles is no longer relevant. With 4 weighings you eliminate 2 nuggets. You need to eliminate 14 of the 16 nuggets, which takes 28 weighings with this method.

Edit 4: There is a straightforward way to do it in 22.
Spoiler:
Split into two piles of 8.
Find the heaviest in each pile. This takes 7+7 weighings.
Use one weighing to select the heaviest of those two nuggets. This is the heaviest nugget overall, so lay it aside as your first choice.
You now have one pile of 7 nuggets, and a pile of 8 from which you know the heaviest.
Use 6 weighings to find the heaviest in the pile of 7, and one more weighing to choose between that and the one from the other pile.
This is a total of 7+7+1+6+1 = 22 weighings.

Edit 5: With a little more thought and taking Cradarc's hint, it can be done in 18.
Spoiler:
First do an elimination tournament, doing 8+4+2+1=15 comparisons to get the heaviest nugget. This gives you a tree like this, which I have ordered to put the winners on the left side of each pairing:

Code: Select all

`1  a b c d e f g h i j k l m n o p2   a   c   e   g   i   k   m   o3     a       e       i       m4         a               i5                 a`

When you remove nugget a, the overall heaviest, you only need to propagate b up through the ranks to get the second heaviest:

Code: Select all

`1  . . c d e f g h i j k l m n o p2   b   c   e   g   i   k   m   o3     ?       e       i       m4         ?               i5                 ?`

This takes three more comparisons to get the heaviest of b, c, e, and i as the choice of your second nugget.

Jeff_UK
Posts: 66
Joined: Sat Nov 03, 2007 10:38 pm UTC

Re: Two gold nugget puzzle

I think I can do it in 1518

Spoiler:
Standard tournament of 1-18 = 15 weighings (weighments?)

Then discount any that lost to anything other than the winner.

Leaving you 4 candidates which can be sorted with 3 further weighings.
"Please only print this post if you really need to"
...hmm....I wonder how much extra energy is required to generate that request...We need a cost/benefit analysis, STAT!

micha
Posts: 2
Joined: Wed Jan 20, 2016 5:53 pm UTC

Re: Two gold nugget puzzle

Spoiler:
Often intuitions are wrong in logic puzzles, but in this case I don't think we can do better than a 'pyramidal' tournament. 15 rounds to find the heaviest one, and 3 more rounds to find the second one ( you only have to weight in the 4 that the heaviest beat at some point, which takes 3 rounds ), so 18 total.

To do it faster we would have to weight many at the same time, but this doesn't really help us I think, when the weight can be wildly different.

if you weight AB vs CD for example, there are 2 key information you DO NOT get :
-Which side has the heaviest nugget ( the side with the heaviest one could be lighter if the other one is very light )
-Which of the 2 on the heavy side is the heaviest one

Without these 2 key information, I feel like weighting many at a time is counterproductive.
Even if you then merge groups ( AB vs CD, EF vs GH, then AB vs EF, or AC vs BD... ) it doesn't really help because there's no limit to how heavy/how light a nugget can be.
If AB > CD and AC < BD...
You know that C weight less than B... And that's about it. B and C could still be the 2 heaviest, OR the 2 lightest.
It takes you 2 weighting just to find an extremely vague and barely helpful information, that you could've got in just 1 weighting of C and B.

I don't think you can find valuable information in a productive way by weighting multiples... Thus, I think 18 is the best solution. Then again if that is it will be quite disappointing.

typhonic
Posts: 1
Joined: Sun Feb 28, 2016 11:04 pm UTC

Re: Two gold nugget puzzle

16
Spoiler:
I'll pair the nuggets say 1 with 9, 2 with 10, etc.
Weigh the pairs, that's 8 comparisons. For each comparison, place the heavy on the left, but keep track of the pairs through the next steps because the second heaviest may be in the group on the right. If it is, it is paired with the heaviest on the left.
Second step, go down the left side and compare the first with the second, the third with the fourth, the fifth with the sixth and the seventh with the eighth. That will give us the four heaviest from the eight that were on the left, and so far, there were 12 weighings.
Third time through, repeat the second step with the four remaining on the left. 14 weighings.
Fourth time through repeat the second step with the two remaining on the left. 15 weighings.
Last time, compare the lighter of the two from the previous step with the right nugget paired with the heaviest nugget. 16 weighings.

mward
Posts: 121
Joined: Wed Jun 22, 2011 12:48 pm UTC

Re: Two gold nugget puzzle

For the theoretical minimum number of weighings, it is possible that no two nuggets weigh the same. In fact it is also possible that no two arbitrary piles of nuggets weigh the same. In this case, any weiging can only give one bit of information. So the minimum number of weighings is at least 7.

rmsgrey
Posts: 3511
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: Two gold nugget puzzle

mward wrote:For the theoretical minimum number of weighings, it is possible that no two nuggets weigh the same. In fact it is also possible that no two arbitrary piles of nuggets weigh the same. In this case, any weiging can only give one bit of information. So the minimum number of weighings is at least 7.

16C2=120, so you need at least 7 weighings to find the best pair, but you also need to involve every nugget in a weighing that compares it (directly or indirectly) with both of the heaviest.

Assuming that you can only weigh 1 against 1, that gives a lower bound of 15 (to find the single heaviest) plus some number to make sure everything is also compared to the second heaviest.

In order to get all the comparisons in only 7 weighings, you need to average 2v2 and it's not clear that you can get useful information from that.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Two gold nugget puzzle

If there is a solution of fewer weighings than the solution given in this thread, I have a feeling that it will take into account that the order of the top two nuggets doesn't matter. The given solution ends with knowing the heaviest and the second heaviest, which is redundant information. However, if we are restricting ourselves to just 1-to-1 weighings, then even the first weighing could possibly be between the two heaviest. I'm not sure if there's a way to reduce weighings by avoiding that information.

While there seems to be a consensus that weighing multiples is unhelpful, a method that does weigh multiples could provide a path that finds the two heaviest without knowing their individual ranks.

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

Re: Two gold nugget puzzle

typhonic wrote:16
Spoiler:
I'll pair the nuggets say 1 with 9, 2 with 10, etc.
Weigh the pairs, that's 8 comparisons. For each comparison, place the heavy on the left, but keep track of the pairs through the next steps because the second heaviest may be in the group on the right. If it is, it is paired with the heaviest on the left.
Second step, go down the left side and compare the first with the second, the third with the fourth, the fifth with the sixth and the seventh with the eighth. That will give us the four heaviest from the eight that were on the left, and so far, there were 12 weighings.
Third time through, repeat the second step with the four remaining on the left. 14 weighings.
Fourth time through repeat the second step with the two remaining on the left. 15 weighings.
Last time, compare the lighter of the two from the previous step with the right nugget paired with the heaviest nugget. 16 weighings.

There are four different nuggets that were each knocked out by being weighed against the heaviest nugget, and any one of them could be the second heaviest.