Conference rusure::math

>1. Let the number of different divisors of the integer n be N(n) e.g. 24 has
>   the divisors 1,2,3,4,6,8,12 and 24, so N(24) = 8. Determine whether the sum
>
>   N(1) + N(2) + ... + N(1989) is odd or even.

I think we've seen this one in this conference before. Anyhow, in general 
the divisors of N appear in pairs, e.g. {d, N/d}, unless N is a square when 
d=n^.5 is unique. So N(n) is even unless n is square, and there are 44 
squares in [1..1989], so sum(N(n), n=1..1989) is even.

>3. The numbers u[1], u[2], u[3], . . . satisfy the conditions
>
>	u[1] = 1, and
>
>	u[n] = 1/(u[1] + . . . + u[n-1]) for all integers n > 1
>
>   Prove that there exists a positive integer N such that
>
>   u[1] + u[2] + . . .  + u[N] > 1989

Each term of u equals or exceeds the corresponding term of the harmonic
series (1/n), and the sum of that series diverges (however slowly), so this
one also diverges. 

>> 7. Let f(n) be defined for positive integers n. It is known that
>>
>>   (i)  f(f(n)) = 4n + 9 for each positive integer n, and
>>   (ii) f(2^k) = 2^(k+1) + 3 for each non-negative integer k.
>>
>>   Determine f(1789).
>>
>>   {Extra question: Determine f(1989).}

	By (ii), f(2^k) = 2^(k+1) + 3 = 2(2^k) + 3, which suggests
	trying f(n) = 2n + 3.  Plugging that into (i) one finds that
	2(2n + 3) + 3 = 4n + 9, so that f(n) = 2n + 3 satisfies both
	(i) and (ii).  That doesn't rule out the possibility of other
	functions satifying (i) and (ii), but it strongly suggests
	that if there is a unique answer will be f(1789) = 2*1789 + 3 = 3581
	(and f(1989) = 2*1989 + 3 = 3981 for the extra question).

	If you work backwards, 1789 = 4n + 9 implies n = 445.  Then
	445 = 4n + 9 implies n = 109; 109 = 4n + 9 implies n = 25;
	25 = 4n + 9 implies n = 4.  4 is of the form 2^k so we can
	work forwards from it.  The property of f used is shown
        at the left.

		(ii) f(4) = f(2^2) = 2^(2+1) + 3 = 2^3 + 3 = 8 + 3 = 11
		(i)  f(11) = f(f(4)) = 4*4 + 9 = 25
		(i)  f(25) = f(f(11)) = 4*11 + 9 = 53
		(i)  f(53) = f(f(25)) = 4*25 + 9 = 109
		(i)  f(109) = f(f(53)) = 4*53 + 9 = 221
		(i)  f(221) = f(f(109)) = 4*109 + 9 = 445
		(i)  f(445) = f(f(221)) = 4*221 + 9 = 893
		(i)  f(893) = f(f(445)) = 4*445+9 = 1789
		(i)  f(1789) = f(f(893)) = 4*893 + 9 = 3581 (as suspected)

	So by using only (i) and (ii) [i.e., without assuming f(n) = 2n + 3]
	one can derive that f(1789) =  3581.

	Now for the extra question: 1989 = 4*495 + 9; 495 = 486 + 9
	= 4*(121 1/2) + 9.  Aha, the process will not continue
        this time.  If you use (i) then f(f(495)) = 4*495 + 9 = 1989.
        Then by (i) again f(1989) = f(f(f(495))) = 4*f(495) + 9.
        So if f(495) is specified then f(1989) = 4*f(495) + 9.  But
        for any positive integer m you can find an f satisfying
        (i) and (ii) such that f(495) = m, in which case f(1989) = 4m + 9.
        
        Dan

        re .2 (problem 3)
        
        u[1] + u[2] + . . .  + u[N] grows a lot faster than the
        harmonic series.
        
        Let s[n] = u[1] + u[2] + . . .  + u[n].
        
        Then s[1] = 1 and for all integers n > 1
        
        	s[n]	= u[1] + u[2] + . . .  + u[n]
        		= (u[1] + u[2] + . . . + u[n-1]) + u[n]
        		= s[n-1] + 1/(u[1] + . . . + u[n-1])
        		= s[n-1] + 1/(s[n-1])
        
                 2         2                 2
        Then s[n]  = s[n-1]  + 2 + 1/(s[n-1])  and telescoping
        this (i.e. rewriting s[n-1]^2 in the same way, then
        rewriting s[n-2]^2 in the same way, etc.) gives
        
                    2       2                    2                     2
        	s[n]  = s[1]  + 2(n-1) + 1/(s[1])  + . . . + 1/(s[n-1])
        
        or
                    2
        	s[n]  > 1 + 2(n-1)
        
        So s[n] = u[1] + u[2] + . . .  + u[n] > sqrt(2n-1) for
        all integers n > 1, and so exceeds 1989 much earlier than
        the harmonic series does.
        
        Dan

