December Exam 1

This is a 4 hour paper

Various questions from Ukraine

1. Consider the collection of 5-digit (base 10) integers with digits increasing from left to right. Is it possible to erase a digit (and close up if necessary) from each of these 5-digit integers, and obtain the collection of all 4-digit integers with digits increasing from left to right? Solution Each of the sets in question has size (_{5}^{9}) = (_{4}^{9}) so such a bijection is not out of the question. Jacob Shepherd uniquely supplied an answer to this question, and he also supplied an explicit bijection in the form of a matrix:

\begin{matrix}0 & 0 & 0 & 0 & X & · & · & · & · \\ 0 & 0 & 0 & · & 0 & X & · & · & · \\ 0 & 0 & 0 & X & · & 0 & · & · & · \\ 0 & 0 & 0 & X & · & · & 0 & · & · \\ 0 & 0 & 0 & X & · & · & · & 0 & · \\ 0 & 0 & · & 0 & 0 & X & · & · & · \\ 0 & 0 & · & · & 0 & 0 & X & · & · \\ 0 & 0 & · & 0 & · & 0 & X & · & · \\ 0 & 0 & · & 0 & X & · & 0 & · & · \\ 0 & 0 & · & 0 & X & · & · & 0 & · \\ 0 & 0 & X & · & 0 & · & 0 & · & · \\ 0 & 0 & X & · & 0 & · & · & 0 & · \\ 0 & 0 & X & · & · & 0 & · & 0 & · \\ 0 & · & 0 & · & 0 & · & 0 & X & · \end{matrix}

which says it all really. The first row of this matrix corresponds to the following 4-digit numbers (focus on the zeros):

1234, 2345, 3456, 4567, 5678, 6789, 1789, 1289, 1239

where the digits from 1 to 9 are written in cyclic order starting in each of the 9 possible places, and the digits falling in positions marked by a zero are put in ascending order. There are 14 rows giving rise to all 14×9 = (_{4}^{9}) ascending strings of digits of length 4. If you read each X as a 0 you get the (_{5}^{9}) ascending strings of digits of length 5. Erasing the digit in position X yields the required bijection.

2. Let I denote the incentre of triangle ABC. Let the bisector of ^{}B̸AC meet BC at A_{1}, and the bisector of ^{}B̸CA meet AB at C_{1}. Let M be an arbitrary point on the line segment AC. Lines through M parallel to the given bisector lines meet AA_{1}, CC_{1}, AB, CB at points H, N, P and Q respectively. Let the lengths of BC, AC and AB be a, b and c respectively. Let d_{1}, d_{2} and d_{3} be the respective distances from H, I, N to the line P Q. Prove the following inequality.

\frac{d_{1}}{d_{2}} + \frac{d_{2}}{d_{3}} + \frac{d_{3}}{d_{1}} ≥ \frac{2ab}{a^{2} + bc} + \frac{2ca}{c^{2} + ab} + \frac{2bc}{b^{2} + ca}.

So far no solution has been offered.

3. Let a_{1}, a_{2}, …, a_{n} be real numbers such that a_{1} + a_{2} + ⋯ + a_{n} ≥ n^{2}, a_{1}^{2} + a_{2}^{2} + ⋯ + a_{n}^{2} ≤ n^{3} + 1. Prove that n − 1 ≤ a_{k} ≤ n + 1 for all k. Solution We are given that ∑_{i} a_{i} ≥ n^{2} and ∑_{i} a_{i}^{2} ≤ n^{3} + 1. Now

∑_{i}(a_{i} − n)^{2} = ∑_{i} a_{i}^{2} − 2n ∑_{i} a_{i} + n^{3} ≤ n^{3} + 1 − 2n^{3} + n^{3} = 1.

Thus |a_{i}−n| ≤ 1 for every i in the range 1 ≤ i ≤ n. Notice that this is a mean and variance question, and uses the same trick which gives rise to the method of variance in proving geometric theorems.

4. There are n mathematicians in each of three countries. Each mathematician corresponds with at least n + 1 foreign mathematicians. Prove that there exist three mathematicians who correspond with each other. Solution We assume (for contradiction) that no triple of mutually corresponding mathematicians. We prove that for all k in the range 1 ≤ k ≤ n, each mathematician corresponds with at least k mathematicians from each other country. The hypothesis of the question ensures that the result holds when k = 1 and we proceed by induction. Suppose the result holds when 1 ≤ k = r < n and consider a mathematician from country A and the situation regarding his (or her) corresponents in country B. There must be at least 1 of them, and each one of them corresponds with at least k mathematicians from country C, none of which can be a correspondent of A else wwould form a triangle. Thus A corresponds with at most n − k mathematicians from country C, and therefore must correspond with at least k + 1 mathematicians from country B. We are done. Thus every mathematician corresponds with every mathematician outside his or her own country, and this violates the no triangle condition. There are other ways to cast this, but this version is very clear and has comedy value.