Conference rusure::math

Lemme take the easy one...

>1. Find a pair of 2 six-digit numbers such that, if they are written down side
>by side to form a twelve-digit number, this number is divisible by the product
>of the two original numbers. Find all such pairs of six-digit numbers. (3 pts)

In other words, looking for a, b where:

(1)	99999 < a < 1000000
(2)	99999 < b < 1000000
(3)	ab | 1000000*a+b

Now ab | x --> (a | x and b | x/a), so (3) --> b | 1000000+(b/a)
where, by (1), b > 99999 * (b/a) and, by (1) and (2), 0 < b/a < 10

so b = 1000000+(b/a) / K, where 1 < K < 1000010 / (999999*(b/a))

This is actually a very small search space because of the limit on b; only
a few small divisors K of 1000001 through 1000005 need be considered, and
1000006 through 1000009 can be eliminated immediately. 

The only solution is when b/a = 2 and K=3, and is: b = 333334, a=166667.

>3. A club of 11 people has a committee. At every meeting of the committee a new
>committee is formed which differs by 1 person from its predecessor (either one
>new member is included or one member is removed). The committee must always
>have at least three members and, according to the club rules, the committee
>membership at any stage must differ from its membership at every previous
>stage. Is it possible that after some time all possible compositions of the
>committee will have already occurred? (6 pts)

Huh? I'm confused. This seems too easy for a 6-pointer. The committee
composition at any time is given by describing each club member as In or Out,
so there are less than 2^11 compositions and the answer is obviously Yes, with
most of the problem wording treated as a red herring. What am I missing? 

