0

There are similar puzzles but I think this one is different.

You are given eight metal balls. You know one weighs less than the rest.

You are given a balance scale. What is the smallest number of weighings it takes to find the lighter one?

Once you have solved that,

if you can weigh ten times, what is the largest number of balls you can have and still find the lighter one?

Gareth McCaughan
  • 119,120
  • 7
  • 313
  • 454
Hashbrowns
  • 575
  • 2
  • 14
  • (The question quotes a Wikipedia page which essentially gives the solution to the generalized version here, though it states it for 2,3,4 weighings rather than giving a general formula or the answer when w=10.) – Gareth McCaughan Nov 23 '16 at 17:28
  • ... Actually, my comments above are not quite accurate: having essentially given the general version of the problem in the question, that question then asks the general version of the problem (perhaps the questioner was unable to see how to extend the sequence 3,9,27,81?), which is then explicitly solved in an answer. – Gareth McCaughan Nov 23 '16 at 17:30
  • Actually the smallest possible amount of weighings can be 1, but that cannot always be true: you pick 2 balls and measure them. If you're lucky enough you picked the one that weighs less. If not, you go with the method of @GarethMcCaughan in his accepted answer – Mattia Nocerino Nov 24 '16 at 09:12

2 Answers2

2

You can do it in

two weighings

as follows:

First weigh ABC against DEF. If they come out equal then the odd one must be one of G,H; weigh them against one another and you're done. Otherwise the lighter group has the odd ball; now weigh two of them against one another, choose the lighter if they don't balance and the third ball if they do.

You can't do better because

there are 8 possibilities and one weighing has only 3 possible outcomes.

For the follow-up question

clearly the number is at most $\lfloor3^{10}\rfloor$. Can we achieve this? Yes. If we can do $n$ balls in $w$ weighings then we can do $3n$ balls in $w+1$ weighings: weigh $n$ against $n$ and then we are left, one way or another, with a group of $n$ to handle. We can do 1 ball in 0 weighings, so by induction we can do $3^w$ balls in $w$ weighings; and just by counting possibilities we can't do better.

(My apologies; an earlier version of this had an entirely wrong upper bound in it without proof, because I'm an idiot. Hopefully de-idiotized now.)

boboquack
  • 21,982
  • 1
  • 66
  • 138
Gareth McCaughan
  • 119,120
  • 7
  • 313
  • 454
1

You can do it in

two weighings

Explanation

Take two 3 bunches of balls and weigh them. If they come out to be equal, then, weigh G and H and one of them is lighter. And If they are not equal, the lighter one has the odd ball and now weigh two of them against each other and choose the lighter one. And you are done.

Sid
  • 15,153
  • 2
  • 43
  • 94