 How Cheenta works to ensure student success?
Explore the Back-Story

# IOQM 2022 problems, solutions, discussion ## Solutions of IOQM 2022

Problem 1: A triangle $A B C$ with $A C=20$ is inscribed in a circle $\omega$. A tangent $t$ to $\omega$ is drawn through $B$. The distance of $t$ from $A$ is $25$ and that from $C$ is $16$. If $S$ denotes the area of the triangle $A B C$, find the largest integer not exceeding $\frac{S}{20}$.

Solution:

Let $O$ be the circumcentre of $\triangle ABC$ and let $M, N$ be the foot of perpendiculars from $A$ and $C$ to the tangent $t$ respectively

$O T =\sqrt{R^2-(25-R)^2}=5 \sqrt{2 R-25}=B M$

$A B=\sqrt{A M^2+B M^2}=\sqrt{25^2+25(2 R-25)}=5 \sqrt{2 R}$

Similarly,

$O T=4 \sqrt{2 R-16}=B N$

$B C=\sqrt{B N^2+C N^2}=4 \sqrt{2 R}$

$[A B C]=\frac{1}{2} A C \times B C \times \sin C$

we know that,

$A B=2 R \sin C$

$\Rightarrow \sin C=\frac{5 \sqrt{2 R}}{2 R}=\frac{5}{\sqrt{2 R}}$

$\Rightarrow \ [A B C] =\frac{1}{2} \times 20 \times 4 \sqrt{2 R} \times \frac{5}{\sqrt{2 R}}=200=S$

Therefore, $\frac{S}{20}=10$

Problem 2: In a parallelogram $A B C D$, a point $P$ on the segmènt $A B$ is taken such that $\frac{A P}{A B}=\frac{61}{2022}$ and a point $Q$ on the segment $A D$ is taken such that $\frac{A Q}{A D}=\frac{61}{2065}$. If $P Q$ intersects $A C$ at $T$, find $\frac{A C}{A T}$ to the nearest integer.

Solution:

Let $A B = l, A D = b$.

$\Rightarrow A P=\frac{61 l}{2022}$ ; $A Q=\frac{61 b}{2065}$

Draw a line parallel to PQ that passes through B and let it intersect AD at L. Since, $\triangle A P Q \sim \triangle A B L$

$\Rightarrow \frac{A L}{A Q}=\frac{A B}{A P} \Rightarrow A L=\frac{2022 b}{2065}$

Hence, $L$ is a point inside the segment $\overline{A D}$

Observe that,

$\triangle AXL \sim \triangle CXB$, since $A D || B C$

$\Rightarrow \frac{A X}{C X}=\frac{A L}{B C}=\frac{2022}{2065}$

$\Rightarrow \frac{A X}{A C}=\frac{1}{1+\frac{C X}{A X}}=\frac{2022}{4087}$

Since $P Q || B L$,

$\Rightarrow \frac{A T}{A X}=\frac{A P}{A B}=\frac{61}{2022}$

$\frac{A C}{A T}=\frac{4087}{61}=67$

Problem 3: In a trapezoid $A B C D$, the internal bisector of angle $A$ intersects the base $B C$ (or its extension) at the point $E$. Inscribed in the triangle $A B E$ is a circle touching the side $A B$ at $M$ and side $B E$ at the point $P$. Find the angle $D A E$ in degrees, if $A B: M P=2$.

Solution:

Let, $\angle D A E=\theta \quad \Rightarrow \quad \angle A E B=\theta$ (since $D A || B E$)

Hence, $\triangle A B E$ is an isoceles triangle.

All of these arguments are valid even if the point $E$ lies outside of the side $B C$, but we assume that $B C$ is one of the parallel sides of the trapezoid for this solution.

Since, $B M$ and $B P$ are tangents from a common point $B$ to the circle, $B M = B P$

Therefore, $\triangle B M P \sim \triangle B A E$

Let, $P M = x, A B = 2x$ and $A E = y$

$\Rightarrow \frac{B M}{A B}=\frac{P M}{A E} \Rightarrow B M=\frac{2 x^2}{y}=B P$

Since $\triangle A B E$ is isoceles, $A N = N E$ by symmetry

$\Rightarrow A N=\frac{y}{2}=A M$ (since, tangents are equal for common points)

$\Rightarrow A M+B M=A B$

$\Rightarrow \frac{y}{2}+\frac{2 x^2}{y}=2 x$

$\Rightarrow (2 x-y)^2=0$

$\Rightarrow \frac{y}{x}=2$

Since $\triangle A B E$ is isoceles, $\angle B N A=\angle B N E=90^{\circ}$, since $N$ is the midpoint of $A E$

$\Rightarrow \cos \theta=\frac{A N}{A B}=\frac{y / 2}{2 x}=\frac{1}{2}$

$\Rightarrow \theta=60^{\circ}$

Problem 4: Starting with a positive integer $M$ written on the board, Alice plays the following game: in each move, if $x$ is the number on the board, she replaces it with $3 x+2$. Similarly, starting with a positive integer $N$ written on the board, Bob plays the following game: in each move, if $x$ is the number on the board, he replaces it with $2 x+27$. Given that Alice and Bob reach the same number after playing 4 moves each, find the smallest value of $M+N$.

Solution:

$81x+80 = 16y+405$
$81x-16y = 325$
The solution is
$x=325-16k$ , $y=1625-81k$
And the least possible values are $x=5$, $y=5$
Hence, $Min(x+y) = 10$

Problem 5: Let $m$ be the smallest positive integer such that $m^2+(m+1)^2+\cdots+(m+10)^2$ is the square of a positive integer $n$. Find $m+n$.

Solution:

$n^2=m^2+(m+1)^2+\cdots+(m+10)^2$

we know that, $\quad 1^2+2^2+\cdots+k^2=\frac{k(k+1)(2 k+1)}{6}$

$\Rightarrow n^2=\frac{(m+10)(m+11)(2 m+21)}{6}-\frac{(m-1) m(2 m-1)}{6}$

After Simplification,

$n^2=11\left(m^2+10 m+35\right)=11\left((m+5)^2+10\right)$

Let $y=m+5$,

$n^2=11\left(y^2+10\right)$, since $11$ is a prime $\Rightarrow 11$ divides $y^2+10$

$\Rightarrow \quad y^2 \equiv 1 \quad(\bmod 11)$

$\Rightarrow \quad y= 11s \pm 1, s \in \mathbb{N}$

Hence,
$\left(\frac{n}{11}\right)^2=11 s^2 \pm 2 s+1=$ Perfect square

Now substituting $s=1,2$, we obtain a perfect square for $s=2$ and a "+" sign as follows,

$\left(\frac{n}{11}\right)^2=11(2)^2+2(2)+1=7^2 \Rightarrow n=77$

$y=11 s+1=11(2)+1=23=m+5 \Rightarrow m=18$

$m+n=18+77=95$

Problem 6: Let $a, b$ be positive integer satisfying $a^3-b^3-a b=25$. Find the largest possible value of $a^2+b^3$

Solution:

$a, b \in \mathbb{N}$,

$a^3-b^3-a b=25$

$(a-b)\left[a^2+b^2+a b\right]-a b=25$

$(a-b) \left[(a-b)^2+3 a b\right]-a b=25$

Note that if $a-b \leq 0$, then $LHS < 0$. So, $a-b>0$

$(a-b)^3+3 a b(a-b)-a b=25$

$\Rightarrow (a-b)^3+a b[3(a-b)-1]=25$

Observe that, $3(a-b)-1>0$

$\Rightarrow a-b=1\text{ (or) }2$, else $LHS > 25$

Let $a - b = 2$,

$\Rightarrow 8+a b(5)=25$, but $5\not|\ 8$, hence contradiction

Let $a-b=1$,

$\Rightarrow 1+a b(2)=25 \Rightarrow a b=12$

$\Rightarrow a=4, b=3$

${Max}\left(a^2+b^3\right)=4^2+3^3=43$

Problem 7: Find the number of ordered pairs $(a, b)$ such that $a, b \in{10,11, \ldots, 29,30}$ and ${GCD}(a, b)+{LCM}(a, b)$ $=a+b$.

Solution:

Let $gcd(a, b) = d$
So, $a=dp$ and $b=dq$ with $gcd(p,q)=1$
Let $b>a$ then $q>p$
So $lcm(a,b)=aq=bp=apq > a+b$ if $p,q>1$, which can be verified easily
So one of $p,q$ is $1$ or both $p,q$ is $1$
One of $p,q$ is $1$ implies one of $a,b$ is multiple of another.
That gives us $(10,20),(10,30),(11,22),…,(15,30)$ that is $7$ pair.
If $p=q=1$ then $a=b$ then there are $21$ possible pair.
So total number of ordered pairs is $21+2 \times 7=35$

Problem 8: Suppose the prime numbers $p$ and $q$ satisfy $q^2+3 p$ = $197 p^2+q$. Write $\frac{q}{p}$ as $l+\frac{m}{n}$, where $l, m, n$ are positive integer, $m<n$ and ${GCD}(m, n)=1$. Find the maximum value of $l+m+n$.

Solution:

$q^2+3 p=197 p^2+q \Rightarrow q(q-1)=p(197 p-3) \rightarrow(1)$

Observe that prime $q>p \Rightarrow p \mid q-1$

So, let $q=k_1 p+1, k_1 \in \mathbb{N}$

Now multiply $k_1^2$ throughout equation $(1)$,

$k_1^2 q(q-1)=k_1 p\left(197 k_1 p-3 k_1\right)$ = $(q-1)\left(197 q-197-3 k_1\right)$

$\Rightarrow \quad k_1^2 q=197 q-197-3 k_1$

$\Rightarrow \quad\left(197-k_1^2\right) q=3 k_1+197 \rightarrow (2)$

Hence, $k_1$ can take values from $1$ to $14$

But $\quad 197-k_1^2 \leq \frac{3 k_1+197}{2}$ (from $(2)$)

$\Rightarrow \quad 10 \leq k_1 \leq 14$

Substituting these $5$ values for $k_1$, we observe that $q$ is an integer only for $k_1=14$

$q=\frac{3 k_1+197}{197-k_1^2}=239 \Rightarrow q=239$, which is a prime

$q=k_1 p+1 \quad \Rightarrow \quad p=17$

$\frac{q}{p}=\frac{239}{17}=14+\frac{1}{17} \Rightarrow l=14, m=1, n=17$

$l+m+n=14+1+17=32$

Problem 9: Two sides of an integer sided triangle have lengths 18 and $x$. If there are exactly 35 possible integer values $y$ such that $18, x, y$ are the sides of a non-degenerate triangle, find the number of possible integer values $x$ can have.

Solution:

$x$ is given to us and $x, y$ are integers

By triangle inequality, (for non-degenerate triangle),

CASE 1: $18 \geq x$

$18-x<y<18+x$

$\Rightarrow \quad y$ can take $2 x-1$ integer values

$\Rightarrow \quad 2 x-1=35 \Rightarrow x=18$

CASE 2: $18<x$

