12 ball problem again

Hi again,

I just thought I'd let you know I found an even better, more general solution to the 12 ball problem mentioned yesterday, generalized to (3^N-3)/2 balls where N = the number of weighings.  Check it out here:

Here's the solution to the n-weighing version of this problem that
I said I'd recently read. It was found by Dyson and Lyness in 1946;
I think I've improved the exposition. I'll explain it for the original
problem first, and then explain the generalization.

Label the 12 coins by the sequences

AAB ABA ABB ABC BBC BCA BCB BCC CAA CAB CAC CCA

and in the

1st AAB ABA ABB ABC BBC BCA BCB BCC
2nd weighings put AAB CAA CAB CAC in pan A, ABA ABB ABC BBC in pan B.
3rd ABA BCA CAA CCA AAB ABB BCB CAB

Now in a given weighing, a pan will either end up in the

Canonical position (C) that it assumes when the pans are balanced, or
Above that position (A), or
Below it (B),

so the weighings determine a sequence of three of these letters.

If this sequence is CCC, then there's no fake coin. Otherwise,
for just one of the two pans the sequence is among the 12 above,
and names the fake coin, whose weight is Above or Below the proper
one according as the pan is A or B.

N weighings can be used to locate a possible fake from among
(3^N - 3)/2 coins in the same way, by labelling them with all
the non-constant sequences of N letters from A,B,C whose
first change is A-to-B or B-to-C or C-to-A, and at the
kth weighing putting those whose kth letter is A in pan A
and those whose kth letter is B in pan B.

Neat, isn't it?

John Conway

12 Ball Probelm

Dear Internet,

I'm a little disappointed in you.  I recently got hooked by the 12 ball problem (defined shortly), and while I found some solutions and discussion, you left me without a satisfying solution: one that really got to the meat of the issue and explained what's going on.

Here's a statement of the 12 ball problem.  You are given 12 balls, 12 identical except one weighs slightly more or slightly less than the others.  Your task is to discover the oddball and report if it's heavier or lighter.  You are given a balance scale which is the only instrument you may use to make this judgement, and you may have no more than three weighings of groups of balls (choose any number on each side of the balance) against each other to determine which of the 12 is different, and whether it's lighter or heavier.  Moreover, you must determine which balls are to be weighed against each other ahead of time - it is illegal to make your weighing schedule contingent on previous results.

There are a few solutions out there, and you can look them up.  Here's one.  However, I couldn't find a satisfying treatment of the approach used to solve this problem, so I'm offering one to you, O Mighty Internet, right here, right now.  (OK, far below this text so I don't spoil anything.)  Give it a shot, if you like.  It took a satisfying 15 minutes or so for me, including one 2-minute stroll.  Hint: start with a principled approach; trial-and-error will take a long time.






















Is your screen this tall?  Yes?  OK, I'll add more whitespace.























OK.  That should do it.  Here are the facts to get you started.  There are 24 possible problem states, and you have 3 observations per weighing.  Each weighing can have the scale tip left, tip right, or stay steady: 3 states.  Therefore, there are 3*3*3=27 possible observations, mapping onto 24 states you have to distinguish.  That's pretty tight, and given a fixed schedule of what balls to weigh when, you're going to need to ensure each outcome is about equally likely, or you simply won't have enough information to disambiguate the 24 possibilities.  Scroll down for the next hint.




























To make each possibility approximately equally likely, you're going to need to weigh the balls 4 against 4, reserving 4 for later.  Then the chances of a left, right or steady observation are equal on each round.  Scroll for more...






















Since you don't know if the oddball is heavier or lighter than the others, you can't have any patterns where, say, ball 2 being heavy would tip the scales R(ight) L C while a heavy 4 tips them L R C, since a light 4 would be indistinguishable from a heavy 2.




















That means there need to be 4 similar groups of 3 balls, each of which would tip the scales in an idiosyncratic way.  Group I would cause tips in all three rounds, twice in one direction and one in the other direction.  Group II causes tips in the same direction in two of the three rounds, and an even weighing on the third.  Group III causes tips in opposite directions on two of the three rounds, and an even weighing on the third.  Group IV causes tips on only one round.

