IOQM 2024 Paper solutions (Done 1-21, 29)

Q1(number-theory). The smallest positive integer that does not divide 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 is:
Solution:
This product has all the integers from 1 to 9.
So smallest integer not dividing it would be the next prime after 9.
Which is 11.
Answer: 11

Q2(combinatorics): The number of four-digit odd numbers having digits 1, 2, 3, 4, each occurring exactly once, is:
Solution:
Last digit has to be 1 or 3: 2C1
Choosing remaining 3 digits: 3C3
Arranging those 3 digits: 3!
Answer: 2C1*3C3*3! = 12

Q3(number-theory): The number obtained by taking the last two digits of \(5^{2024}\) in the same order is:
Solution:
To get last 2 digits from number, divide by 100 and take the remainder.
So we have to compute mod 100.
25 mod 100 = 25
25.5 mod 100 = 125 mod 100 = 25
5^3.5 mod 100 = 25.5 mod 100 = 25
5^4.5 mod 100 = 25.5 mod 100 = 25
.....
So:
5^2024 mod 100 = 25.

Q4(geometry): Let ABCD be a quadrilateral with \(\angle ADC = 70^\circ\), \(\angle ACD = 70^\circ\), \(\angle ACB = 10^\circ\) and \(\angle BAD = 110^\circ\). The measure of \(\angle CAB\) (in degrees) is:
Solution:

In \(\triangle ADC\) $$ 70^\circ + 70^\circ + \angle DAC = 180^\circ $$ $$ \Rightarrow \angle DAC = 40^\circ $$ Now \(\angle DAC + \angle CAB = 110^\circ\) $$ \Rightarrow \angle CAB = 110^\circ - 40^\circ = 70^\circ $$

Q5(algebra) Let \(a = \frac{x}{y} + \frac{y}{z} + \frac{z}{x}\), let \(b = \frac{x}{z} + \frac{y}{x} + \frac{z}{y}\), and let \(c = \left( \frac{x}{y} + \frac{y}{z} \right)\left( \frac{y}{z} + \frac{z}{x} \right)\left( \frac{z}{x} + \frac{x}{y} \right)\). The value of \(|ab - c|\) is:
Solution:
Quick way to solve is to put x = y = z = 1 and see that the answer is 1.
If it works for this case, it will be true in general since the question demands a numeric answer irrespective of the x,y,z values.
A formal solution:
\(a = \frac{x}{y} + \frac{y}{z} + \frac{z}{x}\)  ...(i)

and \(b = \frac{x}{z} + \frac{y}{x} + \frac{z}{y}\)  ...(ii)

and \(c = \left( \frac{x}{y} + \frac{y}{z} + \frac{z}{x} \right) \left( \frac{y}{z} + \frac{z}{x} + \frac{x}{y} \right) \left( \frac{z}{x} + \frac{x}{y} + \frac{y}{z} \right)\)

$$ = \left( a - \frac{z}{x} \right) \left( a - \frac{x}{y} \right) \left( a - \frac{y}{z} \right) $$ $$ = a^3 - \left( \frac{z}{x} + \frac{x}{y} + \frac{y}{z} \right) a^2 + \left( \frac{z}{x} \cdot \frac{x}{y} + \frac{x}{y} \cdot \frac{y}{z} + \frac{y}{z} \cdot \frac{z}{x} \right) a - 1 $$ $$ = a^3 - a^3 + ab - 1 $$ ∴ $1 = ab - c$

