Via Linear Search

One thing I noticed is the scale will NOT tell you weight of any single coin. It will only tell you the difference between two coins. Additionally, I read the question to indicate that number of 30 fakes is known in advance, and that we only need to find ONE fake, not sort out all of them. Applying these limitations changes the procedure somewhat.

To get my coins, I would choose one coin at random as a control, and then start weighing, where each coin is sorted into possible results of -2, -1, even, +1, +2 from the control (only three of these groups will have any coins, depending on where I start. From here, there are a number of possible outcomes:

1. I choose a fake coin as the control. In this case, I only have to weigh until I find either a +2 or -2. This could happen on my first attempt! I might only have to weigh one set of coins to get a result. However, in a worst-case scenario I might compare with as many as 30 real coins first. Additionally, if all the fake coins by chance happen to also have the same weight I might compare with as many as 29 other fake coins, for a total of 59 attempts before I find my result, meaning in the worst case scenario I might still need 60 attempts.

2. I happened to choose a real coin as the control. In this case, I might need to compare it with as many as 30 other real coins, but as soon as that happens I know I have a real coin as the control, and any difference at all will be fake. Additionally, as soon as I've seen both a -1 and a +1 I know I'm working with a real coin as a control, and any difference must be fake. This could happen as quickly as 2 attempts, but the worst case is to compare with 29 other evens plus all 30 of the fake coins, if all but one of the coins are the same and I don't find that one until the last possible moment. In this case, I might make 60 attempts before knowing what is what. The final possibility is to weigh all 68 remaining real coins before even putting a fake on the scale.

So with this procedure, the answer is 68.

###Via Binary Search

I don't have this completely worked out yet, but I suspect there is a much faster procedure this way.

Divide the coins up as evenly as possible into groups of 49 and 50, and weigh them. Note the difference. The exact difference number doesn't matter (it might even the same!), but the change in this number will matter as we continue. Remove 24 coins from each pile (48 total), and re-check the weights. If the weights are different, we know the removed coins have at least one fake coin, and we can start again with the coin supply reduced by half. Unfortunately, it doesn't prove anything if the weights are the same, because you may have just removed the same proportion of real and fake coins, and this becomes increasingly likely as the number of coins in the pool decreases. Again, I don't have that part worked out yet, but I suspect an algorithm is possible that will get this down to something approaching a binary search, which might naturally produce answer as small as 7 or 8 plus whatever additional we need to do to solve problem of not selecting a fake coin on the first attempt.

Via Linear Search

One thing I noticed is the scale will NOT tell you weight of any single coin. It will only tell you the difference between two coins. Additionally, I read the question to indicate that number of 30 fakes is known in advance, and that we only need to find ONE fake, not sort out all of them. Applying these limitations changes the procedure somewhat.

To get my coins, I would choose one coin at random as a control, and then start weighing, where each coin is sorted into possible results of -2, -1, even, +1, +2 from the control (only three of these groups will have any coins, depending on where I start. From here, there are a number of possible outcomes:

1. I choose a fake coin as the control. In this case, I only have to weigh until I find either a +2 or -2. This could happen on my first attempt! I might only have to weigh one set of coins to get a result. However, in a worst-case scenario I might compare with as many as 30 real coins first. Additionally, if all the fake coins by chance happen to also have the same weight I might compare with as many as 29 other fake coins, for a total of 59 attempts before I find my result, meaning in the worst case scenario I might still need 60 attempts.

2. I happened to choose a real coin as the control. In this case, I might need to compare it with as many as 30 other real coins, but as soon as that happens I know I have a real coin as the control, and any difference at all will be fake. Additionally, as soon as I've seen both a -1 and a +1 I know I'm working with a real coin as a control, and any difference must be fake. This could happen as quickly as 2 attempts, but the worst case is to compare with 29 other evens plus all 30 of the fake coins, if all but one of the coins are the same and I don't find that one until the last possible moment. In this case, I might make 60 attempts before knowing what is what. The final possibility is to weigh all 68 remaining real coins before even putting a fake on the scale.

So with this procedure, the answer is 68.

Via Binary Search

I don't have this completely worked out yet, but I suspect there is a much faster procedure this way.

Divide the coins up as evenly as possible into groups of 49 and 50, and weigh them. Note the difference. The exact difference number doesn't matter (it might even the same!), but the change in this number will matter as we continue. Remove 24 coins from each pile (48 total), and re-check the weights. If the weights are different, we know the removed coins have at least one fake coin, and we can start again with the coin supply reduced by half. Unfortunately, it doesn't prove anything if the weights are the same, because you may have just removed the same proportion of real and fake coins, and this becomes increasingly likely as the number of coins in the pool decreases. Again, I don't have that part worked out yet, but I suspect an algorithm is possible that will get this down to something approaching a binary search, which might naturally produce answer as small as 7 or 8 plus whatever additional we need to do to solve problem of not selecting a fake coin on the first attempt.

Via Linear Search

One thing I noticed is the scale will NOT tell you weight of any single coin. It will only tell you the difference between two coins. Additionally, I read the question to indicate that number of 30 fakes is known in advance, and that we only need to find ONE fake, not sort out all of them. Applying these limitations changes the procedure somewhat.

To get my coins, I would choose one coin at random as a control, and then start weighing, where each coin is sorted into possible results of -2, -1, even, +1, +2 from the control (only three of these groups will have any coins, depending on where I start. From here, there are a number of possible outcomes:

1. I choose a fake coin as the control. In this case, I only have to weigh until I find either a +2 or -2. This could happen on my first attempt! I might only have to weigh one set of coins to get a result. However, in a worst-case scenario I might compare with as many as 30 real coins first. Additionally, if all the fake coins by chance happen to also have the same weight I might compare with as many as 29 other fake coins, for a total of 59 attempts before I find my result, meaning in the worst case scenario I might still need 60 attempts.

2. I happened to choose a real coin as the control. In this case, I might need to compare it with as many as 30 other real coins, but as soon as that happens I know I have a real coin as the control, and any difference at all will be fake. Additionally, as soon as I've seen both a -1 and a +1 I know I'm working with a real coin as a control, and any difference must be fake. This could happen as quickly as 2 attempts, but the worst case is to compare with 29 other evens plus all 30 of the fake coins, if all but one of the coins are the same and I don't find that one until the last possible moment. In this case, I might make 60 attempts before knowing what is what. The final possibility is to weigh all 68 remaining real coins before even putting a fake on the scale.

So with the procedure, the answer is 68.

###Via Binary Search

I don't have this completely worked out yet, but I suspect there is a much faster procedure this way.

Divide the coins up as evenly as possible into groups of 49 and 50, and weigh them. Note the difference. The exact difference number doesn't matter (it might even the same!), but the change in this number will matter as we continue. Remove 24 coins from each pile (48 total), and re-check the weights. If the weights are different, we know the removed coins have at least one fake coin, and we can start again with the coin supply reduced by half. Unfortunately, it doesn't prove anything if the weights are the same, because you may have just removed the same proportion of real and fake coins, and this becomes increasingly likely as the number of coins in the pool decreases. Again, I don't have that part worked out yet, but I suspect an algorithm is possible that will get this down to something approaching a binary search, which might naturally produce answer as small as 7 or 8 plus whatever additional we need to do to solve problem of not selecting a fake coin on the first attempt.

Via Linear Search

One thing I noticed is the scale will NOT tell you weight of any single coin. It will only tell you the difference between two coins. Additionally, I read the question to indicate that number of 30 fakes is known in advance, and that we only need to find ONE fake, not sort out all of them. Applying these limitations changes the procedure somewhat.

To get my coins, I would choose one coin at random as a control, and then start weighing, where each coin is sorted into possible results of -2, -1, even, +1, +2 from the control (only three of these groups will have any coins, depending on where I start. From here, there are a number of possible outcomes:

1. I choose a fake coin as the control. In this case, I only have to weigh until I find either a +2 or -2. This could happen on my first attempt! I might only have to weigh one set of coins to get a result. However, in a worst-case scenario I might compare with as many as 30 real coins first. Additionally, if all the fake coins by chance happen to also have the same weight I might compare with as many as 29 other fake coins, for a total of 59 attempts before I find my result, meaning in the worst case scenario I might still need 60 attempts.

2. I happened to choose a real coin as the control. In this case, I might need to compare it with as many as 30 other real coins, but as soon as that happens I know I have a real coin as the control, and any difference at all will be fake. Additionally, as soon as I've seen both a -1 and a +1 I know I'm working with a real coin as a control, and any difference must be fake. This could happen as quickly as 2 attempts, but the worst case is to compare with 29 other evens plus all 30 of the fake coins, if all but one of the coins are the same and I don't find that one until the last possible moment. In this case, I might make 60 attempts before knowing what is what. The final possibility is to weigh all 68 remaining real coins before even putting a fake on the scale.

So with this procedure, the answer is 68.

###Via Binary Search

I don't have this completely worked out yet, but I suspect there is a much faster procedure this way.

Divide the coins up as evenly as possible into groups of 49 and 50, and weigh them. Note the difference. The exact difference number doesn't matter (it might even the same!), but the change in this number will matter as we continue. Remove 24 coins from each pile (48 total), and re-check the weights. If the weights are different, we know the removed coins have at least one fake coin, and we can start again with the coin supply reduced by half. Unfortunately, it doesn't prove anything if the weights are the same, because you may have just removed the same proportion of real and fake coins, and this becomes increasingly likely as the number of coins in the pool decreases. Again, I don't have that part worked out yet, but I suspect an algorithm is possible that will get this down to something approaching a binary search, which might naturally produce answer as small as 7 or 8 plus whatever additional we need to do to solve problem of not selecting a fake coin on the first attempt.