Conference rusure::math

    You can balance 3 tubes and you can balance 2, each case by symmetry.

    By superposition of balanced subcases you can then balance 5,
    by interleaving the symmetric arrangement of the 2 and 3 cases.

    I assume that's why they have 12 slots on the centrifuge.

    - Jim

You can also get 7, at positions 1,2,3,6,7,9,10. In fact, the only ones you 
can't get are 1 and 11.

    Add a slug.  Shaped and weighted like a test tube. ;-)

For centrifuge with n positions, what numbers of tubes x cannot
be balanced?

    Here are a few simple results.  Assume n > 1, and n >= x.

	If n and x are even, (n,x) can be balanced.
	(n,x) can be balanced iff (n,n-x) can be balanced.
	(n,1) cannot be balanced.
	(p*q,p) can be balanced (integer p and q, p > 1).

    Can (p*q,p+q) always be balanced (p,q > 1)?

    Re .4:
    
    > Can (p*q,p+q) always be balanced (p,q > 1)?
    
    No.  (2*3,2+3) clearly cannot be balanced.
    
    (Greater than one is assumed unless stated otherwise.)
    
    Further, (pq,p+q) for unequal primes p and q cannot be balanced by
    superposing equal spacings of p tubes and q tubes in a pq slot
    centrifuge.  This is because an equal spacing of p tubes places tubes
    at slots numbered mq for integers m, 0 <= m < p, arbitrarily numbering
    the first slot zero, and the equal spacing of q tubes places tubes at
    slots numbered np+a for integers n, 0 <= n < q, for some integer a.
    But no matter what a is, there is always an m and an n such that mq =
    np+a (Chinese Remainder Theorem).  This does not exclude potential
    balancings of p+q tubes by some other scheme.
    
    If (jk,j+k) can be balanced [by a superposition of (jk,k) and (jk,j) --
    can this restriction be removed?], then (jkl,j+kl) can be balanced.
    Proof:  Take a balancing of (jk,k) and rotate it by 360/jkl degrees.
    Repeat this to form l balancings of (jk,k) at slightly different
    offsets.  Superpose these balancings to form a balancing of (jkl,kl).
    This superposition can be done because the slots in all of the offset
    balancings are at different places, so there is no conflict.  Superpose
    with a balancing of (jk,j) to form a balancing of (jkl,j+kl).  This
    last superposition can be done because the slots from only one of the
    (jk,k) balancings line up with the slots of the (jk,j) balancing, and
    we know the tubes in these can be superposed because (jk,j+k) can be
    balanced by assumption.  QED. 
         
    
    				-- edp

    Call a balancing (n,k) "symmetric" if the k positions are regularly
    spaced around the centrifuge.  Is it true that all balancings are
    either symmetric, or a simple superposition of symmetric balancings?

    No, the following provides a counterexample (n=60); the sets and set
    operations are on multi-sets.

	{10,12,24,36,48,50} = {0,12,24,36,48} + {20,50} + {10,40} - {0,20,40}

    This is not a 'simple' superposition, because of the subtraction
    (i.e., that symmetric balancing has a factor of -1).

    Is it true that all balancings are either symmetric, or a (not necessarily
    simple) superposition of symmetric balancings?

    If m or n is composite and the other is greater than one, (mn,m+n) can
    be balanced.  Let m = rs, r and s being some numbers greater than one.
    To balance (rsn,rs+n), balance one set of n tubes in the slots whose
    numbers are congruent to zero modulo r.  In the slots that are not
    congruent to zero modulo r, we can balance any number of sets of s
    tubes up to (r-1)n sets.  Now r >= 2 >= n/(n-1), so rn-r >= n, or rn-n
    >= r, so (r-1)n sets of s is r sets or more, and we can reduce the
    number of sets by taking them out one at a time, so r sets of s tubes
    can be balanced.  Thus, (rsn,rs+n) or (mn,m+n) can be balanced. 
    
    Also, (m^2,2m) can be balanced if m is not one, simply by placing tubes
    in slots that are zero or one module m. 
    
    So in general, (mn,m+n) with m and n not one can be balanced if m or n
    is composite or m=n.  This is an "iff" if unequal primes m and n cannot
    be balanced by any method (we have only excluded superposition of m and
    n).
     
    
    				-- edp 

re .5,.7:
    I'm having trouble following some of the arguments.  So I've rederived
    and restated the ones from 820.5, generalizing some slightly.  But
    I'm still having trouble with 820.7.  Eric, would you elucidate?

    Thm 1: For p and q relatively prime, (pq,p+q) cannot be balanced by
    superposing equal spacings of p tubes and q tubes in a pq slot centrifuge.
    Proof:  Use the Chinese Remainder Theorem.

    Thm 2: If (jk,w) can be balanced, then (jkl,w+mk) can be balanced,
    for any 0 <= m < l, where jkl >= w+mk.
    Proof:  (by construction)  Let {a[i] mod jk} be the set of tubes in the
    (jk,w) balancing.  Form the (jkl,w) balancing: { a[i]*l mod jkl }, and
    superpose it with m different (jkl,k) balancings: { njl + b mod jkl },
    1 <= b <= m < l.  There is no intersection between these, since that would
    imply njl + b = a[i]*l (mod jkl), so that b = 0 (mod l), which contradicts
    1 <= b < l.  The result is a (jkl,w+mk) balancing, for any 1 <= m < l,
    and the inclusion of m = 0 in the theorem is trivial.

