Number System: CAT previous year questions

Solution

Allowed digits (non-zero, not perfect squares): 2, 3, 5, 6, 7, 8. Primes among them: 2, 3, 5, 7; non-primes: 6, 8.

Exactly one prime means the digits are 6, 8 and one prime.

Smallest such number: digits 2, 6, 8 give $N = 268$.

$268 = 2^2 \times 67$, so the number of factors $= 3 \times 2 = 6$.

Solution

Let $A = m + 2n$ and $B = 2m + n$ with $AB = 27$. Then $m = \dfrac{2B - A}{3}$, $n = \dfrac{2A - B}{3}$, and $2m - 3n = \dfrac{7B - 8A}{3}$.

Integer $m, n$ need $2B - A$ divisible by 3: $(A, B) = (3, 9), (9, 3), (-3, -9), (-9, -3)$.

Values of $2m - 3n$: $13, -17, -13, 17$.

Maximum $= 17$ (at $m = 1$, $n = -5$).

Solution

$625^{65} = 5^{260}$ and $128^{36} = 2^{252}$.

Product $= 10^{252} \times 5^8 = 390625 \times 10^{252}$.

Sum of digits $= 3 + 9 + 0 + 6 + 2 + 5 = 25$.

Solution

$3ac = 8(a + b) \Rightarrow b = \dfrac{a(3c - 8)}{8}$.

$a = 1$: $c = 8$, $b = 2$ gives $3 + 4 + 8 = 15$.

$a = 2$: $b = \dfrac{3c - 8}{4}$; $c = 4$ gives $b = 1$, and $3(2) + 2(1) + 4 = 12$ (check: $3 \times 2 \times 4 = 24 = 8 \times 3$ ✓).

Larger $a$ only increase the total (e.g. $a = 4$: 28; $a = 8$: 29).

Smallest value $= 12$.

Solution

A divisor $\equiv 1 \pmod 3$ cannot contain 3, so it is $2^a 5^c 7^d$.

Mod 3: $2 \equiv -1$, $5 \equiv -1$, $7 \equiv 1$. We need $(-1)^{a + c} = 1$, i.e. $a + c$ even.

$a \in \{0..6\}$ (4 even, 3 odd), $c \in \{0..3\}$ (2 even, 2 odd): $4 \times 2 + 3 \times 2 = 14$ ways; $d$ has 3 choices.

Total $= 14 \times 3 = 42$.

Solution

Let the number be $ABCD$. $A + B + C = 15$ and $B + C + D = 16 \Rightarrow D = A + 1$.

$C = D + 6$, so $D \leq 3$, and $A = D - 1 \geq 1$ gives $D = 2$ or $3$.

$D = 2$: $A = 1$, $C = 8$, $B = 6$: 1682. $D = 3$: $A = 2$, $C = 9$, $B = 4$: 2493.

Difference $= 2493 - 1682 = 811$.

Solution

$10^{25} - 123 = \underbrace{99\ldots9}_{22}877$ (25 digits).

Adding $10^{50}$ puts a 1 in front with zeros in between.

Digit sum $= 1 + 22 \times 9 + 8 + 7 + 7 = 1 + 198 + 22 = 221$.

Solution

$10 \equiv 3 \pmod 7$ and $3^6 \equiv 1 \pmod 7$.

$100 = 6 \times 16 + 4$, so $10^{100} \equiv 3^4 = 81 \equiv 4 \pmod 7$.

Remainder $= 4$.

Solution

Group by the value of $\lfloor\sqrt{n}\rfloor$:

1 for $n = 1$–3 (3 terms), 2 for 4–8 (5), 3 for 9–15 (7), 4 for 16–24 (9), 5 for 25–35 (11), 6 for 36–48 (13), 7 for 49–50 (2).

Sum $= 3 + 10 + 21 + 36 + 55 + 78 + 14 = 217$.

Solution

$n$ must divide both exponents 25 and 40, and $n > 1$, so $n = 5$.

$m = 2^5 \times 3^8 = 32 \times 6561 = 209952$.

$m - n = 209947$.

Solution

$3^5 = 243 = 22 \times 11 + 1$, so $3^5 \equiv 1 \pmod{11}$.

$333 = 5 \times 66 + 3 \Rightarrow 3^{333} \equiv 3^3 = 27 \equiv 5 \pmod{11}$.

Solution

$10^3 = 1000 \equiv -1 \pmod{13}$, so $10^6 \equiv 1$.

$68 = 6 \times 11 + 2 \Rightarrow 10^{68} \equiv 10^2 = 100 \equiv 9 \pmod{13}$.

Solution

$168 = 2^3 \times 3 \times 7$ and $1134 = 2 \times 3^4 \times 7$.

$1134^n$ needs at least $2^3$: $n = 3$, giving $1134^3 = 2^3 \times 3^{12} \times 7^3$.

$168^m = 2^{3m} 3^m 7^m$ needs $3^{12}$: $m = 12$.

$m + n = 15$.

Solution

$144^{145} = 2^{580} \times 3^{290}$.

Make $n$ as large and $m$ as small as possible: $m = 1$, $a = 3^{290}$, $b = 2$, $n = 580$.

$n - m = 579$.

Solution

$k$ divides $(3m + 4n) - 2(m + 2n) = m$.

Then $k$ also divides $(m + 2n) - m = 2n$.

So $k$ is a common divisor of $m$ and $2n$.

Solution