(The exact upper bound on compositions is a little more interesting, it is no
more than 1981 but could be less, and could depend on the initial composition.)

    re .2                                     
    
    It's a little unclear. I haven't looked at this problem but ...
    
    consider the different committees as nodes in a network where two nodes
    are connected if they meet the condition for change of committee (i.e.
    differ by 1 person) and ignoring all committees with less than three
    members then the question asks whether there is a path through the
    network visiting every node exactly once. By symmetry it should not
    depend on the starting node.

    Yes, I read it that way the first time. Going back and looking for an
    alternative reading that made more sense, I interpreted the last line
    as meaning "Is it possible to pass through all permissible committees
    (ie every subset with three or more members) following the "only one
    change" rule? Or do you necessarily get stuck at some point where there
    are valid committees that have not occurred, but these cannot be
    reached without violating the change rule?
    
    The question then becomes:
    
    Can the set of all subsets of {1,2,...11} with three or more members be
    ordered such that each element differs from its predecessor by exactly
    one member?
    
    On the face of it, it looks as though the answer should be a definite
    "yes". I'll see if I can come up with an ordering.
    
    Andy.
         

    re .3: Notes collision!
    
    Yes, that was the approach I was taking. Note that we need only a path,
    not a circuit. If it's not a circuit then it could well depend on the
    starting node, equivalent solutions would exist for all other nodes
    with the same number of elements.
    
    The nodes split into classes according to the number of elements. Each
    of the C(11,n) nodes of class n connects to exactly (11-n) nodes of
    class n+1 and n nodes of class n-1, with the obvious exception for n=3.
    That's an awful lot of connections, which should make it quite easy. :)
    
    I seem to remember a coding system for electromechanical A/D converters
    where are wheel was marked out in 2^n sectors covered in conducting and
    non-conducting bands such that every band was uniquely coded and
    adjecent sectors differed in only one band. This ensured there were no
    spurious values due to edge effects. If this coding exists for all n
    (or at least, for n=11) then it solves the problem with the 3 member
    constraint removed. (A committee of zero persons is very efficient!).
    
    This gives us a solution with at most C(11,2) = 55 gaps where the
    sequence dips down to committees of size 2 or less. (Actually
    fewer since we need to get down to 1's and than means comming back via
    anothe 2, so 2 2's sit in one gap). Perhaps these gaps could be
    "stitched together" to complete the sequence?
    
    Andy.

    There's no such Hamiltonian path through this bipartite graph.
    
    If the nth committee has an even number of members, then the (n+1)th
    has an odd number of members. So:
    
    |Number of committees with an odd number of members|
  - |Number of committees with an even number of members|
  = -1,0 or +1.
    
    Now if we were operating with the full set of 2^11 = 2048 committees,
    then we would have no problem providing the Hamiltonian path. However,
    the quorum restriction removes 1+55 = 56 even committees, and only 11
    odd committees. So there's no possible path. Not even close.
    
    Cheers,
    Andrew.
    

>    I seem to remember a coding system for electromechanical A/D converters

It's called Gray code, and exists for all 'n'.  The GE 635 had instructions
to convert between Gray and binary for 36-bit numbers...

    For 1 <= i <= 101, sort the rectangles (a(i),b(i)) according to their
    shorter (a) side.

    We must be able to find two rectangles to fit, since there must be at least
    one repetition in the a's, a(r) = a(r+1) say.

    Let these two rectangles be (a(r),b(r)) and (a(r+1),b(r+1)). Assume we can
    find no other rectangles that can be contained by the former or contain the
    latter. The preceding rectangles must have b(i) > b(r) and the succeeding
    ones must have b(i) < b(r+1). Again, pigeonholing tells us:

    2(100 - b(r))    >= r - 1   (otherwise some b is repeated three times)
    2(b(r) - a(101)) >= 100 - r (similarly, also a(i) <= b(i))

    adding these we get 2(b(r) - b(r-1)) >= 2a(101) - 101

    Pigeonholing overall tells us that the minimum a(101) is 51 (otherwise some
    a is repeated three times).

    So we get 2(b(r) - b(r-1)) >= 1 which contradicts our sorting. Therefore
    there is a third rectangle.

    Dick
    Not very well explained but it is Monday.
    

    Here's a slightly different approach to number 5.
    
    Suppose that we have a set of rectangles.
    
    If A lies in B, call this a *containment*.
    
    Let rung_i be the set of all rectangles (x,y) x>y such that x+y = i, for
    i=2,200.
    
    Let I by the smallest i such that rung_i is not empty. Suppose make each
    rectangle in rung_I longer by 1 (i.e.: x->x+1). We know that we haven't
    introduced a containment. Why?
    
    Well, let r be a rectangle in rung_i. r is bigger, so it can't fit in
    any rectangle that it couldn't fit in before. r is only 1 element
    longer, and by the definition of rung_I, any rectangle which r can now
    contain, it could already be contained by before.
    
    We can iterate the rung_I trick until we reach a point where I=101.
    Similarly, we can reduce the width of every rectangle in rung_J, where
    J is the largest i such that rung_i is non-empty. We can do this until
    J = 101.
    
    Therefore, if there is any set of rectangles, then there is a set of
    rectangles with no more containments, with every rectangle lying in
    rung_101. But rung_101 can contain at most 2*50 = 100 rectangles
    without triple containment (A in B in C).
    
    So if we have any set of 101 rectangles, then there must be a triple
    containment.
    
    Andrew. 

re .5
    
>    Yes, that was the approach I was taking. Note that we need only a path,
>    not a circuit. If it's not a circuit then it could well depend on the
>    starting node, equivalent solutions would exist for all other nodes
>    with the same number of elements.
    
    Oops, yes, correct. My statement that it does not depend on the
    starting node was incorrect. It could perhaps have been said that it
    depends on the starting node only in so far as it depends on the number of
    members in the committee that corresponds to that node. However as Andrew
    shows in his succinct manner, such a path does not exist (for any starting
    node) anyway.

    Colour the regions black and white, so that no two adjacent regions
    share the same colour.
    
    For each region, count the number of points which are incident to that
    region, p. If the region is black, label the region p, else label it
    -p.
    
    Each region is incident to at least 1 and at most N points, so the
    label is within the required bounds.
    
    Consider a point. To each side of any line through it, it will
    contribute +1+(-1)=0. To one side of any line which does not pass
    through it, it will contribute +1+(-1)+1+(-1) = 0. Therefore the sum of
    all the labels to either side of a line is 0.
    
    Cheers,
    Andrew.

    re .11
    
    My incomplete proof was heading along similar lines except that I
    didn't go for colouring but rather just that the signs alternate. It is
    necessary to show that such a colouring/alternation is always possible.
    It seemed to me that induction on the number of lines is sufficient to
    show this - or is there some more obvious demonstration of this?

    re .12
    
    	Pick a region, r. Colour each other region, s, black/white if there is a
    walk of even/odd length ending in s. Colouring is well-defined, else
    there is a circuit (r->r) of odd length. But any circuit must cross
    each line an even number of time so the total length is even.
    Contradiction.
    
    Andy