## Two gold nugget puzzle

**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)?

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)?

### 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|

Thanks, skeptical scientist, for knowing symbols and giving them to me.

^{2})(∫|q|^{2}) ≥ (∫|pq|)^{2}Thanks, skeptical scientist, for knowing symbols and giving them to me.

### Re: Two gold nugget puzzle

**Spoiler:**

### 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.

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.

### 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.

Compare any 2 nuggets.

The heavier gets compared to the next nugget, and the lighter gets ignored.

Repeat another 14 times.

### 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

16 choose 2 = 120. Each weighing can give 3 distinct results. Logbase3(120) = ~4.36

**Spoiler:**

This is a block of text that can be added to posts you make. There is a 300 character limit.

### 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.36Spoiler:

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?

### Re: Two gold nugget puzzle

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

Jim

Jim

### 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).

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.

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(g

GENERATION A(g

_{64}, g_{64}): Social experiment. Take the busy beaver function of the generation number and add it to your signature.### Re: Two gold nugget puzzle

I can do it in 12.

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.

Edit 4: There is a straightforward way to do it in 22.

Edit 5: With a little more thought and taking Cradarc's hint, it can be done in 18.

**Spoiler:**

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:**

Edit 4: There is a straightforward way to do it in 22.

**Spoiler:**

Edit 5: With a little more thought and taking Cradarc's hint, it can be done in 18.

**Spoiler:**

### Re: Two gold nugget puzzle

I think I can do it in ~~15~~18

**Spoiler:**

"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!

...hmm....I wonder how much extra energy is required to generate that request...We need a cost/benefit analysis, STAT!

### 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.

### 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.

^{16}C

_{2}=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.

### 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.

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.

### Re: Two gold nugget puzzle

typhonic wrote:16Spoiler:

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.

### Who is online

Users browsing this forum: No registered users and 6 guests