PLEASE CLICK ON AN AD AND HELP US TO SURVIVE

Tuesday, 22 July 2014

CMI 2014 SOLUTIONS

JUMP OF A FROG AND THE LOTUS PROBLEM (I.S.I. B.MATH 2014 SOLUTION)


n (> 1) lotus leafs are arranged in a circle. A frog jumps from a particular leaf by the following rule: It always moves clockwise. From staring point it skips 1 leaf and jumps to the next. Then it skips 2 leaves and jumps to the following. That is in the 3rd jump it skips 3 leaves and 4th jump it skips 4 leaves and so on. In this manner it keeps moving round and round the circle of leaves. It may go to one leaf more than once. If it reaches each leaf at least once then n (the number of leaves) cannot be odd.
Discussion:
Suppose we number the leaves as 1, 2, 3, upto n. Leaf 1 being the starting point of the frog.
Step 1 – Leaf 1
Step 2 – Leaf 3 (because the frog skips 1 leaf)
Step 3 – Leaf 6 (1+2+3) ( because it skips 2 leaves in second jump)
In this manner the frog will be in the
\mathbf{ \frac{m(m+1)}{2} }  (modulo n) leaf in the mth step.
If n = 2k+1 (that is if we have odd number of leaves) then in the 2k step and 2k+1 step it will be on Leaf 2k+1.
This is because \mathbf{\frac{(2k+1)(2k)}{2} = k(2k+1) \equiv 0 \text{mod} 2k+1 } and \mathbf{\frac{(2k+1)(2k + 2)}{2} = (k+1)(2k+1) \equiv 0 \text{mod} 2k+1 }
Also notice that after the first 2K+1 steps the position of the frog repeats.
This is because for even value (2m) \mathbf{\frac{2m(2m+1)}{2} \equiv m(2m+1) \equiv \frac{(2m + 2k + 1) (2m+ 2k + 2)}{2} \equiv (2m+2k+1)(m+k+1) \mod 2k+1 }
Since \mathbf{ (2m+2k+1)(m+k+1) \equiv (2m)(m+k+1) + (2k+1)(m+k+l) \equiv 2m^2 + 2mk + 2m }
But \mathbf{ 2m^2 + 2mk + 2m \equiv 2m^2 + m + 2mk + m \equiv m(2m+1) + m(2k+1) \equiv m(2m+1) \mod 2k+1 }
Similarly for odd values (2m+1) 
\mathbf{\frac{(2m+2)(2m+1)}{2} \equiv (m+1)(2m+1) \equiv \frac{(2m + 1 + 2k + 1) (2m + 1 + 2k + 2)}{2} \equiv (m+k+1)(2m+2k+3) \mod 2k+1 }
Since \mathbf{(m+k+1)(2m+2k+3) \equiv (2m+2)(m+k+1) + (2k+1)(m+k+l) \equiv 2m^2 + 2mk + 2m + 2m + 2k +2 }
But \mathbf{ (2k+1)m + (2k+1) + 1 + 3m + 2m^2 \equiv (m+1)(2m+1) \mod 2k+1 }
As every 2k+1 values (modulo 2K+1) need to be distinct if the frog visits every leaf, it visits leaf number 2k+1 in the last two steps, hence some leaf must be missing.Special NoteExtension: The frog may visit each leaf if and only if number of leaves is a power of 2.

MAP FROM A POWER SET TO N-SET (CMI ENTRANCE 2014 SOLUTION)