$\Rightarrow \quad x-18<y<x+18$

$\Rightarrow y$ can take $35$ integer values for any $x>18$

So, in this case $x$ can take all integer values $>18$

Problem 10: Consider the 10-digit number $M=9876543210$. We obtain a new 10-digit number from $M$ according to the following rule: we can choose one or more disjoint pairs of adjacent digits in $M$ and interchange the digits in these chosen pairs, keeping the remaining digits in their own places. For example, from $M=9876543210$, by interchanging the 2 underlined pairs, and keeping the others in their places, we get $M_1=9 \overline{78} 6 \overline{45} 3210$. Note that any number of (disjoint) pairs can be interchanged. Find the number of new numbers that can be so obtained from $M$.

Solution:

$M=9876543210$

Instead of underlining the adjacent pairs to be interchanged, we put an arrow mark on the first number of the underlined pair. For eg.,

Now, note the number of underlined pairs possible equals the number of all possible combinations of arrow marks put on $987654321$ that are NOT ADJACENT.

So, we just find the number of ways to choose any number $(\neq 0)$ of numbers from $987654321$ that are NOT ADJACENT.

Let us find the number of ways to choose "$r$" non-consecutive numbers from the set $\{1,2,3,....,n\}$. Observe that there is a bijection of "$r$" non-consecutive numbers from $\{1,2,3,....,n\}$ with choosing any "$r$" numbers from $\{1,2,3,....,n-r+1\}$ which is established as follows, let $\{x_1, x_2, x_3, ... x_r\}$ be the non-consecutive $r$ element subset of $\{1,2,3,....n\}$ in the increasing order, then

$\{x_1, x_2, x_3, \ldots, x_n\}\longleftrightarrow\{x_1, x_2-1, x_3-2, \ldots, x_r-r+1\}$

where, $\{x_1, x_2-1, x_3-2, \ldots, x_r-r+1\}$ = $r$ element subset of $\{1,2,3,....,n-r+1\}$

So, number of ways = ${}^{n-r+1} C_r$

Using the above formula for $n=9, \forall r>0$ we get,

Therefore, Number of new numbers $M$ = ${}^{9} C_1$ + ${}^{8} C_2$ + ${}^{7} C_3$ + ${}^{6} C_4$ + ${}^{5} C_5$

$=88$

Problem 11: Let $A B$ be a diameter of a circle $\omega$ and let $C$ be a point on $\omega$, different from $A$ and $B$. The perpendicular from $C$ intersects $A B$ at $D$ and $\omega$ at $E(\neq C)$. The circle with centre at $C$ and radius $C D$ intersects $\omega$ at $P$ and $Q$. If the perimeter of the triangle $P E Q$ is $24$ , find the length of the side $P Q$.

Solution:

Let,

$\angle P Q D=\alpha$, since $C$ is centre of $2^{\text {nd }}$ circle

$\Rightarrow \angle P C D=2 \alpha=\angle P C E=\angle P Q E=\angle P Q D+\angle D Q E$

$\Rightarrow \quad \angle D Q E=\alpha=\angle P Q D$

Hence, $Q D$ and similarly $P D$ are internal angle bisectors of $\triangle Q P E$. So, $D$ is the incentre of $\triangle Q P E$ and hence $C E$ is the angle bisector of $\angle P E Q$.

Observe that $O D \perp C E \Rightarrow D$ is the midpoint of chord $C E$.

Let $k$ be the intersection of $C E$ and $P Q$

$\angle C P K= \angle C E P=\frac{L E}{2}$

$\angle P C K=\angle P C E$ (common angle)

$\Rightarrow \triangle C P K \sim \triangle C E P$

$\Rightarrow \frac{C P}{C E}=\frac{C K}{C P} \rightarrow (1)$

Observe that,

$C P=C D=\frac{C E}{2}$

$\Rightarrow \quad C K=\frac{C P}{2}=\frac{C D}{2}$ (from $(1)$)

Let $C D=x, P K=l, Q K=m$

$\Rightarrow \quad C K=\frac{x}{2} \quad \& \quad D K=\frac{x}{2}\ \&\ D E=x$

By Angle Bisector Theorem,

$\frac{P K}{P E}=\frac{D K}{D E}=\frac{x / 2}{x}=\frac{1}{2}$

$\Rightarrow P E=2l$, similarly $QE = 2m$

Perimeter of $\triangle A B C$ = $P E+Q E+P K+Q K$

$= 2l + 2m +l + m = 3(l+m) = 24$

$\Rightarrow |PQ| = l+m = 8$

Problem 12: Given $\triangle A B C$ with $\angle B=60^{\circ}$ and $\angle C=30^{\circ}$, let $P, Q, R$ be points on sides $B A, A C, C B$ respectively such that $B P Q R$ is an isosceles trapezium with $P Q | B R$ and $B P=Q R$. Find the maximum possible value of $\frac{2[A B C]}{[B P Q R]}$ where $[S]$ denotes the area of any polygon $S$

Solution:

Since, the problem asks for only ratios, we can assume AB = 1, AC = $\sqrt{3}$, BC = 2. Let AP $= x$, due to sin values,

$A Q=\sqrt{3} x$, $P Q=2 x$

Let h be the height of $\triangle A Q P$ on $Q P$,

$\frac{1}{2} h(P Q)=\frac{1}{2}(\sqrt{3} x) x \Rightarrow h=\frac{\sqrt{3} x}{2}$

Height of trapezium $=$ height of $\triangle A B C$ on BC - h

= $\frac{\sqrt{3}}{2}(1-x)$

Let $T$ be feet of $\perp$ from $P$ to $B C$,

$\Rightarrow \quad B T=B P \quad \cos 60=\frac{1-x}{2}$

$\Rightarrow \quad B R=P Q+2 B T$ (since it is isosceles trapezium)

$=2 x+1-x=1+x$

$\frac{2[A B C]}{[B P Q R]}=\frac{2 \times \frac{1}{2} \times \sqrt{3} \times 1}{\frac{1}{2} \times \text { height } \times \text { sum of } ||^{el} \text { sides }}=\frac{2 \sqrt{3}}{\frac{\sqrt{3}}{2}(1-x)(1+3 x)}$

$\frac{2[A B C]}{[B P Q R]}=\frac{4}{(1-x)(1+3 x)}=\frac{4}{\frac{4}{3}-\left(\sqrt{3} x-\frac{1}{\sqrt{3}}\right)^2}$

Note that this expression has no upper bound and hence no maximum value. Thus, let us change this question and find the minimum value. It happens when,

$\sqrt{3} x-\frac{1}{\sqrt{3}}=0 \Rightarrow x=\frac{1}{3}$

${Min}\left(\frac{2[A B C]}{[B P Q R]}\right)=\frac{4}{4 / 3}=3$

This question is solvable only if $P, Q, R$ lie inside the sides of the triangle.

Problem 13: Let $A B C$ be a triangle and let $D$ be a point on the segment $B C$ such that $A D=B C$. Suppose $\angle C A D=x^{\circ}, \angle A B C=y^{\circ}$ and $\angle A C B=z^{\circ}$ and $x, y, z$ are in an arithmetic progression in that order where the first term and the common difference are positive integers. Find the largest possible value of $\angle A B C$ in degrees.

Solution:

Since y < z, angle y is always acute and point D lie inside BC.

$x+z=2 y$ $\Rightarrow \quad \angle A D B=2 y$ & $\angle B A C=180-(y+z)$

Sine rules in $\triangle A B D, \triangle A B C$,

$\frac{A B}{A D}=\frac{\sin 2 y}{\sin y}=\frac{A B}{B C}$ & $\frac{A B}{B C}=\frac{\sin z}{\sin (y+z)}$

$\Rightarrow \quad \frac{\sin 2 y}{\sin y}=\frac{\sin z}{\sin (y+z)}$

$\Rightarrow \quad 2 \sin (y+z) \cos y=\sin z$

$\Rightarrow \quad \sin (y+z+y)+\sin (y+z-y)=\sin z$

$\Rightarrow \sin (2 y+z)=0$

either, $2 y+z=180^{\circ}$ or, $2 y+z=360^{\circ}$

$2 y+z=360^{\circ}$ is impossible because $y$ and $z$ are angles of $\triangle A B C$ and $y + z < 180^{\circ}$. So, $2y + z < 180^{\circ}$.

$2 y+z=180^{\circ} \Rightarrow \angle B A C=y$

Since, $x < y < z$ and all are positive integers,

$\Rightarrow 2 y+z>3 y$ $\Rightarrow 180^{\circ}>3 y$ $\Rightarrow y<60^{\circ}$

Hence, $y=59^{\circ}=\angle A B C$, is the largest integer angle possible with a common difference of $1^{\circ}$.

Problem 14: Let x, y, z be complex number such that

$\frac{x}{y+z}+\frac{y}{z+x}+\frac{z}{x+y}=9$

$\frac{x^2}{y+z}+\frac{y^2}{z+x}+\frac{z^2}{x+y}=64$

$\frac{x^3}{y+z}+\frac{y^3}{z+x}+\frac{x^3}{z+y}=488$

If $\frac{x}{y z}+\frac{y}{z x}+\frac{z}{x y}=\frac{m}{n}$ where $m, n$ are positive integers with ${GCD}(m, n)=1$, find $m+n$.

Solution:

$\left(\frac{x}{y+z}+\frac{y}{z+x}+\frac{z}{x+y}\right)(x+y+z)$

= $\frac{x^2}{y+z}+\frac{y^2}{z+x}+\frac{z^2}{x+y}+(x+y+z)$

$\Rightarrow 9(x+y+z)=64+(x+y+z)$

$\Rightarrow x+y+z=8 \rightarrow$ (1)

Similarly note that,

$\left(\frac{x^2}{y+z}+\frac{y^2}{z+x}+\frac{z^2}{x+y}\right)(x+y+z)$

$=\frac{x^3}{y+z}+\frac{y^3}{z+x}+\frac{z^3}{x+y}+ (x^2+y^2+z^2)$

$\Rightarrow 64(8)=488+x^2+y^2+z^2$

$\Rightarrow x^2+y^2+z^2=24\rightarrow$ (2)

From (1) and (2),

$x y+y z+z x=\frac{(x+y+z)^2-\left(x^2+y^2+z^2\right)}{2}=20 \rightarrow$ (3)

Given,

$\frac{x}{y+z}+1+\frac{y}{z+x}+1+\frac{z}{x+y}+1=9+3=12$

$\frac{1}{y+z}+\frac{1}{z+x}+\frac{1}{x+y}=\frac{12}{x+y+z}=\frac{3}{2}$ (from (1)) $\rightarrow$(4)

$\frac{1}{y+z}+\frac{1}{z+x}+\frac{1}{x+y}=\frac{12}{x+y+z}=\frac{3}{2}$

Observe that,

$x^2+y^2+z^2$= $\left(\frac{x}{y+z}+\frac{y}{z+x}+\frac{z}{x+y}\right)(x y+y z+z x)-x y z\left(\frac{1}{y+z}+\frac{1}{z+x}+\frac{1}{x + y}\right)$

