| Q2. On a circle are a set E of 2n-1 points (n an integer >=3). If
exactly k of these points are coloured black, the colouration is said to be
"good" if there exist at least one pair of black points such that an *open*
arc [ie excluding the endpoints] contains exactly n points of E.
What is the smallest value of k for which every colouration in black of
exactly k points of E is good?
--------------------------------------------------------------------------------
A2. Define a graph G, for which the vertex set is E, by stating that uv
is an edge in G iff an open arc linking u & v in the original circle contains
exactly n points.
G must be regular of degree 2. No point is linked to itself, or
twice to another, so G consists of a number of disjoint cycles. What is
the size of those cycles?
Starting from a point u, the length of a cycle is the minimum t
such that 2n-1 | t(n+1). gcd(2n-1,n+1) = gcd(-3,n+1)
= 1 if n <> 2 mod 3 (=> t = 2n-1)
= 3 if n == 2 mod 3 (=> t = (2n-1)/3)
So, if n <> 2 mod 3, G consists of 1 odd cycle of 2n-1 elements.
Painting n of them black is necessary and sufficient to ensure that one edge
is incident to 2 black vertices.
If n == 2 mod 3, G consists of 3 odd cycles of (2n-1)/3 elements.
Painting 3*[(2n-1)/6 - 1/2] + 1 of them black is necessary and sufficient to
ensure that one edge in one cycle is incident to 2 black vertices. This
evaluates to n-1.
So: for n <> 2 mod 3, k = n
for n == 2 mod 3, k = n-1
--------------------------------------------------------------------------------
Q3. Find all the integers n >= 1 such that (2^n + 1)/(n^2) is an integer.
--------------------------------------------------------------------------------
A3. Suppose p is prime, and n = q.p^a, where p does not divide q.
Firstly, it's obvious that p > 2, since 2^n+1 is odd. Now we can write:
p^(2a) | 2^(q.p^a) + 1
The element coprime to p mod p^k form a cyclic group, G_p^k, order
(p-1).p^(k-1) [dir /tit=Carmichael for proof, I think]. Let g generate
G_p^(2a), and let 2 == g^r mod p^2a. We know that -1 == g^((p-1)/2).p^(2a-1).
So:
((p-1)/2).p^(2a-1) | r.q.p^a
=> ((p-1)/2).p^(a-1) | r.q
p does not divide q, so p^(a-1) divides r. If (p-1)/2 | r, then we have
a situation where:
(*) 2^(p^a) == -1 mod p^(2a)
We use this equation twice. First, let's try p = 3. Since (p-1)/2 = 1,
the hypothesis above is easily satisfied, and (*) holds.
Suppose a >= 2. Then
if f(a) = (2^(3^a) + 1)
f(a) = f(a-1)*(f(a-1)^2 - 3*f(a-1) +3]
So if 3^x|f(a), then 3^x+1|f(a+1), and no greater power.
Since 3^2|f(1), have 3^(a+1)|f(a). And hence (*) cannot hold for
a > 1. We have hence a = 1, if 3 divides n at all.
Now. let p be the smallest prime > 3 dividing n. The equation (*)
above implies:
2 == -1 mod p (since x^(p-1) == 1 mod p)
which is nonsense. Therefore the hypothesis that (p-1)/2 | r is false, and
x = ((p-1)/2,q) <> 1. But p is the smallest prime > 3. So by the above
x = 1 or 3 => p = 3 (out) or 7.
Suppose 2^n = -1 mod 7. Then -2 is a square mod 7. But this is
not so. Therefore no such p exists.
n = 1 and 3 are the only solutions.
--------------------------------------------------------------------------------
Q4. Let Q+ denote the strictly positive rationals. Construct a function
f from Q+ to Q+ which satisfies:
f(x*f(y)) = f(x)/y.
--------------------------------------------------------------------------------
A4. Let p_i be the ith prime, then define:
f(p_2i) = p_(2i+1)
f(p_(2i+1)) = 1/p_2i
Now extend this to a definition for all strictly positive rationals
through the requirement:
f(x*y) = f(x)f(y)
It's straightforward do check that this works.
--------------------------------------------------------------------------------
Q5. Two players A & B alternately pick integers. We designate by
n_1, n_3, ... , n_(2k+1) and n_2, n_4, ... , n_(2k+2) the numbers chosen
by A and B respectively.
An integer n_0 >= 2 is given: A picks n_1 such that n_0 =< n_1 =< (n_0)^2,
then B picks n_2 such that n1/n2 is a perfect power of a prime number. And
so on. If B has chosen n_(2k), k>= 1, then A choses n_(2k+1) such that
n_(2k) =< n_(2k+1) =< (n_(2k))^2, and then B choses n_(2k+2) such that
n_(2k+1)/n_(2k+2) is a perfect power of a prime number.
A wins if he succeeds in picking 1990. B wins if he succeeds in picking 1.
(a) for which values of n_0 can A always win?
(b) for which values of n_0 can B always win?
(c) for which values of n_0 can each player prevent the other from winning?
--------------------------------------------------------------------------------
A5. (a) If n_2k lies in {45,...,1990}, A can win immediately by saying 1990.
If n_2k lies in {21,...,44}, A can win in two moves. He first goes
to 420, and B's choices lie in {84,...,210}, which is a subset of {45,...,1990}
from which A wins as above.
If n_2k lies in {16,...,20}, A can win in three moves. He first goes
to 252, and B's choices lie in {28,...,126} which is a subset of {21,...,1990}
from which A wins as above.
If n_2k lies in {10,...,15}, A can win in four moves. He first goes
to 90, and B's choices lie in {18,...,45} which is a subset of {16,...,1990}
from which A wins as above.
If n_2k lies in {8,9}, A can win in five moves. He first goes to 60,
and B's choices lie in {12,...,30} which is a subset of {10,...,1990} from
which A wins as above.
Thus A can win from n_2k in {8,...,1990}.
If n_2k > 1990, then r > 3 can be found such that:
9.2^(r-1) < n_2k =< 9.2^r. Then A plays to 9.2^r, and B's must reduce to
9 =< n_2(k+1) < n_2k. This process is repeated until n_2l in {8,...,1990}
is reached, at which point A can win as above.
So A can win from n_2k >= 8.
(b) If n_2k = 2, then A's play lies in {2,3,4} and in each case B wins
in 1 move.
If n_2k = 3, then A's play lies in {3,...,9}, and the choice which
is not a prime power (permitting an immediate win for B) is 6. Then B goes
to 2 and wins as above.
If n_2k = 4, then A's play lies in {4,...,16}, and those which are
not prime powers have at most two primes dividing, and one prime power
dividing is < 4. So B goes to 2 or 3 and wins as above.
If n_2k = 5, then A's play lies in {5,...,25}, and those which are
not prime powers have at most two primes dividing, and one prime power dividing
is < 5. So B goes to 2,3 or 4, and wins as above.
If n_2k = {2,3,4,5}, then B wins.
(c) If n_2k = 6, then A's play lies in {6,...,36}. Numbers with at
most two primes dividing lose as in (b) above. So A's unique move is to
30, which has three primes dividing. B must move to =< 7 or lose as in
(a). So B goes to 6, A goes to 30, and so on.
If n_2k = 7, then A's play lies in (7,...,49}. Numbers with at
most two primes dividing lose as in (b) above. So A must play to 30 or
42, which have three primes dividing. 30 is a draw as above. On 42, B
must play to =< 7 and 6 is his only play. So A goes to 30 and so on.
Thus n_2k = 6,7 are draws.
This exhausts all the possible starting positions.
--------------------------------------------------------------------------------
Q6. Prove that there exists a convex polygon with 1990 sides which
satisfies the following two properties:
(i) all the angles of the polygon are equal
(ii) the lengths of the sides form a permutation of the numbers
1^2, 2^2, 3^2, ..., 1989^2, 1990^2.
--------------------------------------------------------------------------------
A6. Imagine we have such a polygon. Then we can regard each of the
edges E_j, as a point in the complex plane:
R_j*exp(2*pi*i*j/1990)
where R_j = |E_j|, for j=0,1989.
That the 1990 points define a polygon is to say that the centre of
mass of the points is the origin. That the polygon is convex is to observe
that each external angle is 2*pi*i*1990, and thus 1990 of them are necessary
to effect a rotation of 2*pi. There is no possibility therefore that the
polygon crosses itself, and no internal angle is obtuse.
So it remains to see if one can assign the R_j in such a way that
the centre of mass remains at 0, and so we get the correct set {R_j} = {j^2}
emerging.
S_j = (j mod 199) + (j mod 5)*199
S_j = S_k => j = k.
0 =< S_j =< 1989 => S-j span every number from 0 to 994
{S_j*exp(2*pi*j/1990)} has centre of mass 0, since it is composed
of 5 sets of 199 points and 199 sets of 5 points, each of which has centre
of mass 0, since the points are equally spread round the circle.
Now examine each pair of points R_2j and R_(2j+1):
R_2j = 4*S_j + 3 + (2*S_j + 1)^2 = (2*S_j + 2)^2
R_(2j+1) = (2*S_j + 1)^2
R_2j is always even, R_(2j+1) is always odd. R_2j = R_2k => j=k.
R_(2j+1)=R(2k+1) => j=k. Each R_j is a square, between 1^2 & 1990^2, thus
they span all possible values. We have our polygon.
--------------------------------------------------------------------------------
Regards,
Andrew.
|