Indian math olympiad questions are famous (infamous?) for being very analytical. There mostly do not exist any clever one line proofs. Multiple cases have to be analyzed and exhaustively eliminated before arriving upon the correct answer.
I tried solving problems from the Indian National Mathematics Olympiad, 2013 today. My solutions are different (lengthier, and hence perhaps instructive) from the official solutions given online. Hopefully they can be of help to anyone interested in mathematical problem solving.
The Indian National Mathematics Olympiad (INMO) is offered to those candidates who have cleared the Regional Mathematics Olympiad (RMO). The questions that are given are of a difficulty level comparable with P1, P4 of the International Math Olympiad.
I do plan on running a seminar on competitive math problem solving this summer. This is useful for all sorts of things, like getting better at algorithms, improving analytical skills in finance, etc. Please do let me know if you’d be interested in that sort of thing.
- Find all positive integers
and primes
, such that
First, we make a couple of observations. As is a multiple of
,
will also have to be a multiple of
. This can be re-written as
. On factorizing the left hand side, we get
. Hence, as the right hand side is a multiple of
, either
is a multiple of
, or
is a multiple of
.
If is a multiple of
and
is not, then it has to be a multiple of
, as
is the only possibility. This is impossible as
. Hence,
. Note that from our previous observation, we also know that
. Hence, combining the two, we get
.
Let . Then we have
(we obtain this after canceling out
on both sides). For
, we have
. Hence, as the right hand side is
, we have
. This implies that
. The right hand side is a multiple of
while the left hand side is not. Hence, this is only possible if
, or
. As
, we get
.
From this, we can deduce that , and hence
and
.
is the only solution. QED
- Let
be positive integers such that
. Prove that
has no integer solutions.
Let be a solution. Clearly
cannot be a solution, as then we would have
, which is impossible as
is a positive integer. Hence, let us assume that
is a non-zero integer. Then we have
. Therefore,
. Let
. Then we have
. Continuing like this, we get
, where
,
, and
.
In other words, we have . Clearly, as
, we have
. Hence, $x$ is not an integer. Hence proved. QED
- Â Let
be a positive integer. Call a nonempty subset
of
good if the arithmetic mean of the elements of
is also an integer. Further, let
denote the number of good subsets of
. Prove that
and
are either both odd or even.
Clearly, this is equivalent to proving that is always even. Note that subsets consisting of one element have an arithmetic mean that is an integer. Hence, we can prove that the number of good subsets of
containing at least two elements will be even. The way that we’ll prove this assertion is by forming a pairing between sets: if
is one such subset, then consider the set
. Clearly this set will also have an integer average, and the map
is idempotent. Hence, the mapping is bijective.
Case 1: Let be even. The only cases in which bijective pairing maps a set to itself is for every
in the set,
is also included in it. As there is no
such that
, as
is odd, a set for which bijective pairing fails will have to contain an even number of elements. Hence,
is even for all
. For sets of the form
, if
and
are both included, then the average will be
, which is clearly not an integer as
is odd. Hence, every good set can be bijectively paired with a different good set, which implies that the total number of good sets is even.
Case 2: Let be odd. Let us study the good sets for which the map
does not produce a different set. The only different is that when
,
. Hence, sets of both odd and even number of elements can map to themselves through this pairing. However, if we can prove that
and
are both odd, then their sum will be even. Combining this with the fact that the number of sets which map to other sets is anyway even, we get a total number of even sets.
Let us consider . Any set of this form will have to contain the element
. The total number of such sets is hence
, which is odd.
Let us now consider . Then the element
cannot be contained in such a set. Hence, the total number of elements is
, which is odd.
Adding both cases together, we get an even number of sets that map to themselves through this mapping.
Hence, the total number of sets is even, which proves our assertion. QED
- Â Let
be positive real numbers such that
and
. If
,
, and
, then prove that
and
.
This is one of my favorite problems. Without loss of generality, let . Then keeping
constant, bring
and
. This keeps
unchanged, and hence
(as
), which implies
. Now keeping
constant, bring
and
. This again implies that
, which implies that
. Hence,
if any of these changes happens. Hence, as
, none of these changes should happen, and
and
. QED