Conference rusure::math

    I realized that I made a minor mistake - here is the correction.

         <<< Note 1268.1 by ALLVAX::JROTH "It's a bush recording..." >>>
                          -< Perspective drawing... >-

>> 8.   [Not actually in the competition, but recounted to me by a kid of 12.]
>>	I have a unmarked ruler of length 1, and two points in the plane 
>> separated by distance d, where 1 < d [& say that d < 2, for simplicity]. Can 
>> I draw a straight line linking the two points?

Let the points be l and r.  I can lay out a pair of long lines A and B
passing through the righthand point r and passing nearby above and below the
left point l by successively extension of lines initially less than the length
of the ruler.

Now draw a line passing upward and right thru l and intersecting A at a,
and a line passing downward and right thru l and intersecting B at b, and
draw the line ac forming a triangle.  The idea is to make another perspective
triangle to the right of this one.

Next draw lines passing thru a' on A parallel to la and ab (using the
length of the ruler to do this); the line parallel to ab hits B at b'.
Draw a line parallel to lb passing thru b'; this line intersects the line
parallel to la at l' forming a perspective view with point r as a vanishing
point, so we can now draw the line M = ll' and extend it to the right to
pass thru r.

Diagram:  (I omitted the lines A, B, and M but it should be clear.)

          |/
          a          |/
         /|          a'
        / |         /|        line A = a a' r
       /  |        / |
      /   |       /  |
   \ /    |    \ /   |
    l     |     l'   |        line M = l l' r            r
   / \    |    / \   |
      \   |       \  |
       \  |        \ |        line B = b b' r
        \ |         \|
         \|          b'
          b          |\
          |\ 

When I was a kid I had a fascination with perspective drawing and could
have easily done this problem at the age of 12.

- Jim

>Next draw lines passing thru a' on A parallel to la and ab (using the
>length of the ruler to do this); 

MUCH too handwavy. Remember, you don't have a compass to help construct 
perpindiculars and parallels. Nor have you any assurance that the 
straightedge has reliable angles to work with.

Lynn

>2.	Three boys, Anatole De Face, Bertrand Du Dessus, and Christophe De
>C�t�, must calculate the volume of a cuboidal shoebox, whose 3 dimensions are
>each a whole number of centimetres.   But they don't use the right formula:
>they use V = A + h instead of V = A*h where V is the volume, A the area of the
>base, and h the height.   Anatole, Bertrand and Christophe find respectively
>304,416 & 169 cm�.
>
>	What is the volume of the box, in cm�.

10*14*29=4060

>4.	You have a sequence of real positive numbers.   The first is 1, and
>each is the sum of the two which follow it.   Let A be the 1990th number, and
>B = 1/A.   If B is written as a decimal, what is the number before the decimal
>point, and the number after the decimal point.   [No electronic help!]

It should be apparent that the sequence is the inverse of the Fibonacci 
series; A(1990) =~ 1/F(1990), so B=~F(1990). Now F(5*n) is divisible by 5; 
the last digits are 5,5,0,5,5,0,5,5,0,.... Since 1990 is not a multiple of 
3, the last digit of F(1990) is 5. Also, F(n) is asymptotic to phi^n, 
where phi = (1+sqrt(5))/2, with the odd approximants too large and the even 
ones too small. So B is actually a tiny bit less than F(1990), so the digit 
sequence looks like *4.9*.

     <<< Note 1268.3 by CIVAGE::LYNN "Lynn Yarbrough @WNP DTN 427-5663" >>>
                       -< A sharp pencil is not enough >-

>>Next draw lines passing thru a' on A parallel to la and ab (using the
>>length of the ruler to do this); 

> MUCH too handwavy. Remember, you don't have a compass to help construct 
> perpindiculars and parallels. Nor have you any assurance that the 
> straightedge has reliable angles to work with.

I thought it would be obvious how to make a parallel line using a calibrated
straightedge.  I was not saying to "eyball" it!

Oh well, here's one way:  To produce a parallel to L, choose a point o nearby
above L and find points a and b on L the length of the ruler distant
from o on L.  You have an isososceles triangle.  Extend the lines ao and bo
and mark points a' and b' equidistant from o and draw L' between and beyond
them.

   ------a'------b'---------	L'
	  \     /
	   \   /			oa, ob, oa', ob' = length of ruler
	    \ /
	     o
	    / \
	   /   \
	  /     \
   ------a-------b----------	L


