IOQM 2023 solutions

Q1. Let $n$ be a positive integer such that $1\le n\le 1000$. Let $M_n$ be the number of integers in the set $X_n=\{\sqrt{4n+1},\sqrt{4n+2},\dots ,\sqrt{4n+1000}\}$. Let
$$a = \max\{M_n : 1 \leq n \leq 1000\}, \quad \text{and} \quad b = \min\{M_n : 1 \leq n \leq 1000\}.$$

Find $a - b$.

Solution:
Quick tip:
If n^2 = k then (n+1)^2 = k + (2n + 1)
We will use this here.
Also as the numbers grow larger the gap between 2 perfect squares becomes less and less.
For. e.g. there are 10 perfect squares between 1 and 100 but only 4 perfect squares between 101 and 200.
So
X1 = {sqrt(5) ... sqrt(1004)}
will have the most number of perfect squares.
While
X1000 = {sqrt(4001)...sqrt(5000)}
will have the least.

In X1 the first integer square root is 3 and we know that 1024 is the square of 32 so the last integer will be 31.
Total: 31 - 3 + 1 = 29 integers in X1.

In X1000,
We know that 64^2 = 4096 so 64 is the first integer.
70^2 = 4900 and 71^2 = 4900 + 141 > 5000 so 70 is the last.
Total: 70 - 64 + 1 = 7
Answer: 29 - 7 = 22.

Q2.

Find the number of elements in the set

$$\{(a, b) \in \mathbb{N} : 2 \leq a, \, b \leq 2023, \, \log_a(b) + 6 \log_b(a) = 5\}$$

---

Solution:

---

$$t + \frac{6}{t} = 5$$ $$\therefore t^2 + 6 = 5t$$ $$t^2 - 5t + 6 = 0$$ $$t = 2, \, 3$$ $$\log_a b = 2, \quad \log_a b = 3$$ $$\therefore b = a^2, \quad b = a^3$$

---

So we need to find perfect squares and cubes between 2 and 2023.
For squares we know that 45^2 = 2025 so we will have 2^2 to 44^2 => 43 pairs.
For cubes we know from Ramanujan number 1729 = 12^3 + 1^3 that 12^3 = 1728.
And then we compute 13^3 which comes out to be 2197.
So we have 11 pairs.
Answer: 54.

Q3. 

---

Let $\alpha$ and $\beta$ be positive integers such that

$$\frac{16}{37} < \frac{\alpha}{\beta} < \frac{7}{16}.$$

Find the smallest possible value of $\beta$.

---

Solution:

---

$$\frac{16}{37} < \frac{\alpha}{\beta} < \frac{7}{16}$$ $$16\beta < 37\alpha \quad\quad 16\alpha < 7\beta$$ $$\beta < \frac{37\alpha}{16} \quad\quad \beta > \frac{16\alpha}{7}$$ $$\frac{16\alpha}{7} < \beta < \frac{37\alpha}{16}$$

For $\alpha = 1, 2, 3, \ldots, 9$, $\beta \notin \mathbb{I}^+$
At $\alpha = 10$

$$22.8571 < \beta < 23.125$$ $$\boxed{\beta = 23}$$

---

Now note that we shouldn't try each value from 1 to 10 here.
Start with 1, 5, 10. Whenever you get a valid answer, then take the previous value until you are sure you have found the minimum.

Q4.

---

Let $x,y$ be positive integers such that

$$x^4 = (x - 1)(y^3 - 23) - 1.$$

Find the maximum possible value of $x + y$.

---

Solution:

---

Sol.

$$x^4 = (x - 1)(y^3 - 23) - 1$$ $$\Rightarrow \frac{x^4 + 1}{x - 1} = y^3 - 23$$ $$\Rightarrow \frac{x^4 + 1}{x - 1} + 23 = y^3 \quad \Rightarrow \quad \frac{x^4 + 1 + 23x - 23}{x - 1} = y^3$$ $$\Rightarrow \frac{x^4 + 23x - 22}{x - 1} = y^3$$

Since $x$ and $y$ are integers
$\therefore x - 1$ will completely divide $x^4 + 23x - 22$

$$\begin{array}{r|rrrrr} 1 & 1 & 0 & 0 & 23 & -22 \\ & & 1 & 1 & 1 & 24 \\ \hline 1 & 1 & 1 & 1 & 24 & (2) \ \text{remainder} \end{array}$$

There shouldn't be any remainder, thus 2 must be divisible by $x - 1$ and since $x \in \mathbb{I}$, only possible values are 2 and 3.

When $x = 2$:

$$y^3 = \frac{2^4 + 23 \times 2 - 22}{1} = \frac{46 - 6}{1} = 40$$

which means $y \notin \mathbb{I}$.

When $x = 3$:

$$y^3 = \frac{81 + 69 - 22}{2} = \frac{59 + 69}{2} = \frac{128}{2} = 64$$

Thus $y = 4$.

$\therefore x + y = 3 + 4 = 7$.

---

Q5.

---

In a triangle $ABC$, let $E$ be the midpoint of $AC$ and $F$ be the midpoint of $AB$.
The medians $BE$ and $CF$ intersect at $G$. Let $Y$ and $Z$ be the midpoints of $BE$ and $CF$ respectively. If the area of triangle $ABC$ is $480$, find the area of triangle $GYZ$.

---

Solution:

Solution link.

Q6.

---

Let $X$ be the set of all even positive integers $n$ such that the measure of the angle of some regular polygon is $n$ degrees. Find the number of elements in $X$.

---

Solution:

---

Sol. Let number of sides of polygon be $P$.

$$\therefore \frac{(P - 2) \cdot 180^\circ}{P} = n^\circ$$

then

$$P(180 - n) = 360$$ $$\therefore P = \frac{360}{180 - n}$$

But $n = 2k$ then

$$P = \frac{180}{90 - k}$$

---

Now we need to find divisors of 180 between 1 to 89 since k can be 1 to 89 so 90 - k  is also 1 to 89.
180 = 2^2*3^2*5
Total divisors = 3*3*2 = 18
Let's enumerate:
With 2^0:
2^0 3^0 5^0 = 1
2^0 3^0 5^1 = 5
2^0 3^1 5^0 = 3
2^0 3^1 5^1 = 15
2^0 3^2 5^0 = 9
2^0 3^2 5^1 = 45

With 2^1, multiply all the above with 2:
2
10
6
30
18
90 (invalid since > 89)

With 2^2, multiply all the above with 2:
4
20
12
60
36
180(invalid > 89)
So total valid divisors = 6 + 5 + 5 = 16 = Answer. 

Q7.

---

Unconventional dice are to be designed such that the six faces are marked with numbers from 1 to 6 with 1 and 2 appearing on opposite faces. Further, each face is colored either red or yellow with opposite faces always of the same color. Two dice are considered to have the same design if one of them can be rotated to obtain a dice that has the same numbers and colors on the corresponding faces as the other one. Find the number of distinct dice that can be designed.

---

Solution:

---

Sol. Arrangement of 3, 4, 5, 6 can be done in $3!$ ways = 6 ways (using circular permutation)
Coloring can be done in $2 \times 2 \times 2 \times 2 = 8$ ways

$\Rightarrow$ Total designs are $8 \times 6 = 48$ ways.

---

One important point to note here is that we can also get 24 as the answer if we make a mistake.
Let's say we fix 1 and 2 as the top/bottom face of the dice.
Then we are left with 4 distinct numbers to be arranged in the horizontal plane in a circular manner.
Now circular permutation theory implies that there are (4-1)! ways to arrange 4 distinct people around a table.
But we might get confused and apply the necklace/garland logic here and divide it by 2.
That would be wrong.
When we use the necklace logic, we are saying that 3-4-5-6 clockwise and counter-clockwise is same.
Here that's not true.
Because let's say we have this config:
Top-1, Bottom-2,Left-3,Right-4,Front-5,Back-6
Here 3-5-4-6 is the clockwise permutation.
Compare with this:
Top-1, Bottom-2,Left-4,Right-3,Front-6,Back-5
Here 3-5-4-6 is the counter-clockwise permutation.
If they are same we should be able to rotate the first one and get the second one.
But no matter how you rotate, you won't be able to do that.

Q8.

---

Given a $2\times 2$ tile and seven dominoes ($2\times 1$ tile), find the number of ways of tiling (that is cover without leaving gaps and without overlapping of any two tiles) a $2\times 7$ rectangle using some of these tiles.

---

Solution:

Case 1: Use only 2x1 tiles.

Let $f(n)$ be the number of ways to tile a $2\times n$ board using only $2\times1$ dominoes.

Look at the leftmost column(s) of any tiling and split into two mutually exclusive cases:

1. A vertical domino in column 1

|#|          <- vertical domino in col 1
|#|  | |...| |

Once you place that vertical domino, the rest is a $2\times(n-1)$ board, which can be tiled in $f(n-1)$ ways.

2. No vertical domino in column 1

Then the two squares in column 1 must each be covered by a horizontal domino. That forces two horizontal dominoes spanning columns 1–2:

##|          <- top horizontal covers (1,1)-(1,2)
##|          <- bottom horizontal covers (2,1)-(2,2)
   | |...| |

After that, what remains is a $2\times(n-2)$ board, giving $f(n-2)$ possibilities.

These two cases are disjoint and exhaustive, and choosing the first placement uniquely determines the smaller sub-board you must tile. Hence the recurrence:

$$f(n) = f(n-1) + f(n-2),$$

with bases $f(0)=1$ (empty board) and $f(1)=1$ (one vertical domino).
So $f(n)$ is the Fibonacci sequence shifted by one index: $f(n)=F_{n+1}$.

•  Case 1: Use only 2x1 tiles. Then
  $f(0)=1,\; f(1)=1,\; f(n)=f(n-1)+f(n-2)\Rightarrow f(2..6)=(2,3,5,8,13)$.
  So domino-only tilings of $2\times7$ = $f(7)=21$.

• Case 2: If we use the single $2\times2$ tile, place it covering columns $i,i+1$ for $i=1,\dots,6$.
  This splits the board into independent strips of sizes $2\times(i-1)$ and $2\times(6-i)$.
  Count for a fixed $i$: $f(i-1)\,f(6-i)$.

Sum over $i$:

$$\begin{aligned} &f(0)f(5)+f(1)f(4)+f(2)f(3)+f(3)f(2)+f(4)f(1)+f(5)f(0)\\ &=1\cdot8+1\cdot5+2\cdot3+3\cdot2+5\cdot1+8\cdot1=38. \end{aligned}$$

Total tilings $= 21 + 38 = \boxed{59}$.

Q9.

---

Find the number of triples $(a,b,c)$ of positive integers such that

(a) $ab$ is a prime;
(b) $bc$ is a product of two primes;
(c) $abc$ is not divisible by square of any prime and
(d) $abc \leq 30$.

---

Solution:

Here’s the text from the image:

---

Sol. $abc \leq 30$
and $abc$ is not divisible by 4, 9, 25

So $abc$ can take values:
$1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30$

$\therefore ab$ is prime.

Case 1: When $a = 1$ and $b$ is prime number.

$a = 1, \ b = 2, \ c = 3, 5, 7, 11, 13$
$b = 3, \ c = 2, 5, 7$
$b = 5, \ c = 2, 3$
$b = 7, \ c = 2, 3$
$b = 11, \ c = 2$
$b = 13, \ c = 2$

There are total 14 triples of $(a, b, c)$.

Case 2: When $b = 1$ and $a$ is prime number.

$b = 1, \ a = 2, \ c = 15$
$a = 3, \ c = 10$
$a = 5, \ c = 6$

There are 3 triples of $(a, b, c)$.

From Case I and Case II, total 17 triples of $(a, b, c)$ are possible.

---

Q10.

---

The sequence $⟨a_n{⟩}_{n\ge 0}$ is defined by $a_0=1$, $a_1=-4$ and $a_{n+2}=-4a_{n+1}-7a_n$, for $n\ge 0$. Find the number of positive integer divisors of $a_{50}^2-a_{49}{a}_{51}$.

---

Solution:
One way to solve it is to compute:
a1^2 - a0a2 = 7
a2^2 - a1a3 = 49
a3^2 - a2a4 = 343
So 
a50^2 - a49a51 = 7^50 which has 51 divisors = answer.

Method 2:

---

Sol. The sequence $\{a_n\}$, $n \ge 0$ and $a_0 = 1$, $a_1 = -4$ and given that $a_{n+2} = -4a_{n+1} - 7a_n$ ….(1)

Now

$$a_n^2 - a_{n+1} \cdot a_{n-1} = a_n^2 - (4a_n - 7a_{n-1}) a_{n-1}$$ $$= a_n^2 + 4a_n a_{n-1} + 7a_{n-1}^2$$ $$= -a_n (7a_{n-2}) + 7a_{n-1}^2$$ $$= 7(a_{n-1}^2 - a_n a_{n-2})$$ $$= 7^2(a_{n-1}^2 - a_{n-1} a_{n-3})$$

…

$$\therefore a_n^2 - a_{n+1} a_{n-1} = 7^{n-1} (a_1^2 - a_0 a_2) = 7^{n-1}(16 - 1 \cdot 9) = 7^n$$ $$\therefore a_{50}^2 - a_{49} a_{51} = 7^{50}$$ $$\therefore \text{Number of positive integer divisors of } 7^{50} = 50 + 1 = 51$$

---

Method 3:
Since this is a linear homogeneous recurrence equation of order 2 with constant coefficients, see this for how to solve.

asdf

asdf