a problem to solve

[mensanator at aol.com]

Michael Tobis wrote:
> First do a little estimation. We know we have to find four out of 16
> switches,

4 panels, eight switches each, 32 total.

> so the number of possibilities to search is only C(4,16) =
> 1820, so an exhaustive search will work.

Yes, but for the wrong reason. It's not combinations, the switch
selection

A = 1  B = 2  C = 3  D = 4

is not the same as

A = 4  B = 3  C = 2  D = 1

You want permutations with replacement, so there are

8**4 = 4096

possibilities, which is still tractable.

>
> These will turn on 15 lights in each set of 20, of which the number of
> possibilities is C(15,20)**4 = 57779667567968256L

No, there are only 8 possible patterns on each panel.
Not every possible 15 lamp pattern is realized.

>
> The number of these that are successes is the number of ways to pick 3
> out of 4 twenty times: 4**20 = 1099511627776L
>
> For each pick, your chance of success is then
> float(1099511627776L)/57779667567968256L = 1.9029386530869287e-05

Chance doesn't enter into it. Unless you ask what is the chance
that a randomly selected switch pattern is a solution? But no one
is asking that.

>
> You get 1820 distinct tries. Assuming no overlap (which slightly
> overestimates your chances if it's a false assumption), the odds that
> there is a solution are
>
> 1820 * 1.9029386530869287e-05 = 0.034633483486182101
>
> or about 3.5%. Not great.

The odds are 100% if there is at least one solution.

>
> There seem to be some symmetries I haven't used, which may conceivably
> help your cause. I just wonder if you have some basis for beleiving
> that there is a solution.

There is. I solved it using the technique I outlined in my previous
posts.

> 
> mt