- Jim

4.	You have a sequence of real positive numbers.  The first is 1, and
each is the sum of the two which follow it.   Let A be the 1990th number, and
B = 1/A.   If B is written as a decimal, what is the number before the decimal
point, and the number after the decimal point.   [No electronic help!]

>> .4
>> It should be apparent that the sequence is the inverse of the Fibonacci 
>> series; A(1990) =~ 1/F(1990), so B=~F(1990). Now F(5*n) is divisible by 5; 
>> the last digits are 5,5,0,5,5,0,5,5,0,.... Since 1990 is not a multiple of 
>> 3, the last digit of F(1990) is 5. Also, F(n) is asymptotic to phi^n, 
>> where phi = (1+sqrt(5))/2, with the odd approximants too large and the even 
>> ones too small. So B is actually a tiny bit less than F(1990), so the digit 
>> sequence looks like *4.9*.

	We are given x[n] = x[n+1] + x[n+2], so the standard method
	of assuming a solution of the form x[n] = r^n yields the
	equation r^n = r^(n+1) + r^(n+2), or 1 = r + r^2.  This has
	the two roots -T and 1/T, where T is "tau" or (sqrt(5) + 1)/2
	and 1/T = (sqrt(5) - 1)/2 = T-1.  So the general solution is

		x[n] = a (-T)^n + b (1/T)^n

	Usually you plug in the members of the sequence for two values
	of n to solve for a and b.  Here we only have x[1] = 1 and the
	information that all members of the sequence are real and positive.
	Since |T| > 1 and |1/T| < 1, as n gets large the contribution
	of the term b (1/T)^n becomes negligible and the contribution
	of the a (-T)^n term dominates, resulting in a sequence whose
	members eventually alternate in sign ... unless a is zero.  Since
	all members of the sequence are positive, a must be zero, and
	then using x[1] = 1 yields b = T, and so x[n] = T (1/T)^n or
	x[n] = (1/T)^(n-1).  So A = x[1990] = 1/T^1989 and B = 1/A = T^1989.

	The problem now is to give the digits immediately before and
	immediately after the decimal point in the decimal representation
	of B (or take the easy way out ... the "number before the
	decimal point" is [ B ] = the greatest integer <= B, and "the
	number after the decimal point" is B - [ B ].) :-)

	Note that for the Fibonacci series F[n+2] = F[n+1] + F[n] with
	F[0] = 0, F[1] = 1, the equation becomes s^2 = s + 1 with roots
	T and -1/T and general solution F[n] = (T^n - (-1/T)^n)/sqrt(5),
	which for large n is approximately (T^n) / sqrt(5).

	The suggestion in reply .4 to use F[n] as an approximation to
	T^n then does not work, as the correct approximation is that
	T^n is approximately F[n] sqrt(5).  Finding the units and "one-tenth"
	digits of F[n] sqrt(5) involves multiplying sqrt(5) by a massive
	integer, using lots of precision.

	But at least we know that B = T^1989 = ((sqrt(5) + 1)/2)^1989,
	even if we don't yet know those two digits.

	Dan

Still, I think, too handwavy:

>		To produce a parallel to L, choose a point o nearby
>above L and find points a and b on L the length of the ruler distant
>from o on L.

It strikes me that this operation - or rather, its lack of definition - is 
the reason you need a compass for these constructions. With a compass, you 
can define a and b as the intersections of two loci; without the compass 
you are only guessing whether you have found the points. At least I think 
that's the Euclidian point of view.

I think the only things you can define with a straightedge with one 
distance marked are: Line segments of the given length or shorter with one 
end point given; and line segments through the endpoints of previously 
defined segments. From these, certain linkages can be described, and one can 
draw certain conclusions about invariants in those linkages. But since we 
are dealing in essence with two independent linkages from each initial 
point, unless some relation can be deduced between the linkages that is 
independent of rotation about each point, I don't think the problem can be 
solved exactly, in the Euclidian sense.

With a point light source (everyone has a laser in their pocket these days, 
don't they?) a "practical" solution is to stand the strightedge on one end
at point A and let the shadow fall on point B. Mark some other point on the 
shadow between A and B and you can connect the dots. Euclid would rotate 
about his Y-axis.

>3.	Take a number of 4 digits, for example 1990.   Add the 1st and the
>last digit mod 10, to get a digit u.   Form again a new number of 4 digits by 
>placing u on the right of the last three digits of the starting number.   
>Repeat this procedure.   If you begin with 1990, you get 9901 & 9010 & 0109 &
>1099 & ... you get back to 1990 after exactly 1560 steps.
>
>	Find a number of 4 digits which aren't all the same, doesn't begin with
>a zero, and which returns to the start before 20 steps.   [I have wilfully
>mistranslated this question to make it slightly harder.]
>
The operation of addition and reduction mod 10 transforms the set {0,5} 
into itself. Since there are only 2^4=16 arrangements of 2 digits, any
arrangement of 5's and 0's, say 5050, will do. 

>               <<< Note 1268.6 by GUESS::DERAMO "Dan D'Eramo" >>>
>	But at least we know that B = T^1989 = ((sqrt(5) + 1)/2)^1989,
>	even if we don't yet know those two digits.

	Agreed.   Now only a very few people (of whom I was not one) managed
to figure out the neat trick required for the next step during the morning
session.   It took me two days!

Regards,
Andrew.

>>	>               <<< Note 1268.6 by GUESS::DERAMO "Dan D'Eramo" >>>
>>	>	But at least we know that B = T^1989 = ((sqrt(5) + 1)/2)^1989,
>>	>	even if we don't yet know those two digits.
>>
>>		Agreed.   Now only a very few people (of whom I was not one)
>>	managed to figure out the neat trick required for the next step during
>>	the morning session.   It took me two days!

	Aha!  Powers of T (tau, i.e. (sqrt(5) + 1)/2) can be
	expressed as linear combinations of T and 1, with the
	coefficients being Fibonacci numbers.

	Specifically I'll use F[0] = 0, F[1] = 1, F[n+2] = F[n+1] + F[n].

	Then since T^2 = T + 1 we have T = 1 + 1/T.  Multiply both
	sides by T to see T^2 = T + 1 = (1 + 1/t) + 1 = 2 + 1/T.
	Then T^3 = 2T + 1 = 2(1 + 1/T) + 1 = 3 + 2/T.  In general

		T^n = F[n+1] + F[n] / T

	Likewise, 1/T = T - 1, so 1/T^2 = (T - 1)/T = 1 - 1/T =
	1 - (T - 1) = -T + 2, and 1/T^3 = -1 + 2/T = -1 + 2(T - 1) =
	2T - 3, and in general

		(-1/T)^n = -F[n] T + F[n+1]

	Adding,

		T^n + (-1/T)^n = 2 F[n+1] - F[n].

	For n = 1989, this becomes

		T^1989 - 1/T^1989 = 2 F[1990] - F[1989]

	The "unknown" is B = T^1989 which is seen to equal
	2 F[1990] - F[1989] + A.  The ones digit of this is
	the ones digit of 2 F[1990] - F[1989], and the "one-tenths"
	digit is zero because A = 1/T^1989 is so small.

	So the answer to this question is that B = ... d point 0 ...
	where d = 2 F[1990] - F[1989] mod 10.

	Doing the Fibonacci sequence "mod 10" by hand shows a period
	of 60, so that F[1990] mod 10 = F[1990 mod 60] mod 10 = F[10] mod 10
	= 5, and F[1989] mod 10 = F[1989 mod 60] mod 10 = F[9] mod 10 = 4.
	So d is 2 * 5 - 4 mod 10 = 6, and the digits immediately before
	and after the decimal point of B are 6 (before) and 0 (after).

	Dan

>>	Adding,
>>
>>		T^n + (-1/T)^n = 2 F[n+1] - F[n].

	Oops, this wasn't handwaving, I merely left out the
	substitution 1/T = T - 1, getting

		T^n + (-1/T)^n	= F[n+1] + F[n] / T + -F[n] T + F[n+1]
				= F[n+1] + F[n](T - 1) + -F[n] T + F[n+1]
				= 2 F[n+1] - F[n]

	T^n expressed as a combination of T and 1 (instead of 1 and 1/T
	as I used) would be T^n = F[n+1] + F[n] / T = F[n+1] + F[n](T - 1)
	= F[n] T + (F[n+1] - F[n]) = F[n] T + F[n-1].  It might have been
	neater to write it up that way, but I actually solved it using
	1 and 1/T and except for filling in this one step I didn't see the
	need to pretend my method had been prettier. :-)

	Dan

	I did it a different way.

	If U = (1-sqrt(5))/2, then T^1989 is clearly just a *tiny* bit 
more than T^1989 + U^1989.   Now the trick.

	1989 = 3*663.
	T^3 = (1+sqrt(5))�/8 = 2 + sqrt(5)
Sim:	U^3 = 2 - sqrt(5)

	Now, expanding (2 + sqrt(5))^663 + (2 - sqrt(5))^663, half the terms
cancel, and of the result most are not relevant to us because they are
multiples of ten.   All that remains is 2^664 which is 6 mod 10.

Regards,
Andrew.

>1.	General Emile Itaire is at the head of a corps comprising between
>1000 and 1990 men.   He decides to arrange them in an original way: as
>a number of columns (at least two) with each column containing one more man
>than the previous column.   However, despite all his efforts, he does not
>succeed.
>
>	How many men are in the corps?

Let the number of men be M then note that -

a) all odd numbers are expressible as 2n + 1 = n + (n+1), so M is even.

