Conference rusure::math

    I think two of the vertices in your example are mislabelled:
    
nodes               vertices
A,B,N,O  ------>     11
C, D     ------>     12
E        ------>      4 (not 5)
F, H     ------>     10
G        ------>      3
I, J     ------>      2
K        ------>      1
L        ------>      9
M        ------>      5 (not 4)
    
    The problem should admit a fairly efficient solution, using dynamic
    programming.  That is, compute, the following 3*3*(15)^2 values:
    
    	X[ from-node, from-vertex, to-node, to-vertex ]
    
    where X[...] is the number of ways the counter-clockwise path from
    from-node to to-node can be assigned to vertices (meeting the rules),
    such that the from-node is at from-vertex (one of that node's three
    vertices), and to-node is at to-vertex.
    
    The trick is to compute these efficiently.  I'd suggest the following
    order:
    
    	for d := 0 to 15 do				-- path length
    	    for node := 'A' to 'O' do
    		for fv := 1 to 3 do for tv := 1 to 3 do
    		    compute X[ node, fv, node+d, tv ]
    
    The rest is fairly straight-forward.

    re .1
    You are right, I some what switched the node numbers in the diagram?
    Thanks for the correction.
    I know it is doable by computer, but is there any combinatorial
    argument that can give the answer quickly.  Also I shall be grateful
    if someone finds the solution for me.
    Eugene
    

     What's the deadline for a solution?
     
     Dan

    Whatever the solution, I think that Eugene deserves credit for what
    must be this years "most complex MATH drawing with a character cell
    terminal".
    
    You said that you "...need..." an anwser.  Does this mean that this
    problem is actually work-related? (?!!?)
    
    ( Let me know, because I always put out extra for problems of immediate
    practical value ).
    
    --  Barry

    There is no deadline for this problem, and the problem is not work
    related.  The strange thing about this problem is that it turns
    out in an Algebraic Topology book.  It is the very first excersize
    of a section (usually very easy to do).  The problem was stated
    in a different form, but can essentially be reduced to the problem
    as stated in .0.  I tried that problem (thinking that it must be
    easy), but couldn't get it.  You know how it goes.  After a while,
    it gets personal :-).  First you say to yourself:  I got to get
    it done.  After a while, you say I got to know the answer.  After
    a while, I realized that there is no way to do the problem but with
    a computer, so I quit trying, but I still got to know the answer
    :-) :-)....  I guess I was born a mathematician :-) :-).
    As for drawing the most complex MATH drawing with a character cell
    terminal....  Actually, I have a graphics terminal, but just don't
    know how to make full use of it.  Also I got a lot of help from
    a friend of mine around here (He is a contractor with a Ph.D degree
    in math from Yale.  Did something in Lie group, very smart guy).
    Eugene 

    The problem is characterized by the 12 values: 2,1,1,1,1,2,2,0,2,1,2,0,
    where each value is the number of nodes in each (successive) triangle.
    Call these e , e , ..., e  .
                0   1        11
    
    Define the following 3x3 matrices:
    
    	     [ 0 1 0 ]        [ 1 1 1 ]        [ 2 3 3 ]
    	X  = [ 0 0 1 ],  X  = [ 1 1 1 ],  X  = [ 2 3 3 ]
    	 0   [ 0 0 0 ]    1   [ 0 1 1 ]    2   [ 2 3 3 ]
    
    Now the number of ways the nodes can be assigned according to the
    constraints is:
    
    	trace( X  * X  * ... * X   )
    	        e    e          e
    	         0    1          11
    
    N.B., The trace is the sum of the values on the major diagonal.

    Observation 1:
    
    	Legal mapping of nodes to vertices according to constraint #1
    	(but NOT constraint #2) are:
    
    	O,A:	6, 7,11
    	B: 	7,11,12
    	C: 	7, 8,12
    	D: 	4, 8,12
    	E: 	4,10,12
    	F,G: 	3, 4,10
    	H,I: 	2, 3,10
    	J,K: 	1, 2, 9
    	L: 	1, 5, 9
    	M,N: 	5, 9,11

    
    Observation 2:
    
    	According to Constraint #2, the following combinations of node
    	to vertex mappings are not allowed:
    	
    	A6,  B12
    	B11, C8
    	C7,  D4
    	D8,  E10
    	E12, F3
    	G4,  H2
    	I3,  J1;    I3,  J9;    I10, J1;    I10, J9
    	K2,  L5
    	L1,  M11
    	N5,  O6;    N5,  07;    N9,  06;    N9,  O7
    
    Observation 3:
    
    	By Obsv.'s 1 & 2, it is clear that the mappings assumed by any
    	two nodes in the same triangle are completely independent of
    	each other, and thus total combinations may be calculated
    	independently (ie. multiplied).
    
    Assertion 1:
    
    	Series of N side-adjacent triangles with single (and thus dependent)
    	node interior triangles and dual node (and thus otherwise 
    	independent) end-trianlges can assume S(n) different mappings,
    	where:
    		S(n) = 3*S(n-1) - S(n-2)
    	and	S(1) = 3, S(0) = 1
    
    Examples:
    
    	S1:	 /\1		= 3
    		/A \
    	      2------3
    
    	S2:			= 3*(3) - (1)  = 8
    		1+----------4
    	        / \    C  /
    	       /   \ B   /
    	      /  A  \   /
    	     / O     \ /
    	   2+----------3

    
    	S3:			= 3*(8) - (3)  = 21
    		1+---------4
    	        / \       / \
    	       /   \ B   /   \
    	      /  A  \   / C   \
    	     / O     \ /    D  \
    	   2+----------3--------+5

    	Etc.  Note that rotations of the triangles make no difference
    	so long as they stay side-adjacent.
    
    	NOTE:  The proof of this assertion is left as an exercise for
    	the reader.
    
    Therefore:
    
    	The total number of mappings is equal to:
    
    		Total mappings of (A-B-C-D-F)	=  S(6)  = 377
    	times  (total mappings of (G-H)		=  S(2)  =   8
    	times  (total mappings of (I-J)		=<count> =   5
    	times  (total mappings of (K-L-M)       =  S(3)  =  21
    	times  (total mappings of (N-O)		=<count> =   5

    							 = 1,583,400
    
    --  Barry