Q6.(number-theory) Find the number of triples of real numbers (a, b, c) such that \(a^{20} + b^{20} + c^{20} = a^{24} + b^{24} + c^{24} = 1\).
Solution:
Answer: 6 triples
Why only the “0–1” patterns work
1. Because both exponents are even, the two equations depend only on the absolute values \(x=|a|,\;y=|b|,\;z=|c|\ge 0\).
2. Compare the two powers for a single non-negative number:
$$ x^{24}-x^{20}=x^{20}\bigl(x^{4}-1\bigr) $$ If \(0\le x<1 br="" le="" x=""> If \(x=1\)    → \(x^{24}=x^{20}=1\).
If \(x>1\)    → \(x^{24}>x^{20}\).
3. In the system $$ x^{20}+y^{20}+z^{20}=1=\;x^{24}+y^{24}+z^{24}, $$ any term with x >1 would make the first sum exceed 1, which is impossible (all terms are non-negative).
Hence every coordinate satisfies \(0\le x,y,z\le 1\).
4. With all three coordinates in \([0,1]\) we have \(x^{24}\le x^{20}\), \(y^{24}\le y^{20}\), \(z^{24}\le z^{20}\).
Equality of the *totals* therefore forces equality term-by-term: \(x^{24}=x^{20},\;y^{24}=y^{20},\;z^{24}=z^{20}\).

5. The only non-negative numbers satisfying \(t^{24}=t^{20}\) are t=0,1. But the first equation says the sum of the 20-th powers is 1, so **exactly one** of x,y,z equals 1 and the other two equal 0.

Thus, up to absolute value, the solutions are $$ (1,0,0),\;(0,1,0),\;(0,0,1). $$ Re-introducing the signs:

Because the exponents are even, each non-zero coordinate can be either 1 or -1. without affecting the equations.
So every pattern above splits into two signed versions.
$$ \begin{aligned} (1,0,0),\;(-1,0,0),\quad (0,1,0),\;(0,-1,0),\quad (0,0,1),\;(0,0,-1). \end{aligned} $$ Counting them gives 6 real triples in total.

Q7(geometry. Determine the sum of all possible surface areas of a cube two of whose vertices are (1, 2, 0) and (3, 3, 2).
Solution: Distance-sqaure between the given vertices = 4+1+4 = 9.
3 cases:
Case 1: Adjacent vertices. a^2 = 9 => 6.a^2 = 54
Case 2: Same face diagonal. 2.a^2 = 9 => 6.a^2 =27
Case 3: Diagonal across faces. 3.a^2 = 9 => 6.a^2 = 18
Answer: 54 + 27 + 18 = 99.

Q8(number-theory).Let n be the smallest integer such that the sum of digits of n is divisible by 5 as well as the sum of digits of (n + 1) is divisible by 5. What are the first two digits of n in the same order?
Solution:
In 'n', Last digit can't be 0 to 8. Else sum of digits of 'n+1' would be just 1 more than that of 'n' and hence not divisible by 5.
If the last digit is 9, then adding 1 to it will make it 0 and take the carry forward. Eventually '1' will be added to the sum of digits and '9' will be reduced.
So net-net the number will change by 8. But that won't make it divisible by 5.
Similarly it can be shown that when last 2 or 3 digits are 9, even then adding 1 will not change the sum of digits by multiple of 5.
But with last 4 digits being 9, it does.
What is the smallest number with last 4 digits as 9 and having sum of digits divisible by 5: 49,999.


Q9(combinatorics).Consider the grid of points \(X = \{(m,n) \mid 0 \leq m,n \leq 4 \}\). We say a pair of points \(\{(a,b), (c,d)\}\) in X is a knight-move pair if \((c = a \pm 2 \text{ and } d = b \pm 1)\) or \((c = a \pm 1 \text{ and } d = b \pm 2)\). The number of knight-move pairs in X is:
Solution:
First of all let's figure out if the problem is asking for ordered pairs or unordered pairs.
The problem wants pairs in this form: {(a,b), (c,d)}. Curly braces mean it's a set and order doesn't matter.
So {(0,0),(2,1)} and {(2,1),(0,0)} are same.
If ordered pairs were required, the question would ask like this: ((a,b),(c,d)) or <(a,b),(c,d)>.

Now, let's figure out the rest.
Knight can move in x,y directions like this:
1. (+-2,+-1) OR
(4) 2. (+-1,+-2)
(4)
Total 8 cases.
Let's take any one of them and rest all are exactly same.
For (+2,+1) case:
Starting x can be 0,1,2 and y can be 0,1,2,3 => 3*4 = 12 such ways.
So 12*8 = 96.
But each pair is counted twice and problem is asking for unordered pairs: 96/2 = 48 is the answer.

Q10(algebra).Determine the number of positive integral values of 'p' for which there exists a triangle with sides a, b and c which satisfy:
$$ a^2 + (p^2 + 9)b^2 + 9c^2 - 6ab - 6pbc = 0. $$
Solution:
Rewrite it as:
(a - 3b)^2 + (pb - 3c)^2 = 0
=> a = 3b and pb = 3c
So 3b,b,pb/3 are sides of a triangle.
=> 4 > p/3, 1 + p/3 > 3, 3 + p/3 > 1
=> p < 12, p > 6, p > -6.
=> 6 < p < 12
=> p = 7,8,9,10,11
Answer: 5

Q11(number-theory).
The positive real numbers a, b, c satisfy: $$ \frac{a}{2b+1} + \frac{2b}{3c+1} + \frac{3c}{a+1} = 1 $$ $$ \frac{1}{a+1} + \frac{1}{2b+1} + \frac{1}{3c+1} = 2 $$ What is the value of \(\frac{1}{a} + \frac{1}{b} + \frac{1}{c}\) ?
Answer (12)
Solution:
$$ \frac{3c}{a+1} + \frac{a}{2b+1} + \frac{2b}{3c+1} = 1 $$

$$ \frac{1}{a+1} + \frac{1}{2b+1} + \frac{1}{3c+1} = 2 $$

Add (i) and (ii):
$$ \Rightarrow \frac{3c+1}{a+1} + \frac{a+1}{2b+1} + \frac{2b+1}{3c+1} = 3 $$
$$ \Rightarrow \text{A.M.} \geq \text{G.M.} $$ Note that here A.M. and G.M. are equal which is possible only if all the underlying numbers for which A.M. and G.M. are computed, are same.

$$ \Rightarrow \left( \frac{3c+1}{a+1} + \frac{a+1}{2b+1} + \frac{2b+1}{3c+1} \right) \div 3 \geq (1)^{{1}^{\div 3}} $$ $$ \Rightarrow \frac{3c+1}{a+1} = 1 \quad \text{and} \quad \frac{2b+1}{3c+1} = 1 $$ $$ \Rightarrow \frac{a+1}{2b+1} = 1 $$ $$ \Rightarrow (a+1) = (2b+1) = (3c+1) = k $$ $$ \Rightarrow \frac{1}{k} + \frac{1}{k} + \frac{1}{k} = 2 \Rightarrow \frac{3}{k} = 2 \Rightarrow k = \frac{3}{2} $$ $$ \Rightarrow a = \frac{1}{2},\quad b = \frac{1}{4},\quad c = \frac{1}{6} $$ $$ \Rightarrow \frac{1}{a} + \frac{1}{b} + \frac{1}{c} = 2 + 4 + 6 = 12 $$

Q12(geometry): Consider a square ABCD of side length 16. Let E,F be points on CD such that CE = EF = F D. Let the line BF and AE meet in M. The area of △MAB is:

Solution:

Let A = (0,0) B = (16,0), C = (16,16) D = (0,16).
=> E = (32/3,16) and F = (16/3,16)
Equation of AE: y = x.3/2
Equation of BF: y = (16-x).3/2
Intersection of AE,BF = M = (8,12)
Area of MAB = 1/2.12.16 = 96
Answer: 96

Solution 2:
MEF and MAB are similar triangles(by AAA).
Side ratios = 16/(16/3) = 3.
=> AM = 3/4.AE
AE = sqrt(16^2 + (32/3)^2)
=> Height of MAB = sqrt(AM^2 - 8^2) = 12.
Area of MAB = 1/2.12.16 = 96.

Q13(algebra). Three positive integers a,b,c with a > c satisfy the following equations:
ac + b + c = bc + a + 66 and a + b + c = 32. Find the value of 'a'.
Solution:
We have 2 equations and 3 variables. So we need to somehow get 3 equations. We will use the fact that a,b,c are positive integers to come up with some factor based equation.

From the first equation:
c(a-b) + (b-a) + c = 66.
(a-b).(c-1) + c = 66.
(a-b).(c-1) + c -1 = 66 - 1.
(a-b + 1).(c-1) = 65.
From the second equation:
(a-b + 1).(32-a-b-1) = 65.
(a-b + 1).(31-a-b) = 65.
Since a,b are integers, we can build cases.
Case 1: a-b+1 = 65 and 31-a-b = 1 => a+b = 30
2a = 94 => a = 47 => b ≤ 0. Invalid.

Case 2: a-b+1 = 1 and 31-a-b = 65 => a+b ≤ 0
Invalid.

Case 3: a-b+1 = 13 and 31-a-b = 5 => a+b = 26
=> 2a = 38, a = 19, b = 7, c = 6. Valid.
Case 4: a-b+1 = 5 and 31-a-b = 13 => a+b = 18
=> 2a = 22, a = 11, b = 7, c = 14 => c > a. Invalid.
So only valid case is a = 19, b = 7, c = 6.
Answer: 19.

Q14(combinatorics). Initially, there are \(3^{80}\) particles at the origin (0,0). At each step the particles are moved to points above the x-axis as follows: if there are n particles at any point (x,y), then \(\left\lfloor \frac{n}{3} \right\rfloor\) of them are moved to (x+1, y+1), \(\left\lfloor \frac{n}{3} \right\rfloor\) are moved to (x, y+1) and the remaining to (x-1, y+1).

For example, after the first step, there are \(3^{79}\) particles each at (1,1), (0,1) and (-1,1). After the second step, there are \(3^{78}\) particles each at (-2,2) and (2,2), \(2 \times 3^{78}\) particles each at (-1,2) and (1,2), and \(3^{79}\) particles at (0,2). After 80 steps, the number of particles at (79,80) is:
Solution link.

Q15(geometry,number-theory). Let X be the set consisting of twenty positive integers n, n + 2,...,n + 38. The smallest value of n for which any three numbers a, b, c ∈ X, not necessarily distinct, form the sides of an acute-angled triangle is:
Solution:
Sum of any 2 numbers from X should be more than any other number from X.
Take the 2 smallest. Their sum should be bigger than the biggest.
=> n + n > n + 38 => n > 38 => Smallest n to form triangle = 39.

Now for all angles to be acute, the biggest angle should be acute.
For the biggest angle let's create a triangle with sides a = n, b = n, c = n+38.
Cosine of the biggest angle should be > 0.
Cos(C) = a^2 + b^2 - c^2/2ab > 0.
2.n^2 - (n+38)^2 > 0.
n^2 - 76n - 38^2 > 0.
From quadratic formula:
(n-x)(n-y) > 0 where x,y are roots.
x,y = (76 +- sqrt(76^2 + 4.38^2))/2.76
= 38(1 +- sqrt(2))
So n > 38(1 + sqrt(2))
n > 38*(2.414)
=> n > 91.74
=> n = 92.

Q16(algebra).
Let \( f : \mathbb{R} \to \mathbb{R} \) be a function satisfying the relation \[ 4f(3 - x) + 3f(x) = x^2 \] for any real \( x \). Find the value of \( f(27) - f(25) \) to the nearest integer. (Here \( \mathbb{R} \) denotes the set of real numbers.)
Solution:
Replace x with 3-x to get:
$$ \begin{align*} 4f(3 - (3 - x)) + 3f(3 - x) &= (x-3)^2 \\ 4f(x) + 3f(3 - x) &= (x-3)^2 \\ 4f(3 - x) + 3f(x) &= x^2 \\ \end{align*} $$ Solving for f(x) we get:
$$ \begin{align*} 7f(x) &= 4(x-3)^2 - 3x^2 \\ 7f(27) &= 4\cdot 24^2 - 3\cdot 27^2 \\ 7f(25) &= 4\cdot 22^2 - 3\cdot 25^2 \\ f(27) -f(25) &= 8 \end{align*} $$

Q17(geometry). Consider an isosceles triangle ABC with sides BC = 30, CA = AB = 20. Let D be the foot of the perpendicular from A to BC, and let M be the midpoint of AD. Let P Q be a chord of the circumcircle of triangle ABC, such that M lies on P Q and P Q is parallel to BC. The length of P Q is:
Solution:





Step 1: Compute the area of ABC and use that to compute circuradius using [ABC] = abc/4R. You will get R = \(\frac{40}{\sqrt(7)}\).
Step 2: By using Pythagoras theorem, AD =\(\sqrt(20^2 - 15^2) = 5\sqrt(7)\) = 2.AM.
Step 3: Since R > AD, it means that circumcenter is outside the triangle. You can verify it by computing Cos(C) which will be negative hence implying an obtuse triangle.
Step 4: Let the circumcenter be O. It lies on the line AMD extended towards O since AD is the perpendicular bisector of BC.
Step 5: PQ || BC and PQ passes through M. It means that ODM is perpendicular to PQ. So OM is the perpendicular bisector of PQ because OPQ is an isosceles triangle. It means that PM = MQ = PQ/2
Step 6: Now QM^2 = OQ^2 - OM^2. OQ is the radius. OM = OA - AM = radius - AM. Using this we get QM = 25/2 => PQ = 25.

Q18(number-theory). Let p, q be two-digit numbers neither of which are divisible by 10. Let r be the four-digit number by putting the digits of p followed by the digits of q (in order). As p, q vary, a computer prints r on the screen if gcd(p, q)=1 and p + q divides r. Suppose that the largest number that is printed by the computer is N. Determine the number formed by the last two digits of N (in the same order).

Solution:

r = 100p + q, hence r grows with p. So we will try to find the largest p.
p + q divides r => p + q | 100p + q.
p + q | 99p
gcd(p,q) = 1 => gcd(p+q,p) = 1 (quickly verify using Euclid gcd algo).
So p + q can't divide p hence it has to divide 99.
p+q | 99
\begin{align*} 11 \le p,q \le 99 \\ \Rightarrow 22 \le p + q \le 198 \\ \Rightarrow p + q \in \{33,99\} \\ \end{align*}
If p + q = 33 then:
\begin{align*} q \ge 11 \\ \Rightarrow p \le 22 \\ \end{align*}
As stated earlier we want to find largest p, in order to find largest r.
p = 22, q = 11, gcd = 11, reject.
p = 21, q = 12, gcd = 3, reject.
p = 20, q = 13, p ends in 0, reject.
p = 19, q = 14, gcd = 1, accept.
So largest r = 1914.

If p + q = 99 then:
\begin{align*} q \ge 11 \\ \Rightarrow p \le 88 \\ \end{align*}
As stated earlier we want to find largest p, in order to find largest r.
p = 88, q = 11, gcd = 11, reject.
p = 87, q = 12, gcd = 3, reject.
p = 86, q = 13, gcd = 1, accept.
So largest r = 8613.

N = 8613 and answer = 13.

Q19(combinatorics). Consider five points in the plane, with no three of them collinear. Every pair of points among them is joined by a line. In how many ways can we color these lines by red or blue, so that no three of the points form a triangle with lines of the same color.
Solution:
Let the points be P1,P2,P3,P4,P5.
Let's say all 4 lines from P1 are red.
=> P1P2, P1P3, P1P4, P1P5 are red.
Now P2P3,P2P4,P2P5 will have to be blue otherwise P1P2P3, P1P2P4, P1P2P5 will be red triangles.
Similarly P3P4, P3P5, P4P5 will also have to blue.
But then, P2P3P4 will be a blue triangle. That's not allowed.
So we can't have all 4 lines from any point with same color.

What about 3 lines from one point being of same color?
Let's say P1P2, P1P3, P1P4 are red.
And P1P5 is blue.
Now P2P3, P2P4, P3P4 have to be blue.
=> Triangle P2P3P4 is blue. Which is not allowed.
So we can't even have 3 lines of same color from any point.

What about 2?
That has to be allowed. Because there is no way without it.
So we have established now that each point will have 2 Red and 2 Blue lines attached to it.

Let's say P1P2, P1P3 are Red and P1P4, P1P5 are blue. There are 4C2 = 6 ways to create such combinations.
So
Red = P2---P1---P3
Blue = P4---P1---P5

Now this forces P2---P3 to be blue and P4---P5 to be Red. There is no choice here. So we still have 4C2 ways. Now:
Red = P2---P1---P3    P4---P5
Blue = P4---P1---P5   P2---P3

Remember that we earlier proved that each point will have 2 Red and 2 Blue lines.
P2 has one red line so far. For the second red line it can pair with P4 or P5 since P2P3 is already blue.
So P2 has 2 choices: 2C1.
Total ways so far: 4C2 * 2C1 = 12.

Let's say P2 chooses P4. Now:
Red = P3---P1---P2---P4---P5
Blue = P4---P1---P5   P2---P3

Now P2 has 2 red lines with P1,P4. So it has to have 2 blue lines with P3,P5. No choice here.
Red = P3---P1---P2---P4---P5
Blue = P4---P1---P5---P2---P3
Now P3,P5 are left with 1 red line each. Rest all have 2 red lines. So they will have to pair up. No choice here.
Red = P3---P1---P2---P4---P5---P3(circle here)
Similarly P4,P3 are forced to have a blue line.
Blue = P4---P1---P5---P2---P3---P4(circle here).

So there are only 12 ways to get such combinations. Which is the answer.
Note that in both Red and Blue lines, we can start from one point and come back to it without visiting it again. This is called a Hamiltonian cycle. Essentially we are creating a necklace with 5 different pearls. And we know from circular permutations that there are (n-1)!/2 ways to do it. Which also gives the same answer of 12 here.




Q20.
On a natural number 'n' you are allowed two operations: (1) multiply n by 2 or (2) subtract 3 from n. For example starting with 8 you can reach 13 as follows: \(8 \rightarrow 16 \rightarrow 13\). You need two steps and you cannot do in less than two steps. Starting from 11, what is the least number of steps required to reach 121?

Solution:

Notice that it's better to divide by 2 when it's even. And subtract 3 when it's odd. If you subtract 3 when it's even, you will take one extra step to reach the same number. For e.g. 62->31->34 is 2 steps but 62->65->68->34 is 3 steps. So strategy is this:
1. Start from 121
2. If odd, add 3 else divide by 2.
3. Once you reach 8, then you can make an exception to this rule and add 3 even though it's not odd. This will help you reach 11 faster.

Q21.
An integer n is such that \(\left\lfloor \frac{n}{9} \right\rfloor\) is a three digit number with equal digits, and \(\left\lfloor \frac{n-172}{4} \right\rfloor\) is a 4 digit number with the digits 2, 0, 2, 4 in some order. What is the remainder when n is divided by 100?

Solution:
Let [n/9] = aaa. So n = 9*aaa + q where q is from 0 to 8.
=> Range of n = [8991,8999]. This is the max range of n.
If a = 8 then n = [7992,8000]


Q22. In a triangle ABC, \(\angle BAC = 90^\circ\). Let \(D\) be the point on \(BC\) such that AB + BD = AC + CD. Suppose BD : DC = 2 : 1. If $$ \frac{AC}{AB} = \frac{m + \sqrt{p}}{n}, $$ where m, n are relatively prime positive integers and p is a prime number, determine the value of m + n + p.

Solution:

Method 1
Since no lengths are given and only ratios are given and asked for, we can assume that BC = 3, BD = 2 and CD = 1.
AB^2 + AC^2 = 9
AB + 2 = AC + 1 => AB + 1 = AC
AB^2 + (AB + 1)^2 = 9 => 2AB^2 + 2AB - 8 = 0 => AB^2 + AB - 4 = 0
=> AB = [-1 -+ sqrt(1 + 16)]/2 but AB > 0 => AB = (sqrt(17) - 1)/2
AC = AB + 1 = (sqrt(17) + 1)/2
AC/AB = (sqrt(17) + 1)/(sqrt(17) - 1) = [(sqrt(17) + 1)^2]/16 = (18 + 2.sqrt(17))/16 = (9 + sqrt(17))/8
m = 9, p = 17, n = 8 => m + p + n = 34.

Method 2
BC = a, AC = b, AB = c.
AB + BD = AC + CD
=> D is point of contact of A-excircle with BC.
=> BD = s - c and CD = s - b. Where s = semiperimeter = (a+b+c)/2
Proof of this part: Let the A-excircle touch BC at D, AB(extended) at E and AC(extended) at F.
Then equal tangent property means that AE = AF, BD = BE and CD = CF.
AE = AB + BE = AB + BD.
AF = AC + CF = AC + CD
Hence AB + BD = AC + CD
Given $$ \frac{BD}{DC} = \frac{2}{1} \ \Rightarrow \ \frac{s - c}{s - b} = \frac{2}{1} \ \Rightarrow \ \frac{a + b - c}{a + c - b} = \frac{2}{1} $$ \(\Rightarrow a + 3c = 3b \quad \ldots (1)\) Also given \(a^2 = b^2 + c^2 \quad \ldots (2)\) \(\Rightarrow (3b - 3c)^2 = b^2 + c^2 \ \Rightarrow \ 8b^2 + 8c^2 - 18bc = 0\) $$ \Rightarrow 4\left(\frac{b}{c}\right)^2 - 9\left(\frac{b}{c}\right) + 4 = 0 \ \Rightarrow \ \frac{b}{c} = \frac{9 \pm \sqrt{81 - 64}}{8} $$ $$ \left(\frac{AC}{AB}\right) = \frac{9 + \sqrt{17}}{8} = \frac{m + \sqrt{p}}{n} $$ \(\Rightarrow m + p + n = 9 + 17 + 8 = 34\)

Method 3:

$$ y + 2x = AC + x \Rightarrow AC = x + y $$ $$ (x + y)^2 + y^2 = (3x)^2 \Rightarrow x^2 + 2y^2 + 2xy = 9x^2 \Rightarrow 8x^2 - 2y^2 - 2xy = 0 \Rightarrow 4a^2 - a - 1 = 0 \left[ \therefore a = \frac{x}{y} \right] $$ $$ \Rightarrow a = \frac{1 \pm \sqrt{1 + 16}}{8} \Rightarrow a = \frac{1 \pm \sqrt{17}}{8} \Rightarrow \frac{AC}{AB} = \frac{x}{y} + 1 = a + 1 $$ $$ \Rightarrow \frac{AC}{AB} = \frac{1 + \sqrt{17}}{8} + 1 \Rightarrow \frac{AC}{AB} = \frac{9 + \sqrt{17}}{8} \Rightarrow m + n + p = 34 $$

Q23. Consider the fourteen numbers, \(1^4, 2^4, \ldots, 14^4\). The smallest natural number 'n' such that they leave distinct remainders when divided by 'n' is:

Solution:

We want the fourth powers $$ 1^4,2^4,\dots,14^4 $$ to give different residues mod n. Equivalently: for any two different \(x,y\in\{1,\dots,14\}\) we must not have $$ x^4\equiv y^4\pmod n . $$ Since $$ x^4-y^4=(x-y)(x+y)(x^2+y^2), $$ it's same as: $$ n \nmid (x-y)(x+y)(x^2+y^2)\qquad\text{for all distinct }x,y. \tag{★} $$ So we’re looking for the smallest n for which (★) holds.

2) A quick lower bound: n>27
For \(x,y\in\{1,\dots,14\}\), the sum x+y can be any integer from 3 to 27. If \(n\le 27\), pick x,y with x+y=n. Then \(n\mid(x+y)\), hence \(n\mid(x^4-y^4)\), violating (★).
Therefore \(n\ge 28\).

3) Rule out n=28,29,30 We just need to find one bad pair (x,y) for each candidate n.
* n=28: take x=8, y=6. Then \((x-y)(x+y)=2\cdot14=28\), so \(28\mid(x^4-y^4)\). Bad.
* n=29 (prime): make one factor equal to 29. Take x=5,y=2: \(x^2+y^2=25+4=29\). So \(29\mid(x^4-y^4)\). Bad.
* n=30: take \(x=8,\;y=2\). Then \((x-y)(x+y)=6\cdot10=60\), so \(30\mid(x^4-y^4)\). Bad.
Thus n must be at least 31.

