Conference rusure::math

Off the top of my head: Turn on one quadrant (25) of the lights. Now any 
row or column change cannot decrease the number of lights that are turned 
on, so we have a local minimum. Is it a global minimum as well? If so, it's 
a good candidate for the maxmin set.

Quick, someone - put together a DECwindows widget for this game! I've just 
about forgotten how to program anything... sigh.

Re: Local and global minima.  A local minimum isn't necessarily a global
minimum.  For example:


	O � � � �  O O O � �
	� O � � �  � O O O �
	� � O � �  � � O O O
	� � � O �  O � � O O
	� � � � O  O O � � O

	O � � O O  � � � � �
	O O � � O  � � � � �
	O O O � �  � � � � �
	� O O O �  � � � � �
	� � O O O  � � � � �

This has 35 lit bulbs.  This can be reduced to 25 (by toggling the first
5 rows and first five columns), even though toggling any *single* row or
column would *increase* the number of lit bulbs.


The following shows that R >= 27.  The 2^100 states of the bulbs form
2^(100-20) equivalence classes.  Let's visit the equivalence classes
that have a minimized configuration with only 0,1,2,... bulbs set, and
'discard' them.  When we've discarded 2^80-1 classes, the remaining class
has the highest R value.  Let s(k) be the number of equivalence classes
that have a minimized configuration with k bulbs set, and let C(n,k) be the
binomial coefficient.  Since C(100,k) >= s(k), we have

	LHS = 2^80-1 - s(0) - s(1) - s(2) - ... - s(d)
	   >= 2^80-1 - C(100,0) - C(100,1) - C(100,2) - ... - C(100,d) = RHS
	
We're interested in the first d that makes LHS <= 0.  This is hard to compute.
But we can easily compute the first d that makes the RHS <= 0 is d = 27.
Since LHS >= RHS, LHS first becomes <= 0 for some d >= 27.  Thus, R >= 27.

Thinking this over last night, I came to the conclusion that R is about 40.
Here's the argument:

Using the transformation you cite in .-1 to reduce from 35 to 25, you can 
reduce an excess of "on"'s to <= 25 in each diagonal *pair* of quadrants. 
I.e. call the quadrants 
	+---+---+
	| 1 | 2 |
	+---+---+
	| 3 | 4 |
	+---+---+
and using that transform, you can invert quads 1 and 4 while leaving 2 
intact, etc. What the largest number of "on"'s you can then put in each 
quadrant? 

Realize that a 'quadrant' in a broader sense need not be contiguous - it 
may be composed of columns 1,3,4,8,9 and rows 3,4,5,6,8, etc. So any row 
or column must, on average, contain <= 5 "on"'s, which works out to 2.5 per 
quadrant. Unless someone comes up with a clever scheme for packing more 
"on"s into useful places, the figure turns out to be 2 per row/col per 
quad, or 40 in all. *Maybe* 44.

An example of R=40 is, I think, made up of multiples of the following 
pattern, rotated and overlaid, 2 per quadrant:
	1 0 0 0 0
	0 0 1 0 0
	0 0 0 0 1
	0 1 0 0 0
	0 0 0 1 0

	I have written a little program in VAX C to run this game.
	in curses.  Interested people can contact me.  It is about 120 lines,
	sets up random lights (about half of them, boy that was hard, did you
	know that rand() alternates even/odd exactly?) and allows you to
	toggle rows, columns, or just one light.
Tom

    Did you say rand alternates even/odd exactly?
    You mean now at gives even, next time you call it return an odd random
    number?
    That makes it half random i would say, but half a random is still 
    random! right? since even numbers are infinite and odd number are
    infinite, you still getting a random number !

					...	did you
	know that rand() alternates even/odd exactly?) 

That's typical of multiplicative congruential generators of random *integers*
but the routine should be using the leftmost bits of the word, e.g. tack on
an exponent field and treat as real*4. 