From (2), (3), (4),

$24=9(20)-\frac{3 x y z}{2}$

$\Rightarrow x y z=104\rightarrow$ (5)

Divide (2) by (5),

$\frac{x^2+y^2+z^2}{x y z}=\frac{24}{104}$

$\Rightarrow \quad \frac{x}{y z}+\frac{y}{z x}+\frac{z}{x y}=\frac{3}{13}$

$\Rightarrow m=3, n=13$

$m+n=16$

Problem 15: Let $x, y$ be real numbers such that $x y=1$. Let $T$ and $t$ be the largest and the smallest values of the expression

(x+y)2−(xy)−2(x+y)2+(xy)−2.

If $T+t$ can be expressed in the form $\frac{m}{n}$ where $m, n$ are nonzero integers with ${GCD}(m, n)=$ 1 , find the value of $m+n$.

Solution:

$\frac{(x+y)^2-(x-y)-2}{(x+y)^2+(x-y)-2}=\frac{x^2+y^2-(x-y)}{x^2+y^2+(x-y)}=n$

$\Rightarrow \quad n-1=\frac{2(y-x)}{(y-x)^2-(y-x)+2}$, if $y=x \Rightarrow n=1$

Let $y \neq x$,

$\Rightarrow \quad n-1=\frac{2}{(y-x)+\frac{2}{(y-x)}-1}$

Note that " $n-1$ " is maximum when $(y-x)+\frac{2}{(y-x)}$ holds the least possible positive value and it is minimum when $(y-x)+\frac{2}{(y-x)}$ holds the largest negative value.

By AM-GM Inequality,

$|s|+\frac{2}{|s|} \ge 2 \sqrt{2}$, and the equality holds when $|s|=\sqrt{2}$

$\Rightarrow T=\frac{2}{2 \sqrt{2}-1}+1>1 ; \quad t=\frac{2}{-2 \sqrt{2}-1}+1<1$

$T+t=2+2\left(\frac{1}{2 \sqrt{2}-1}-\frac{1}{2 \sqrt{2}+1}\right)=2+2\left(\frac{2}{8-1}\right)$

$T+t= 18 + 7 = 25$

Problem 16: Let $a, b, c$ be reals satisfying

3ab+2=6b,3bc+2=5c,3ca+2=4a.

Let $\mathbb{Q}$ denote the set of all rational numbers. Given that the product $a b c$ can take two values $\frac{r}{s} \in \mathbb{Q}$ and $\frac{t}{u} \in \mathbb{Q}$, in lowest form, find $r+s+t+u$.

Solution:

$3 a b+2=6 b$ $\Rightarrow 2=3 b(2-a) \rightarrow (1)$

$3 b c+2=5 c$ $\Rightarrow 2=c(5-3 b) \rightarrow(2)$

$3 c a+2=4 a \rightarrow (3)$

From $(1)$,

$a=\frac{6 b-2}{3 b} \rightarrow(4)$

From $(2)$,

$c=\frac{2}{5-3 b}$ $\rightarrow (5)$

Substituting $(4)$ & $(5)$ in $(3)$,

$3\left(\frac{2}{5-3 b}\right)\left(\frac{6 b-2}{3 b}\right)+2=4\left(\frac{6 b-2}{3 b}\right)$

after simplification,

$27 b^2-39 b+14=0$

Let $y=3 b \Rightarrow 3 y^2-13 y+14=0$

$y=\frac{13 \pm \sqrt{13^2-3(4)(14)}}{2(3)}=\frac{13 \pm 1}{6}$

$\Rightarrow \quad y=\frac{7}{3}, 2$

$a b c=\left(\frac{6 b-2}{3 b}\right) \cdot\left(\frac{2}{5-3 b}\right)$

$=\frac{4}{3}\left(\frac{3 b-1}{5-3 b}\right)=\frac{4}{3}\left(\frac{y-1}{5-y}\right)$

upon substitution of value of $y$,

$a b c=\frac{2}{3}, \frac{4}{9}$

$r+s+t+u=2+3+4+9=18$

Problem 17: For a positive integer $n>1$, let $g(n)$ denote the largest positive proper divisor of $n$ and $f(n)=n-g(n)$. For example, $g(10)=5, f(10)=5$ and $g(13)=1, f(13)=12$. Let $N$ be the smallest positive integer such that $f(f(f(N)))=97$. Find the largest integer not exceeding $\sqrt{N}$.

Solution:

$f(f(f(N)))=97$

Let $f(m)=97$ $\Rightarrow m-g(m)=97 \Rightarrow g(m)=m-97$

$\Rightarrow m-97 \mid m$ and is the largest proper divisor of $m$

$m=k m-97 k$ $\Rightarrow 97 k=m(k-1)$

since $k$, $k-1$ are co-prime $\Rightarrow \ k-1 \mid 97$ $\Rightarrow k=2,98.$

$k=98$, will not work as $1(=98-97)$ is not the largest proper divisor of $98$

Hence, $k=2$ $\Rightarrow m=97 \times 2$ $\Rightarrow f(f(N))=97 \times 2$

Let $f(n)=97 \times 2$ $\Rightarrow g(n)=n-97 \times 2$

$\Rightarrow n-97 \times 2\ \text{divides}\ n \Rightarrow 97 \times 2k^{\prime}$ $=n\left(k^{\prime}-1\right)$ $\Rightarrow k^{\prime}-1 \mid 2 \times 97$

$Therefore, k^{\prime}=2,3,98,195$

$k^{\prime}=2 \Rightarrow n=97 \times 4$

$k^{\prime}=3 \Rightarrow n=97 \times 3$, and both of these satisfy that $g(n)=n-97 \times 2$

But for $k^{\prime}=98,195$, $\ g(n) \neq n-97 \times 2$

Therefore, n=f(N)=97×3,97×4

CASE 1:

$f(N)=97 \times 4$ $\Rightarrow g(N)=N-97 \times 4$

$\Rightarrow 97 \times 4 k^{\prime \prime}=N\left(k^{\prime}-1\right)$

$\Rightarrow \quad k^{\prime \prime}=2,3,5,98,195,389\ ;\ N=388\left(\frac{k^{\prime \prime}}{k^{\prime \prime}-1}\right)$

Since, the question asks for smallest $N$, we use the largest value of $k^{\prime \prime}$ which gives the smallest $N$.

So, $k^{\prime \prime}$ = $389$. Since $389$ is a prime number, it follows that $g(N)=N-97 \times 4$. Hence, $N=389$ is a valid smallest solution for CASE 1.

CASE 2:

$f(N)=97 \times 3 \Rightarrow g(N)=N-91 \times 3$

$\Rightarrow 97 \times 3 k^{\prime \prime \prime}=N\left(k^{\prime \prime \prime}-1\right)$

$\Rightarrow k^{\prime \prime \prime} = 2, 4, 98, 292$

Since $292$ is not a prime, $\ g(292) \neq 292-97 \times 3$, so $N \neq 292$

If $k^{\prime \prime \prime}=98$ $\Rightarrow N=3 \times 98=2 \times 147=294$

but $g(2 \times 147)=147 \neq 2 \times 147-97 \times 3$

hence, $N \neq 294$

If $k^{\prime \prime \prime}=4 \Rightarrow N=97 \times 4=2 \times 194=388$

but $g(388)=194 \neq 388-97 \times 3$

hence $N \neq 388$

Now for $k^{\prime \prime \prime}=2 \Rightarrow N>389$

Hence, $N=389$ is the smallest positive integer such that $f(f(f(N)))=97$

$\lfloor\sqrt{N}\rfloor=\lfloor\sqrt{389}\rfloor=19$

Problem 18: Let $m, n$ be natural numbers such that

m+3n−5=2LCM(m,n)−11GCD(m,n)
Find the maximum possible value of $m+n$.

Solution:

Let $gcd (m,n) = d$

$\Rightarrow m = dp$, $n =dq$, where $gcd (p,q) = 1$

$mn = gcd (m,n) \times lcm (m,n)$ $\Rightarrow lcm (m,n) = dpq$

Substituting them in the equation,

$d p+3 d q-5=2 d p q-11 d$

$\Rightarrow d(p+3 q-2 p q+11)=5$

$d=1$ (or) $5$

CASE 1:

$d = 1$ $\Rightarrow p+3 q-2 p q+11=5$

By rearranging and taking the terms common,

$(2 q-1)(2 p-3)=15$

Observe that $p, q \in \mathbb{N}$ $\Rightarrow 2 q-1>0$ $\Rightarrow 2 p-3>0$ and so, we consider only positive divisors of 15.

$2 q-1=1$; $2 p-3=15$

$2 q-1 = 3\ ;\ 2p-3 = 5$

$2 q-1 = 5\ ;\ 2p-3 = 3$

$2 q-1 = 15\ ;\ 2p-3 = 1$

$\Rightarrow (p, q)=(9,1); (4,2); (3,3); (2,8)$

But, the last $3$ solutions are invalid, as the $gcd (p,q)$ is $1$.

$\Rightarrow (p, q)=(9,1)$

$(m, n)=(d p, d q)=(9, 1)$

CASE 2:

$d = 5$ $\Rightarrow p+3 q-2 p q+11=1$

$\Rightarrow (2 q-1)(2 p-3)=23$

$2 q-1=1$; $2 p-3=23$

$2 q-1=23$; $2 p-3=1$

$\Rightarrow (p, q)=(13,1) ; (2,12)$

The latter solution is invalid.

$\Rightarrow(p, q)=(13,1)$

$\Rightarrow (m, n)=(d p, d q)=(65,5)$

Hence, $Max(m+n) = 65+5 = 70$

Problem 19: Consider a string of $n$ 1's. We wish to place some $+$ signs in between so that the sum is $1000$. For instance, if $n=190$, one may put $+$ signs so as to get $11$ ninety times and $1$ ten times, and get the sum $1000$. If $a$ is the number of positive integers $n$ for which it is possible to place $+$ signs so as to get the sum $1000$ , then find the sum of the digits of $a$.

Solution: Observe that after inserting the "+" signs, the numbers that one would get are possibly $1, 11, 111$. Rest all the numbers are greater than $1000$. After splitting let the numbers of $1$'s, $11$'s, and $111$'s be $k_1, k_2, k_3$ respectively.

$\Rightarrow k_1+11 k_2+111 k_3=1000$; $k_1+2 k_2+3 k_3=n$

Now we just need to find the number of possible $n$ 's such that $k_1+11 k_2+11 k_3=1000$ and we need not find the number of Solutions of $k_1, k_2, k_3$, since $k_1, k_2, k_3 \in \mathbb{N}_0$

$n=1000-9 k_2-108 k_3$ gives the no. of values of n for $k_2, k_3 \ge \ 0$ and also we need $k_1 \ge 0 \Rightarrow n-\left(3 k_3+2 k_2\right) \ge 0$

For $k_2, k_3 \ge 0$,

The Final two equations are,

$n=1000-9\left(12 k_3+k_2\right)\ ;\ n-\left(3 k_3+2 k_2\right) \ge 0$