4) Show n=31 works:
We just need to prove that x^2 + y^2 isn't divisible by 31.
Assume that it is.
So x^2 = -y^2 mod 31.
Raise both sides to 15th power:
x^30 = -1.y^30 mod 31.
Using Fermat's little theorem:
x^30 mod 31 = 1 = y^30 mod 31.
So there is a contradiction unless one of x or y mod 31 is 0.
Which is not the case. So 31 doesn't divide x^2 + y^2.
$$ \boxed{n=31} $$

Q24.Consider the set F of all polynomials whose coefficients are in the set of {0, 1}. Let q(x) = x³ + x + 1. The number of polynomials p(x) in F of degree 14 such that the product p(x)q(x) is also in F is:
Solution:

Let $$ p(x) = a_{14}x^{14} + a_{13}x^{13} + \dots + a_0 $$ and $$ q(x) = x^3 + x + 1. $$ Then $$ \begin{aligned} p(x) \cdot q(x) &= x^{17}(a_{14}) \\ &\quad + x^{16}(a_{13}) \\ &\quad + x^{15}(a_{14} + a_{12}) \\ &\quad + x^{14}(a_{14} + a_{13} + a_{11}) \\ &\quad + x^{13}(a_{13} + a_{12} + a_{10}) \\ &\quad + x^{12}(a_{12} + a_{11} + a_{9}) \\ &\quad + x^{11}(a_{11} + a_{10} + a_{8}) \\ &\quad + x^{10}(a_{10} + a_{9} + a_{7}) \\ &\quad + x^{9}(a_{9} + a_{8} + a_{6}) \\ &\quad + \dots \\ &\quad + x^{3}(a_{3} + a_{2} + a_{0}) \\ &\quad + x^{2}(a_{2} + a_{1}) \\ &\quad + x(a_{1} + a_{0}) \\ &\quad + a_{0}. \end{aligned} $$ Since \(p(x) \cdot q(x) \in F\), each coefficient above must be 0 or 1. Given \(\deg(p) = 14\), we have \(a_{14} = 1\). From the coefficient of \(x^{15}\): $$ a_{14} + a_{12} \le 1 \quad \Rightarrow \quad a_{12} = 0. $$ From the coefficient of $x^{14}$: $$ a_{14} + a_{13} + a_{11} \le 1 \quad \Rightarrow \quad a_{13} = 0,\ a_{11} = 0. $$ For \(a_{10}\), it can be 0 or 1:

* If \(a_{10} = 1\), then by the same logic \(a_{9} = a_{8} = a_{7} = 0\).
* If \(a_{10} = 0\), we can check \(a_9\); if \(a_9 = 1\), then the next three coefficients must be 0, and so on.

We see a pattern:

* Start at \(a_{13}\) (since \(a_{14}\) is fixed as 1).
* If \(a_i = 1\), then the next 3 coefficients must be 0.
* If \(a_i = 0\), we shift the check to \(a_{i-1}\) and start afresh.

This is equivalent to forming a binary sequence of length 14 using “chunks” of:

* 0001 (a block of length 4), or
* 0 (a block of length 1).

This is the same as tiling a \(1 \times 14\) board with \(1 \times 4\) tiles and \(1 \times 1\) tiles.

Let a = number of 4-tiles (0001 blocks), b = number of 1-tiles (single zeros).
Then 4a+b = 14. The possibilities are:

$$ (a,b)=(0,14),\ (1,10),\ (2,6),\ (3,2). $$
For fixed (a,b), the tiles are indistinguishable, so the number of orders is
\(\binom{a+b}{a}\) (choose where the 'a' long tiles go among the 'a+b' total tiles).

Thus the total number is
$$ \binom{14}{0}+\binom{11}{1}+\binom{8}{2}+\binom{5}{3} =1+11+28+10 = \boxed{50}. $$