>    In the Mathematics Department commons room at Bell Labs in Murray Hill
>    there is a light-bulb game built by Elwym Berlekamp about 20 years ago.
                                             ^
   [ Error correcting code detected spelling error - should be n ]

   Anyhow, there's a geometric way of looking at this that may give some
   ideas.  Suppose the matrix and vectors have +/- 1's instead of
   ones and zeroes.  Then "counting" the one bits corresponds to
   taking the multilinear functional of the two vectors with the matrix
   playing the role of a second rank tensor.

   Since the vectors are constrained to point at the corners of a hypercube
   we can think of the matrix transforming a unit cube centered at the origin
   to some parallelotope.  Then, what is the minimum dot product
   the second vector can attain against all corners of the parallelotope?
   I think because of the symmetries the solution matrix cannot be singular
   and it may help to classify them according to eigenvalues & vectors.
   That could cut down on the search space considerably.

   Actually, even just considering equivalence by permuting rows and
   columns, and transposing, there are far fewer than 2^(N^2) possible
   matrices.  I worked out the number for a few low order cases:

	N	unique matrices	possible matrices
       ---	--------------- -----------------
	1	      2                2 = 2^1
	2	      6		      16 = 2^4
	3	     26		     512 = 2^9
	4	    192		   65536 = 2^16
	5	   3014		23554432 = 2^25

    I only stopped counting since 32 bits wasn't enough to go further
    and I didn't feel like figuring out to make Maple do it.

    As a rough estimate, there should be somewhat more than 2^100/(2*10!^2)
    of them for this problem, still quite a lot!

    - Jim

	problem: get randomly distributed aperiodic bit, 1 or 0.
	attempt: rand() mod 2.  
	result: alternated 0,1,0,1,0,1 always.
	attempt: rand () AND ^X80.
	result: by inspection, aperiodic and evenly distributed.

	If I want bits, why should I convert the integer result of rand()
	to float?
	
	Defining aperiodicity seems like an opportunity for EE approaches, in 
	bandwidth.  An aperiodic series taken as samples in a waveform,
	analyzed for frequency content, should be wide-bandwidth.
	
	What would it take to make a random function that would return numbers
	for which all moduluses of constants smaller than the range of the
	function (and >0) would be aperiodic.
tom

>If I want bits, why should I convert the integer result of rand() to float?

The noter didn't say he wanted bits. That being the requirement, it may be 
faster to use a 32-bit shift register random *bit* generator such as IRBIT2
in Math Recip.: 

	FUNCTION IRBIT2 (ISEED)
	PARAMETER (IB1 = 1, IB2 = 2, IB5 = 16, IB18 = 131072, 
	1   MASK = IB1 + IB2 + IB5)
C======================================================================
	IF (IAND(ISEED, IB18) .NE. 0) THEN
	    ISEED = IOR(ISHFT(IEOR(ISEED, MASK), 1), IB1)
	    IRBIT2 = 1
	ELSE
	    ISEED = IAND(ISHFT(ISEED, 1), NOT(IB1))
	    IRBIT2 = 0
	END IF
	RETURN
	END

Re .8
	attempt: rand () AND ^XFF.
	result: periodic with period 256, and *very* evenly distributed.

The i'th call to rand() returns ( a^i + b.(a^i-1)/(a-1) ) mod 2^31, where
a = ^X41C64E6D and b = ^X3039.