>> 5. Let n be a non-negative integer, d[0],d[1],d[2],...,d[n] be each either
>>
>>                                                     k                 n
>>    equal to 0, 1 or 2  and d[0] + 3*d[1] + . . . + 3 *d[k] + . . . + 3 *d[n] be
>>    the square of a positive integer. Prove that d[i] = 1 for at least one i,
>>    where 0 <= i <= n.
        
        This just states that all square positive integers have
        at least one "1" digit in their base three representation.
        That's obvious.  Let the number be m^2 for some positive
        integer m.  Write m as (3^r)s for nonnegative integer r
        and positive integer s not divisible by 3.  Then either
        s == 1 mod 3 or s == 2 mod 3, but in either case
        s^2 == 1 mod 3.  Then m^2 = (3^(2r))(s^2) has a "1" in its
        base three representation, just to the left of a string
        of 2r trailing zeroes.
        
        Dan
        

    RE .(so far)
    
    
    
re .1

CIVAGE::LYNN  -< 1 is easy >-

Yes, Question 1 must be the one they put in so nobody goes home empty handed.

>I think we've seen this one in this conference before.

I think you're right but I couldn't find it.



re .2
CIVAGE::LYNN  -< superharmonic >-

>Each term of u equals or exceeds the corresponding term of the harmonic
>series (1/n)

Question 3:

You may be right but this isn't intuitively obvious to me. Can you supply a
proof?

In particular if u[n] is too much bigger than 1/n then sum u[n] will grow too
quickly and u[n+1] will therefore shrink too quickly and drop below 1/(n+1).



re .3
GUESS::DERAMO  -< problem 7 >-

>	So by using only (i) and (ii) [i.e., without assuming f(n) = 2n + 3]
>	one can derive that f(1789) =  3581.

Yep.

It is possible to show by induction that f(n) is indeed 2n+3 for n for which f
is defined.

>	Now for the extra question: 1989 = 4*495 + 9; 495 = 486 + 9
>	= 4*(121 1/2) + 9.  Aha, the process will not continue
>	this time.  If you use (i) then f(f(495)) = 4*495 + 9 = 1989.
>	Then by (i) again f(1989) = f(f(f(495))) = 4*f(495) + 9.
>	So if f(495) is specified then f(1989) = 4*f(495) + 9.  But
>	for any positive integer m you can find an f satisfying
>	(i) and (ii) such that f(495) = m, in which case f(1989) = 4m + 9.

I put in the extra question in case anyone was too quick to assume that f(n) =
2n + 3 for all n. Given the information about f, f(1989) is undefined. [This is
obvious because if it had been defined, the question would have asked for
f(1989) instead of f(1789). :-)]

Is there some property of n that immediately allows one to conclude that n can
never be reached?



re .4
GUESS::DERAMO  -< on the growth rate of the sum in problem 3 (reply 2) >-

A clever derivation.

Here is my proof for problem 3 which is quite elementary.

Proof by reduction ad absurdum.

Suppose the proposition is false i.e. u[1] + . . . + u[n] <= 1989 for all n