Q25. A finite set M of positive integers consists of distinct perfect squares and the number 92. The average of the numbers in M is 85. If we remove 92 from M, the average drops to 84. If \(N^2) is the largest possible square in M, what is the value of N?
Solution:
Prerequisite: Sum of squares.
$$ \frac{a_1^2 + a_2^2 + a_3^2 + \dots + a_0^2 + 92}{n + 1} = 85 \quad \dots (i) $$ If we remove 92, then $$ \frac{a_1^2 + a_2^2 + a_3^2 + \dots + a_n^2}{n} = 84 \quad \dots (ii) $$ From (i) and (2) $$ 84n + 92 \times 85n + 85 $$ $$ \Rightarrow n = 7 $$ Now, $$ a_1^2 + a_2^2 + a_3^2 + \dots + a_6^2 + a_7^2 = 84 \times 7 = 588 $$ If \(a_1 = 1, a_2 = 2, a_3 = 3, a_4 = 4, a_5 = 5, a_6 = 6\) Then $$ 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2 + a_7^2 = 588 $$ $$ \Rightarrow a_7^2 = 588 - 91 $$ $$ \Rightarrow a_7^2 = 497 \quad (\text{not possible}) $$ If \(a_1 = 1, a_2 = 2, a_3 = 3, a_4 = 4, a_5 = 5, a_6 = 7\) Then $$ 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 7^2 + a_7^2 = 588 $$ $$ \Rightarrow a_7^2 = 484 $$ $$ \Rightarrow a_7 = 22 $$ $$ \Rightarrow N = 22 $$