Within each group, there's room to make the three member balls tip on different rounds, since there are three rounds total.  Is that enough for a solution? Try it.  If not, scroll down.























OK.  Let Group I be balls 1, 2 and 3.  Let X be an unallocated ball - assume for now all Xs are "normal" and make sure if 1, 2 or 3 are oddballs, they'll be distinctive.  As a rule of thumb, it will be easier to fit all the balls where they need to be if we start with Group I and try to make each round and side roughly balanced.  To represent our schema, let's place 1, 2 and 3 in a grid like so (each row is a round of weighing):

X	X	X	1			2	3	X	X
X	X	X	2			1	3	X	X
X	X	X	3			1	2	X	X

So, Group I tips the scales 3 times, always.  We'll have to make sure *only* Group I tips the scales one direction or the other for all three rounds.  Moreover, 1 tips the scales in a different way the 1st round, 2 tips the scales in a different way the 2nd time, and 3 tips the scales in a different way the 3rd time, so once we know it's a Group I ball, we can distinguish 1, 2 and 3.  Finally, we can tell if the oddball is heavier or lighter by looking at the way the scales tip.  Also note that each round includes all of the Group I balls: this is necessary so that any Group I ball tips the scales each time.

On to Group II: balls 4, 5 and 6.  They all tip the scales the same way 2 out of 3 times; let 4 not tip the scales the first round, 5 not tip the scales the second round, and 6 not tip the scales the third round.  Then one way of doing things is:

X	6	5	1			2	3	X	X
X	6	4	2			1	3	X	X
X	X	4	3			1	2	5	X

Again, *only* group II balls  tip the scales precisely twice with the tips in the same direction.  Knowing which round there was no tip, you can distinguish 4, 5 and 6, and looking at the way the scales tipped tells you if the oddball's lighter or heavier.

Group III is like Group II in that the scales tip 2 out of 3 rounds, but for Group III the scales tip in *different* directions for the two times they tip.  That distinguishes Group II from Group III, and further we can distinguish between Group III's 3 members by looking at which of the 3 rounds had a neutral weighing.  As before, let 7 not tip the 1st round, 8 not tip the second round, and 9 not tip the third:

X	6	5	1			2	3	8	9
9	6	4	2			1	3	7	X
8	7	4	3			1	2	5	X

Group IV is now a cinch: they just tip the scales once.  Let 10 tip on the first round, 11 on the second, and 12 on the third:

10	6	5	1			2	3	8	9
9	6	4	2			1	3	7	11
8	7	4	3			1	2	5	12

There you have it!  With the above weighing schedule, perform the following:

1. If the scales tip 3 times, the oddball is in Group I (1, 2 or 3)
2. If they tip twice in the same direction, the oddball's in Group II (4, 5 or 6)
3. If they tip twice in different directions, the oddball's in Group III (7, 8 or 9)
4. If they tip once, the oddball's in Group IV (10, 11 or 12)

 In each case, you can tell which of the three Group members is the oddball, and whether it's heavier or lighter than the rest, based on the tips.

There you have it: a principled way to solve the 12 ball problem.  Much more satisfying than trial and error, don't you agree?