b) consider the sum -

n + (n+1) + (n+2) ... + (n+2m) = (2m+1)(n+m)

since summing the n gives (2m+1)n and 1 + 2 + ... + 2m = �.2m.(2m+1) = m(2m+1)

Then any odd prime is expressible as 2m+1 and hence does not divide M since
if it did M would be expressible as (2m+1)(n+m).

Therefore M = 1024 since that is the only number between 1000 and 1990 which
is a power of 2.

    Brian

        1024 is the "obvious" answer for question (1) but I don't
        think .13 has established it yet.  For one thing, it
        doesn't consider the case of an even number of columns
        and whether that can rule 1024 out as a possible answer.
        Secondly, it doesn't consider that writing M as
        (2m+1)(n+m) may result in n, the number of men in the
        column with fewest men, being negative.
        
        My initial thoughts on this problem were similar to
        .13's.  With two columns you have n men in the first
        column and n+1 men in the second, for a total of 2n+1
        men.  Since any odd M in the given range (between 1000
        and 1990) can be expressed this way, none of the possible
        answers is odd.  Note that this includes ruling out any
        prime M as a possible answer.
        
        Now consider k columns with n being the number of men in
        the column with fewest men.  k >= 2, n >= 1.  There are two
        cases, k even k=2m and k odd k=2m+1 (either way m >= 1).
        
        The first case gives a total of M = kn + k(k-1)/2 = 2mn +
        2m(2m-1)/2 = 2mn + m(2m-1) = m(2n + 2m - 1).  Since n and
        m are both >= 1, 2n + 2m - 1 is >= 3 and is odd.  So this
        case cannot rule out M = 1024.  If m is odd, then M is a
        product of two odd numbers and is odd, so no even numbers
        get ruled out.  For this case to rule out even M requires
        that 2 divides m exactly as many times as it divides M. 
        So for example if M = 512 * 3, then the try m = 512
        yields 3 = 2n + 1024 - 1 yields a very negative value for
        n.  So there are other even numbers besides 1024 that
        this case doesn't rule out.
        
        The second case is considered in .13 and gives M = kn +
        k(k-1)/2 = (2m+1)n + (2m+1)(2m+1-1)/2 = (2m+1)n + (2m+1)m
        = (2m+1)(n+m).  Again, as m >= 1 this contains an odd
        factor >= 3, and so this case cannot rule out 1024,
        either.  This M=1024 is definitely one of the possible
        solutions (the problems as stated allow more than one
        solution).  The example M = 512 * 3 from the previous
        paragraph now falls to m = 1 and n+m = 512 which yields
        columns 511,512,513.  Does this case rule out all
        remaining M (even but not a power of two)?  Consider M =
        67 * 32.  If 2m+1 = 67 them m = 33, and n+m=32 requires n
        = -1 which is not a valid solution!  Fortunately this M
        is outside the range 1000 to 1990. I think 79 * 16 is
        another example like this, but though it is in the range
        it is ruled out by the previous case with k = 2m = 32
        columns. But "close" examples like this make me hesitate
        before saying that this case rules out all M containing
        an odd factor >= 3 ... there is no guarantee that n =
        M/(2m+1) - m is going to be positive.  But anyway this
        case will rule out most such M.  Since all even numbers
        have already been ruled out, this leaves 1024 as a
        definite solution and maybe a few special cases of even
        numbers with odd prime factors as possible solutions.
        
        So group the even numbers between 1000 and 1990 by how
        many factors of two they have.  Let t be the highest
        power of two that divides M.  Consider the possible
        cases:
        
        t=2:  Use case 1, M = m(2n + 2m - 1), with m = t = 2.
        The second factor, 2n + 2m - 1 = 2n + 3 is between 500
        and 995 and so yields a positive n.  So these numbers are
        ruled out.
        
        t=4:  Same as t=2, except now 2n + 7 is between 250 and
        497 1/2 and so n is positive.
        
        t=8:  Same as t=2, except now 2n + 15 is between 125 and
        248 3/4 and so n is positive.
        
        t=16:  Same as n=2, except now 2n + 31 is between 62 1/2
        and 124 3/8 and so n is positive.
        
        t=32:  Will this work?  Using case 1 with M = m(2n + 2m -1)
        with m = t = 32 yields an odd factor of 2n + 63 which is
        between 1000/32 = 31 1/4 and 1990/32 = 62 3/16.  All n
        obtained this way will be negative, and so we must turn
        to the second case (odd number of columns) to rule out
        multiples_of_32_but_not_64.  So let M = 32w where w is
        odd and between 31 1/4 and 62 3/16.  Try k = w = 2m+1
        columns yielding M = (2m+1)(n+m).  Since 33 <= w <= 61
        and w = 2m+1, then 16 <= m <= 30.  Since n+m here is 32,
        the required n is positive in all such cases.
        
        t=64:  The case 1 approach requires an odd factor 2n + 127
        between 15 5/8 and 31 3/32 which results in negative n. 
        So let M = 64w with w odd, and try w = 2m+1 columns (case
        2).  Then M = 64w = 64(2m+1) = (n+m)(2m+1) yields n+m=64,
        with m bounded so that 17 <= 2m+1 <= 31.  All such w will
        result in positive m.
        
        I suppose the cases for t = 128, 256, and 512 will work
        out the same way, i.e., there is a configuration with an
        odd number of columns that rules it out.  The closest
        miss came with t=32 where the bound 2m+1 <= 1990/32
        restricted 2m+1 to be <= 61, thus yielding a "barely" positive
        solution for n in n+m=32.  I think 65 * 32 has a solution
        as 65 has smaller odd factors, but 67 * 32 may not have
        one.
        
        Okay, so the only answer for problem (1) is that he has
        1024 men.
        
        Dan