Q26. The sum of [x] for all real numbers x satisfying the equation 16 + 15x + 15x² = [x]³ is:

Solution:
Let x = n + t where n is the integer part and t is the fractional part, t is [0,1).
Then: 15(1 + x + x^2) = n^3 - 1 = (n-1)(1 + n + n^2)
1 + x + x^2 is always positive since coefficient of x^2 is positive and it has imaginary roots(cube roots of unity). Similarly for (1 + n + n^2).
So every factor on both sides is positive except (n-1) => n >= 2.
Now replace x = n + t.
(n-1)(1 + n + n^2) = 15(n^2 + n + 1 + t^2 + 2nt + t)
Take (1 + n + n^2) to LHS
(n-16)(1 + n + n^2) = 15(t^2 + t(2n+1))
\(0 \le t \lt 1\) and n >= 2 => RHS >= 0
So it forces n >= 16 since the other factor on LHS is always positive.
Now look at RHS. Given that t is [0,1) => 15(t^2 + t(2n+1)) < 15(1 + 2n + 1) = 30(n + 1).
So (n-16)(1 + n + n^2) < 30(n+1)________[1].
Look at LHS for n >= 18. LHS >= (18-16)(1 + n + n^2) => LHS >= 2(1 + n + n^2)
Compare 2(1 + n + n^2) with 30(n+1)
2(1 + n + n^2) - 30(n+1) = 2[n^2 - 14n - 14] = 2[(n-7)^2 - 63] > 0 for n>= 18________[2]
[1] above was the general result which gets contradicted by the specific result [2] which occurs when n >= 18.
=> 16 <= n < 18.
So n is {16,17}.
Now solve the original equation with n = 16, 17.
n = 16 and simplifying gives x^2 + x - 272 = 0 => x = 16, -17 but n = 16 => x = 16.
n = 17 gives 15x^2 + 15x + 16 = 17^3 => 15(1 + x + x^2) = 17^3 - 1 = (17 - 1)(1 + 17 + 17^2)
=> 15[(x + 1/2)^2 + 3/4] = 16(18 + 289) = 16(307)
=> [(x + 1/2)^2 + 3/4] = (16*307)/15 ~= 16*20.5 = 328
=> (x + 1/2)^2 = 327.25 => x + 1/2 ~= 18.something => x ~= 17.something so [x] = 17.
So answer 16 + 17 = 33.

