Balls are fake

Logic Level 3

A shop was delivering $3^{15}-2$ balls. Some children placed a fake ball, perfectly identical to the original balls which is heavier than original ones. Authorities came to know it and brought an accurate weighing scale on which load is placed on both sides. So how many minimum number of trials are required to identify the fake ball?

14 2 17 13

\frac{3^{15}-1}{2}

16 15 3

2 solutions

Hung Woei Neoh
Jul 16, 2016

Relevant wiki: Information Compression

For every single trial, we divide the pile into $3$ groups. We measure the two groups with the same number of balls. If one is heavier, the bomb is in there; if both have the same mass, then the unmeasured group will have the bomb.

First trial

Divide into $\color{#3D99F6}{3^{14}},\;\color{#D61F06}{3^{14}-1},\;\color{#D61F06}{3^{14}-1}$ , measure the two groups with $\color{#D61F06}{3^{14}-1}$ balls

Second trial

If the bomb is in $\color{#3D99F6}{3^{14}}$ pile: Divide into $\color{#EC7300}{3^{13}}$ for all 3 piles, and measure any two groups
If it is in the $\color{#D61F06}{3^{14}-1}$ pile: Divide into $\color{#EC7300}{3^{13}},\;\color{#EC7300}{3^{13}},\;\color{#20A900}{3^{13}-1}$ , measure the two groups with $\color{#EC7300}{3^{13}}$ balls

Third trial

If the bomb is in $\color{#EC7300}{3^{13}}$ pile: Divide into $\color{#69047E}{3^{12}}$ for all 3 piles, and measure any two groups
If it is in the $\color{#20A900}{3^{13}-1}$ pile: Divide into $\color{#69047E}{3^{12}},\;\color{#69047E}{3^{12}},\;\color{teal}{3^{12}-1}$ , measure the two groups with $\color{#69047E}{3^{12}}$ balls

$n$ th trial, $n\geq 4$

If the bomb is in $\color{#624F41}{3^{15-n+1}}$ pile: Divide into $\color{magenta}{3^{15-n}}$ for all 3 piles, and measure any two groups
If it is in the $\color{olive}{3^{15-n+1}-1}$ pile: Divide into $\color{magenta}{3^{15-n}},\;\color{magenta}{3^{15-n}},\;\color{cyan}{3^{15-n}-1}$ , measure the two groups with $\color{magenta}{3^{15-n}}$ balls

Notice that when we reach $n=15$ :

$15$ th trial

If the bomb is in $\color{#3D99F6}{3^{1}=3}$ pile: Take any two remaining balls and measure. If one of them is heavier, it's the bomb; if both have the same mass, the unmeasured one is the bomb
If it is in the $\color{#D61F06}{3^{1}-1=2}$ pile: Compare the two remaining balls. One of them will be heavier than the other

Therefore, we can see that a minimum of $\boxed{15}$ trials is required to locate the bomb

Simply wow solution (+1)

Ashish Menon - 4 years, 11 months ago

Great solution +1. Can you generalise it i.e. for n trials?

Prince Loomba - 4 years, 11 months ago

For a pile with $3^n-2$ balls, we will need $n$ trials to find the bomb. Is this what you're looking for?

Hung Woei Neoh - 4 years, 11 months ago

Obviously n trials meant that

Prince Loomba - 4 years, 11 months ago

In general, we'd need $\lceil \log_3 n \rceil$ comparisons.

Agnishom Chattopadhyay - 4 years, 11 months ago

I want proof. Ik that

Prince Loomba - 4 years, 11 months ago

@Prince Loomba – With every comparison, you are narrowing down the search space by a factor of 3. There can be at most $\lceil \log_3 n \rceil$ such comparisons.

Agnishom Chattopadhyay - 4 years, 11 months ago

Nice Solution...+1

Sabhrant Sachan - 4 years, 11 months ago

I suppose this argument is correct though you didn't made explicit in your proof why the procedure used gives you the minimum number of steps.

Just when that is made explicit you can finally conclude that you obtain the bomb in the least number of moves and it's important so it should be let implicit anyway.

Btw , there is also another cute problem with weightings which is also interesting to analyze I suppose anyway . This one asks what is the minimum number of weightings if you know that the fake ball is either heavier or lighter but don't know which of two anyway.

That problem is a little bit harder maybe than this one as it's procedure isn't as direct but may help for arriving at very general understanding of problems like this one anyway. It's also interesting to analyze different procedures and their optimal time compared with one another.

Nonetheless it's not a very very hard problem so maybe it's not all that interesting.

And cute solution btw anyway.

A A - 4 years, 11 months ago

Neice Paris?

Refath Bari - 4 years, 11 months ago

Alex Li
Aug 21, 2016

For those wanting proof that Hung Woei Neoh's solution is the smallest:

The balance only can have 3 results of each weighing: "Right-side is heavier, left-side is heavier, and both are equal"

Therefore, no matter what way how we consider our results, since there are only 3 pieces of information possible to obtain, we can, at most, separate the balls into 3 groups. The most efficient method of doing this, if we want to reduce possibilities to 1, is to split them into equally-sized groups. Otherwise, there will be a chance of having the bomb in the biggest group, and since we are assuming the worst possible scenario, there will always be a bomb in the biggest group.

Hope that makes sense!

Balls are fake

2 solutions

0 pending reports