Now $12 k_3+k_2$ can take all the values from 0 to 111 as there always exist a quotient and remainder when divide by 12 .

$\Rightarrow n$ can take 112 values, but out of these some values will have $n-\left(3 k_3+2 k_2\right)<0$ & we need to eliminate them.

$\left(k_3, k_2\right)=(9,3) ;(9,2) ; (9,1) ;(8,11)$ are the ones that contradict, which correspond to "$n$" value of $1,10,19,37$. For these "$n$" values, whatever $k_2, k_3$ values that one can take, the second equation goes invalid because $k_2<12$ is the best choice for the pair ($k_2, k_3$) otherwise $k_2$ shoots up by $12$, making the second equation worse than before

$a=112-4=108$

Sum of digits of $a$ = $1+0+8=9$

Problem 20: For an integer $n \geq 3$ and a permutation $\sigma=\left(p_1, p_2, \ldots, p_n\right)$ of ${1,2, \ldots, n}$, we say $p_l$ is a landmark point if $2 \leq l \leq n-1$ and $\left(p_{l-1}-p_l\right)\left(p_{l+1}-p_l\right)>0$. For example, for $n=7$, the permutation $(2,7,6,4,5,1,3)$ has four landmark points: $p_2=7, p_4=4, p_5=5$ and $p_6=1$. For a given $n \geq 3$, let $L(n)$ denote the number of permutations of ${1,2, \ldots, n}$ with exactly one landmark point. Find the maximum $n \geq 3$ for which $L(n)$ is a perfect square.

Solution: We represent the permutation sequence in a graphical form. For example, ${1,4,2,3}$ and ${2,1,3,4}$ are represented below respectively,

Observe that each of the bends are nothing but a "Landmark point". Bend that looks like a hill are "HILL" and that look like a valley are "VALLEY".

Since there is only one bend for the problem, either it must be "HILL" (or) a "VALLEY" as shown below,

Observe that in a HILL structure, the topmost point correspond to the largest number " $n$ " and in a VALLEY, the bottom point correspond to the smallest number "$1$". Now in each structure, the two sides wings are non-empty and are either in ascending (or) descending order and hence we just need to choose non-empty subsets of the remaining "$n-1$ " element set (since the largest (or) smallest element is already filled up in the vertex) for a wing and it automatically gets arranged.

Number of non-empty subsets of the "$n-1$" element set = ${}^{n-1} C_{1} + {}^{n-1} C_{2} + \cdots + {}^{n-1} C_{n-2}$

$=2^{n-1}-2$

Notice that, We left out ${}^{n-1} C_{n-1}$, because the other side wing must also be non-empty

Number of HILL (or) VALLEY of $n$-element set = $2\left(2^{n-1}-2\right)$

$\Rightarrow L(n)=2^n-4$

Let $m^2=2^n-4 \Rightarrow\left(\frac{m}{2}\right)^2=m_0^2=2^{n-2}-1, m, m_0 \in \mathbb{N}$ observe that $m_0^2 \equiv 3 (mod\ 4)$, for all $n \ge 4$ but we know that no perfect square leaves a remainder $3$ when divided by $4$

$\Rightarrow L(3)=4$ $\Rightarrow n=3$ is the only such value.

Problem 21: An ant is at a vertex of a cube. Every 10 minutes it moves to an adjacent vertex along an edge. If $N$ is the number of one hour journeys that end at the starting vertex, find the sum of the squares of the digits of $N.$

Solution:

In the cube, mark the alternate vertices with "$.$" and " $\times$ " as shown in the diagram. Note that for any move, the ant alternates between a dot and a cross in each move. Suppose the ant starts from the vertex $A$ and let the diagonally opposite vertex of $A$ be $B$.

According to the problem, we need to find the number of ways in which the ant covers 6 edges (not necessarily distinct) and come back to $A$ after its $6^{\text {th }}$ move.

Since, the ant alternates the dot and the cross for any possible move of the ant, it should be at a cross after its 5th move. Note that all the cross expect $B$ are adjacent to $A$, and hence it can reach $A$. So, we need to subtract the no. of ways to reach $B$ from the total number of ways for the $5$ moves.

There are a total of $3$ paths to choose for the ant from each vertex and hence total of $3^5$ ways for the 5 moves

$N=3^5$ - (no. of ways to reach $B$ in $5$ moves)

After $4$ moves, the ant must be at "dot" and all the dots except $A$ are adjacent to $B$ and hence it can move to $B$. Hence,

No. of ways to reach $B$ in $5$ moves = $3^4$ - (no. of ways to reach $A$ in $4$ moves)

Similarly arguing we get,

No. of ways to reach $A$ in $4$ moves = $3^3$ - (no. of ways to reach $B$ in $3$ moves)

So we get,

$N = 3^5$ - ($3^4$ - ($3^3$ - ($3^2$ - ($3$ - (no. of ways to reach $B$ in $1$ move)))))

Since $A$ and $B$ are not adjacent and the ant starts from $A$, there is no way for the ant to reach $B$ in $1$ move.

$N=3^5-3^4+3^3-3^2+3=183$

Sum of squares of digits of $N = 1^2+8^2+3^2=74$

Problem 22: A binary sequence is a sequence in which each term is equal to $0$ or $1$ . A binary sequence is called friendly if each term is adjacent to at least one term that is equal to $1$ . For example, the sequence $0,1,1,0,0,1,1,1$ is friendly. Let $F_n$ denote the number of friendly binary sequences with $n$ terms. Find the smallest positive integer $n \geq 2$ such that $F_n>100$.

Solution:

Let $B_n$ denote the number of friendly binary sequences with $n$ terms that start with $1$. Let us find a recursive relation between $F_n$ and $B_n$.

Consider a sequence that starts with $1$. Except the $1^{st}$ digit, the remaining "$n-1$" digits can be filled with $B_n-1$ sequences that start with and are hence friendly.

Suppose the $2^{nd}$ digit is $0,$ then that $0$ is adjacent to $1$. So, we just care about whether (or) not the remaining "$n-2$" digit sequence is friendly (or) not and so, there are $F_{n-2}$ ways for it to be friendly. Hence,

$B_n=B_{n-1}+F_{n-2}$

Now consider a sequence of $n$ digits that starts with $0$.

Observe that the $2^{nd}$ digit must be a $1$, otherwise the first $0$ is not adjacent to a $1$.

Hence, the last "$n-1$" digit is nothing but a friendly sequence that starts with $1$ and there are $B_{n-1}$ sequences possible. Also, $F_n-B_n$ gives the number of sequence with $n$ digits that starts with $0$.

$\Rightarrow F_n-B_n=B_{n-1}$

Hence the recurrence relations are:

$B_n=B_{n-1}+F_{n-2}\ ;\ F_n=B_n+B_{n-1} \rightarrow$ (1)

Combining them we get,

$B_n=B_{n-1}+B_{n-2}+B_{n-3} \rightarrow$ (2)

and note that $B_2=2, B_3=3 \ (101,110,111)$,

$B_4=6(1001,1010,1101,1110,1011,1111)$

Using equation (2),

$B_5=6+3+2=11$, $B_6=11+6+3=20$, $B_7=20+11+6=37$, $B_8=37+20+11=68$

Using equation (1),

$F_3=5$, $F_4=9$, $F_5=11+6=17$, $F_6=20+11=31$, $F_7=37+20=57$, $F_8=68+37=105 > 100$

$\Rightarrow n=8$

Problem 23: In a triangle $A B C$, the median $A D$ divides $\angle B A C$ in the ratio $1: 2$. Extend $A D$ to ?, $E$ such that $E B$ is perpendicular $A B$. Given that $B E=3, B A=4$, find the integer nearest to $B C^2$.

Solution:

Let $\angle B A E=\theta \Rightarrow \angle C A E=2 \theta$

Given that $\sin \theta=\frac{3}{5}, \cos \theta=\frac{4}{5} \Rightarrow 30^{\circ}<\theta<45^{\circ}$

Hence, $\angle B A C=3 \theta>90^{\circ}$ is obtuse and $\angle A B C$ will be acute, so the point E lies outside $\triangle A B C$ as shown in the figure

$\frac{[A B D]}{[A C D]}=\frac{\frac{1}{2}\times h \times B D}{\frac{1}{2}\times h \times C D}$ $=1=\frac{\frac{1}{2}(A B)(A D) \sin \theta}{\frac{1}{2}(A C)(A D)\sin 2 \theta}$ (Since BD = CD)

$\Rightarrow \quad A C=\frac{4}{2 \cos \theta}=\frac{4}{2(4 / 5)}$ $\Rightarrow A C=\frac{5}{2}$

$\cos 3 \theta=\cos \angle B A C$ $=4 \cos ^3 \theta-3 \cos \theta=-\frac{44}{125}$

By cosine law in $\triangle A B C$ for the $\angle B A C$,

$\cos 3 \theta=\frac{A B^2+A C^2-B C^2}{2 A B \cdot A C}$ $=\frac{4^2+\left(\frac{5}{2}\right)^2-B C^2}{2 \times 4 \times \frac{5}{2}}=-\frac{44}{125}$

$\Rightarrow B C^2=16+\frac{25}{4}+\frac{880}{125}$

$=29+\frac{1}{4}+\frac{1}{25}$

$\Rightarrow B C^2=29.29$ units $^2$

Therefore, integer nearest to $B C^2$ = $29$

Problem 24: Let $N$ be the number of ways of distributing 52 identical balls into 4 distinguishable boxes such that no box is empty and the difference between the number of balls in any two of the boxes is not a multiple of 6 . If $N=100 a+b$, where $a, b$ are positive integers less than 100 , find $a+b$.

Solution:

The number of ball in the boxes are in the form
$6k+r\ ;\ r=\{0, 1, 2, 3, 4, 5\}$
Let the number of balls in the boxes be $6k+a$, $6k+b$, $6k+c$, $6k+d$, respectively, where $a, b, c, d \in r$ and are different from each other.

So, $52-(a+b+c+d) = 6n$
That gives $a+b+c+d =10$ and no other values are possible to obtain distinct remainders

$\Rightarrow n = 7$

CASE 1:

So, the remainders are $1,2,3,4$ and can be arranged $4!$ ways.
Now there are $7$ identical collection of $6$ balls each which we have to divide it into $4$ distinct boxes.
Using stars and bars method we get that,
There are ${ }^{10} C_3$ = $120$ ways to distribute them in those distinct boxes
So total number of ways is $120 \times 24 = 2880$

CASE 2:

The remainders can also be $0, 2, 3, 5\ \text{(or)}\ 0, 1, 4, 5$ as it sums up to $10$ as well

There are no more remainders which add up to $10$

Hence we just get $3 \times 2880$ in total

But now, there could be some empty boxes due to that $0$ remainder and hence we need to subtract that out!, which is,
$4(2(3!) \times { }^{9} C_2) = 1728$

$N = 3\times2880 - 1728 = 6912$
$a = 69\ ;\ b = 12$
Hence, $a+b = 81$