Exactly two factors other than 1 and itself means exactly 4 factors: $p^3$ or $pq$.

$p^3 < 50$: 8, 27 (2 numbers).

$pq < 50$: $2 \times \{3, 5, 7, 11, 13, 17, 19, 23\}$ (8), $3 \times \{5, 7, 11, 13\}$ (4), $5 \times 7$ (1).

Total $= 2 + 13 = 15$.

Solution

$8^m = 2^{3m}$ and $8^n = 2^{3n}$. Powers of 2 strictly between them: $3n - 3m - 1 = 41 \Rightarrow n - m = 14$.

Smallest sum: $m = 1$, $n = 15$, so $n + m = 16$.

Solution

15 factors: $p^{14}$ or $p^4 q^2$.

Smallest candidates: $2^4 \times 3^2 = 144$, $2^2 \times 3^4 = 324$, $2^4 \times 5^2 = 400$, …

Sum of the two smallest $= 144 + 324 = 468$.

Solution

$3^k + 4^k + 5^k$: $k = 1$ gives 12, $k = 2$ gives 50; $\gcd = 2$, and the sum is always even. So $A = 2$.

$4^k + 3 \cdot 4^k + 4^{k+2} = 4^k(1 + 3 + 16) = 20 \times 4^k$, which is 80 at $k = 1$ and a multiple of 80 always. So $B = 80$.

$A + B = 82$.

Solution

$y(x + z) = 19$ (prime): $y = 1$, $x + z = 19$ ($y = 19$ is impossible).

$z(x + 1) = 51$: $z = 3, x = 16$ ($x + z = 19$ ✓) or $z = 17, x = 2$ ($x + z = 19$ ✓).

$xyz = 48$ or $34$. Minimum $= 34$.

Solution

$\left[\dfrac{1}{5} + \dfrac{n}{25}\right] = \left[\dfrac{n + 5}{25}\right]$.

This is 0 for $n \leq 19$ and 1 for $20 \leq n \leq 44$ (25 terms).

The sum first equals 25 at $N = 44$.

Solution

$(n!)!$ divides $15000!$ exactly when $n! \leq 15000$.

$7! = 5040 \leq 15000$ but $8! = 40320 > 15000$.

Largest $n = 7$.

Solution

LCM of 9, 10, 12, 25 $= 900$, so $N = 900k + 4 < 5000$.

$N$ divisible by 11: $900 \equiv 9 \pmod{11}$, so $9k + 4 \equiv 0 \Rightarrow k \equiv 2 \pmod{11}$, giving $k = 2$, $N = 1804$.

Teams of 12: $\left\lfloor \dfrac{1804}{12} \right\rfloor = 150$.

Solution

For $\overline{abc}$: $\overline{cba} - \overline{abc} = 99(c - a) = 198 \Rightarrow c = a + 2$.

$a$ can be 1 to 7 and $b$ can be 0 to 9: $7 \times 10 = 70$ numbers.

Solution

Let the number be $ABCD$. $A + B + C = 14$ and $B + C + D = 15 \Rightarrow D = A + 1$.

$C = D + 4 = A + 5 \leq 9 \Rightarrow A \leq 4$, and $B = 14 - A - C = 9 - 2A$.

The largest number takes $A = 4$: $C = 9$, $D = 5$, $B = 1$.

Answer: $4195$.

Solution

Let the prices be $2k$, $5k$ and $L$: $10k^2 L = 800$.

After the increase: $(2k + 6)(5k + 6)L = 3200$. Dividing: $(2k + 6)(5k + 6) = 40k^2$.

$30k^2 - 42k - 36 = 0 \Rightarrow 5k^2 - 7k - 6 = 0 \Rightarrow k = 2$, so $L = 20$.

Prices 4, 10, 20; sum $= 34$.

Solution

100 students in 12 months: if every month had at most 8, the total would be at most 96.

So some month has at least 9, and 9 is achievable (e.g. 4 months of 9 and 8 months of 8).

Smallest $x_0 = 9$.

Solution

$\overline{aabb} = 1100a + 11b$ with $a = 1$–9 and $b \in \{0, 2, 4, 6, 8\}$ (even).

All combinations occur equally, so mean $= 1100 \times 5 + 11 \times 4 = 5544$.

Solution

$\dfrac{ab}{bc} = \dfrac{a}{c} = \dfrac{432}{96} = \dfrac{9}{2}$, so $a = 4.5c$, meaning $c$ is even.

$c = 2$: $b = 48$, $a = 9$, sum 59. $c = 4$: $b = 24$, $a = 18$, sum 46. $c = 6$: $b = 16$, $a = 27$, sum 49. $c = 8$: $b = 12$, $a = 36$, sum 56.

Smallest $= 46$.

Solution

$x \in \{3, \dots, 9\}$ and $y \in \{15, \dots, 22\}$, so $N = x + y$ ranges over 18 to 31.

$N > 25$: $N = 26, 27, \dots, 31$: $6$ values.

Solution

Count numbers divisible by 2, 5 or 7 using inclusion–exclusion:

$60 + 24 + 17 - 12 - 8 - 3 + 1 = 79$.

Numbers divisible by none $= 120 - 79 = 41$.

Solution

$4^{2017} = 2^{4034}$, which has 4035 divisors.

Each pair $a \leq b$ with $ab = 2^{4034}$ matches a divisor $a \leq 2^{2017}$: $\dfrac{4035 + 1}{2} = 2018$ pairs.