Conference rusure::math

     <<< Note 1805.0 by TROOA::RITCHE "From the desk of Allen Ritche..." >>>
                              -< Domino Problem >-

< Suppose you have 12 dominoes (let's say each are 1" by 2" by 1/4" thick).

< The dominoes are stacked one on top of another into a vertical pile.
< Then each dominoe is moved slightly along its length so as to extend the
< horizontal span of the structure without collapsing.

< 1.  What is maximum horizontal span possible and how would such a structure
<     be created? 

< 2.  Can a 13th dominoe then be added on top to increase the span without 
<     toppling the pile?

< 3.  What is the theoretical limit of span possible in (1) given as many 
<     dominoes as you needed?

This is an old problem.  The answers are (I'm not going to work it out, but the
basis for the solution is to put each domino piece as far out as possible and
to figure out how far each domino can extend beyond the one directly under it):

1.  1 + 1/2 + 1/3 + 1/4 + ... 1/12

2.  Yes

3.  Infinity; the sum of the harmonic series grows without bounds.

    Let the length of a domino be L (2") and let N be the number of dominoes
    (12 in the problem).  Number the dominoes from top down, starting
    with 1.  Let x[i] be the offset of the 'backward' edge of domino i from
    the bottom domino.  Thus x[N] = 0, and we wish to maximize x[1].
    
    To prevent a topple, the center (of mass) of dominoes above i must not
    be beyond the forward edge of domino i:
    
        i-1			    	 i-1
    	Ave (x[j]+L/2) <= x[i] + L,  or  Ave x[j] <= x[i] + L/2		(1)
    	j=1			         j=1
    
    [Fwiw, we ignore the requirement that the center of mass not be before the
     backward edge of domino i.  Adding these provisos would horribly complicate
     the problem!  See below.]
    
    We have N-1 unknowns, N-1 inequalities, and we wish to maximize x[N] + L.
    It's tempting to make the inequalities equalities and solve, but what's
    the justification for this?
    
    The justification is this.  Note that all the inequalities are linear,
    so each represents a half-space.  Their intersection is the solution
    space, and is either empty or a convex region.  If there is a unique
    solution satisfying all the inequalities (this one does), then the
    solution space has a single vertex.  I.e., it's either a single point,
    a ray, or a cone.  Then an extreme (max or min) of any linear function
    of the variables will either be this point, or be without limit.  For a
    given N, the solution is obviously not limitless.
    
    [Now aren't you glad we didn't include the backward requirements?]
    
    Solving the equations is easy.  From (1) with equalities, take the
    equations for i and i+1 to derive x[i+1] = x[i] - (L/2)/i.  Then since
    x[N] = 0, we can work backwards to get some harmonic numbers.
    
    
    This is close, but something's wrong.  What?

        re .2,
        
>    This is close, but something's wrong.  What?
        
        You didn't take into account how the gravitational field
        decreases as the pile grows away from the surface of the
        earth. :-)
        
        Dan

>
>< 2.  Can a 13th dominoe then be added on top to increase the span without 
><     toppling the pile?
>
>
>2.  Yes
>
Given that a maximum structure of 12 is set up, how would the 13th be
"added on top"?

Allen

	I remember reading an old article by the British puzzlist 
D.StP.Barnard, where examines the question:

	What is the widest bridge that can be made using 28 dominoes?
I don't think he was able to prove his solution maximal, but he had some
ingenious ideas:

	(1) orient dominoes diagonally, to extend reach by factor of 
diagonal/length.

	(2) use some dominoes to make the spans of the bridge, others as
counter-balances, to stop the bridge toppling.

	(3) have a central piece which touched its two props only at its
tips...

	(4) ...therefore the solution is assymetrical, with 14 dominoes on
one side, and 13 dominoes on the other.

Cheers,
Andrew.