Edit:  I've used 24 of the 27 conceivable observations: the patterns CCC, LLL and RRR are never used.  It's possible to use LLL or RRR (for example, switch the left 4 balls with the right 4 balls on the first round and 1 will yield RRR or LLL depending on whether it's heavy or light), CCC can never be useful since it can never tell you if the oddball is heavier or lighter than the rest.

FTL Neutrinos and the Fine Structure Constant

Hi again,

It looks like the fine structure constant ain't so constant.  The fine structure constant is a pure number of about 1/137 that was thought to be a fundamental constant.  It's the ratio between the energy needed to overcome electrostatic repulsion between two electrons a distance d apart and the energy of a photon of wavelength 2 pi d.  Chemistry is all about the energies involving electrons and light, so the fine structure constant pops up a lot in quite a few fields.  The fine structure constant depends on the charge of the electron, the speed of light in a vacuum and Plank's constant, so as long as all these are in fact constant, their ratio will be a universal.

This past Hallowe'en, however, Physical Review Letters published a highly-confirmed yet still extremely controversial paper showing that in old galaxies, the fine structure constant is higher in older galaxies.  There are only three possible causes; one of them must be true:

1. The charge on the electron is larger in older galaxies
2. The speed of light is smaller in older galaxies
3. Plank's constant is smaller in older galaxies.

None of these choices are all that appetizing, but #2 is consistent with the idea of my previous post that there's a particle field we haven't found yet that's slowing down photons a bit. As a nice bonus, the order of magnitude of the change in the fine structure constant observed is pretty close to the order of magnitude of the factor of the photon slowdown seen in the OPERA experiment.

These thoughts are still just tantalizing ideas, and there probably isn't a connection.  Drop me a line if you have ideas about this!

Cheers,

LeDopore

FTL Neutrino Predictions

I thought I'd jot down my ideas about the recent OPERA superluminal neutrinos at CERN.  In case you hadn't heard, the experiment found neutrinos that (as far as they can tell) move slightly faster than the speed of light.

If correct, this is a big deal, since "faster than light" in one reference frame means "back in time" in another.  Being able to send information back in time would lead to implausible, crazy new technology.

My best guess as to what's going on is that there’s a systematic error in OPERA we haven’t found yet.
My second best guess: light actually travels a little slower than c, at least around Earth. This could be due to interaction with some unknown particle cloud that’s consistently uniform and has a refractive index of 1.0002.

No, this isn’t the aether, and this isn’t experimentally contradicted by the fact that the speed of light doesn’t change as the Earth changes velocity through this field. Just as the speed of light through a moving glass rod isn’t greater or smaller than through a still glass rod (neglecting dispersion, which comes into play as the Doppler-shifted frequency of light causes n to change slightly), moving through this weakly-interacting particle background doesn’t change the observed velocity of light, unless the medium is dispersive. A good assumption would be the medium isn't noticeably dispersive: whatever transitions the light interacts with are of such high energy that photons we generate all look about the same, and dispersion isn’t measurable.

Heck, the medium could even be dark matter. This hypothesis solves a bunch of problems, like why the neutrinos from the 1987A supernova were coincident with (and not before) the photons. Under this hypothesis, the photons traveling though deep interstellar space would not be slowed by the presumably rarefied dark matter there.

Like I said, my money’s still on the possibility that there’s a systematic experimental error at OPERA. However, I find the idea of a vacuum/dark matter refractive index a lot more palatable than particles that violate causality. I haven’t yet heard a good reason to discredit this idea, so I thought I’d post it.
Background: I have an honours physics undergrad degree, but I’m now a neuroscientist. None of my colleagues are capable of evaluating this idea; if it’s rubbish please don’t hesitate to point out why.

News Flash: Rocks Too Deadly for Schoolkids?

Greetings, daredevils.

I just happened upon a great Forbes article about the insane lengths the Consumer Product Safety Commission goes to keep dangerous toys like plain old rocks out of the hands of schoolchildren. I'd write more, but in some ways res ipsi locutor, and I have to get to work too.

Via BoingBoing.

Give Parents a Chance: Part 1: diaper diatribe

Greetings, potential p1 generation.

It's been a long time since I posted to this blog. My life's been irrevocably improved by a nine-month-old daughter, and I've changed cities as well. I bet you might have thought I was gone for good, but here I am, back with another cold, hard numerical look at our decisions.

Today, I'm going to write a post I wish I'd read a few months before coming a dad; this may evolve into a short series.

Over-educated parents get weird about a whole lot of things and one of them is diapers. It's practically taboo for a Ph.D.-toting couple like us to use throw-away diapers that will sit in a landfill for eternity. We've bowed to social pressure and bought a g-diaper system, complete with multiple reusable covers (that need a lot of laundering nonetheless) and flushable inserts.

The joke's on us, however, since cloth diapers on the whole are not any more environmentally friendly than disposables. Laundering cloth diapers in soap and hot water takes as much energy and releases as many chemicals into the environment as having disposable diapers.

The three big advantages of disposable over cloth are:

1. Cost (disposables are about half as expensive)
2. Baby's skin (disposables these days can keep 'em dry through the night)
3. Time (it's much faster to change a disposable diaper than a cloth one, and when you're only getting 4 hours of sleep a night for the first three months, even an extra 5 minutes 8 times a day is really appreciated)

