Problem:
Let f be a bijective function from the set to itself. Show that there is a positive integer
such that
for each
. Here,
denotes the composite function
repeated M times.
Proof:
The student should be familiar with the following properties of bijective functions:
a) If is a bijective function then there is a unique bijective function
such that
, the identity function on A. The function g is called the inverse of f and is denoted by
. Thus,
b)
c) If f and g are bijections from A to B, then so are and
.
d) If f, g, h are bijective functions from A to B and , then
.
Apply at left to both sides to obtain
.
Coming to the problem, since A has n elements, we see that there are only finitely many (in fact, n!) bijective functions from A to A as each bijective function f gives a permutation of by taking
. Since f is a bijective function from A to A, so is each of the functions in the sequence:
,
,
,
, \ldots
All these cannot be distinct since there are only finitely many bijective functions from A to A. Hence, for some two distinct positive integers , say, we must have
If , we take $, latex M=m$, to obtain the result. If
, multiply both sides by
, to get
. We take
to get the relation
when
.
Note this means for all
.
Aliter:
Take any element r in the set A and consider the sequence of elements
obtained by applying f successively. Since A has only n elements there must be repetitions in the above sequence. But, when the first repetition occurs, this must be r itself, for, if the above sequence looks (for instance) like:
where the first repetition is an element c other than r, this would imply
and
contradicting the fact that f is a bijection. Thus, for some positive integer
, we have
.
This is true for each r in the set . By taking M to be the lcm of
, we get
for each
.
Note: If f itself is the identity function the above proof fails because each . But, in this case, we may take M to be any integer greater than or equal to 2.
Problem:
Show that there exists a convex hexagon in the plane such that:
(a) all its interior angles are equal, (b) its sides are 1,2,3,4,5,6 in some order.
Proof:
Let ABCDEF be an equiangular hexagon with side-lengths as 1,2,3,4,5,6 in some order. We may assume WLOG that . Let
,
,
,
,
.
Since the sum of all the angles of a hexagon is equal to , it follows that each interior angle must be equal to
. Let us take A as the origin, the positive x-axis along AB and the perpendicular at A to AB as the y-axis. Use vectors. If the vector is denoted by
, we then have
,
This is because these vectors are inclined to the positive x-axis at angles respectively.
Since the sum of all these 6 vectors is , it follows that
,
and, . That is,
…call this I
and ….call this II.
Since , in view of II, we have the following:
(i)
ii) .
iii)
Note: the possibility that and
in (i), for instance,need not be considered separately, because we can reflect the figure about
and interchange these two sets.
Case (i):
Here, . Since
,
, this is not possible.
Case (ii):
Here, =2c-2=2$. This is satisfied by
Case (iii):
Here,
This is satisfied by .
Hence, we have essentially two different solutions: and
. It may be verified that (I) and (II) are both satisfied by these sets of values.
Aliter:
Consider an equilateral triangle of side 9 units. Remove from the three corners equilateral triangles of sides 1 unit, 2 units, and 3 units respectively. The remaining portion is now an equiangular hexagon ABCDEF with sides 1,6,2,4,3,5 as required.
Problem:
There are ten objects with total weight 20, each of the weights being a positive integer. Given that none of the weights exceed 10, prove that the ten objects can be divided into two groups that balance each other when placed in the two pans of a balance.
Solution:
Let denote the weights of the 10 objects in decreasing order. It is given that
and that
. For each i,
, let
. (For example,
,
, etc.Consider the 11 numbers
. Note that all these 11 numbers are non-negative and we have
and
for
. Now, look at the remainders when these 11 numbers are divided by 10. We have 10 possible remainders and 11 numbers and hence, by the Pigeon Hole Principle at least some two of these 11 numbers have the same remainder.
Case (i):
For some j, has the remainder 0, that is,
is multiple of 10. But, since
, the only possibility is that
. Thus, we get a balancing by taking the two groups to be
and
.
Case (ii):
Suppose is a multiple of 10. But, then since
, this forces
, which, in turn, implies that all the weights are equal and equal to 2 as they add up to 20. In this case, taking any five weights in one group and the remaining in the other we again get a balancing.
Case (iii):
For some j and k, say , we have that
and
have the same remainder, that is,
is a multiple of 10. But, again since
, we should have
, that is,
, and we get a balancing.
Case (iv):
Suppose and
for some j (
) have the same remainder, that is,
is a multiple of 10. As in the previous cases, this implies that
. That is,
. Hence,
and
balance each other.
Thus, in all cases, the given 10 objects can be split into two groups that balance each other.
Problem:
At each of the eight corners of a cube write +1 or -1 arbitrarily. Then, on each of the six faces of the cube write the product of the numbers written at the four corners of that face. Add all the fourteen numbers so written down. Is it possible to arrange the numbers +1 and -1 at the corners initially so that this final sum is zero?
Solution:
Let be the numbers written at the corners. Then, the final sum is given by
.
Because there are fourteen terms in the above sum, and each of the terms is +1 or -1, the sum will be zero only if some seven terms are +1 each and the remaining 7 terms are -1 each.
But, the product of the fourteen terms is .
Therefore, it is impossible to have an odd number of -1’s in the above sum.
We conclude that the desired arrangement is not possible.
Problem:
Given the 7-element set , find a collection T of 3-element subsets of A such that each pair of elements from A occurs exactly in one of the subsets of T.
Solution:
One possible solution collection is as follows:
,
,
,
.
,
,
. Note that there could be other combinations obtained by permitting the letters. WLOG, a can be associated with three pairs b,c,d; e, f, g. Now b can be associated with d, f and e, g. The possible choices left for c are only the pairs e,f and d,g. This arrangement does work.
Hope you all enjoy such type of questions. Please compare your attempts with the solutions given above.
Cheers,
Nalin Pithwa.
Reference: Problem Primer for the Olympiad, C. R. Pranesachar, B J Venkatchala, C. S. Yogananda, Prism Books.
Amazon India link:
If you are interested in knowing more about the RMO and INMO, please refer to: