1
$\begingroup$

We have $14$ identical looking balls, one of them is heavier than the rest of $13$ (all the others weigh exactly the same), how many of weighings (minimum) to find the heavier one? And I want to know if there is mathematical formula for this problem?

(Sorry for my English)

$\endgroup$
  • $\begingroup$ If you are lucky you need 2 weightings, at maximum you need 13 weightings. (I assume you can only weight one ball at a time) Is this what you are asking for? $\endgroup$ – RoyPJ Nov 3 '17 at 10:32
  • $\begingroup$ @RoyPJ but for the example of 9 balls we can do it in 2 weightings just we make 3 groups of 3 balls A,B,C....youtube.com/watch?v=0Jgow5x09qw but for this example i try to make a groups of 4/4/4/2 and i get 4 weightings (not sure that i'm correcte !) !! $\endgroup$ – Djarallah Brahim Nov 3 '17 at 10:39
  • 1
    $\begingroup$ So my assumption was incorrect. I can do it in 3 weightings. $\endgroup$ – RoyPJ Nov 3 '17 at 10:47
  • $\begingroup$ @bof i'll fixed it :) thank u $\endgroup$ – Djarallah Brahim Nov 3 '17 at 11:01
  • $\begingroup$ have you consulted puzzling section ? there is a lot of similar issues posted there. $\endgroup$ – Abr001am Nov 3 '17 at 11:35
2
$\begingroup$

You need at most 3 weightings.

One possible solution algorithm is:

Divide the balls in 2 groups of 7 balls.

Compare the 2 groups.

Divide the heavier group of 7 balls into 3 groups (3-3-1)

Compare the 2 groups containing 3 balls. If they are equal, then the 1 remaining is the heaviest.

Else: Divide the heavier group of 3 balls into 3 groups containing 1 ball.

Compare 2 of those balls. If they are equal, the remaining ball is the heaviest.

One can also start with 3 groups (5-5-4) and terminate in 3 weighting steps (and I bet there are more different solutions). It is obvious that you can't terminate with 2 weighting steps at most, but I can't prove this formally.

$\endgroup$
  • $\begingroup$ thank you i think it is correcte $\endgroup$ – Djarallah Brahim Nov 3 '17 at 11:05
1
$\begingroup$

To solve the problem in a general context, we need the following lemma:

LEMMA. With one possibility of weighing $n$ balls, we can localize in worst case scenario the heavy ball in a group of $\lceil \frac{n}{3}\rceil$ balls

Proof. Start with the groups $(\lceil \frac{n}{3}\rceil,\lceil \frac{n}{3}\rceil, n-2\lceil \frac{n}{3}\rceil$). We notice $n-2\lceil \frac{n}{3}\rceil\leq \lceil \frac{n}{3}\rceil$. By weighting the first two groups, we can localize the ball in one of the groups as mentioned. It stays to show that we can't do it in a better way. Suppose we weight with the first two groups in a division $(a,b,c)$. We can only get information, when $a=b\leq \frac{n}{2}$, $c=n-2a$, so we get division $(a,a, n-2a)$. Suppose we take $a>\lceil \frac{n}{3}\rceil$. Then in worst case we can localize the heavy ball under $a$ balls, which is a bader strategy then our strategy. Suppose we take $a<\lceil \frac{n}{3}\rceil$. Then in worst case we can localize the heavy ball under $n-2a\geq \lceil \frac{n}{3}\rceil$ balls, which isn't a better strategy then ours, too. So we have showed the lemma.

With the lemma we conclude that we need $\lceil \frac{\log n}{\log 3}\rceil$ weighings, so $3$ in our case.

$\endgroup$
-1
$\begingroup$

You need just three weighings.

Number the balls in odd numbers, and the remaining number is 20, except 13. Then use numbers 0 and 26

So the balls are numbered, 0,1,3,5,7,9,11,15,17,19,20,21,23,25,26 or in base 3,

000, 001, 010, 012, 021, 100, 102, 120, 122, 201, 210, 212, 221,222

454 v 454 v 454 for the odd numbers, and 5,4,5 for this set.

Label the pans 0 and 2, and leave 1 off. Weigh the three digits, and record which pan goes down, or 1 for equal. The number written is the base 3 value of the heavy ball.

This is actually a three-state system, and the trinary numbers give the weighings, The solution is good for 26 balls, numbered in trinary numbers 0 to 27 (222) except 13 (111).

0 = put ball in left pan heavy 0 makes this pan go down

1 = leave ball off heavy 1 makes pans equal

2 = put ball in right pan. heavy 2 makes right pan go down.

Since the heavy ball is comprised of three trinary numbers, the weighings will give up to 26 unique numbers.

The solution as given is a slightly modified version of the problem where one coin is known good, and one of thirteen coins is defective, can be either heavy or light. This has a solution in

M = left pan; 0 = left off; 1 = right pan.

The 13 coins are numbered from 1 to 13, in trinary, with the even numbers in reverse sign, viz 1, -2, 3, -4, ..., -13. In trinary, they look like

001, 0m1, 010, 0mm, 1mm, m10, 1m1, m01, 100, m0m, 11m, mm0, 111.

The known good coin is numbered -7, ie m1m.

You weigh the coins according to first, second, third digit, and get the numbers as m = left pan down, 0 = balance, 1 = right pan down.

If the number is even (ie an odd number of 0's), swap the m and 1's, eg m10 = 1m0,

You have then determined the number of the coin (as the weightings are 9,3,1), and whether it's heavy or light. So 1m0 gives +9-3.1 = +6, coin 6 is defective, and heavy.

But you can't do it with 14 coins in three weighings unless you know the defect is +. In that case, you can do as many as 26 weighings.

$\endgroup$
  • $\begingroup$ You seem to have a clever solution. Unfortunately it's quite difficult to understand how it works. Could you clarify? $\endgroup$ – md2perpe Nov 3 '17 at 16:30
  • $\begingroup$ It uses trinary. It's a slightly modified version of the 13-coin heavy/light solution. It works with 120 coins, with no 61=(3^5+1)/4. $\endgroup$ – wendy.krieger Nov 4 '17 at 10:35
  • $\begingroup$ That it was based on trinary was obvious, but exactly how it works was not. I think that I have understood it now: Take the five balls with $0$ as first digit and weigh them against the five balls with $2$ as first digit. This gives the first digit in the ball's number ($1$ for equal). The repeat for the second and third digits. Now you have three trinary digits that give the number/label of the heavier ball. $\endgroup$ – md2perpe Nov 4 '17 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.