## Solutions of IOQM 2022

Problem 1: A triangle $A B C$ with $A C=20$ is inscribed in a circle $\omega$. A tangent $t$ to $\omega$ is drawn through $B$. The distance of $t$ from $A$ is $25$ and that from $C$ is $16$. If $S$ denotes the area of the triangle $A B C$, find the largest integer not exceeding $\frac{S}{20}$.

Solution:

Let $O$ be the circumcentre of $\triangle ABC$ and let $M, N$ be the foot of perpendiculars from $A$ and $C$ to the tangent $t$ respectively

$O T =\sqrt{R^2-(25-R)^2}=5 \sqrt{2 R-25}=B M$

$A B=\sqrt{A M^2+B M^2}=\sqrt{25^2+25(2 R-25)}=5 \sqrt{2 R}$

Similarly,

$O T=4 \sqrt{2 R-16}=B N$

$B C=\sqrt{B N^2+C N^2}=4 \sqrt{2 R}$

$[A B C]=\frac{1}{2} A C \times B C \times \sin C$

we know that,

$A B=2 R \sin C$

$\Rightarrow \sin C=\frac{5 \sqrt{2 R}}{2 R}=\frac{5}{\sqrt{2 R}}$

$\Rightarrow \ [A B C] =\frac{1}{2} \times 20 \times 4 \sqrt{2 R} \times \frac{5}{\sqrt{2 R}}=200=S$

Therefore, $\frac{S}{20}=10$

Problem 2: In a parallelogram $A B C D$, a point $P$ on the segmènt $A B$ is taken such that $\frac{A P}{A B}=\frac{61}{2022}$ and a point $Q$ on the segment $A D$ is taken such that $\frac{A Q}{A D}=\frac{61}{2065}$. If $P Q$ intersects $A C$ at $T$, find $\frac{A C}{A T}$ to the nearest integer.

Solution:

Let $A B = l, A D = b$.

$\Rightarrow A P=\frac{61 l}{2022}$ ; $A Q=\frac{61 b}{2065}$

Draw a line parallel to PQ that passes through B and let it intersect AD at L. Since, $\triangle A P Q \sim \triangle A B L$

$\Rightarrow \frac{A L}{A Q}=\frac{A B}{A P} \Rightarrow A L=\frac{2022 b}{2065}$

Hence, $L$ is a point inside the segment $\overline{A D}$

Observe that,

$\triangle AXL \sim \triangle CXB$, since $A D || B C$

$\Rightarrow \frac{A X}{C X}=\frac{A L}{B C}=\frac{2022}{2065}$

$\Rightarrow \frac{A X}{A C}=\frac{1}{1+\frac{C X}{A X}}=\frac{2022}{4087}$

Since $P Q || B L$,

$\Rightarrow \frac{A T}{A X}=\frac{A P}{A B}=\frac{61}{2022}$

$\frac{A C}{A T}=\frac{4087}{61}=67$

Problem 3: In a trapezoid $A B C D$, the internal bisector of angle $A$ intersects the base $B C$ (or its extension) at the point $E$. Inscribed in the triangle $A B E$ is a circle touching the side $A B$ at $M$ and side $B E$ at the point $P$. Find the angle $D A E$ in degrees, if $A B: M P=2$.

Solution:

Let, $\angle D A E=\theta \quad \Rightarrow \quad \angle A E B=\theta$ (since $D A || B E$)

Hence, $\triangle A B E$ is an isoceles triangle.

All of these arguments are valid even if the point $E$ lies outside of the side $B C$, but we assume that $B C$ is one of the parallel sides of the trapezoid for this solution.

Since, $B M$ and $B P$ are tangents from a common point $B$ to the circle, $B M = B P$

Therefore, $\triangle B M P \sim \triangle B A E$

Let, $P M = x, A B = 2x$ and $A E = y$

$\Rightarrow \frac{B M}{A B}=\frac{P M}{A E} \Rightarrow B M=\frac{2 x^2}{y}=B P$

Since $\triangle A B E$ is isoceles, $A N = N E$ by symmetry

$\Rightarrow A N=\frac{y}{2}=A M$ (since, tangents are equal for common points)

$\Rightarrow A M+B M=A B$

$\Rightarrow \frac{y}{2}+\frac{2 x^2}{y}=2 x$

$\Rightarrow (2 x-y)^2=0$

$\Rightarrow \frac{y}{x}=2$

Since $\triangle A B E$ is isoceles, $\angle B N A=\angle B N E=90^{\circ}$, since $N$ is the midpoint of $A E$

$\Rightarrow \cos \theta=\frac{A N}{A B}=\frac{y / 2}{2 x}=\frac{1}{2}$

$\Rightarrow \theta=60^{\circ}$

Problem 4: Starting with a positive integer $M$ written on the board, Alice plays the following game: in each move, if $x$ is the number on the board, she replaces it with $3 x+2$. Similarly, starting with a positive integer $N$ written on the board, Bob plays the following game: in each move, if $x$ is the number on the board, he replaces it with $2 x+27$. Given that Alice and Bob reach the same number after playing 4 moves each, find the smallest value of $M+N$.

Solution:

$81x+80 = 16y+405$
$81x-16y = 325$
The solution is
$x=325-16k$ , $y=1625-81k$
And the least possible values are $x=5$, $y=5$
Hence, $Min(x+y) = 10$

Problem 5: Let $m$ be the smallest positive integer such that $m^2+(m+1)^2+\cdots+(m+10)^2$ is the square of a positive integer $n$. Find $m+n$.

Solution:

$n^2=m^2+(m+1)^2+\cdots+(m+10)^2$

we know that, $\quad 1^2+2^2+\cdots+k^2=\frac{k(k+1)(2 k+1)}{6}$

$\Rightarrow n^2=\frac{(m+10)(m+11)(2 m+21)}{6}-\frac{(m-1) m(2 m-1)}{6}$

After Simplification,

$n^2=11\left(m^2+10 m+35\right)=11\left((m+5)^2+10\right)$

Let $y=m+5$,

$n^2=11\left(y^2+10\right)$, since $11$ is a prime $\Rightarrow 11$ divides $y^2+10$

$\Rightarrow \quad y^2 \equiv 1 \quad(\bmod 11)$

$\Rightarrow \quad y= 11s \pm 1, s \in \mathbb{N}$

Hence,
$\left(\frac{n}{11}\right)^2=11 s^2 \pm 2 s+1=$ Perfect square

Now substituting $s=1,2$, we obtain a perfect square for $s=2$ and a "+" sign as follows,

$\left(\frac{n}{11}\right)^2=11(2)^2+2(2)+1=7^2 \Rightarrow n=77$

$y=11 s+1=11(2)+1=23=m+5 \Rightarrow m=18$

$m+n=18+77=95$

Problem 6: Let $a, b$ be positive integer satisfying $a^3-b^3-a b=25$. Find the largest possible value of $a^2+b^3$

Solution:

$a, b \in \mathbb{N}$,

$a^3-b^3-a b=25$

$(a-b)\left[a^2+b^2+a b\right]-a b=25$

$(a-b) \left[(a-b)^2+3 a b\right]-a b=25$

Note that if $a-b \leq 0$, then $LHS < 0$. So, $a-b>0$

$(a-b)^3+3 a b(a-b)-a b=25$

$\Rightarrow (a-b)^3+a b[3(a-b)-1]=25$

Observe that, $3(a-b)-1>0$

$\Rightarrow a-b=1\text{ (or) }2$, else $LHS > 25$

Let $a - b = 2$,

$\Rightarrow 8+a b(5)=25$, but $5\not|\ 8$, hence contradiction

Let $a-b=1$,

$\Rightarrow 1+a b(2)=25 \Rightarrow a b=12$

$\Rightarrow a=4, b=3$

${Max}\left(a^2+b^3\right)=4^2+3^3=43$

Problem 7: Find the number of ordered pairs $(a, b)$ such that $a, b \in{10,11, \ldots, 29,30}$ and ${GCD}(a, b)+{LCM}(a, b)$ $=a+b$.

Solution:

Let $gcd(a, b) = d$
So, $a=dp$ and $b=dq$ with $gcd(p,q)=1$
Let $b>a$ then $q>p$
So $lcm(a,b)=aq=bp=apq > a+b$ if $p,q>1$, which can be verified easily
So one of $p,q$ is $1$ or both $p,q$ is $1$
One of $p,q$ is $1$ implies one of $a,b$ is multiple of another.
That gives us $(10,20),(10,30),(11,22),…,(15,30)$ that is $7$ pair.
If $p=q=1$ then $a=b$ then there are $21$ possible pair.
So total number of ordered pairs is $21+2 \times 7=35$

Problem 8: Suppose the prime numbers $p$ and $q$ satisfy $q^2+3 p$ = $197 p^2+q$. Write $\frac{q}{p}$ as $l+\frac{m}{n}$, where $l, m, n$ are positive integer, $m<n$ and ${GCD}(m, n)=1$. Find the maximum value of $l+m+n$.

Solution:

$q^2+3 p=197 p^2+q \Rightarrow q(q-1)=p(197 p-3) \rightarrow(1)$

Observe that prime $q>p \Rightarrow p \mid q-1$

So, let $q=k_1 p+1, k_1 \in \mathbb{N}$

Now multiply $k_1^2$ throughout equation $(1)$,

$k_1^2 q(q-1)=k_1 p\left(197 k_1 p-3 k_1\right)$ = $(q-1)\left(197 q-197-3 k_1\right)$

$\Rightarrow \quad k_1^2 q=197 q-197-3 k_1$

$\Rightarrow \quad\left(197-k_1^2\right) q=3 k_1+197 \rightarrow (2)$

Hence, $k_1$ can take values from $1$ to $14$

But $\quad 197-k_1^2 \leq \frac{3 k_1+197}{2}$ (from $(2)$)

$\Rightarrow \quad 10 \leq k_1 \leq 14$

Substituting these $5$ values for $k_1$, we observe that $q$ is an integer only for $k_1=14$

$q=\frac{3 k_1+197}{197-k_1^2}=239 \Rightarrow q=239$, which is a prime

$q=k_1 p+1 \quad \Rightarrow \quad p=17$

$\frac{q}{p}=\frac{239}{17}=14+\frac{1}{17} \Rightarrow l=14, m=1, n=17$

$l+m+n=14+1+17=32$

Problem 9: Two sides of an integer sided triangle have lengths 18 and $x$. If there are exactly 35 possible integer values $y$ such that $18, x, y$ are the sides of a non-degenerate triangle, find the number of possible integer values $x$ can have.

Solution:

$x$ is given to us and $x, y$ are integers

By triangle inequality, (for non-degenerate triangle),

CASE 1: $18 \geq x$

$18-x<y<18+x$

$\Rightarrow \quad y$ can take $2 x-1$ integer values

$\Rightarrow \quad 2 x-1=35 \Rightarrow x=18$

CASE 2: $18<x$

$\Rightarrow \quad x-18<y<x+18$

$\Rightarrow y$ can take $35$ integer values for any $x>18$

