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)
On
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.
On
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 need at most 3 weightings.
One possible solution algorithm is:
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.