re .14

Let me take the points one at a time.

>       ... For one thing, it
>        doesn't consider the case of an even number of columns

    There is no point in considering an even number of columns.
    n + (n+1) + ... + (n + 2m-1) = m(2m + 2n - 1) and this doesn't
    do anything for me.

>       and whether that can rule 1024 out as a possible answer.

    We are told in the question that there is at least one value of M
    such that it cannot be expressed as n + (n+1) + (n+2) ... . I have
    shown that every other number in the range 1000 -> 1990 can be
    expressed in that form. Therefore I do not need to waste time showing
    that 1024 can be expressed in that form. Read the question, please!

>       Secondly, it doesn't consider that writing M as
>       (2m+1)(n+m) may result in n, the number of men in the
>       column with fewest men, being negative.

    This is wrong. We choose the value of n according to our candidate M.

    The whole point of considering an odd number of columns is that they sum to
    a number which factors into an odd number - (2m+1) - and a number which
    can, if we want, be as small as half that odd number - (n+m) (we may choose
    n to be 0 - in which case we have an even number of columns!). Then

	All primes other than 2 are odd. 
	43 < 1990^� < 47 - so we only have to consider primes <= 43.
	22 x 43 = 946 < 1000 (Remember we are only interested in the range
	1000 -> 1990 !)

	Therefore for any M in the range 1000 -> 1990 if it is divisible by
	43 we can find a value of n >=0 such that 43(n+22) = M. Hence
	M cannot be the answer we are looking for. If you are really bored
	you might like to reproduce the same argument for all the odd primes 
	less than 43. It then follows that M does not have any odd prime as
	one of its factors. Therefore it must be a power of 2. QED.