So, in this case $x$ can take all integer values $>18$

Problem 10: Consider the 10-digit number $M=9876543210$. We obtain a new 10-digit number from $M$ according to the following rule: we can choose one or more disjoint pairs of adjacent digits in $M$ and interchange the digits in these chosen pairs, keeping the remaining digits in their own places. For example, from $M=9876543210$, by interchanging the 2 underlined pairs, and keeping the others in their places, we get $M_1=9 \overline{78} 6 \overline{45} 3210$. Note that any number of (disjoint) pairs can be interchanged. Find the number of new numbers that can be so obtained from $M$.

Solution:

$M=9876543210$

Instead of underlining the adjacent pairs to be interchanged, we put an arrow mark on the first number of the underlined pair. For eg.,

Now, note the number of underlined pairs possible equals the number of all possible combinations of arrow marks put on $987654321$ that are NOT ADJACENT.

So, we just find the number of ways to choose any number $(\neq 0)$ of numbers from $987654321$ that are NOT ADJACENT.

Let us find the number of ways to choose "$r$" non-consecutive numbers from the set $\{1,2,3,....,n\}$. Observe that there is a bijection of "$r$" non-consecutive numbers from $\{1,2,3,....,n\}$ with choosing any "$r$" numbers from $\{1,2,3,....,n-r+1\}$ which is established as follows, let $\{x_1, x_2, x_3, ... x_r\}$ be the non-consecutive $r$ element subset of $\{1,2,3,....n\}$ in the increasing order, then

$\{x_1, x_2, x_3, \ldots, x_n\}\longleftrightarrow\{x_1, x_2-1, x_3-2, \ldots, x_r-r+1\}$

where, $\{x_1, x_2-1, x_3-2, \ldots, x_r-r+1\}$ = $r$ element subset of $\{1,2,3,....,n-r+1\}$

So, number of ways = ${}^{n-r+1} C_r$

Using the above formula for $n=9, \forall r>0$ we get,

Therefore, Number of new numbers $M$ = ${}^{9} C_1$ + ${}^{8} C_2$ + ${}^{7} C_3$ + ${}^{6} C_4$ + ${}^{5} C_5$

$=88$

Problem 11: Let $A B$ be a diameter of a circle $\omega$ and let $C$ be a point on $\omega$, different from $A$ and $B$. The perpendicular from $C$ intersects $A B$ at $D$ and $\omega$ at $E(\neq C)$. The circle with centre at $C$ and radius $C D$ intersects $\omega$ at $P$ and $Q$. If the perimeter of the triangle $P E Q$ is $24$ , find the length of the side $P Q$.

Solution:

Let,

$\angle P Q D=\alpha$, since $C$ is centre of $2^{\text {nd }}$ circle

$\Rightarrow \angle P C D=2 \alpha=\angle P C E=\angle P Q E=\angle P Q D+\angle D Q E$

$\Rightarrow \quad \angle D Q E=\alpha=\angle P Q D$

Hence, $Q D$ and similarly $P D$ are internal angle bisectors of $\triangle Q P E$. So, $D$ is the incentre of $\triangle Q P E$ and hence $C E$ is the angle bisector of $\angle P E Q$.

Observe that $O D \perp C E \Rightarrow D$ is the midpoint of chord $C E$.

Let $k$ be the intersection of $C E$ and $P Q$

$\angle C P K= \angle C E P=\frac{L E}{2}$

$\angle P C K=\angle P C E$ (common angle)

$\Rightarrow \triangle C P K \sim \triangle C E P$

$\Rightarrow \frac{C P}{C E}=\frac{C K}{C P} \rightarrow (1)$

Observe that,

$C P=C D=\frac{C E}{2}$

$\Rightarrow \quad C K=\frac{C P}{2}=\frac{C D}{2}$ (from $(1)$)

Let $C D=x, P K=l, Q K=m$

$\Rightarrow \quad C K=\frac{x}{2} \quad \& \quad D K=\frac{x}{2}\ \&\ D E=x$

By Angle Bisector Theorem,

$\frac{P K}{P E}=\frac{D K}{D E}=\frac{x / 2}{x}=\frac{1}{2}$

$\Rightarrow P E=2l$, similarly $QE = 2m$

Perimeter of $\triangle A B C$ = $P E+Q E+P K+Q K$

$= 2l + 2m +l + m = 3(l+m) = 24$

$\Rightarrow |PQ| = l+m = 8$

Problem 12: Given $\triangle A B C$ with $\angle B=60^{\circ}$ and $\angle C=30^{\circ}$, let $P, Q, R$ be points on sides $B A, A C, C B$ respectively such that $B P Q R$ is an isosceles trapezium with $P Q | B R$ and $B P=Q R$. Find the maximum possible value of $\frac{2[A B C]}{[B P Q R]}$ where $[S]$ denotes the area of any polygon $S$

Solution:

Since, the problem asks for only ratios, we can assume AB = 1, AC = $\sqrt{3}$, BC = 2. Let AP $= x$, due to sin values,

$A Q=\sqrt{3} x$, $P Q=2 x$

Let h be the height of $\triangle A Q P$ on $Q P$,

$\frac{1}{2} h(P Q)=\frac{1}{2}(\sqrt{3} x) x \Rightarrow h=\frac{\sqrt{3} x}{2}$

Height of trapezium $=$ height of $\triangle A B C$ on BC - h

= $\frac{\sqrt{3}}{2}(1-x)$

Let $T$ be feet of $\perp$ from $P$ to $B C$,

$\Rightarrow \quad B T=B P \quad \cos 60=\frac{1-x}{2}$

$\Rightarrow \quad B R=P Q+2 B T$ (since it is isosceles trapezium)

$=2 x+1-x=1+x$

$\frac{2[A B C]}{[B P Q R]}=\frac{2 \times \frac{1}{2} \times \sqrt{3} \times 1}{\frac{1}{2} \times \text { height } \times \text { sum of } ||^{el} \text { sides }}=\frac{2 \sqrt{3}}{\frac{\sqrt{3}}{2}(1-x)(1+3 x)}$

$\frac{2[A B C]}{[B P Q R]}=\frac{4}{(1-x)(1+3 x)}=\frac{4}{\frac{4}{3}-\left(\sqrt{3} x-\frac{1}{\sqrt{3}}\right)^2}$

Note that this expression has no upper bound and hence no maximum value. Thus, let us change this question and find the minimum value. It happens when,

$\sqrt{3} x-\frac{1}{\sqrt{3}}=0 \Rightarrow x=\frac{1}{3}$

${Min}\left(\frac{2[A B C]}{[B P Q R]}\right)=\frac{4}{4 / 3}=3$

This question is solvable only if $P, Q, R$ lie inside the sides of the triangle.

Problem 13: Let $A B C$ be a triangle and let $D$ be a point on the segment $B C$ such that $A D=B C$. Suppose $\angle C A D=x^{\circ}, \angle A B C=y^{\circ}$ and $\angle A C B=z^{\circ}$ and $x, y, z$ are in an arithmetic progression in that order where the first term and the common difference are positive integers. Find the largest possible value of $\angle A B C$ in degrees.

Solution:

Since y < z, angle y is always acute and point D lie inside BC.

$x+z=2 y$ $\Rightarrow \quad \angle A D B=2 y$ & $\angle B A C=180-(y+z)$

Sine rules in $\triangle A B D, \triangle A B C$,

$\frac{A B}{A D}=\frac{\sin 2 y}{\sin y}=\frac{A B}{B C}$ & $\frac{A B}{B C}=\frac{\sin z}{\sin (y+z)}$

$\Rightarrow \quad \frac{\sin 2 y}{\sin y}=\frac{\sin z}{\sin (y+z)}$

$\Rightarrow \quad 2 \sin (y+z) \cos y=\sin z$

$\Rightarrow \quad \sin (y+z+y)+\sin (y+z-y)=\sin z$

$\Rightarrow \sin (2 y+z)=0$

either, $2 y+z=180^{\circ}$ or, $2 y+z=360^{\circ}$

$2 y+z=360^{\circ}$ is impossible because $y$ and $z$ are angles of $\triangle A B C$ and $y + z < 180^{\circ}$. So, $2y + z < 180^{\circ}$.

$2 y+z=180^{\circ} \Rightarrow \angle B A C=y$

Since, $x < y < z$ and all are positive integers,

$\Rightarrow 2 y+z>3 y$ $\Rightarrow 180^{\circ}>3 y$ $\Rightarrow y<60^{\circ}$

Hence, $y=59^{\circ}=\angle A B C$, is the largest integer angle possible with a common difference of $1^{\circ}$.

Problem 14: Let x, y, z be complex number such that

$\frac{x}{y+z}+\frac{y}{z+x}+\frac{z}{x+y}=9$

$\frac{x^2}{y+z}+\frac{y^2}{z+x}+\frac{z^2}{x+y}=64$

$\frac{x^3}{y+z}+\frac{y^3}{z+x}+\frac{x^3}{z+y}=488$

If $\frac{x}{y z}+\frac{y}{z x}+\frac{z}{x y}=\frac{m}{n}$ where $m, n$ are positive integers with ${GCD}(m, n)=1$, find $m+n$.

Solution:

$\left(\frac{x}{y+z}+\frac{y}{z+x}+\frac{z}{x+y}\right)(x+y+z)$

= $\frac{x^2}{y+z}+\frac{y^2}{z+x}+\frac{z^2}{x+y}+(x+y+z)$

$\Rightarrow 9(x+y+z)=64+(x+y+z)$

$\Rightarrow x+y+z=8 \rightarrow$ (1)

Similarly note that,

$\left(\frac{x^2}{y+z}+\frac{y^2}{z+x}+\frac{z^2}{x+y}\right)(x+y+z)$

$=\frac{x^3}{y+z}+\frac{y^3}{z+x}+\frac{z^3}{x+y}+ (x^2+y^2+z^2)$

$\Rightarrow 64(8)=488+x^2+y^2+z^2$

$\Rightarrow x^2+y^2+z^2=24\rightarrow$ (2)

From (1) and (2),

$x y+y z+z x=\frac{(x+y+z)^2-\left(x^2+y^2+z^2\right)}{2}=20 \rightarrow$ (3)

Given,

$\frac{x}{y+z}+1+\frac{y}{z+x}+1+\frac{z}{x+y}+1=9+3=12$

$\frac{1}{y+z}+\frac{1}{z+x}+\frac{1}{x+y}=\frac{12}{x+y+z}=\frac{3}{2}$ (from (1)) $\rightarrow$(4)

$\frac{1}{y+z}+\frac{1}{z+x}+\frac{1}{x+y}=\frac{12}{x+y+z}=\frac{3}{2}$

Observe that,

$x^2+y^2+z^2$= $\left(\frac{x}{y+z}+\frac{y}{z+x}+\frac{z}{x+y}\right)(x y+y z+z x)-x y z\left(\frac{1}{y+z}+\frac{1}{z+x}+\frac{1}{x + y}\right)$

From (2), (3), (4),

$24=9(20)-\frac{3 x y z}{2}$

