Solve the Brain Teasers: Find the Broken Machine

[Davorak]

Three related brain teasers:(I did not see them posted before)

There is a mint, let's say the Denver mint. In the mint there are 100 penny making machines. In the problems below there is something wrong with one of the machines. You may produce as many coins as you would like from any of the machines and weigh them, but there is only one scale. The goal is to find the broken machine with the lest number of weigh ins. Oh and you will break the scale if you put infinite coins on it.

#1
1 of the hundred machines produces coins that weigh 10% more then they should.
How many weigh ins do you have to have to find the broken machine? What is your method?

#2
1 of the hundred machines produces coins that weigh 10% or 5%(not both, all the coins produced from this machine are 10% heavier or 5% heavier) more then they should.
How many weigh ins do you have to have to find the broken machine? What is your method?

#3
1 of the hundred machines produces coins that weighs plus or minus 10%(That is any given coin is +10% or minus 10%) more then they should.
How many weigh ins do you have to have to find the broken machine? What is your method?

Some of you have more then likely seen #1 and #2, but #3 is my own little twist.

 

[TenaliRaman]

Your #3 is definitely a nice twist on the old problem.
I think i can do it in 9 weighing but i cannot see if i can do better than this.

-- AI

 

[Davorak]

TenaliRaman For which part?
Sould I break this thread into three posting the next two after the first has died off?

 

[TenaliRaman]

The solution to #1 has already been posted on this forum before and regardless to the number of machines , we can find the defective in 1 weighing.

The solution to #2 i believe can be done in 2 weighings and the solution to this follows closely on the heels of solution to #1. (Again the number of weighing is not related anyway to the number of machines here)

The solution to #3 however does depend on the number of machines (atleast the solution that i have), infact as i thought abt it in the morning, there is a manageable solution for this one in 5/6 weighings. (The solution i have in mind for this one is same as the one to the "odd coin among 12 coins" problem.)

For #3, my solution obviously doesn't take advantage of the fact that i can take any number of coins out of the machine. Its probable that a suitable weighting can reduce the number of weighings. One thing for sure is that the amount of coins one has to take out of every machine must be odd.

-- AI

 

[Davorak]

Solutions:
Since these have been seen before:

Solution #1 is one weighing
Each machine produces a uniqe number of coins, from how much the weigh is off from it would be idealy with no machines broken tells you which machine is broken
Solution #2 is one weighing
Similar to Solution 1:
machine:coins produced
M1:1
M2:3
M3:7
M4:15
Nnew = 2*Nold +1

Or you can just use all prime numbers. This makes it so each machine has a unquie weight with the 5% or the 10% case
Solution #3 maximum of 7 weighings. 6->7 corrected by RandallB
It is impossible to say weather or not any weight has been add on even number of coins. Binary search technique is called for. 6 weigh ins for 100 coins.
What if it was +10% or -5%: Then on avg coins would 5% heavy, just produce enough coins so that it is statistically unlikely to chose the wrong one.
Or using a similar method as in Sol 2 create a unique weight range for each machine

 

[RandallB]

Solutions:
Solution #3 maximum of 6 weighings.

6 will for 64 machines - don't you need 7 for 100

Using your system and every test comes out over or under by just 10% of one coin, won't you still have two machines left??

Also: On #2 wouldn't odd number coin counts work just as well.

 

[NateTG]

#3 Is somewhat interesting:

Clearly there is a binary search using one coin from each machine that will give you the result in 7 weighings. Since alternating + and - 10% limit the variation, you can't correlate the size of the variation with the machine directly, that's the best you can do in an absolute sense.

Since it's unspecified in the problem as posed, this is going out on a limb, but if we suppose that the machine has a probabiltiy [itex]p[/itex] of producing a heavy coin, and a probability [itex]1-p[/itex] of producing a light one, then a larger number of coins is likely to have a larger variation.

That means that picking, say, 1,9,25,49 (squares of odd numbers) is likely to get you a larger variation if you end up putting in a large number from the odd press. Moreover, the size of the variation can be used to make educated guesses about which pile contains the odd coin.

This means that the average number of weighings necessary can be cut to significantly below 7 (in the limit I think it's 3.5), but how much below 7 is affected by the number of coins that can actually be put on the scale. It may well make for a tricky optimization problem.

 

[RandallB]

#3 Is somewhat interesting:
1,9,25,49 (squares of odd numbers)

No even #'s ??
First weigh in - what do you do if off by 10% of one coin?
Plus "p" could be near 0.5