>	attempt: rand () AND ^XFF.
>	result: periodic with period 256, and *very* evenly distributed.
    
    So much for "inspection".  How about (rand () mod 31) AND ^X1 ?
    (I.e., some approach that doesn't require floating point).
    
      John

I'm still confused about the original puzzle.  You said a front swith

	"changes the state of a row or column"

Do you mean

	toggles all on-bulbs to off and off-bulbs to on in a row or column

To me, "changes the state" could mean toggle, or shift right, or all off,
or all on, or anything else.

Thanks for clarification.

/Eric

    In a linear congruential RNG with a power-of-two modulus (which seems
    to be what RAND is).  The lower 'n' bits (and thus the n'th least
    significant bit) have a period of at most 2^n.  This is because on each
    iteration the new value of the n'th bit depends only on the old value
    of the n'th bit and the n-1 bits to its "right".  Therefore, the high
    order bits are the "most-random".  A related, but more subtle effect
    appears even in LCGs with non-power-of-two moduli (adjacent n-tuples
    occur in (n-1)-dimensional hyperplanes).

    It seems natural, unfortunately to use the low-order bits.  If the
    value is treated as scaled to lie between 0 and 1, either interpretted
    as fixed-point or converted to floating point, using the high-order
    bits becomes natural.  But all you have to do is use the high-order
    bits (in this case, bit).

    So use ((unsigned)rand())>>B, where B is the appropriate number of
    bits.  Or, in ANSII C, if you are just going to treat the result as
    TRUE/FALSE, you can use (rand() & (RAND_MAX>>2)).

					Topher

    I've modified Tom Janzen's version of this game (see note .4) so that
    it also quickly computes the minimum for any set of lights.  Interested
    people can contact me.

    I experimentally generated random matrices and then sought their
    minima by toggling the row and column switches, recording the best
    one seen so far.  Each time a new best was seen, I then tried to
    add an additional one bit to each empty slot; if this failed to
    "improve" the matrix, it was declared a local optimum.

    This procedure has given a few examples with 33 lamps set, but nothing
    greater...  peculiar since there is a row (or column) with only 1 lamp
    set; you'd think this would be a golden opportunity to add more...

    Of course, I've probably got bugs in the little program I hacked
    together.  Note that the set of row and column sums are suspiciously
    similar, so the random search may be just hitting permutations of the
    same example.

    Perhaps I'll leave one running overnight.

    - Jim

	0 0 0 0 1 0 0 1 0 0
	0 0 0 1 0 1 0 1 1 0
	0 0 1 0 0 0 0 1 1 0
	1 0 0 1 1 0 1 0 0 0
	0 1 0 1 0 0 0 1 0 1
	1 0 0 0 0 1 1 0 1 0
	0 1 1 0 1 0 0 0 1 0
	1 1 0 0 0 1 0 0 0 0
	1 1 0 0 0 0 0 0 1 1
	0 0 0 0 0 0 0 0 0 1
	
	0 1 0 1 1 0 0 0 1 0
	0 0 0 0 1 1 1 0 0 0
	0 0 0 0 0 0 1 1 0 0
	1 0 1 0 1 1 0 0 0 1
	1 0 1 0 0 0 0 1 0 1
	0 1 0 0 1 0 1 0 0 1
	0 0 1 0 1 0 0 1 0 0
	1 0 0 0 0 0 1 0 1 1
	0 0 0 1 0 0 0 0 0 0
	1 0 0 1 0 1 0 0 0 0

	1 0 0 1 1 0 0 0 1 0
	0 1 0 0 0 0 1 0 1 0
	0 0 1 0 0 1 0 1 1 0
	0 0 1 1 0 0 0 0 0 1
	0 0 0 0 1 0 1 0 1 1
	1 1 0 0 0 1 0 0 0 1
	1 0 1 0 0 0 0 1 1 0
	0 0 1 0 1 0 0 1 0 1
	1 0 0 1 0 0 0 0 0 0
	0 0 0 0 0 0 1 0 0 0

	0 1 0 1 0 0 0 0 0 0
	0 0 1 1 1 1 1 0 0 0
	0 0 0 0 1 1 0 0 1 0
	0 0 0 0 0 1 0 1 0 1
	1 0 0 0 0 0 1 0 0 0
	1 0 0 0 1 0 1 1 0 1
	1 1 0 0 1 0 0 0 0 0
	0 1 0 0 0 1 1 0 1 0
	0 0 1 1 0 0 0 0 0 1
	0 0 0 1 0 0 1 0 1 1

   I left a program running for a few hours the other day and it found
   several examples of matrices with 34 as a minimum (out of over 5 million
   trials.)

   As an experiment I also ran a program which exhaustively tried each
   class of 5 by 5 matrix (there are 3014 unique ones up to permutation
   and transposition) and got many hits on the maximum of 7 but stupidly
   didn't count them or write a log file. (I just left it in a window
   while doing some other work.)

   There are 127757 unique 6 by 6 matrices, so an exhaustive search
   is even feasable for that case.  For n = 7 and 8 we get 16853750
   and 7343780765 respectively, probably out of the question to do
   exhaustive searches (maybe 7 would be possible.)  (I don't know an
   efficient way to enumerate the number of unique ones in general.
   Any ideas?)

   - Jim

    Here is a way of estimating the upper attainable bound in this
    problem, which turns out to be close to Lynn's guesstimate of
    40.

    As we run thru the 1024 row switch settings, we will run thru
    all 1024 lamp states in any column, and also thru all "folded"
    column sums, where we automatically toggle that column if more
    than 5 lamps are let.  Changing the initial states of the lights
    merely permutes this list of column sums (indexed by the row switch
    settings) and does not change the average.

    This average is

	SUM(k = 0,4) C(10,k)/2^9 + C(10,5)/2^10 = 3.76953125

    so the average over all 10 columns is 37.6953125.

    It is thus not possible for any matrix to have a lower bound above
    this average value.

    - Jim

    Peter mentioned a transcription error in my note - I forgot to include
    the factor of k in my expectation!