Q27. In a triangle ABC, a point P in the interior of ABC is such that $$ \angle BPC - \angle BAC = \angle CPA - \angle CBA = \angle APB - \angle ACB. $$ Suppose \(\angle BAC = 30^\circ\) and AP = 12. Let D, E, F be the feet of perpendiculars from P on to BC, CA, AB respectively. If \(m\sqrt{n}\) is the area of the triangle DEF where m, n are integers with n prime, then what is the value of the product mn?

Solution:

Let \(\angle BPC - \angle BAC = \angle CPA - \angle CBA = \angle APB - \angle ACB = \alpha\) $$ \Rightarrow \angle BPC = \alpha + A, \quad \angle CPA = \alpha + B, \quad \angle APB = \alpha + C $$ $$ \angle BPC + \angle CPA + \angle APB = 360^\circ \ \Rightarrow\ \alpha = 60^\circ $$ Claim \(\triangle DEF\) is equilateral
Proof: Let \(\angle PBF = \alpha \ \& \ \angle PCE = \theta\)
Using cyclic quadrilateral PDCE, $$ \angle PDE = \angle PCE = \theta $$ $$ \angle PCB = C - \theta, \quad \angle EDC = 90^\circ - \theta $$ $$ \& \ \angle CPD = \angle DEC $$ $$ = 180^\circ - C - (90^\circ - \theta) = 90^\circ + \theta - C $$ Similarly, in cyclic quadrilateral PDFB: $$ \angle PDF = \alpha, \quad \angle PBD = B - \alpha, \quad \angle BDF = 90^\circ - \alpha, \ \& $$ $$ \angle BPD = \angle BFD $$ $$ = 180^\circ - B - (90^\circ - \alpha) = 90^\circ + \alpha - B $$ $$ \angle BPC = \angle CPD + \angle BPD $$ $$ = 180^\circ + \theta + \alpha - (B + C) = A + \theta + \alpha $$ But \(\angle BPC = 60^\circ + A \ \Rightarrow\ 60 + A = A + \theta + \alpha\) $$ \Rightarrow \theta + \alpha = 60 $$ $$ \Rightarrow \angle EDF = \theta + \alpha = 60^\circ $$ Similarly \(\angle DEF = \angle DFE = 60^\circ\) \(\Rightarrow \triangle DEF\) is equilateral triangle.
\(\Rightarrow\) AP is diameter of circumcircle of quadrilateral AEPF, let circumradius of \(\triangle AEF\) is R $$ \Rightarrow 2R = AP = 12 $$ $$ \Rightarrow R = 6 $$ Applying sine rule in \(\triangle AEF\): $$ \frac{\text{EF}}{\sin 30^\circ} = 2R \quad \Rightarrow \quad \text{EF} = 6 $$ Area of \(\triangle DEF\) = \(\frac{\sqrt{3}}{4} (\text{EF})^2\) $$ = \frac{\sqrt{3}}{4} (6)^2 = 9\sqrt{3} $$ $$ = m\sqrt{n} $$ \(\Rightarrow m \times n = 9 \times 3 = 27 \ \text{Ans.}\)