$\Rightarrow x y z=104\rightarrow$ (5)

Divide (2) by (5),

$\frac{x^2+y^2+z^2}{x y z}=\frac{24}{104}$

$\Rightarrow \quad \frac{x}{y z}+\frac{y}{z x}+\frac{z}{x y}=\frac{3}{13}$

$\Rightarrow m=3, n=13$

$m+n=16$

Problem 15: Let $x, y$ be real numbers such that $x y=1$. Let $T$ and $t$ be the largest and the smallest values of the expression

(x+y)2−(xy)−2(x+y)2+(xy)−2.

If $T+t$ can be expressed in the form $\frac{m}{n}$ where $m, n$ are nonzero integers with ${GCD}(m, n)=$ 1 , find the value of $m+n$.

Solution:

$\frac{(x+y)^2-(x-y)-2}{(x+y)^2+(x-y)-2}=\frac{x^2+y^2-(x-y)}{x^2+y^2+(x-y)}=n$

$\Rightarrow \quad n-1=\frac{2(y-x)}{(y-x)^2-(y-x)+2}$, if $y=x \Rightarrow n=1$

Let $y \neq x$,

$\Rightarrow \quad n-1=\frac{2}{(y-x)+\frac{2}{(y-x)}-1}$

Note that " $n-1$ " is maximum when $(y-x)+\frac{2}{(y-x)}$ holds the least possible positive value and it is minimum when $(y-x)+\frac{2}{(y-x)}$ holds the largest negative value.

By AM-GM Inequality,

$|s|+\frac{2}{|s|} \ge 2 \sqrt{2}$, and the equality holds when $|s|=\sqrt{2}$

$\Rightarrow T=\frac{2}{2 \sqrt{2}-1}+1>1 ; \quad t=\frac{2}{-2 \sqrt{2}-1}+1<1$

$T+t=2+2\left(\frac{1}{2 \sqrt{2}-1}-\frac{1}{2 \sqrt{2}+1}\right)=2+2\left(\frac{2}{8-1}\right)$

$T+t= 18 + 7 = 25$

Problem 16: Let $a, b, c$ be reals satisfying

3ab+2=6b,3bc+2=5c,3ca+2=4a.

Let $\mathbb{Q}$ denote the set of all rational numbers. Given that the product $a b c$ can take two values $\frac{r}{s} \in \mathbb{Q}$ and $\frac{t}{u} \in \mathbb{Q}$, in lowest form, find $r+s+t+u$.

Solution:

$3 a b+2=6 b$ $\Rightarrow 2=3 b(2-a) \rightarrow (1)$

$3 b c+2=5 c$ $\Rightarrow 2=c(5-3 b) \rightarrow(2)$

$3 c a+2=4 a \rightarrow (3)$

From $(1)$,

$a=\frac{6 b-2}{3 b} \rightarrow(4)$

From $(2)$,

$c=\frac{2}{5-3 b}$ $\rightarrow (5)$

Substituting $(4)$ & $(5)$ in $(3)$,

$3\left(\frac{2}{5-3 b}\right)\left(\frac{6 b-2}{3 b}\right)+2=4\left(\frac{6 b-2}{3 b}\right)$

after simplification,

$27 b^2-39 b+14=0$

Let $y=3 b \Rightarrow 3 y^2-13 y+14=0$

$y=\frac{13 \pm \sqrt{13^2-3(4)(14)}}{2(3)}=\frac{13 \pm 1}{6}$

$\Rightarrow \quad y=\frac{7}{3}, 2$

$a b c=\left(\frac{6 b-2}{3 b}\right) \cdot\left(\frac{2}{5-3 b}\right)$

$=\frac{4}{3}\left(\frac{3 b-1}{5-3 b}\right)=\frac{4}{3}\left(\frac{y-1}{5-y}\right)$

upon substitution of value of $y$,

$a b c=\frac{2}{3}, \frac{4}{9}$

$r+s+t+u=2+3+4+9=18$

Problem 17: For a positive integer $n>1$, let $g(n)$ denote the largest positive proper divisor of $n$ and $f(n)=n-g(n)$. For example, $g(10)=5, f(10)=5$ and $g(13)=1, f(13)=12$. Let $N$ be the smallest positive integer such that $f(f(f(N)))=97$. Find the largest integer not exceeding $\sqrt{N}$.

Solution:

$f(f(f(N)))=97$

Let $f(m)=97$ $\Rightarrow m-g(m)=97 \Rightarrow g(m)=m-97$

$\Rightarrow m-97 \mid m$ and is the largest proper divisor of $m$

$m=k m-97 k$ $\Rightarrow 97 k=m(k-1)$

since $k$, $k-1$ are co-prime $\Rightarrow \ k-1 \mid 97$ $\Rightarrow k=2,98.$

$k=98$, will not work as $1(=98-97)$ is not the largest proper divisor of $98$

Hence, $k=2$ $\Rightarrow m=97 \times 2$ $\Rightarrow f(f(N))=97 \times 2$

Let $f(n)=97 \times 2$ $\Rightarrow g(n)=n-97 \times 2$

$\Rightarrow n-97 \times 2\ \text{divides}\ n \Rightarrow 97 \times 2k^{\prime}$ $=n\left(k^{\prime}-1\right)$ $\Rightarrow k^{\prime}-1 \mid 2 \times 97$

$Therefore, k^{\prime}=2,3,98,195$

$k^{\prime}=2 \Rightarrow n=97 \times 4$

$k^{\prime}=3 \Rightarrow n=97 \times 3$, and both of these satisfy that $g(n)=n-97 \times 2$

But for $k^{\prime}=98,195$, $\ g(n) \neq n-97 \times 2$

Therefore, n=f(N)=97×3,97×4

CASE 1:

$f(N)=97 \times 4$ $\Rightarrow g(N)=N-97 \times 4$

$\Rightarrow 97 \times 4 k^{\prime \prime}=N\left(k^{\prime}-1\right)$

$\Rightarrow \quad k^{\prime \prime}=2,3,5,98,195,389\ ;\ N=388\left(\frac{k^{\prime \prime}}{k^{\prime \prime}-1}\right)$

Since, the question asks for smallest $N$, we use the largest value of $k^{\prime \prime}$ which gives the smallest $N$.

So, $k^{\prime \prime}$ = $389$. Since $389$ is a prime number, it follows that $g(N)=N-97 \times 4$. Hence, $N=389$ is a valid smallest solution for CASE 1.

CASE 2:

$f(N)=97 \times 3 \Rightarrow g(N)=N-91 \times 3$

$\Rightarrow 97 \times 3 k^{\prime \prime \prime}=N\left(k^{\prime \prime \prime}-1\right)$

$\Rightarrow k^{\prime \prime \prime} = 2, 4, 98, 292$

Since $292$ is not a prime, $\ g(292) \neq 292-97 \times 3$, so $N \neq 292$

If $k^{\prime \prime \prime}=98$ $\Rightarrow N=3 \times 98=2 \times 147=294$

but $g(2 \times 147)=147 \neq 2 \times 147-97 \times 3$

hence, $N \neq 294$

If $k^{\prime \prime \prime}=4 \Rightarrow N=97 \times 4=2 \times 194=388$

but $g(388)=194 \neq 388-97 \times 3$

hence $N \neq 388$

Now for $k^{\prime \prime \prime}=2 \Rightarrow N>389$

Hence, $N=389$ is the smallest positive integer such that $f(f(f(N)))=97$

$\lfloor\sqrt{N}\rfloor=\lfloor\sqrt{389}\rfloor=19$

Problem 18: Let $m, n$ be natural numbers such that

m+3n−5=2LCM(m,n)−11GCD(m,n)
Find the maximum possible value of $m+n$.

Solution:

Let $gcd (m,n) = d$

$\Rightarrow m = dp$, $n =dq$, where $gcd (p,q) = 1$

$mn = gcd (m,n) \times lcm (m,n)$ $\Rightarrow lcm (m,n) = dpq$

Substituting them in the equation,

$d p+3 d q-5=2 d p q-11 d$

$\Rightarrow d(p+3 q-2 p q+11)=5$

$d=1$ (or) $5$

CASE 1:

$d = 1$ $\Rightarrow p+3 q-2 p q+11=5$

By rearranging and taking the terms common,

$(2 q-1)(2 p-3)=15$

Observe that $p, q \in \mathbb{N}$ $\Rightarrow 2 q-1>0$ $\Rightarrow 2 p-3>0$ and so, we consider only positive divisors of 15.

$2 q-1=1$; $2 p-3=15$

$2 q-1 = 3\ ;\ 2p-3 = 5$

$2 q-1 = 5\ ;\ 2p-3 = 3$

$2 q-1 = 15\ ;\ 2p-3 = 1$

$\Rightarrow (p, q)=(9,1); (4,2); (3,3); (2,8)$

But, the last $3$ solutions are invalid, as the $gcd (p,q)$ is $1$.

$\Rightarrow (p, q)=(9,1)$

$(m, n)=(d p, d q)=(9, 1)$

CASE 2:

$d = 5$ $\Rightarrow p+3 q-2 p q+11=1$

$\Rightarrow (2 q-1)(2 p-3)=23$

$2 q-1=1$; $2 p-3=23$

$2 q-1=23$; $2 p-3=1$

$\Rightarrow (p, q)=(13,1) ; (2,12)$

The latter solution is invalid.

$\Rightarrow(p, q)=(13,1)$

$\Rightarrow (m, n)=(d p, d q)=(65,5)$

Hence, $Max(m+n) = 65+5 = 70$

Problem 19: Consider a string of $n$ 1's. We wish to place some $+$ signs in between so that the sum is $1000$. For instance, if $n=190$, one may put $+$ signs so as to get $11$ ninety times and $1$ ten times, and get the sum $1000$. If $a$ is the number of positive integers $n$ for which it is possible to place $+$ signs so as to get the sum $1000$ , then find the sum of the digits of $a$.

Solution: Observe that after inserting the "+" signs, the numbers that one would get are possibly $1, 11, 111$. Rest all the numbers are greater than $1000$. After splitting let the numbers of $1$'s, $11$'s, and $111$'s be $k_1, k_2, k_3$ respectively.

$\Rightarrow k_1+11 k_2+111 k_3=1000$; $k_1+2 k_2+3 k_3=n$

Now we just need to find the number of possible $n$ 's such that $k_1+11 k_2+11 k_3=1000$ and we need not find the number of Solutions of $k_1, k_2, k_3$, since $k_1, k_2, k_3 \in \mathbb{N}_0$

$n=1000-9 k_2-108 k_3$ gives the no. of values of n for $k_2, k_3 \ge \ 0$ and also we need $k_1 \ge 0 \Rightarrow n-\left(3 k_3+2 k_2\right) \ge 0$

For $k_2, k_3 \ge 0$,

The Final two equations are,

$n=1000-9\left(12 k_3+k_2\right)\ ;\ n-\left(3 k_3+2 k_2\right) \ge 0$

Now $12 k_3+k_2$ can take all the values from 0 to 111 as there always exist a quotient and remainder when divide by 12 .