Item 3 is so important that I'll come out and declare that even if 1 and 2 were not true, it would probably still be best for the family to use disposables overall. When you're taking care of a newborn, you need time. Other things like budgets and environmental concerns - especially the matter of a couple of cubic meters of solid waste (all the diapers that the baby will make over their lifetime) - can and should be put on a back burner. Be with your kid, not your laundry service.

In conclusion, let me absolve any prospective parent out there (I can do this now that I'm officially ordained - another story) of any disposable-related guilt. Disposables are awesome technology - use 'em with a clear conscience.

Getting a D in Health

Greetings, indoor, computer-reader.

The Sunbathing Ape

It's natural for us to feel drawn to amazing photographs of sun-soaked landscapes. We humans evolved as mostly-naked, outdoorsy folks in sunny Africa. Although the cultures (and to some degree the genes) of migrating peoples have done what they can to adapt to more polar environments, if you dig at all deep into our biology you'll see we still aren't fine-tuned to live indoor, boreal lives.

One of the biologically unmet expectations humans in the USA and Canada experience is low sun exposure, leading to Vitamin D deficiency. This article in the Globe and Mail suggests that Canadians typically have about one third of optimal concentrations of vitamin D in their bloodstream.

What's D Good For?

Until recently, it was thought that the major effect of vitamin D deficiency was rickets. Since (last time I checked) rickets wasn't an endemic problem to North Americans, vitamin D was seen as being a non-issue; the mandated additions of D and A to dairy products seemed to be sufficient to keep bone formation normal in children.

However, vitamin D has more functions than merely the regulation of bone density. It's also an important chemical precursor to a lot of important cellular signaling mechanisms: not having sufficient vitamin D is the equivalent of trying to run a government when there's a shortage of notepads to write on.

D and Cancer Rates

One of the worst consequences of screwing up chemical messages is to impede natural anti-cancer cellular mechanisms. Does our D-prived culture result in fact in increased cancer rates? The only way to know for sure is with a double-blind experiment where groups are given vitamin D and placebos at random, and to track prevalence of cancers in the two groups. That's exactly what this study did, and what they found is almost unbelievable. Giving 1.5g supplemental Calcium with 1100 IU per day (about 3 liters of milk worth, but the study used pills) decreased cancer rates by 77% after one year.

Great moons of Neptune! That's a huge decrease! The cautious part of me finds it hard to believe that one factor could be responsible for over half of cancers, and to be fair the study tracked only 1200 women over 4 years, and thus wasn't able to notice enough cases of cancer to have really tight confidence intervals: the range of cancer decreases still consistent with the study is 91%-40% 19 times out of 20. Still, I've started feeding vitamin D to my wife as well as taking it, if not daily, than at least often.

Public Health Consequences

Suppose the study's numbers bear up, and that about half of cancers could be prevented by 1100 IU of vitamin D per day. Would it be a good policy for health insurers (or friendly socialist governments like Canada's) to simply hand out vitamin D supplements? It looks like the cost of vitamin D is pretty much nothing: this bottle of 250 pills (almost a year's supply) with 1000 IU of vitamin D is only $10. On the flipside, the annual cancer rate in the US is 1 in 200. If that could be halved by the D supplement, and if treatment costs on average $40 000, that's an expected savings of $100 per year. Pay one dollar into prevention, get 10 out in unneeded treatment. (Oh, then there's the whole increase in lifespan and quality of life issue too.)

Last Word

I suppose the cautious policy approach would be to conduct a larger study to figure out where within the wide confidence interval the truth lies. However, I'm inclined to start ramping up vitamin D production and consumption programs, maybe even with heavy subsidy by governments, HMOs or otherwise. Let's get a D in health.