Q28. Find the largest positive integer \(n \lt 30\) such that \(\frac{1}{2}(n^8 + 3n^4 - 4)\) is not divisible by the square of any prime number.
Solution:
\(M = \frac{1}{2}(n^8 + 3n^4 - 4)\) $$ = \frac{1}{2}(n^4 + 4)(n^4 - 1) $$ $$ = \frac{1}{2}(n^4 + 4)(n - 1)(n + 1)(n^2 + 1) $$ $$ = \frac{1}{2}(n^2 + 2 - 2n)(n^2 + 2 + 2n)(n + 1)(n^2 + 1)(n - 1) $$ $$ = \frac{1}{2}((n + 1)^2 + 1)((n - 1)^2 + 1)(n + 1)(n^2 + 1)(n - 1) $$ $$ \Rightarrow \quad n \ \text{can not be odd otherwise} \ n + 1, \ n^2 + 1, \ n^2 + 1, \ n - 1 \ \text{are even then} \ m \ \text{is divisible by} \ 2^2 $$ $$ \Rightarrow \quad n \ \text{must be even} $$ Now last digit of n can not be 8 because both \((n - 1)^2 + 1 \ \& \ n^2 + 1\) is divisible by 5
Also last digit of n can not be 6 because both \((n - 1) \ \& \ (n + 1)^2 + 1\) is divisible by 5
Also last digit of n can not be 4 because both \((n + 1) \ \& \ (n - 1)^2 + 1\) is divisible by 5
Also last digit of n can not be 2 because both \(n^2 + 1 \ \& \ (n + 1)^2 + 1\) is divisible by 5
$$ \Rightarrow \quad 20 \ \text{satisfies the above condition} $$ $$ \Rightarrow \quad n = 20 $$

Q29. Let \(n = 2^{19}3^{12}\). Let M denote the number of positive divisors of \(n^2\) which are less than n but would not divide n. What is the number formed by taking the last two digits of M (in the same order)?

Solution:
Divisors of \(n^2\) come in pairs d, \(\frac{n^2}{d}\). Except when d = n, exactly one in the pair would be \(\lt n\).
Number of divisors of \(n^2\) = 39 * 25 = 975
So number of divisors \(\lt n\) = (975 - 1)/2 = 487
But we have to subtract those divisors which divide n.
Divisors of n = 20 * 13 = 260
But one of them is n itself and we are looking for \(\lt n\).
So divisors of n which are less than n = 259.
And diivisors of n^2 which are less than n = 487.
Answer = 487 - 259 = 228.


Q30. Let ABC be a right-angled triangle with \(\angle B = 90^\circ\). Let the length of the altitude BD be equal to 12. What is the minimum possible length of AC, given that AC and the perimeter of triangle ABC are integers?
Solution:
Call the legs c=AB and a=BC, the hypotenuse b=AC, and the altitude from the right angle h = BD = 12.
1. Area formulae give ac = 12b
2. Make the perimeter condition usable.
Let l= a+c . Since the perimeter is a+b+c = l+b and it is an integer, and b is an integer, l must also be an integer.
3. Relate l and b using Pythagoras.
$$ a^2+c^2=b^2\qquad\text{and}\qquad (a+c)^2=a^2+c^2+2ac. $$ Substitute l=a+c and ac=12b:
$$ l^2=b^2+2ac=b^2+24b \quad\Longrightarrow\quad b^2+24b-l^2=0. \tag{★} $$ 4. Ensure real positive legs a,c:
The legs are the roots of \(t^2-lt+ac=t^2-lt+12b=0\).
Its discriminant must be \(\ge 0\):
$$ \Delta=l^2-4\cdot12b=l^2-48b\ge0. \tag{†} $$ If you combine (★) and (†), or simply substitute \(l^2=b^2+24b\) into (†), you get
$$ b^2-24b\ge0 \quad\Longrightarrow\quad b\ge24. $$ So AC=b is at least 24.
5. Turn (★) into a factorization.
Complete the square in (★):
$$ l^2=(b+12)^2-144. $$ Let \(k=b+12\) (then \(k\ge36\) because \(b\ge24\)).
Then
$$ k^2-l^2=144\quad\Longrightarrow\quad (k-l)(k+l)=144. $$ Here k and l are integers and \(k>l>0\). Since 144 is even, both factors must be even.
To minimize b we minimize k=b+12 subject to (k-l)(k+l)=144 and \(k\ge36\). The smallest even factor pair with \(k\ge36\) is 2 and 72: $$ k=\frac{2+72}{2}=37,\qquad l=\frac{72-2}{2}=35. $$ Then $$ b=k-12=37-12=25. $$ 6. Check it works.
From l = 35 and b=25, $$ a,c=\frac{l\pm\sqrt{l^2-48b}}{2}=\frac{35\pm\sqrt{1225-1200}}{2} =\frac{35\pm5}{2}=20,\,15, $$ so \(h=\dfrac{ac}{b}=\dfrac{15\cdot20}{25}=12\) and the perimeter \(=15+20+25=60\) is an integer. Therefore, the minimum possible length of AC is \(\boxed{25}\).