>	SUM(k = 0,4) C(10,k)/2^9 + C(10,5)/2^10 = 3.76953125

>>	SUM(k = 0,4) k*C(10,k)/2^9 + 5*C(10,5)/2^10 = 3.76953125

   I'm including his mail since it is a clearer explanation of the idea
   (which I saw in a book called _The Probabilistic Method_, it's not
   really mine.)

    - Jim

From:	CLT::TRACE::GILBERT      "Ownership Obligates"  2-MAR-1992 22:05:49.39
To:	clt::GAUSS::ROTH

<reply to .18>

    Aha!  It took me a while to understand the argument in .18.

    Jim has a 'minimization procedure'.  It runs through all 2^10
    row switch settings.  For each of these, it "folds" the columns
    (i.e., toggles a column if there are more than 5 bulbs set).
    One of these 2^10 configurations must minimize the number of
    lit bulbs attainable from the initial states of the lights.

    Over these 2^10 configurations, the average number of lights lit
    in each column is:

    	Sum(k=0..10) min(k,10-k) C(10,k)     3860
        --------------------------------  =  ---- = 3.76953125
    	      Sum(k=0..10) C(10,k)	     1024

    [NB: there must've been a typo in .18]

    And the average number of lights lit in each configuration is 37.6953125.

    Suppose I give Jim's 'minimization procedure' a matrix of lights, and
    claim some M > 37 is minimum for it.  It tries all 2^10 configurations.
    Some of those must have 37 or fewer lights lit, since the *average* is
    only 37.6953125.  So the claim M > 37 is false.

    Suppose I run a Monte Carlo minimization procedure which tries
    millions of matrices and keeps a histogram of the lower bounds
    attained (by throwing column switches) for each one.

    As a form of coupon collectors problem, can I use Bayesian
    statistics on the histogram to estimate the probability of
    having seen the true "optimum" matrix?

    Here is one such histogram, where we have not yet encountered
    an example of a matrix with a lower bound of 34 yet.  Note that
    even a lower bound of zero is attainable, with a probability of
    about 2^-80.

	15 1
	16 4
	17 11
	18 41
	19 138
	20 515
	21 1800
	22 5882
	23 17215
	24 45762
	25 111604
	26 240481
	27 455677
	28 710674
	29 823015
	30 607582
	31 234581
	32 32760
	33 649

    total trials = 3288392

    - Jim

    You can use Bayesian statististics on anything about anything -- the
    question is would you know something new for having done so?  (In
    Bayesian parlance, would there be a basis for changing your belief).

    Think of the minimization surface.  You are randomly sampling that
    surface.  Your histogram represents an approximation of the
    distribution of scores for radnomly selected samples.  It is very easy
    to make on the basis of this histogram statements about your
    expectations if another similar sampling were made.  Furthermore, if
    you make assumptions about the distribution being "well behaved" you
    can use it to estimate an expected optimum value.

    But we can imagine that the surface has a few deep "wells" in it.  The
    true distribution might be bi-modal with a small but real hump well
    below 15.  You would need, for a complete Bayesian analysis, to include
    a prior subjective probability of that being the situation.

					    Topher

FWIW:  If there are 35 or more bulbs lit, then the rows
and columns can be permuted so the upper left 2x2 corner
has all 4 bulbs lit.

This may improve Jim's search strategy. ;^)

(see note 973 for details of this result)

   The search strategy referred to above is a small Monte Carlo program
   I've left running on my workstation as the null job.

   It generates 10 random 10 bit numbers (matrix columns) and loops thru
   computing their folded weights, xor'd by the possible row settings.
   The weights (count of one bits) are computed by indexing a 2^10 entry array
   so this is quite fast.  One way of saving time in this is to notice
   that only 2^9 row switch settings have to be tried, since the other
   "half" are just mirror images which would be folded by the column
   switches.

   But for random searching, a far better optimization is to punt on
   any matrix if any sum is less than 34, the best we've seen so far.
   With this, an average of only 23 row switch settings/matrix need to be
   tried.

   Over a billion matrices/day can be tested with this simple-minded
   technique.  I've logged the ones with weight >= 34 to a file.  So far
   about 1 in 100,000 is a weight 34 minimum matrix, but nothing better
   has turned up.

   I tried another experiment.  I read in the 500 or so matrices in the
   log file, converted their entries to +/-1, and calculated their
   singular value decompositions.  This is a basis independant way to
   look at matrices in that two matrices will have the same singular
   values if one can be obtained from another by pre and post multiplication
   by arbitrary orthogonal matrices.  Since row and column permutations and
   negations (switch flips) are orthogonal, this classifies the "unique"
   matrices, regardless of permutations or row/column switch settings.
   The matrices are square so we catch transpositions too.
   It's somewhat interesting that a simple calculation can factor out
   the combinatorics so well.

   I don't know how to enumerate these (which could shed light on the
   problem perhaps.)

   But interestingly enough, no two of the 500 examples seen are "equivalent",
   though many of them look superficially similar in that they have the
   same row/column sums.  All the matrices are singular, and some have
   a 2 dimensional null space.

   It's unlikely that this will help though, but it was worth a try.

   It may be that this is a kind of knapsack problem which would make
   a systematic search hard.

   - Jim

    Here is the result of an *exhaustive* search of all classes of
    5 by 5 matrices.

    Of the 2^25 possible binary matrices, there are 30 up to equivalence
    by row/col permutation, transposition, and switch throwing.

    The upper bound (by the "probabilistic argument") is 7.8125, and
    we find one representative that attains the limit of 7.

    But notice how one whole row is zero!  Yet, one cannot add another
    light, or reduce this number, by throwing switches!

    I may (if I get energetic) do an exhaustive 6 by 6 search to have some
    more data to think about.

    (Of course, my program may be buggy too - these results remain to be
    double checked.)

    - Jim