>    Thm 1: For p and q relatively prime, (pq,p+q) cannot be balanced by
>    superposing equal spacings of p tubes and q tubes in a pq slot centrifuge.
>    Proof:  Use the Chinese Remainder Theorem.

But it's worth pointing out that unequal spacings may work: e.g. for 
p=3, q=4 putting tubes in slots (1, 2, 4, 5, 8, 9, 10) works.

    .5 referred to p and q unequal primes, as opposed to relatively
    prime.
    
    I didn't check to see if the difference really mattered, though.

    Re .8:
    
    Here is .7 in another form.  Let m = rs.
    
    First put n tubes in
    
    	irs mod mn, 0 <= i < n
    
    For specific a and b (0 <= a < n and 0 < b < r) we can balance s tubes
    in: 
    
    	(in+a)r+b mod mn, 0 <= i < s
    
    Proof:
    
         Each set is a balancing because it places s tubes uniformly
         around the mn slots in slots nr spaces apart.  Next,
    
         (in+a)r+b mod mn mod r = b.       (0)
         (in+a)r+b mod mn mod rn = ar+b.   (1)
    
         None of the sets overlap the tubes in irs because irs mod r =
         0, and b is not zero in (0) above.
         
         No pair of sets, a and b with a' and b', overlap each other:
         Any two sets have different a or different b (or they are the
         same set).  If b <> b', (0) above shows they do not overlap.
         If a <> a', then ar+b <> a'r+b', since b and b' are less than
         r and cannot account for the difference between ar and a'r. 
         
    So in addition to the n tubes, we have a set of balancings of s tubes
    for each possible a and b.  There are n a's and (r-1) b's available, so
    we have (r-1)n balancings of s tubes each of which we can include or
    omit in our superposition as we please. 
    
    Thus, if m is composite with a composition m=rs, we can balance
    (mn,cs+n), where 0 <= c < (r-1)n.  If we can prove (r-1)ns >= m, then
    (mn,m+n) can be balanced. 
    
    r >= 2, since it is a factor in the composition of m.  n/(n-1) is
    clearly less than or equal to two, since n is at least two.
    
    So r >= 2 >= n/(n-1).
    
    	r >= n/(n-1).
    	rn-r >= n.
    	rn-n >= r.
    	(r-1)n >= r.
    	(r-1)ns >= rs.
    	(r-1)ns >= m.
    
    QED.
    
    Also mentioned in .7, (m^2,2m) is balanced with tubes in:
    
    	im+b, 0 <= i < m, 0 <= b < 2.
    
    
    				-- edp

    Thm 3:
	If (pq,x) and (q,y) can be balanced, where (q,y) <> (1,1),
	then (pqr,ix+jy) can be balanced, ipq + jq + <= pqr.

    Proof:  (by construction)

	Let { s[*] mod pq } be the set of tubes in the (pq,x) balancing.
	Let { t[*] mod q } be the tubes in the (q,y) balancing.

	Take the superposition of the sets:

	    { s[*]*r  + u mod pqr }, 0 <= u < i <= r,  i (pqr,x) balancings
	    { t[*]*pr + v mod pqr }, 0 <= v < j <= pr, j (pqr,y) balancings

	and so on.

    Thm 3:
	If (pq,x) and (q,y) can be balanced, where (q,y) <> (1,1),
	then (pqr,ix+jy) can be balanced, ipq + jq + <= pqr.

    Proof:  (by construction)

	Let { s[*] mod pq } be the set of tubes in the (pq,x) balancing.
	Let { t[*] mod q } be the tubes in the (q,y) balancing.

	Take the superposition of the sets:

	    { s[*]*r  + u mod pqr }, 0 <= u < i <= r, for i (pqr,x) balancings
	and
	    { t[*]*pr + v mod pqr }, 0 <= v < pr, for j (pqr,y) balancings,
					where j <= pr, and v <> u (mod r).

	Consider values modulo pr.  Each (pqr,x) balancing 'consumes' p values
	modulo pr.  Each (pqr,y) balancing 'consumes' 1 value modulo pr.  So we
	get the requirement that ip + j <= pr, and this suffices.

When can (n,k) be balanced?

Thm 5.
    Suppose n = pqr, where p and q are relatively prime, and r >= 2.
    Then (n,k) an be balanced if pq - p - q < k < pqr - (pq + p + q).

    [ Note that it's best to apply the theorem with p and q being the
      two smallest distinct prime factors of n. ]

