| I haven't looked at the geometry questions. For the others, 3 is
"book" graph theory and 6 solves itself elegantly. 2 & 5 are simple in
concept, but seemed to take a lot of space to write out.
-------------------------------------------------------------------------------
Question 2.
For p=2, C(2p,p)-2 evaluates to 4. 2^2|4.
(contrary to the indirect implication of the "extra question part 1")
For p=3, C(2p,p)-2 evaluates to 18. 3^2|18.
So let's suppose that p is (odd) >= 5.
C(2p,p)-2
= 2p!/(p!p!) - 2
= 2p(2p-1)...(p+1)/p! - 2
= 2[(2p-1)(2p-2)...(p+2)(p+1) - (p-1)(p-2)...2.1]/(p-1)!
Since p is prime, it remains to show that p^3 divides the element is
square brackets.
(2p-1)(2p-2)...(p+2)(p+1) - (p-1)(p-2)...2.1
= prod(i=1...p-1) (p+i) - prod(i=1...p-1) i
Expanding:
= p^0.0
+ p^1.(p-1)! sum(i=1...p-1) 1/i
+ p^2.(p-1)! sum(i=1...p-1)sum(1=<j<i) 1/(ij)
+ p^3.k (Equation *)
First consider the coefficient of p^1.(p-1)! in (*):
sum(i=1...p-1) 1/i
= sum(i=1...(p-1)/2) p/[i(p-i)]
= p.sum(i=1...(p-1)/2) 1/[i(p-i)]
The integers mod p form a group, with respect to which:
1/[i(p-i)] == -1/i� == -j� for some j(i). Indeed, as i moves from i to
(p-1)/2, j� will cover all the (p-1)/2 different quadratic residues mod p,
since i� = (p-i)�. Therefore:
p^2.sum(i=1...(p-1)/2) 1/[i(p-i)]
== p^2.sum(j=1...(p-1)/2) j� (mod p�)
sum(i...p-1) i� = p(p-1)(2p-1)/6 == 0 mod p (since p <> 2,3)
But that is counting each quadratic residue twice. Each occurs just
once in sum(j=1...(p-1)/20 j� since j� = (p-j)�. So p | sum(j=1...(p-1)/2) j�.
p^3 | p^1.(p-1)! sum(i=1...p-1) 1/i
Now, look at the coefficient of p^2.(p-1)! in the expansion (*) above.
sum(i=1...p-1)sum(1=<j<i) 1/(ij)
Once again, since the residues mod p are a group, so as i,j vary from
1 to p-1, then 1/ij == kl mod p, where k,l will vary from 1 to p-1.
sum(k=1...p-1)sum(1=<l<k) kl
= [sum(k=1...p-1) k]^2 - [sum(k=1...(p-1) k^2]
= [�p(p-1)]^2 - p(p-1)(2p-1)/6
== 0 mod p.
Hence p^3 | p^2.(p-1)! sum(i=1...p-1)sum(1=<j<i) 1/(ij)
Hence p^3 | C(2p,p) - 2
--------------------------------------------------------------------------------
Question 3.
Define a simple graph G on 20 vertices (cities) where an edge
links two vertices iff a Red Flight links the two corresponding cities.
(lack of an edge then means that a Green Flight links the two relevant cities.)
Fact (ii) simply tells us that G is disconnected. So let's divide
the vertices of G into two sets H and H', neither empty, such that no edge
links H to H'. (We do not need to assume anything about the connectedness
of H or of H'.) Then, given any vertex h in H and h' in H', there is no
edge between them, ie: a direct Green Flight exists. Given any vertices h
and h1 in H, any vertex h' in H' can be picked. No edge links h' to h or h1,
so h to h1 via h' is a two step flight on entirely Green Planes. Similarly
if h' and h1' are two vertices in H'.
--------------------------------------------------------------------------------
Question 5.
n,m are given integers > 1. m is even. f is a function from the
non-negative reals to the reals.
f( (x_1)^m + ... + (x_n)^m / n ) = (|f(x_1)|^m + ... |f(x_n)|^m ) / n
First, set x_1 = ... = x_n:
f((x_1)^m) = |f(x_1)|^m (*)
Since every non-negative real r satisfies r = (x_1)^m for some x_1,
f(r) >= 0 for all r.
In the special cases where x=0,1:
f(0) = |f(0)|^m => f(0) >= 0, & (|f(0)|^(m-1)-1).f(0) = 0.
So f(0)= 0 or 1. Similarly, f(1) = 0 or 1.
Now, if n is even, set x_1 = ... = x_(n/2) = (k-1)^1/m. Set x_(n/2+1)
= ... = x_n = (k+1)^1/m. Then:
f(k) = ( |f((k-1)^1/m)|^m + |f((k+1)^1/m)|^m ) / 2
By (*):
f(k) = ( f(k-1) + f(k+1) ) / 2
Alternatively, if n is odd, set x_1 = ... = x_(�(n-1)) = (k-1)^1/m.
Set x_(�(n-1)+1) = ... = x_(n-1) = (k+1)^1/m. Set x_n = k^1/m. Then:
f(k) = ( �(n-1)|f((k-1)^1/m)|^m + �(n-1)|f((k+1)^1/m)|^m + |f(k^1/m)|^m) / n
By (*):
f(k) = ( �(n-1)*f(k-1) + �(n-1)*f(k+1) + f(k) ) / n
=> f(k) = ( f(k-1) + f(k+1) ) / 2 as before.
From this equation, it's clear that f(k) k=0,1,2... is an arithmetic
progression. And we know all the possibilities for the first two terms:
(1) f(0) = 1, f(1) = 0 => f(2) = -1 not possible since f(r) >= 0 for all r.
(2) f(0) = 0, f(1) = 0 => f(n) = 0 for all integers n. Not possible since
in particular f(1988) = 0, contrary to information.
(3) f(0) = 0, f(1) = 1 => f(n) = n for all integers n. Not possible since
in particular f(1986) = 1986, contrary to information.
Hence (4) f(0) = 1, f(1) = 1 is the only possibility => f(n) = 1 for all
integers n, so in particular f(1987) = 1.
--------------------------------------------------------------------------------
Question 6.
For n = 1, equality holds.
Prove the inequality by induction on n.
It remains to show that for all n > 1:
_/(n+1) - _/(n-1) > 1/(_/n)
start from: n� > n�-1
sqrt it: n > _/(n+1)_/(n-1)
*2 + 2n: 4n > n+1 + n-1 + 2_/(n+1)_/(n-1)
sqrt it again: 2_/n > _/(n+1) + _/(n-1)
divide by _/n * (_/(n+1) + _/(n-1)):
_/(n+1) - _/(n-1) > 1/(_/n)
there it is.
|
| Question 4.
Draw one diagram with A,B,C,O on it, draw another with A,B,C,P on it.
Let ABO = a, CBO = a', BCO = b, ACO = b', CAO = c, BAO = c', BAP = d,
CAP = d'. To prove: that c = d.
The sin rule applied 3 times for A,B,C,O tells us:
OA/sin(b') = OC/sin(c)
OC/sin(a') = OB/sin(b)
OB/sin(c') = OA/sin(a)
=> sin(a)sin(b)sin(c) = sin(a')sin(b')sin(c')
Similarly for A,B,C,P:
sin(a)sin(b)sin(d) = sin(a')sin(b')sin(d')
Now CAB = x, say, and c+c' = d+d' = x
So: sin(d)/sin(x-d) = sin(c)/sin(x-c)
differentiating the lhs of this wrt d, we get sin(x)/(sin(x-d))�.
This is positive since x < pi. So sin(d)/sin(x-d) is monotonically
increasing over the interval (0,x) and hence 1-1. So c=d.
|
| re .1
>Question 2.
> (contrary to the indirect implication of the "extra question part 1")
Mea culpa. The extra questions were of course not in the actual exam.
Proving that p� | C(2p,p)-2 is an economical way of avoiding having to
prove the actual question 2 or the extra question part 1 but there is
an 'elegant' proof (not due to me) that p� | C(2p,p)-2
It goes like this.
Consider a committee of p men and p women. They are to choose a
sub-committee of p people such that said sub-committee is not all of
one gender. Obviously C(2p,p)-2 is the number of ways of choosing the
sub-committee. Let this number be n and consider the different possible
sub-committees partitioned according to how many, say, men there are in
the sub-committee. Let the number of men be m.
Clearly n = sum(m=1,p-1) C(p,m)C(p,p-m)
But p | C(p,k) for 1<=k<=p-1
and both m and p-m satisfy the inequality for the given range of m
so p� | C(p,m)C(p,p-m) for each m summed over
so p� | n
QED
Did you give any consideration as to whether higher powers of p divide
C(2p,p)-2? I checked by hand up to p=17 without finding any. Perhaps someone
with access to a computer would like to gather more data and/or make a
conjecture and/or provide a proof.
>Question 6.
> start from: n� > n�-1
Alternately, start from 1/4n� > 0 and follow almost exactly the same
steps. Either way it looks like a rabbit out of a hat.
|
| >Question 1
>
>GKA is an isosceles triangle with base GK of length 2b. GA and AK each have
>length a. Let C be the midpoint of AK and z the circumcircle of the triangle
>GCK. Let Y be the point on the extension of AK such that if E is the inter-
>section of YG with z then EY is of length a/2.
>
>Prove that if x is the length of EC and y is the length of KY then ay=x� and
>xb=y�.
GCKE is a cyclic quadrilateral.
Therefore, angle KGE = angle ECK.
Therefore, triangles KGY and ECY are similar, since they both share the same
angle EYK.
By comparing ratios of the sides of these two triangles, we learn:
ab = xy
|GY| = 2y�/a + y
Now apply the cosine rule, for angle EYK, to the two triangles GYA and ECY.
This gives us two expressions for cos(EYK), which we equate. This simplifies
to x� = ay. Since ab = xy, bx = y�.
Re: Question 2. I like the approach for p�. I don't think the arity of p
as a divisor of C(2p,p) increases with p. p=2,3 fail "because" the sum of
1+2�+3�+...(p-1)� = p(p+1)(2p-1)/6 has 6 as the denominator. The algebraic
complexity does not increase as p does.
Andrew.
|