>       For this case to rule out even M requires
>       that 2 divides m exactly as many times as it divides M. 
>       So for example if M = 512 * 3, then the try m = 512
>       yields 3 = 2n + 1024 - 1 yields a very negative value for
>       n.  So there are other even numbers besides 1024 that
>       this case doesn't rule out.
        
    No! No! No! You completely missed the point!
    512 * 3 = (2*1 + 1)(511 + 1) ie. m = 1, n = 511.
    Therefore 512 * 3 = 511 + 512 + 513.

    Brian

	re .15

	Reply .15 doesn't seem to be accounting for numbers that have one
	odd prime factor larger than 43, e.g., 16 * 79 = 1264.

	Dan

    Thanks, Dan. I'll hve another look.
    
    Brian

    As Dan's counterexample in .16 demonstrates the 'proof' in .13 doesn't
    work for candidate M's of the form p*2^i when p is a prime > 43. The key
    is to consider the even numbered series (again as suggested by Dan, this
    time in .14!).

    We then get n + (n+1) + ... + (n+2m-1) = m(2m + 2n - 1).
 
    This is the product of a number m, which we shall choose to have values 
    2, 4, 8, 16, and an odd number (2m + 2n - 1) which we shall choose
    to be the appropriate primes > 43. 

    We only need to consider values of m up to 16 since although 32 * 61 = 1952
    is in the target range 1900 -> 1990 that can be expressed in the form 
    (2m+1)(n+m) - ie. (2.30 + 1)(2 + 30) as so is the sum of the odd series
    2 + 3 + ... + 62. Clearly so can the other numbers of the form 32*p where 
    p > 43.

    So to summarise -

    Odd M are ruled out since then M = 2n+1 = n + (n+1).
    If M has an odd prime factor p <= 43 then M can be written as (2m+1)(n+m)
    which = n + (n+1) + ... + (n+2m). This form also works for M = p*2^i for
    odd prime p and i >= 5.
    If M = p*2^i where i < 5 then M can be written as m(2m + 2n - 1) which
    = n + (n+1) + ... + (n+2m-1).
    The only candidate M left is 1024. This cannot be expressed as a sum of
    integers whose consecutive difference is 1 since the sum of an odd number
    of such terms is (2m+1)(n+m) which is divisble by an odd number, and
    the sum of an even number of such terms is m(2m+2n-1) which again is
    divisible by an odd number.

    Brian