Therefore u[n+1] >= 1/1989 for all n >= 1 (by definition of u[n])
{This assumes u[n] is always positive but this is obvious.}

also u[1] = 1 (given) >= 1/1989

so u[n] >= 1/1989 for all n

so let N = 1989�+1

u[1] + . . . + u[N] >= (1989�+1)/1989 = 1989 + 1/1989 > 1989

thus establishing a contradiction and proving the result.

{which also shows that sum u[n] diverges since 1989 was arbitrary}

{Most people seem to have realised that sum u[n] diverges but the question could
 have been sneaky and found a convergent series whose limit happened to exceed
 1989.}



re .5
GUESS::DERAMO  -< problem 5 >-

Clever again!

My proof showed that if the proposition is false then d[i] = 0 for all i, thus
the expression is 0, contradicting the information given that it is the square
of a _positive_ integer.

The key observation though is that a square is always either 0 or 1 (never 2)
modulo 3.


I have to admit that I have not succeeded in doing any of the three geometry
problems. I am heartened by the fact that everyone seems to have found the
non-geometry problems easier.

>7. Let f(n) be defined for positive integers n. It is known that
>
>   (i)  f(f(n)) = 4n + 9 for each positive integer n, and
>   (ii) f(2^k) = 2^(k+1) + 3 for each non-negative integer k.
>
>   Determine f(1789).
>
>   {Extra question: Determine f(1989).}

.3>	   But for any positive integer m you can find an f satisfying
.3>        (i) and (ii) such that f(495) = m, in which case f(1989) = 4m + 9.
.3>        
.3>        Dan

	I disagree with Dan at the end, here.

	f(n) = 2n+3 certainly satisfies the rules, so if f is well-defined,
then we have the answer.   But how to show that f is well-defined?

	Let g = f.f.   Each number which is 
		(i) not == 1 mod 4
	or	(ii) 1 or 5 or 9

is the root of a infinite chain x,g(x),g(g(x)),... which we will label <x>.
Each positive integer x appears in exactly one chain <y>.   The question
now is to pair the chains off with one another, using a non-symmetric
relation, R, so that <x>R<y> iff f(x)=y, f(y) = g(x), f(g(x)) = g(y), etc.

	The only constraint that we have to tell us how to do this is 
that <2^k> R <2^(k+1)+3>.   That takes care of a few of the chains, but all
the rest, ie those which are:
		(iii) either 9 or not == 1 mod 4
	and	(iv) not a power of 2
	and	(v) not 3 more than a power of 2
lead chains which could have any other chain for partner.

	We can only assume that 1789 and 1989 happen to lie in chains whose
root is either a power of 2 or 3 more than a power of 2.   Taking each
in turn, and repeatedly taking the function g^(-1):

1789 -> 445 -> 109 -> 25 -> 4
1989 -> 495 -> ???.   495 is a root, whose partner is undefined.

f(1989) = g(x) or g(g(x)), where x is anything satisfying (iii),(iv),(v) above
and also:
		(vi) not equal to 495.

That's still quite a lot of candidates, still...

Regards,
Andrew

        re .7,
        
@ .3>	     But for any positive integer m you can find an f satisfying
@ .3>        (i) and (ii) such that f(495) = m, in which case f(1989) = 4m + 9.
@ .3>        
@ .3>        Dan
@
@	I disagree with Dan at the end, here.
        
        Are you saying that I didn't show enough of my work to
        make this claim, or that there is a positive integer m
        such that it is impossible for f(495) = m for any f
        satisfying (i) and (ii)?
        
        Dan

	there is a positive integer m
        such that it is impossible for f(495) = m for any f
        satisfying (i) and (ii)?
        
	For instance, 495 itself is such an m.   I list the criteria that
m must satisfy for such an f to exist in -.2.

Cheers,
Andrew

        Oops.
        
        Dan

I have searched in vain for an elegant solution to this problem so, for
completeness, here is the straightforward solution.

>Problem:
>
>4. Let n be even. Four different numbers a, b, c, d are chosen from the
>   integers 1,2,...,n in such a way that a + c = b + d.
>
>   Show that the number of such selections is n(n-2)(2n-5)/24.

Solution:

Since n is even, let n = 2k.

Define s = a+c. Clearly 2<=s<=2n. As noted by me in .0, four distinct numbers
can be paired to have the required property in at most one way. So we may
safely find the number of selections for a given s and then sum over all s
without being concerned about double counting selections.

We consider the cases s is odd and s is even separately.

s is ODD
========

Because n is even and s is odd, s <> n and thus we can consider two cases for
s viz. s < n and s > n.

s < n
-----

First we try to choose {a,c}. It is clear that the possible values are
{1,s-1}, {2,s-2}, ..., {(s-1)/2,(s+1)/2}. Thus there are (s-1)/2 choices for
{a,c}. Each choice for {a,c} is also valid for {b,d} except that {a,c} must not
equal {b,d}. This gives one less choice for {b,d} i.e. ((s-1)/2 - 1) = (s-3)/2.
However each {a,b,c,d} is being counted twice, because {a,c} and {b,d} could be
exchanged, and this needs to be accounted for.

The number of selections is therefore

  (s-1)   (s-3)
� ----- � -----
    2       2

The applicable values of s are the odd ones in 3..n-1.

s > n
-----

First we try to choose {a,c}. It is clear that the possible values are
{n,s-n}, {n-1,s-n+1}, ..., {(s+1)/2,(s-1)/2}. Thus there are n-(s-1)/2 choices
for {a,c} and the same reasoning as above applies to choosing {b,d}.

The number of selections is therefore

        (s-1)           (s-1)
� [ n - ----- ] � [ n - ----- - 1 ]
          2               2

The applicable values of s are the odd ones in n+1..2n-1.

Now for each s > n+1, this expression is equal to the previous expression when
s is replaced by (2n+2)-s i.e. there is symmetry about s = n+1 which is a
special case. Evaluating it separately yields �k(k-1).

The total contribution for all odd s is thus

�k(k-1) + Sum(odd s=3,..,n-1) (s-1)/2 � (s-3)/2

Since only odd s are summed over, we replace s by 2t+1 whence t ranges from 1
to k-1 and using the following substitutions, (s-1)/2 = t and (s-3)/2 = t-1, we
get 

�k(k-1) + Sum(t=1,k-1) t(t-1)

= �k(k-1) + Sum(t=1,k-1) t� - Sum(t=1,k-1) t

Using well known formul� for these sums we get

�k(k-1) + (k-1)(k)(2k-1)/6 - (k-1)(k)/2

= k(k-1)(2k-1)/6

= n(n-1)(n-2)/24

s is EVEN
=========

We proceed analogously.

s <= n
------

First we try to choose {a,c}. It is clear that the possible values are
{1,s-1}, {2,s-2}, ..., {(s-2)/2,(s+2)/2}. Thus there are (s-2)/2 choices for
{a,c}. This is one less than when s is odd because the solution a=c=s/2 is
disallowed. Each choice for {a,c} is also valid for {b,d} except that {a,c}
must not equal {b,d}. This gives one less choice for {b,d} i.e. ((s-2)/2 - 1) =
(s-4)/2. However each {a,b,c,d} is being counted twice, because {a,c} and {b,d}
could be exchanged, and this needs to be accounted for.

The number of selections is therefore

  (s-2)   (s-4)
� ----- � -----
    2       2

The applicable values of s are the even ones in 2..n.

s > n
-----

First we try to choose {a,c}. It is clear that the possible values are
{n,s-n}, {n-1,s-n+1}, ..., {(s+2)/2,(s-2)/2}. Thus there are n-s/2 choices
for {a,c} and the same reasoning as above applies to choosing {b,d}.

The number of selections is

        s           s
� [ n - - ] � [ n - - - 1 ]
        2           2

The applicable values of s are the even ones in n+2..2n.

Now for each s > n, this expression is equal to the previous expression when
s is replaced by (2n+2)-s i.e. there is symmetry about s = n+1 (which not being
a possible value of s need not be accounted for separately).

