- Define sequence for . Define for . Suppose that there exists such that , . (In particular this implies s are integers for large enough .) Show that .
- In scalene , is the incentre. (I.e. centre of incircle.) The tangents at and to the circumcircle of intersect at . The incircle touches the side at . Drop perpendicular from to , intersecting at . intersects at . Let line intersect the circumcircle of at . Show that: are colinear if and only if are con-cyclic.
- Let be a closed rectangle. Let be dissected into smaller rectangles, whose sides are parallel to either side of . The vertices of the smaller rectangles are called ‘nodes‘. A segment (which must be part of the partition) joining two nodes is called a basic segment if it contains no nodes other than its two endpoints. Find the maximum number and minimum number of basic segments across all dissecting configurations.
- Let integer . For two permutations of : and , we call them turnings of each other, if there exists positive integer such that . Prove:It is possible to arrange all permutations of into a sequence such that for all , and are turnings of each other. Here we let .
- Let denote the set of all positive integral divisors of positive integer . Find all positive integer such that can be written as the union of two DISJOINT subsets and , which satisfy : , the elements of can be arranged into an arithmetic progression, and the elements of can be arranged into a geometric progression.
- Let be a given integer. Let be two given positive numbers with . Suppose real numbers , find the maximum value of
Q1. My friend Jongmin Lim sent me the following solution. I have been working on it for a a rather extended period, but I constrained myself into a suboptimal approach that proved ultimately unsuccessful.
BTW this Jongmin dude did the IMO at some point in his life. Got 23/42, i.e. barely passed. But the IMO, currently being inundated with people from scrub countries, has a compromised awarding scheme, in which someone who did slightly better than barely passed can be awarded a silver medal; and upon the OP, who, despite his friendship with Jongmin, is consistently scrub-like in Olympiad problem solving, and who almost hit the 50% line but, notwithstanding the maximal effort from Team Leader and Deputy Leader which earned him marks that the OP is not sure whether he would have received without being from an Anglophone country with a respectable Leader, did not quite, a bronze medal is bestowed to signify that fact that he could solve the easiest problems and did not black out on the problems that are more becoming of the IMO’s prestige.
So the problem gave us recursions, linear recursions which we can actually solve. Whenever such thing comes around, solving it is never a bad idea because it doesn’t take up much time and it can be illuminating.
Okay… We see that, if we denote , we have . Thus the two recursions are related in such a superficial way.
Since we have constructed three new parameters, we can express and in terms of them. The conclusion, in new parameters, read: . This looks a lot nicer.
The ‘eventually integer’ condition says a lot. We wish to exploit it.
. This transformation is crucial: it mimics the long division algorithm and permits separate treatment of the remainder from the main part of the quotient.
We of course wish to have is an integer and the other term, the remainder, to be disallowed from being an integer for very large and thus to establish that the remainder is zero always. But that is not easy: how are we going to establish that the main part is an integer at all? It does indeed remind us of the recursion itself, but the term is not at all easy to deal with.
Well, we shall have a closer look at the because we have not really used the integer condition yet. We have that for all large , from which we wish to recover, at least, the rationality of .
So we let be large and choose three consecutive values of to start with.
No matter what the RHS is, we have a linear system in with coefficients in . We thus wish to make further compromise and settle to prove that .
To do that, we only have to show that the coefficient matrix has non-zero determinant.
But a matrix with the first column , second column , third column has its determinant the form of a Vandermonde matrix, which vanishes if and only if the common ratios of two of its geometric progressions are equal. In this case we thus have a non-zero determinant and thus .
That wasn’t too bad. But how to proceed?
Key insight: the denominator of the rational number is unbounded. This is because: . This is because, modulo , . Now, since , is never a multiple of . We need to show that is unbounded. We will do that at the end of the proof. This is how we wish to establish the remainder is non-integer after all. Therefore it only remains to show that has bounded denominator when written in simplest form to finish off the problem. (This is where I made the mistake, I strove to demonstrate that it is an integer, but bounded denominator suffices.)
Since and are both in , and , we actually have that happening. Explicitly, for , where , are called simplest form if is minimised. We write it in simplest form, and define . It is easy to verify that multiplying an element in by an element in does not increase its -value. Thus the value of is bounded. We are done, as for large value of , , has one component whose denominator is very large, thus not an integer.
Wait! I promised to show that is unbounded, now it is time to actualise my promise. . Therefore it suffices for the problem to show that there exists a sequence such that is lower bounded. That can be accomplished by showing the existence of infinitely many such that , when divided by , gives off a remainder that is within the interval .
Suppose that , happens for in an arithmetic progression. Suppose that is an irrational number, the sequence is dense in , where denotes the fractional part of . In particular, this shows the existence of infinitely many such that , or, . This shows that which goes to infinity for large .
Q5. This is all my own work, and I started writing this up as soon as I finished solving this problem by brute force base bash. I believe that while it might not be the most economical method, it is instructive to write up the most natural instinct when the problem is encountered. There are problems — e.g. IMO 2015 Q2, proposed by Dusan Djukic — for which no quick or enlightening methods exist. In such cases, as one is generally never informed of whether the problem he encounters is of this class, it is important to be able to bash. If any improvement on the bash method can be proposed, I will also include it as an alternative. For papers like IMO 15′ day 1, the contestants are discriminated by their ability to finish off bashing work efficiently and correctly. Many well-trained, talented contestants could not perform the bashing perfectly and got 6/7.