[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1776.0. "1993 Canadian Mathematics Olympiad" by RUSURE::EDP (Always mount a scratch monkey.) Tue Jul 20 1993 17:53

    1.  Determine a triangle whose three sides and an altitude are four
    consecutive integers and for which this altitude partitions the
    triangle into two right triangles with integers sides.  Show that there
    is only one such triangle.
    
    2.  Show that the number x is rational if and only if three distinct
    terms that form a geometric progression can be chosen from the sequence
    x, x+1, x+2, x+3, ...
    
    3.  In triangle ABC, the medians to the sides AB and AC are
    perpendicular.  Prove that cot B + cot C >= 2/3.
    
    4.  A number of schools took part in a tennis tournament.  No two
    players from the same school played against each other.  Every two
    players from different schools played exactly one match against each
    other.  A match between two boys or between two girls was called a
    _single_ and that between a boy and a girl was called a _mixed single_. 
    The total number of boys different from the total number of girls by at
    most 1.  The total number of singles differed from the total number of
    mixed singles by at most 1.  At most how many schools were represented
    by an odd number of players?
    
    5.  Let y[1], y[2], y[3], ... be a sequence such that y[1] = 1 and
    which, for k>0, is defined by the relationship:
    
    	y[2k] = { 2y[k] if k is even, 2y[k]+1 if k is odd
    	y[2k+1] = [ 2y[k] if k is odd, 2y[k]+1 if k is even.
    
    Show that the sequence y[1], y[2], y[3], ... takes on every positive
    integer value exactly once.
T.RTitleUserPersonal
Name
DateLines
1776.1Solution to #1TROOA::RITCHEFrom the desk of Allen Ritche...Wed Jul 21 1993 03:2724
>    1.  Determine a triangle whose three sides and an altitude are four
>    consecutive integers and for which this altitude partitions the
>    triangle into two right triangles with integers sides.  Show that there
>    is only one such triangle.


I believe this problem is the easiest of the 5 to solve.

Let the sides of the triangle be x-1, x, with base x+1.
The altitude (which is consecutive) must be x-2.

The two smaller rt triangles then have bases of sqrt(2x-3) and 4*sqrt(x-1)
which must sum to (x+1).

Solving the radical equation yields only 2 roots x=2 or x=26.

Thus we have one real triangle (25, 26, 27) or a degenerate one (1, 2, 3)
that has no height which we will eliminate.

The smaller rt triangles are (7, 24, 25) and (20, 24, 26).

Q.E.D.


1776.2solution to #4UTRTSC::BUIJSThu Jul 22 1993 14:45106
problem 4 was't that difficult as well:

>    4.  A number of schools took part in a tennis tournament.  No two
>    players from the same school played against each other.  Every two
>    players from different schools played exactly one match against each
>    other.  A match between two boys or between two girls was called a
>    _single_ and that between a boy and a girl was called a _mixed single_.
>    The total number of boys different from the total number of girls by at
>    most 1.  The total number of singles differed from the total number of
>    mixed singles by at most 1.  At most how many schools were represented
>    by an odd number of players?


At most 3 schools are represented by an odd number of players
The number of schools with an odd number of players is either 0,1 or 3
The difference between the number of boys and the number of girls from a school 
with an odd number of players is 1.
For schools with an even number of players the number of boys is equal to the
number of girls.

Let n be the total number of schools,
g(i) the number of girls who are representing school i
b(i) the number of boys who are representing school i
c(i) the number of childeren who are representing school i, 
  c(i) = b(i) + g(i)

G = (S i:1<=i<=n: g(i)), the total number of participating girls
B = (S i:1<=i<=n: b(i)), the total number of participating boys

|G - B| <= 1, therefore (G - B)^2  = 0 or (G - B)^2  = 1

Now calculate the total number of singles and of mixed-singles

First calculate the number of singles between girls

a girl representing school j plays against all girls from all other schools so
she plays (S i:1<=i<j v j<i<=n: g(i)) = G - g(j) singles 

all girls representing school j together play g(j) * (G- g(j)) singles

so the total number of singles between girls is 
 (S j:1<=j<=n: g(j)*(G - g(j))/2 
= 
 ( G*(S j:1<=j<=n: g(j)) -  (S j:1<=j<=n: g(j)^2))/2   
= 
 ( G^2 - (S j:1<=j<=n: g(j)^2))/2

The total number of singles for both girls and boys is therefore
 ( G^2 - (S j:1<=j<=n: g(j)^2) + ( B^2 - (S j:1<=j<=n: b(j)^2))/2

Now calculate the number of mixed-singles
a girl from school j plays against all boys from all other schools so 
she plays (S i:1<=i<j v j<i<=n: b(i)) = B - b(j) mixed-singles.

a boy from school j plays againt all girls from all other schools so
he plays  (S i:1<=i<j v j<i<=n: g(i)) = G - g(j) mixed-singles.

all children from school j together play g(j)*(B - b(j)) + b(j)*(G - g(j))
mixed-singles 

so the total number of mixed-singles is
 (S j:1<=j<=n: g(j)*(B - b(j) + b(j)*(G - g(j)))/2
= 
 ( B*(S j:1<=j<=n: g(j)) + G*(S j:1<=j<=n: b(j) - 2*(S j:1<=j<=n: g(j)*b(j)))/2
=
 ( 2*B*G - 2*(S j:1<=j<=n: g(j)*b(j)))/2

the  difference between the number of mixed-singles and the singles is
 ( 2*B*G - 2*(S j:1<=j<=n: g(j)*b(j)))/2 
-
 ( G^2 - (S j:1<=j<=n: g(j)^2) + ( B^2 - (S j:1<=j<=n: b(j)^2))/2
=
 ((S j:1<=j<=n: (g(j) - b(j))^2) - (G - B)^2)/2

This number D is either 0,1 or -1, furthermore (G-B)^2 is 0 or 1
The formula can be written as: 
  (S j:1<=j<=n: (g(j) - b(j))^2) = 2 * D + (G - B)^2  
so 
  (S j:1<=j<=n: (g(j) - b(j))^2) = 0 when D = 0 and (G - B)^2 = 0
or
  (S j:1<=j<=n: (g(j) - b(j))^2) = 1 when D = 1 and (G - B)^2 = 0
or
  (S j:1<=j<=n: (g(j) - b(j))^2) = 3 when D = 1 and (G - B)^2 = 1

So, for all schools (g(j) - b(j))^2 = 0 or (g(j) - b(j))^2 = 1
so
 (g(j) - b(j))^2 = 0 => g(j) = b(j) => c(j) = 2*g(j) is even
 (g(j) - b(j))^2 = 1 => g(j) = b(j) + 1 v b(j) = g(j) + 1 =>
    c(j) = 2 * (min g(j),b(j)) + 1 is odd

Concluding:
 for all schools j : (g(j) - b(j))^2 = 0, therefore all schools are represented
 by an even number of children 
or 
 there is one school i, with (g(i) - b(i))^2 = 1,  
 all other schools are represented by an even number of children with the same
 number of girls as the number of boys                           
or 
 there are 3 schools i, with (g(i) - b(i))^2 = 1,
 in this case it's not possible all 3 schools have g(i) = b(i) + 1 
 or all 3 schools have b(i) = g(i) + 1 
 all other schools are represented by an even number of children with the same
 number of girls as the number of boys                           

Marjan van den Buijs
                                                    
1776.3#5WIBBIN::NOYCEIt's the memory interface, stupid!Thu Jul 22 1993 18:2226
    The sequence in problem 5 is "Gray code."
    
    As i takes on values 1..2^n-1, y[i] also takes on all
    the values in 1..2^n-1.
    
    To show that all the values are different:
    	1<=i & 1<=j & y[i]=y[j] ==> i=j
    use induction on
    	1<=i,j<2^n & y[i]=y[j] ==> i=j.
    Clearly true for n=1.
    For the induction step,
    y[i] = y[j] ==> y[floor(i/2)] = y[floor(j/2)]
    		==> floor(i/2) = floor(j/2) = k
    		==> y[i] = y[j] = 2*y[k] or
    		    y[i] = y[j] = 2*y[k]+1
    		==> i = j
    shows it's true for n+1.

    To show that it takes on all the values, it suffices to
    show that 1 <= i < 2^n  ==>  1 <= y[i] < 2^n.
    Prove by induction: It's true for n=1;
    Assuming it's true for n, then
    	   y[2*i]   <= 2*y[i]+1
    and	   y[2*i+1] <= 2*y[i]+1
    show it's true for n+1.

1776.4AUSSIE::GARSONnouveau pauvreFri Jul 23 1993 04:3134
1776.5...and the converseGEMGRP::NOYCEIt's the memory interface, stupid!Fri Jul 23 1993 15:1426
    Q2. RATIONAL=>GP  (it's easy, now that you showed me how!)
    
    Given x = p/q (p,q integers) form the sequence
    
    p/q,  p/q + p,  p/q + 2p + pq,  where the ratio is 1+q.
    
    (p/q)*(1+q) = p/q + p
                 (p/q + p) * (1+q) = p/q + p + p + pq.
    
    ===========================================================
    
    To find this, I set
    
    p/q + j     p/q + k
    -------  =  -------
      p/q	p/q + j
    
    and solved for k:
    
    (p/q + j)^2 = (p/q)^2 + (p/q)*k
    
    2j + (q/p)*j^2 = k
    
    Setting j=p yields an integer solution for k.
    
    
1776.6CorrectionRICKS::D_ELLISDavid EllisFri Jul 23 1993 18:3110
re: .1 

> The smaller rt triangles are (7, 24, 25) and (20, 24, 26).

Sorry, but (20, 24, 26) is not a right triangle. 

The method looks right, but the details came out wrong.

Correct answer:  (13, 14, 15) divided by altitude 12 into (5, 12, 13) and
(9, 12, 15) right triangles.
1776.7egg on faceTROOA::RITCHEFrom the desk of Allen Ritche...Fri Jul 23 1993 20:5521
RE: .6 and .1,

Thanks to Dave for pointing out the late-night error in .1.
I assumed incorrectly that the base was x+1.  And also didn't
verify correctly.

Below is the corrected solution given in .1

Let the sides of the triangle be x-1, x+1, with base x.
The altitude (which is consecutive) must be x-2.

The two smaller rt triangles then have bases of sqrt(2x-3) and sqrt(6x-3)
which must sum to x.

Solving the radical equation yields only 1 admissable root x=14.

Thus we have one triangle (13, 14, 15) altitude 12.

The smaller rt triangles are (5, 12, 13) and  (9, 12, 15) as per .6

Allen
1776.8AUSSIE::GARSONnouveau pauvreSat Jul 24 1993 06:0321
    re .5

    Your answer is of course correct but one thing bothers me. You have set
    i=0 without apparent justification except that the answer comes out.
    
    In fact more general solutions exist
    
    i = N
    j = i(1+Tq)+Tp
    k = j(1+Tq)+Tp
    
    N and T integers, N >= 0, T >= 1
    
    but this is still somewhat "rabbit out of a hat".
    
    It can be shown that if r, the ratio of the GP, is an integer then it
    must be of the form 1+Tq provided (p,q)=1. Knowing the form of r it is
    easy to generate the above solutions.
    
    All that remains is to investigate the possibilities for r not being an
    integer.
1776.9HERON::BUCHANANThe was not found.Mon Aug 16 1993 12:1225