The total contribution for all even s is thus

Sum(even s=2,..,n) (s-2)/2 � (s-4)/2

Since only even s are summed over, we replace s by 2t whence t ranges from 1
to k and using the following substitutions, (s-2)/2 = t-1 and (s-4)/2 = t-2, we
get 

Sum(t=1,k) (t-1)(t-2)

= Sum(t=1,k) t� - 3 � Sum(t=1,k) t + 2k

Using well known formul� for these sums we get

k(k+1)(2k+1)/6 - 3k(k+1)/2 + 2k

= k/6 � [ (k+1)(2k+1) - 9(k+1) + 12 ]

= k/6 � [ 2k�+3k+1 -9k-9 + 12 ]

= k/6 � (2k�-6k+4)

= k/3 � (k�-3k+2)

= k(k-1)(k-2)/3

= n(n-2)(n-4)/24

All s
=====

Combining the results for odd and even s we get

n(n-1)(n-2)/24 + n(n-2)(n-4)/24

= n(n-2)/24 � [ (n-1) + (n-4) ]

= n(n-2)(2n-5)/24  as required.

    Here's a slightly better approach for Problem 4. It looks a lot shorter but
    that's because I've just outlined the solution.


Define even(n) with domain even integers >= 4 and equal to the number of
selections as required by the problem.

Define odd(n) with domain odd integers >= 5 and equal to the number of
selections for odd n (not required by the problem but we get it too without
much extra work).


With careful counting it can be shown that

odd(n+1)  = even(n) + 2 sigma(j=1,(n-2)/2) j
even(n+1) = odd(n)  + (2 sigma(j=1,(n-1)/2) j) - (n-1)/2

and evaluating the sigmas gives

(A) odd(n+1)  = even(n) + n(n-2)/4
(B) even(n+1) = odd(n)  + (n-1)�/4

    
Eliminating odd() we get

even(n+2)-even(n) = �n� - �n

Clearly even(4) = 1 so we can solve the recurrence.

Experience suggests (proof by race memory) trying even(n) = an� + bn� + cn + d
and solving gives a=1/12, b=-3/8, c=5/12, d=0

so even(n) = (2n�-9n�+10n)/24 = n(n-2)(2n-5)/24        as required.

    
Now substituting for even() in (B) gives

odd(n) = (n-1)(2n�-7n+3)/24 = (n-1)(n-3)(2n-1)/24

    
Easy exercise for the reader: Verify that odd(n) and even(n) are always
integers for odd and even n respectively.

It is interesting to compare even(n) and odd(n) even though they have disjoint
domains. Temporarily ignoring this we find that

even(n) - odd(n) = 3/24     for all n.

(I'ld include a Postscript diagram but my postscript isn't up to it.)

Extend AH to meet BC (BC produced if necessary) in H'

Angle BHA = 90� by definition

Angle BHH' = 180� - Angle BHA (angles on a line) so
Angle BHH' = 90�

Triangle ABH is congruent to Triangle H'BH by ASA because
    Angle ABH = Angle H'BH (since BH is bisector)
    Side BH is common
    Angle BHA = Angle BHH' = 90�

 .
. . HA = HH' (corresponding sides of congruent triangles)


Similarly,

Extend AK to meet BC (BC produced if necessary) in K'

Angle CKA = 90� by definition

Angle CKK' = 180� - Angle CKA (angles on a line) so
Angle CKK' = 90�

Triangle ACK is congruent to Triangle K'CK by ASA because
    Angle ACK = Angle K'CK (since CK is bisector)
    Side CK is common
    Angle CKA = Angle CKK' = 90�

 .
. . KA = KK' (corresponding sides of congruent triangles)


 .
. . Triangle HAK is similar to Triangle H'AK' by SAS because
    H'A = 2HA
    Angle HAK is common
    K'A = 2KA

 .
. . Angle AHK = Angle AH'K' (corresponding angles of similar triangles)

 .
. . KH || K'H' (can't remember what this is called)

and, since K' and H' both lie on BC,

KH || BC

Q.E.D.