(1) Let A = {1, … , k} and B = {1, … , n}. Find the number of maps from A to B .
(2) Define \mathbf{ P_k }  be the set of subsets of A. Let f be a map from \mathbf{P_k \to B } such that if \mathbf{ U , V \in P_k } then \mathbf{ f(U \cup V) }= \mathbf{\text{max} \{ f(U) , f(V) \} } . Find the number of such functions. (For example if k = 3 and n =4 then answer is 100)
Discussion:
(1) For each member x of set A we have n choices for f(x) in B. Hence the number of functions is \mathbf{ n^k }
(2) Claim (i): \mathbf{ f(\phi) } is minimum for any such function f from \mathbf{P_k \to B } . This is because \mathbf{ f(A_1) = f(\phi \cup A_1 ) = \text{max} \{ f(A_1), f(\phi) \} } hence \mathbf{f(A_1)} must be larger than \mathbf{ f(\phi) } for any member \mathbf{A_1} of \mathbf{ P_k }
Claim (ii) If we fix the values of the singleton sets then the entire function is fixed. That is if we fix the values of f({1}) , f({2}) , … , f({k}). Since for any member \mathbf{A_1} of \mathbf{P_k , {A_1} } is union of several singleton sets. Hence it’s value is the maximum of the functional values of those singleton sets. For example let \mathbf{ A_1 = (1, 2) } then \mathbf{f(A_1) = f(\{1\}\cup\{2\}) = \text {max} \{f(\{1\}) , f(\{2\}) \} }
Claim (iii) f({1}) , … , f({k}) are individually independent of each other.
Now we fix \mathbf{ f(\phi) = i}. Since it is the smallest, the singleton sets map to i to n.
Hence if \mathbf{ f(\phi) = 1} each of the singleton sets have n choices from 1 to n; hence there are \mathbf{ n^k }functions. Similarly \mathbf{ f(\phi) = 2} each of the singleton sets have n-1 choices from 2 to n; hence there are \mathbf{ (n-1)^k } functions.
Thus the total number of functions = \mathbf{ \sum_{i=1}^n i^k }

AREA OF A REGION (CMI ENTRANCE 2014 SOLUTION)

\mathbf{ A= \{(x, y), x^2 + y^2 \le 144 , sin(2x+3y) \le 0 \} }  . Find the area of A.
Discussion:
\mathbf{ x^2 + y^2 \le 144 } is a disc of radius 12 with center (0, 0).
Now notice that\mathbf{ sin(2x + 3y) \le 0 \implies sin ( 2(-x) + 3(-y) ) = sin(-(2x+3y)) = -sin(2x+3y) \ge 0 }
Hence if a point (x, y) is in A then (-x, -y) is not in A.
Similarly if there is a point (x, y) not in A then we get a corresponding point (-x, -y) in A.
Therefore we have a bijection between points in A and not in A.
Thus area of A is exactly half the area of the disc = \mathbf{ \frac{\pi (12)^2 }{2} = 72 \pi }

INTEGER X (CMI ENTRANCE 2014 SOLUTIONS)

Let \mathbf{ x \in \mathbb{R} , x^{2014} - x^{2004} , x^{2009} - x^{2004} \in \mathbb{Z} } . Then show that x is an integer. (Hint: First show that x is a rational number)
Discussion:
\mathbf{ x^{2014} - x^{2004} - x^{2009} + x^{2004} = x^{2014} - x^{2009} = x^{2009}(x^{5} - 1 ) } is an integer
\mathbf{x^{2009} - x^{2004} = x^{2004}(x^5 - 1) } is also an integer.
Hence ratio of those two are \mathbf{ \frac{ x^{2009}(x^5 -1)}{x^{2004}(x^5 - 1)} = x^5 } is a rational.
Again \mathbf{(x^5)^{400} = x^{2000}, x^5 - 1 } are rational. Also it is given that \mathbf{ x^{2000}\cdot x^4 \cdot (x^5 - 1) } is integer. Hence \mathbf{ x^4 } is rational.
Therefore \mathbf{ \frac{x^5}{x^4} =x } is rational. Since ratio of rationals is rational.
Suppose x = p/q, then \mathbf{ \frac{p^{2014}}{q^{2014}} - \frac{p^{2004}}{q^{2004}} = k } where gcd(p, q) = 1 and k is an integer. \mathbf{ p^{2014} - p^{2004}q^{10} = kq^{2014} }
But this implies q divides p which means q = 1.
Hence x is an integer. (Proved)
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)