Algorithm for min times the ball to be weighted

[viren_t2005]

There are 6561 balls out of them 1 is heavy. Find the min. no.of times the ball have to be weighted for finding out the heavy ball.

 

[vaishakh]

I didn't understand this. sppose i took 1 bal and weighed it and suppose that is the heavy ball, then i am done just once.

 

[DaveC426913]

I didn't understand this. sppose i took 1 bal and weighed it and suppose that is the heavy ball, then i am done just once.

Yes. But your algorithm for finding the heavy ballis as likely to require 6561 weighings, which is also the worst possible number of weighings.

So let's rephrase:

What method is guaranteed to have the least possible weighings (even with the most pessimistic odds.)

 

[DaveC426913]

I believe I can do it in 8 weighings. (And the fact that you chose that number, leads me pretty storngly to conclude that I'm right.)

 

[D H]

Eight.

Split the pile into three groups of 2187 balls each. Call these piles 1a, 1b, and 1c. Weigh 1a versus 1b. If they don't balance, the heavier set contains the heavy ball. If they do balance, set 1c contains the heavy ball. Discard the two sets that don't contain the heavy ball. Repeat 6 more times, by which time only 3 balls will be left. The final (eighth) weighing will tell which is the heavy ball.

 

[vaishakh]

I got it now men, 6561= 3^8.

 

[vaishakh]

About balls I have another question. There are 1000 machines in a company that manufactures balls. The company has an huge weighing machine such that you can weigh n number of balls in it. The company once observedthat one of the machines are producing heavy balls, the standard ball is 1g and the faulty 1.1g. Find the method to find the faulty machine by using the weighing machine just once.
Further the manager found after few days that the same fault has creeped into a number of machines. Still the weighing has to be used once to find all the faulty machines. Find the method.

 

[D H]

About balls I have another question. There are 1000 machines in a company that manufactures balls. The company has an huge weighing machine such that you can weigh n number of balls in it. The company once observedthat one of the machines are producing heavy balls, the standard ball is 1g and the faulty 1.1g. Find the method to find the faulty machine by using the weighing machine just once.
Further the manager found after few days that the same fault has creeped into a number of machines. Still the weighing has to be used once to find all the faulty machines. Find the method.

I hope that n is a huge number and the scale is very accurate.

For problem 1, take 1 ball from machine #1, 2 from #2, ..., 1000 from #1000. Those balls would mass to 500.5 kg if the machines worked right. The excess mass over 500.5 kg by 0.1 g is the index of the faulty machine.

For problem 2, take 1 ball from machine #1, 2 from #2, 4 from #3, ..., 2^999 from #1000, for a total of 2^1000 - 1 grams. Divide the excess weight by 0.1 g and express the answer in base 2. All the one digits in the answer represent faulty machines.

 

[vaishakh]

Tha is absolutely correct. If you would have to answer in a bit more general then the answers are Arithmetic and Geometric progression respectively. I think that would make the answer much more specific.