# Identify heavier ball in group of $14$

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)

• 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? – RoyPJ Nov 3 '17 at 10:32
• @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 !) !! – Djarallah Brahim Nov 3 '17 at 10:39
• So my assumption was incorrect. I can do it in 3 weightings. – RoyPJ Nov 3 '17 at 10:47
• @bof i'll fixed it :) thank u – Djarallah Brahim Nov 3 '17 at 11:01
• have you consulted puzzling section ? there is a lot of similar issues posted there. – Abr001am Nov 3 '17 at 11:35

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.

• thank you i think it is correcte – Djarallah Brahim Nov 3 '17 at 11:05

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.

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.

• You seem to have a clever solution. Unfortunately it's quite difficult to understand how it works. Could you clarify? – md2perpe Nov 3 '17 at 16:30
• 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. – wendy.krieger Nov 4 '17 at 10:35
• 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. – md2perpe Nov 4 '17 at 11:17