Proof:

    We can superpose the following sets:

	B balancings of (pqr,Fp), 0 <= F <= q, and
	C balancings of (pqr,Gq), 0 <= G <= p, where B + C <= r.

    The sets are:

	{ r*(q*i + f) + b  mod  pqr },	0 <= i < p, 0 <= f < F, 0 <= b < B, and
	{ r*(p*j + g) + c  mod  pqr },	0 <= j < q, 0 <= g < G, B <= c < B+C,
					with B+C = r.

    To see why this works, note that the b and c values prevent the sets from
    interfering with each other.  Also note that each of the F and G values
    may be independently chosen, so that the combined balancing is: 

	         B            C
	(pqr, p Sum F[i] + q Sum G[j] ),
	        i=1          j=1

    with constraints:

	B + C <= r
	0 <= F[i] <= q
	0 <= G[j] <= p

    Assume without loss of generality that p < q.  Our balancings will use:

	One balancing of (pqr,Fp), 0 <= F < q, and
	One balancing of (pqr,Gq), 0 <= G < p, and
	Additional balancings of (pqr,pq).

    so that (pqr,k) can be balanced, where k = Epq + Fp + Gq.


    We note the folowing theorem: If P and Q are relatively prime, then any
    number K > PQ - P - Q can be written as K = aP + bQ, for some non-negative
    a and b.  Assume that P < Q.  If we also require a + b <= B, for some
    bound B >= Q-1, then numbers in the range PQ - P - Q < K < BQ - (Q-P)(Q-1)
    can be written as K = aP + bQ, with a + b <= B (and a < Q).


    We have k = Epq + Fp + Gq = (F)p + (G+Ep)q.  We have a bound:

	(F) + (G+Ep) <= (q-1) + (r-1)p

    The above theorem says that we can satisfy this for any k in the range:

	pq - p - q < k < (r-1)pq + p(q-1)

    Now (r-1)pq+... > pqr/2 = n/2, since r >= 2.  So we can balance (n,k) for
    pq - p - q < k <= n/2.  Since we've passed the halfway mark, and can use a
    balancing (n,k) to yields a balancing for (n,n-k), we can extend the range
    of k to:

	pq - p - q < k < pqr - (pq - p - q)

    [ Note that (pqr,k) also balances for some k outside this range. ]

The following cases are not covered by the Thm 5.  Assuming as true the
conjecture that for prime p, (p,k) balances only when k=0 and k=p, we have:

    Case 1.
	     m
	n = p , p prime, and m >= 1  (and 0 <= k <= n, of course).

	    (n,k) will balance iff k is a multiple of p.

    Case 2.
	n = pq, p and q distinct primes.

	    (n,k) will balance iff k is a multiple of p or q or both.

    Case 3.

	n = pqr, p and q prime, r >= 2, pqr - (pq - p - q) <= k <= pqr.

	    Use (n,k) balances iff (n,n-k) balances, and apply case 4 or 5.

[ If Thm 5 applies, then letting p and q be the smallest prime factors of n,
  implies either r = p, or r >= q.  This leads to two final cases. ]

    Case 4.
	     2
	n = p q, p and q prime, 0 <= k <= pq - p - q.

	    (n,k) will balance iff k can be rewritten as k = ap + bq, for some
	    non-negative a and b.  Note that the solution, if any, is unique,
	    since k < pq.  Use Euclid's algorithm.

    Case 5.
	n = pqr, p and q the smallest prime factors of n, p < q < r,
	and 0 <= k <= pq - p - q.

	    An efficient algorithm would be nice.

Let's subdivide case 5 further.

    Case 5.1.
	Same as case 5, with p = 2.
	    (n,k) can balance except when k = 1 (k = n-1 is covered by case 3).

    Case 5.2.
	Same as case 5, with p = 3.
	    Let s[m] (for 0 <= m < 3) be the smallest prime factor of n
		with n mod 3 = m, or infinity if there is no such factor.
	    Then (n,k) can balance iff:
		k = 0 (mod 3), or
		k = 1 (mod 3) and k >= min(s[1],2s[2]), or
		k = 2 (mod 3) and k >= min(s[2],2s[1]).
	    That is, we use the superposition k = i*p + a*s[m], 0 <= a,m < 3.
	    In any event, (n,k) balances if (but not only if)
		k >= min ( (k mod 3) * s[1], (2k mod 3) * 2s[2] ).

    Case 5.3.
	Same as case 5, with p > 3.
		            e[1]     e[2]        e[f]
		Let n = p[1]     p[2]    ... p[f]     be the prime factorization
		of n, with 3 < p[1] < p[2] < .... < p[f]; p = p[1], q = p[2].
		Let s[m] (for 0 <= m < p) be the smallest prime factor of n
		with n mod p = m, or infinity if there is no such factor.
		Then ... this may be the start of an algorithm.  Note, BTW,
		that we need only be concerned with primes <= pq - p - q.