sum = 0
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 0 0

sum = 1
    1 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 
    
sum = 2
    1 1 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    0 1 0 0 0 
    1 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

sum = 3
    1 1 0 0 0 
    1 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    0 1 1 0 0 
    1 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    0 0 1 0 0 
    0 1 0 0 0 
    1 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

sum = 4
    1 1 0 0 0 
    1 1 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    1 0 1 0 0 
    1 1 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    0 0 0 1 1 
    1 1 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    0 1 1 0 0 
    1 0 0 0 0 
    1 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    1 0 1 0 0 
    0 1 0 0 0 
    1 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    0 0 0 1 1 
    0 1 0 0 0 
    1 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    0 0 0 1 0 
    0 0 1 0 0 
    0 1 0 0 0 
    1 0 0 0 0 
    0 0 0 0 0 

    0 1 0 0 0 
    1 0 0 1 0 
    0 0 0 0 0 
    0 0 0 0 0 
    1 0 0 0 0 

sum = 5
    0 1 1 0 0 
    1 1 0 0 0 
    1 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    0 0 0 1 1 
    1 1 0 0 0 
    1 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    0 1 1 0 0 
    0 1 1 0 0 
    1 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    0 0 0 1 1 
    0 1 1 0 0 
    1 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    0 1 0 1 0 
    0 1 1 0 0 
    1 0 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    0 0 0 1 0 
    0 0 1 0 0 
    0 1 0 0 0 
    1 0 0 0 0 
    1 0 0 0 0 

    1 0 0 1 0 
    0 0 1 0 0 
    0 1 0 0 0 
    1 0 0 0 0 
    0 0 0 0 0 

    0 0 0 0 1 
    0 0 0 1 0 
    0 0 1 0 0 
    0 1 0 0 0 
    1 0 0 0 0 

sum = 6
    0 1 1 0 0 
    1 0 1 0 0 
    1 1 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    0 0 0 1 1 
    1 0 1 0 0 
    1 1 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    0 1 0 1 0 
    1 0 1 0 0 
    1 1 0 0 0 
    0 0 0 0 0 
    0 0 0 0 0 

    0 1 0 1 0 
    1 0 1 0 0 
    0 1 0 0 0 
    1 0 0 0 0 
    0 0 0 0 0 

    0 0 1 0 1 
    1 0 1 0 0 
    0 1 0 0 0 
    1 0 0 0 0 
    0 0 0 0 0 

    0 1 0 0 0 
    0 0 1 0 0 
    0 0 0 1 0 
    0 0 0 0 1 
    1 0 0 0 1 

sum = 7
    0 1 0 1 0 
    0 0 0 1 1 
    0 1 1 0 0 
    1 0 0 0 0 
    0 0 0 0 0