$\Rightarrow n$ can take 112 values, but out of these some values will have $n-\left(3 k_3+2 k_2\right)<0$ & we need to eliminate them.

$\left(k_3, k_2\right)=(9,3) ;(9,2) ; (9,1) ;(8,11)$ are the ones that contradict, which correspond to "$n$" value of $1,10,19,37$. For these "$n$" values, whatever $k_2, k_3$ values that one can take, the second equation goes invalid because $k_2<12$ is the best choice for the pair ($k_2, k_3$) otherwise $k_2$ shoots up by $12$, making the second equation worse than before

$a=112-4=108$

Sum of digits of $a$ = $1+0+8=9$

Problem 20: For an integer $n \geq 3$ and a permutation $\sigma=\left(p_1, p_2, \ldots, p_n\right)$ of ${1,2, \ldots, n}$, we say $p_l$ is a landmark point if $2 \leq l \leq n-1$ and $\left(p_{l-1}-p_l\right)\left(p_{l+1}-p_l\right)>0$. For example, for $n=7$, the permutation $(2,7,6,4,5,1,3)$ has four landmark points: $p_2=7, p_4=4, p_5=5$ and $p_6=1$. For a given $n \geq 3$, let $L(n)$ denote the number of permutations of ${1,2, \ldots, n}$ with exactly one landmark point. Find the maximum $n \geq 3$ for which $L(n)$ is a perfect square.

Solution: We represent the permutation sequence in a graphical form. For example, ${1,4,2,3}$ and ${2,1,3,4}$ are represented below respectively,

Observe that each of the bends are nothing but a "Landmark point". Bend that looks like a hill are "HILL" and that look like a valley are "VALLEY".

Since there is only one bend for the problem, either it must be "HILL" (or) a "VALLEY" as shown below,

Observe that in a HILL structure, the topmost point correspond to the largest number " $n$ " and in a VALLEY, the bottom point correspond to the smallest number "$1$". Now in each structure, the two sides wings are non-empty and are either in ascending (or) descending order and hence we just need to choose non-empty subsets of the remaining "$n-1$ " element set (since the largest (or) smallest element is already filled up in the vertex) for a wing and it automatically gets arranged.

Number of non-empty subsets of the "$n-1$" element set = ${}^{n-1} C_{1} + {}^{n-1} C_{2} + \cdots + {}^{n-1} C_{n-2}$

$=2^{n-1}-2$

Notice that, We left out ${}^{n-1} C_{n-1}$, because the other side wing must also be non-empty

Number of HILL (or) VALLEY of $n$-element set = $2\left(2^{n-1}-2\right)$

$\Rightarrow L(n)=2^n-4$

Let $m^2=2^n-4 \Rightarrow\left(\frac{m}{2}\right)^2=m_0^2=2^{n-2}-1, m, m_0 \in \mathbb{N}$ observe that $m_0^2 \equiv 3 (mod\ 4)$, for all $n \ge 4$ but we know that no perfect square leaves a remainder $3$ when divided by $4$

$\Rightarrow L(3)=4$ $\Rightarrow n=3$ is the only such value.

Problem 21: An ant is at a vertex of a cube. Every 10 minutes it moves to an adjacent vertex along an edge. If $N$ is the number of one hour journeys that end at the starting vertex, find the sum of the squares of the digits of $N.$

Solution:

In the cube, mark the alternate vertices with "$.$" and " $\times$ " as shown in the diagram. Note that for any move, the ant alternates between a dot and a cross in each move. Suppose the ant starts from the vertex $A$ and let the diagonally opposite vertex of $A$ be $B$.

According to the problem, we need to find the number of ways in which the ant covers 6 edges (not necessarily distinct) and come back to $A$ after its $6^{\text {th }}$ move.

Since, the ant alternates the dot and the cross for any possible move of the ant, it should be at a cross after its 5th move. Note that all the cross expect $B$ are adjacent to $A$, and hence it can reach $A$. So, we need to subtract the no. of ways to reach $B$ from the total number of ways for the $5$ moves.

There are a total of $3$ paths to choose for the ant from each vertex and hence total of $3^5$ ways for the 5 moves

$N=3^5$ - (no. of ways to reach $B$ in $5$ moves)

After $4$ moves, the ant must be at "dot" and all the dots except $A$ are adjacent to $B$ and hence it can move to $B$. Hence,

No. of ways to reach $B$ in $5$ moves = $3^4$ - (no. of ways to reach $A$ in $4$ moves)

Similarly arguing we get,

No. of ways to reach $A$ in $4$ moves = $3^3$ - (no. of ways to reach $B$ in $3$ moves)

So we get,

$N = 3^5$ - ($3^4$ - ($3^3$ - ($3^2$ - ($3$ - (no. of ways to reach $B$ in $1$ move)))))

Since $A$ and $B$ are not adjacent and the ant starts from $A$, there is no way for the ant to reach $B$ in $1$ move.

$N=3^5-3^4+3^3-3^2+3=183$

Sum of squares of digits of $N = 1^2+8^2+3^2=74$

Problem 22: A binary sequence is a sequence in which each term is equal to $0$ or $1$ . A binary sequence is called friendly if each term is adjacent to at least one term that is equal to $1$ . For example, the sequence $0,1,1,0,0,1,1,1$ is friendly. Let $F_n$ denote the number of friendly binary sequences with $n$ terms. Find the smallest positive integer $n \geq 2$ such that $F_n>100$.

Solution:

Let $B_n$ denote the number of friendly binary sequences with $n$ terms that start with $1$. Let us find a recursive relation between $F_n$ and $B_n$.

Consider a sequence that starts with $1$. Except the $1^{st}$ digit, the remaining "$n-1$" digits can be filled with $B_n-1$ sequences that start with and are hence friendly.

Suppose the $2^{nd}$ digit is $0,$ then that $0$ is adjacent to $1$. So, we just care about whether (or) not the remaining "$n-2$" digit sequence is friendly (or) not and so, there are $F_{n-2}$ ways for it to be friendly. Hence,

$B_n=B_{n-1}+F_{n-2}$

Now consider a sequence of $n$ digits that starts with $0$.

Observe that the $2^{nd}$ digit must be a $1$, otherwise the first $0$ is not adjacent to a $1$.

Hence, the last "$n-1$" digit is nothing but a friendly sequence that starts with $1$ and there are $B_{n-1}$ sequences possible. Also, $F_n-B_n$ gives the number of sequence with $n$ digits that starts with $0$.

$\Rightarrow F_n-B_n=B_{n-1}$

Hence the recurrence relations are:

$B_n=B_{n-1}+F_{n-2}\ ;\ F_n=B_n+B_{n-1} \rightarrow$ (1)

Combining them we get,

$B_n=B_{n-1}+B_{n-2}+B_{n-3} \rightarrow$ (2)

and note that $B_2=2, B_3=3 \ (101,110,111)$,

$B_4=6(1001,1010,1101,1110,1011,1111)$

Using equation (2),

$B_5=6+3+2=11$, $B_6=11+6+3=20$, $B_7=20+11+6=37$, $B_8=37+20+11=68$

Using equation (1),

$F_3=5$, $F_4=9$, $F_5=11+6=17$, $F_6=20+11=31$, $F_7=37+20=57$, $F_8=68+37=105 > 100$

$\Rightarrow n=8$

Problem 23: In a triangle $A B C$, the median $A D$ divides $\angle B A C$ in the ratio $1: 2$. Extend $A D$ to ?, $E$ such that $E B$ is perpendicular $A B$. Given that $B E=3, B A=4$, find the integer nearest to $B C^2$.

Solution:

Let $\angle B A E=\theta \Rightarrow \angle C A E=2 \theta$

Given that $\sin \theta=\frac{3}{5}, \cos \theta=\frac{4}{5} \Rightarrow 30^{\circ}<\theta<45^{\circ}$

Hence, $\angle B A C=3 \theta>90^{\circ}$ is obtuse and $\angle A B C$ will be acute, so the point E lies outside $\triangle A B C$ as shown in the figure

$\frac{[A B D]}{[A C D]}=\frac{\frac{1}{2}\times h \times B D}{\frac{1}{2}\times h \times C D}$ $=1=\frac{\frac{1}{2}(A B)(A D) \sin \theta}{\frac{1}{2}(A C)(A D)\sin 2 \theta}$ (Since BD = CD)

$\Rightarrow \quad A C=\frac{4}{2 \cos \theta}=\frac{4}{2(4 / 5)}$ $\Rightarrow A C=\frac{5}{2}$

$\cos 3 \theta=\cos \angle B A C$ $=4 \cos ^3 \theta-3 \cos \theta=-\frac{44}{125}$

By cosine law in $\triangle A B C$ for the $\angle B A C$,

$\cos 3 \theta=\frac{A B^2+A C^2-B C^2}{2 A B \cdot A C}$ $=\frac{4^2+\left(\frac{5}{2}\right)^2-B C^2}{2 \times 4 \times \frac{5}{2}}=-\frac{44}{125}$

$\Rightarrow B C^2=16+\frac{25}{4}+\frac{880}{125}$

$=29+\frac{1}{4}+\frac{1}{25}$

$\Rightarrow B C^2=29.29$ units $^2$

Therefore, integer nearest to $B C^2$ = $29$

Problem 24: Let $N$ be the number of ways of distributing 52 identical balls into 4 distinguishable boxes such that no box is empty and the difference between the number of balls in any two of the boxes is not a multiple of 6 . If $N=100 a+b$, where $a, b$ are positive integers less than 100 , find $a+b$.

Solution:

The number of ball in the boxes are in the form
$6k+r\ ;\ r=\{0, 1, 2, 3, 4, 5\}$
Let the number of balls in the boxes be $6k+a$, $6k+b$, $6k+c$, $6k+d$, respectively, where $a, b, c, d \in r$ and are different from each other.

So, $52-(a+b+c+d) = 6n$
That gives $a+b+c+d =10$ and no other values are possible to obtain distinct remainders

$\Rightarrow n = 7$

CASE 1:

So, the remainders are $1,2,3,4$ and can be arranged $4!$ ways.
Now there are $7$ identical collection of $6$ balls each which we have to divide it into $4$ distinct boxes.
Using stars and bars method we get that,
There are ${ }^{10} C_3$ = $120$ ways to distribute them in those distinct boxes
So total number of ways is $120 \times 24 = 2880$

CASE 2:

The remainders can also be $0, 2, 3, 5\ \text{(or)}\ 0, 1, 4, 5$ as it sums up to $10$ as well

There are no more remainders which add up to $10$

Hence we just get $3 \times 2880$ in total

But now, there could be some empty boxes due to that $0$ remainder and hence we need to subtract that out!, which is,
$4(2(3!) \times { }^{9} C_2) = 1728$

$N = 3\times2880 - 1728 = 6912$
$a = 69\ ;\ b = 12$
Hence, $a+b = 81$

## Live Discussion of IOQM 2022 Solutions

This site uses Akismet to reduce spam. Learn how your comment data is processed.

### Knowledge Partner  