February 2002 Exam 1 Solutions

A four hour examination. Iranian Olympaid 2001.

1. Consider n × n matrices. A set of matrix positions containing exactly one position from each row and column of such a matrix is called a generalized diagonal. Let A be an n × n matrix all entries of which are either 0 or 1. Suppose that A has exactly one generalized diagonal with the property that all its entries are 1. Prove that by permuting rows and permuting columns one can obtain an upper triangular matrix from A (i.e. all entries below the leading diagonal are 0). Solution Permuting either row or column entries allows us to assume that the leading diagonal consists of 1’s, i.e. a_{ii} = 1 for all i where 1 ≤ i ≤ n. Now construct a digraph (directed graph) Γ with n vertices v_{1}, v_{2}, …, v_{n} in Vert(Γ) and join v_{i} to v_{j} by a directed edge iff a_{ij} = 1. We claim that this graph does not have any directed cycle, for if it did then

a_{i_{1}i_{2}} = a_{i_{2}i_{3}} = ⋯ = a_{i_{m}i_{1}} = 1

and we obtain a second generalized diagonal (in addition to the leading diagonal) by using the positions of these entries together with diagonal positions other than (i_{t}, i_{t}) as t ranges between 1 and m. Since V has no directed cycle there is a map φ : Vert(Γ) → {1, 2, …, n} such that if a_{i}a_{j} is an edge of Γ, then φ(i) < φ(j) (draw the digraph and squash it flat so that the vertices are in a straight line with the ordering in the line consistent with the digraph ordering). Define π a permutation of 1, 2, …, n by π(i) = φ(v_{i}). Apply π to both rows and columns of the matrix.

2. Suppose that ΔABC has circumcentre O, and that N is the centre of its nine-point circle. Choose a point N′ so that

∠N′BA = ∠NBC, ∠N′AB = ∠NAC.

Suppose that the perpendicular bisector of OA meets BC in A′. Define B′, C′ in a similar fashion. Prove that A′, B′, C′ are on a line 𝔩 which is perpendicular to ON′. Solution My commentary multiplies the length of the model answer by a factor of about 4. I will copy out the answer (and correct it where I can, editorializing in an intrusive and offensive manner as usual, and no doubt introducing further errors). Consider inversion with respect to the circle with centre at A and radius \sqrt{AB · AC/2} (well the model answer doesn’t mention the square root; you need it for two reasons, first because what follows is rubbish otherwise, and second because the dimension police will have you banged to rights if you don’t have it there), and denote it by I. Let R denote reflection in the angle bisector of ∠BAC. Let T = R ∘ I, and they don’t say which way round the composition is meant, but happily these operations commute so we can press on. Let M denote the midpoint of AC and K the midpoint of AB. Thanks to a similar triangles argument T (B) = M and you needn’t repeat the argument, we also get T (C) = K. Of course T is an involution (that is posh for “if you do it twice, you get the identity”) so T (M) = B and T (K) = C. Let AD be the altitude of triangle ABC. Then T (O) = D and T (D) = O, it says here. Well, this isn’t too hard. A certain pair of similar right-angled triangles do the trick (showing you that the angles are right and the distances from A are right). It follows that T sends the circumcircle of MKD to the circumcircle of OBC (inversions and reflections send circles and lines to circles and lines). Let P be the circumcentre of ΔOBC. Note that the nine-point circle of ΔABC is the circumcircle of ΔMKP. Thus AN and AP are symmetric with respect to the angle bisector of ∠A (that is clear because the ray AN produced is mapped to the ray AP produced and vice versa by our map T which does indeed involve reflection in the angle bisector of ∠A). Thus N′ (hitherto ignored, but see the question) lies on AP. Similarly if Q, R denote the circumcentres of ΔOAC and ΔOBC then N′ lies on BQ and CR so we learn that AP, BQ and CR are concurrent at N′ which is very interesting. This actually explains why N′ is an interesting and important point. The loopy definition of N′ given in the question rather disguises the symmetry.

Let A′′, B′′ and C′′ denote the midpoints of OA, OB and OC^{1}. Since P R, RQ and QP are tangent to the circle of radius r = OA′′ = OB′′ = OC′′ centred at O centred at O (it says glibly), it follows that B′′C′′ is the polar of P (this is jargon to say that B′′C′′ is the chord of this circle joining the points of contact of the tangent lines from P). Why does it follow? Well, OB is a chord of the circumcircle of ΔBOC centred at P, and the line segment P B′′ joins the centre of a circle to the midpoint of a chord, so hits at right-angles. Now A′′ is the midpoint of OA, so the polar of A is the line segment perpendicular to OA and through the midpoint of OA′′ (a little exercise in similar triangles).

Let the polars of A and P meet at P′ so that the polar of P′ will be the line AP. This is clearly the application of a standard theorem of which I was hitherto shamefully unaware.^{2} Now we apply a homothety centred at O with scale factor 2. The polar of P is sent to BC, and the polar of A is sent to the perpendicular bisector of OA. Now Q′, R′ (which I assume stand in relation to Q and R as P′ stands to P, but the model answer maintains a dignified silence) are the midpoints of OB′ and OC′. Now since AP, BQ, CR are concurrent, then P′, Q′, R′ are colinear so A′, B′, C′ are colinear and on the line 𝔩′. We have 𝔩 ∥ 𝔩′′ (remember 𝔩? – look at the question). Since N′ lies on the polars of P′, Q′ and R′, so the polar of N′ passes through these points which shows that 𝔩′ is the polar of N′. Since ON′ is perpendicular to 𝔩′, we have 𝔩 ⊥ ON′ and we are done. I don’t really follow the final paragraph, but it is late on Sunday night 17/3/2002. Watch out for later editions when I have the time. Perhaps one our specialist geometers would care to help?

1Well actually the model answer defines A′′ to be the midpoint of O but that is too zen 2It is easy. Just invert in the relevant circle and the result falls out. How pretty.

3. Let A be the set of sequences (x_{1}, x_{2}, …) with integer entries. Let ϕ : A → ℤ be a function such that

(i) ϕ(s + t) = ϕ(s) + ϕ(t) for all s, t ∈ A and

(ii) ϕ(0, 0, …, 1, 0, …) = 1 (i.e. ϕ assumes the value 1 at all sequences which have one entry 1, and all other entries 0.)

(a) Prove that ϕ(1, 2, 4, 8, 16, …) = 0.

(b) Prove that ϕ ≡ 0 (i.e. ϕ is the function on A which always assumes the value 0).

Solution

(a) Let p be a prime number and a_{1}, a_{2}, … ∈ ℤ. Let

n = ϕ(a_{1}p, a_{2}p^{2}, a_{3}p^{3}, …).

Then for every every integer k ≥ 1 we have

n = ϕ(a_{1}p_{1}, …, a_{k}p^{k}, 0, 0, …) + p^{k+1}ϕ(0, 0, …, o, a_{k+1}, a_{k+2}p, …)

using condition (i). Now conditions (i) and (ii) ensure that the first term on the right-hand side of this equation vanishes, and so n is divisible by p^{k+1} for all k so n = 0. In particular using p = 2 and a_{i} = 1 for every i we obtain the required result.

(b) Given and sequence (x_{i}) choose a_{i}, b_{i} ∈ ℤ such that a_{i}2^{i} + b_{i}3^{i} = x_{i}, using Euclid’s algorithm. Now using the result of part (a) and condition (i) to deduce that ϕ(x_{1}, x_{2}, …) = 0.