> 5.	Find the smallest square number which, when written in base 10 is of
> the form aaa....aaa.   ie, the same digit occurs in the first three and the
> last three places of the square, with some unspecified number of digits
> in between.   [No electronic help.]

I don't see any elegant way to crack this one, just working from both ends
towards the middle:

- Working from the low end: the only value for a is 4, since that is the
  only allowable repeated low digit of a square. Furthermore, its square root
  must end in either 12, 38, 62, or 88 (proof by squaring the numbers 1 through
  25 and noting that (50-x)^2 and (50+x)^2 end in the same two digits as x^2).
  From this you can try some more cases and notice that any number whose
  square ends in 444 must end in either 038, 462, 538, or 962.

- Working from the top end, the square root of the number in question must lie
  between the square root of 44400... and 44499...; there are two cases,
  depending on whether the number of digits is even or odd:

  - For an odd number of digits, the square root must be of the form
    2107..., 2108..., or 2109...

  - For an even number of digits, the square root must be of the form
    6663..., 6664..., 6665..., 6666..., 6667..., 6668..., 6669..., or 6670...

Putting this together, the list of candidates to try becomes (in numeric order):

210962, 666462, 666538, 666962, 667038, 2107038, 2107462, ...

And we hit the answer on the second try: 666462^2 = 444171597444

(OK, I admit it, I cheated and used a calculator for those final tries...)

	Answer to Puzzle #6 follows form feed:


	There are two answers:

					Answer #1	Answer #2

			Frame A:	1432211		1522121

			Frame B:	1432211		1521311

			Frame C:	1432211		1441121


	A few minutes of examination reveals the characteristics of
	possible correct answers; after that, generating a list of
	the possibles and eliminating those that don't work took a
	half hour.

	dave