Weighing Marbles

[Teaspoon]

One good coin? Excellent.

I have to head out for a delivery shortly, but I'll probably generate the list of the four best weighings and what the outcomes mean this afternoon during my filler time.

Why did they decide to take me on full-time to do this job? When I was a casual employee I only worked for them about 18 hours a week, and now that I'm full time I'm doing the same amount of work, then just sitting in the office browsing forums and generally farting about for the other 22.

[Penguin]

If you'd like to save some time I can dig up the .xls file I made for homework and upload it, or something. (Yes, an .xls file. I am an idiot at programming, but I can do stuff in Excel. Shut up - if you want to turn it into some magical codey thing, feel free.) It lists which coins go on which side of the scale for each of the four weighings, and has an input of the results of the four weighings (i.e. -1 for left side heavier, 0 for balances, 1 for right side heavier - or vice versa, I don't remember. haha) that spits out which coin is the bad one and whether it's heavier or lighter.

It works for the 41-coin case because you keep one coin off the balance in all 4 weighings, and then the only situation in which you cannot tell immediately whether the bad coin is heavier or lighter is if the scale balances all four times - but you know that the coin you kept off it is the bad one.

[Teaspoon]

Actually, my work involving non-adaptive weighings has all involved Excel too. I used a system where "a/b" means to weigh group "a" against group "b" and the result is 1 for a>b, -1 for a<b and 0 for a=b.

Then we work through 1 1 1 1, 1 1 1 0, 1 1 1 -1, 1 1 0 1 all the way down to 0 0 0 1. The negatives of all of those are for the opposite case (ie, if 1 1 1 1 means coin 1 is heavy, -1 -1 -1 -1 means coin 1 is light). We then need to select a set from the positives to use as the left side of the first weighing and a set from the negatives to use as the right side such that that the number of coins on each side of the weighing never differs by more than one (which we can correct by adding the known good coin).

I won't be programming the spreadsheet so much as I'll be using it as a convenient grid in which to write out the four weighings and listing which set of weigh-results corresponds to each of the possible odd coins.
When I write it I'll do it for 40. The 41st coin isn't worth mucking about with. All you can do in four weighings is find which of 40 coins is different or prove that they're all equal. If they're all equal then the conditions of the puzzle require 41 to be off, but we can't tell you how it's off so it's a bit of a failure anyway.

[jgf]

Finally got the answer after several false starts. Yes, 41 coins is possible in 4 weighings if 1) You don't care whether it is heavier or lighter, just that it is counterfeit, and 2) You have one spare coin you know is not counterfeit. Each condition is worth 1 coin more you can differentiate. It should not be hard to write a script that generates a solution for n-weighings.

In the process, I came across the following relation:

Sum[r in {0..n}](2^r * nCr) = 3^n - 1

[Dionysus]

Easy marble riddle...ok solution:
At the start weigh 8 marbles. Four on each side. If one side is heavier then that is the side with the heavy marble. If they are equal then the last four is the lighter.

Take those four marbles and divide them(two per side) and see shich is heavier.

Take the heavier divide that in half(1 on each side) whichever is heavier is the heavy marble.

And nice comic.

[jwwells]

Dionysus: That's not quite it for the one that was posted... see, suppose you weigh four-and-four, and one side is heavier. You don't know whether that side has a heavy marble, or the other side has a light marble. Your solution does work if you assume the odd one out is heavy, but the problem is much more interesting if it can be heavy or light.

A good start, though.

[Dionysus]

Eh...woops. Never mind then. I'll find another solution.

[aaronspook]

For extra nerdiness points, find and prove a general formula for how many marbles can be determined for an arbitrary number of weighings. I'm fairly certain I have the formula (it's a pretty straightforward extension of the discussion on this board), but I'm a little stuck on the proof.

[Teaspoon]

For each weighing, there are three outcomes: l>r, l=r, l<r. From N weighings, we get 3^N outcomes. We exclude the outcome of all weighings being equal because it's impossible to achieve if at least one coin has a different weight to the others and every coin gets weighed at least once. This leaves us with (3^N)-1 outcomes from N weighings.

For X coins, only one coin will be different, and it will only be different in one of two ways. This means that there are X*2 possible sets of coins.

Thus, the most coins we can analyse given N weighings is when X*2=(3^N)-1, or X=((3^N)-1)/2

For two weighings, we can do four coins. For three, thirteen. For four, forty. For five, one hundred and twenty-one.

These results are only possible if an extra coin that's known to have the correct weight is also available. For example, finding thirteen coins in three weighings requires you to weigh five coins against four for each weighing. Adding a known correct coin to the side which would normally only have four coins makes that sort of weighing possible.