Consider the $\mathbb{Q}$-vector-space $$\{ f : \mathbb{R} \longrightarrow \mathbb{R} \mid f \text{ is continuous and } \mathrm{Image}(f) \subseteq \mathbb{Q} \}$$ What is its dimension?

Let $p$ be a prime number and $F$ a field of $p^{23}$ elements. Let $\phi : F \longrightarrow F$ be the field automorphism of $F$ sending $a$ to $a^p$. Let $K := \{ a \in F \mid \phi(a) = a \}$. What is the value of $[K : \mathbb{F}_p]$?

The domain of a function $f$ is the set of natural numbers. The function is defined as follows: $$f(n) = n + \lfloor \sqrt{n} \rfloor$$ where $\lfloor k \rfloor$ denotes the nearest integer smaller than or equal to $k$. For example, $\lfloor \pi \rfloor = 3$, $\lfloor 4 \rfloor = 4$. Prove that for every natural number $m$ the following sequence contains at least one perfect square $$m, f(m), f^{2}(m), f^{3}(m), \ldots$$ The notation $f^{k}$ denotes the function obtained by composing $f$ with itself $k$ times, e.g., $f^{2} = f \circ f$.

Each integer is colored with exactly one of three possible colors - black, red or white satisfying the following two rules: the negative of a black number must be colored white, and the sum of two white numbers (not necessarily distinct) must be colored black.
(a) Show that the negative of a white number must be colored black and the sum of two black numbers must be colored white.
(b) Determine all possible colorings of the integers that satisfy these rules.

List in increasing order all positive integers $n \leq 40$ such that $n$ cannot be written in the form $a^{2} - b^{2}$, where $a$ and $b$ are positive integers.

For a natural number $m$, define $\Phi_{1}(m)$ to be the number of divisors of $m$ and for $k \geq 2$ define $\Phi_{k}(m) := \Phi_{1}\left(\Phi_{k-1}(m)\right)$. For example, $\Phi_{2}(12) = \Phi_{1}(6) = 4$. Find the minimum $k$ such that $$\Phi_{k}\left(2019^{2019}\right) = 2.$$

For how many natural numbers $n$ is $n^{6} + n^{4} + 1$ a square of a natural number?

A broken calculator has all its 10 digit keys and two operation keys intact. Let us call these operation keys A and B. When the calculator displays a number $n$ pressing A changes the display to $n+1$. When the calculator displays a number $n$ pressing $B$ changes the display to $2n$. For example, if the number 3 is displayed then the key strokes ABBA changes the display in the following steps $3 \rightarrow 4 \rightarrow 8 \rightarrow 16 \rightarrow 17$.
If 1 is on the display what is the least number of key strokes needed to get 260 on the display?

Let $|\cdot| : \mathbb{R} \longrightarrow \mathbb{R}_{\geq 0}$ be a function such that for every $x, y \in \mathbb{R}$, (i) $|x| = 0$ if and only if $x = 0$; (ii) $|x + y| \leq |x| + |y|$; (iii) $|xy| = |x||y|$. Show that the following are equivalent:
(A) The set $\{|n| : n \in \mathbb{Z}\}$ is bounded;
(B) $|x + y| \leq \max\{|x|, |y|\}$ for every $x, y \in \mathbb{R}$.

For a positive integer $n$, let $D(n) =$ number of positive integer divisors of $n$. For example, $D(6) = 4$ because 6 has four divisors, namely $1, 2, 3$ and $6$. Find the number of $n \leq 60$ such that $D(n) = 6$.

Note that $25 \times 16 - 19 \times 21 = 1$. Using this or otherwise, find positive integers $a, b$ and $c$, all $\leq 475 = 25 \times 19$, such that

• $a$ is $1 \bmod 19$ and $0 \bmod 25$,
• $b$ is $0 \bmod 19$ and $1 \bmod 25$, and
• $c$ is $4 \bmod 19$ and $10 \bmod 25$.

(Recall the mod notation: since 13 divided by 5 gives remainder 3, we say 13 is $3 \bmod 5$.)

[12 points] For sets $S$ and $T$, a relation from $S$ to $T$ is just a subset $R$ of $S \times T$. If $(x, y)$ is in $R$, we say that $x$ is related to $y$. Answer the following. Part (i) is independent of (ii) and (iii).
(i) A relation $R$ from $S$ to $S$ is called antisymmetric if it satisfies the following condition: if $(a, b)$ is in $R$, then $(b, a)$ must NOT be in $R$. For $S = \{1, 2, \ldots, k\}$, how many antisymmetric relations are there from $S$ to $S$?
(ii) Write a recurrence equation for $f(k, n) =$ the number of non-crossing relations from $\{1, 2, \ldots, k\}$ to $\{1, 2, \ldots, n\}$ that have no isolated elements in either set. Your recurrence should have only a fixed number of terms on the RHS.
(iii) Using your recurrence in (ii) or otherwise, find a formula for $f(3, n)$.
Definition 1: We say that a relation from $S$ to $T$ has no isolated elements if each $s$ in $S$ is related to some $t$ in $T$ and if for each $t$ in $T$, some $s$ in $S$ is related to $t$.
Definition 2: We say that a relation $R$ from $\{1, 2, \ldots, k\}$ to $\{1, 2, \ldots, n\}$ is non-crossing if the following never happens: $(i, x)$ and $(j, y)$ are both in $R$ with $i < j$ but $x > y$.
Visual meaning: one can visualise a relation $R$ very similarly to a function. List 1 to $k$ as dots arranged vertically in increasing order on the left and similarly list 1 to $n$ on the right. For each $(s, t)$ in $R$, draw a straight line segment from $s$ on the left to $t$ on the right. In the situation one wants to avoid for non-crossing relations, the segments connecting $i$ with $x$ and $j$ with $y$ would cross. Having no isolated elements also has an obvious visual meaning.

$n$ and $k$ are positive integers, not necessarily distinct. You are given two stacks of cards with a number written on each card, as follows.
Stack A has $n$ cards. On each card a number in the set $\{ 1 , \ldots , k \}$ is written. Stack B has $k$ cards. On each card a number in the set $\{ 1 , \ldots , n \}$ is written. Numbers may repeat in either stack. From this, you play a game by constructing a sequence $t _ { 0 } , t _ { 1 } , t _ { 2 } , \ldots$ of integers as follows. Set $t _ { 0 } = 0$. For $j > 0$, there are two cases: If $t _ { j } \leq 0$, draw the top card of stack $A$. Set $t _ { j + 1 } = t _ { j } +$ the number written on this card. If $t _ { j } > 0$, draw the top card of stack $B$. Set $t _ { j + 1 } = t _ { j } -$ the number written on this card. In either case discard the taken card and continue. The game ends when you try to draw from an empty stack. Example: Let $n = 5 , k = 3$, stack $A = 1,3,2,3,2$ and stack $B = 2,5,1$. You can check that the game ends with the sequence $0,1 , - 1,2 , - 3 , - 1,2,1$ (and with one card from stack $A$ left unused).
(i) Prove that for every $j$ we have $- n + 1 \leq t _ { j } \leq k$.
(ii) Prove that there are at least two distinct indices $i$ and $j$ such that $t _ { i } = t _ { j }$.
(iii) Using the previous parts or otherwise, prove that there is a nonempty subset of cards in stack $A$ and another subset of cards in stack $B$ such that the sum of numbers in both the subsets is same.

A prime $p$ is an integer $\geq 2$ whose only positive integer factors are 1 and $p$.
(a) For any prime $p$ the number $p ^ { 2 } - p$ is always divisible by 3.
(b) For any prime $p > 3$ exactly one of the numbers $p - 1$ and $p + 1$ is divisible by 6.
(c) For any prime $p > 3$ the number $p ^ { 2 } - 1$ is divisible by 24.
(d) For any prime $p > 3$ one of the three numbers $p + 1 , p + 3$ and $p + 5$ is divisible by 8.

[11 points] In the XY plane, draw horizontal and vertical lines through each integer on both axes so as to get a grid of small $1 \times 1$ squares whose vertices have integer coordinates.
(i) Consider the line segment $D$ joining $(0,0)$ with $(m,n)$. Find the number of small $1 \times 1$ squares that $D$ cuts through, i.e., squares whose interiors $D$ intersects. (Interiors consist of points for which both coordinates are non-integers.) For example, the line segment joining $(0,0)$ and $(2,3)$ cuts through 4 small squares, as you can check by drawing.
(ii) Now $L$ is allowed to be an arbitrary line in the plane. Find the maximum number of small $1 \times 1$ squares in an $n \times n$ grid that $L$ can cut through, i.e., we want $L$ to intersect the interiors of maximum possible number of small squares inside the square with vertices $(0,0)$, $(n,0)$, $(0,n)$ and $(n,n)$.

[15 points] Solve the following. You may do (i) and (ii) in either order.
(i) Let $p$ be a prime number. Show that $x^2 + x - 1$ has at most two roots modulo $p$, i.e., the cardinality of $\{n \mid 1 \leq n \leq p$ and $n^2 + n - 1$ is divisible by $p\}$ is $\leq 2$. Find all primes $p$ for which this set has cardinality 1.
(ii) Find all positive integers $n \leq 121$ such that $n^2 + n - 1$ is divisible by 121.
(iii) What can you say about the number of roots of $x^2 + x - 1$ modulo $p^2$ for an arbitrary prime $p$, i.e., the cardinality of
$$\left\{n \mid 1 \leq n \leq p^2 \text{ and } n^2 + n - 1 \text{ is divisible by } p^2\right\}?$$
You do NOT need to repeat any reasoning from previous parts. You may simply refer to any such relevant reasoning and state your conclusion with a brief explanation.

Statements
(17) $\sqrt [ 4 ] { 4 } < \sqrt [ 5 ] { 5 }$. (18) $\log _ { 10 } 11 > \log _ { 11 } 12$. (19) $\frac { \pi } { 4 } < \sqrt { 2 - \sqrt { 2 } }$. (20) $( 2022 ! ) ^ { 2 } > 2022 ^ { 2022 }$.

Statements
(25) There is a unique natural number $n$ such that $n ^ { 2 } + 19 n - n ! = 0$. (26) There are infinitely many pairs $( x , y )$ of natural numbers satisfying $$( 1 + x ! ) ( 1 + y ! ) = ( x + y ) ! .$$ (27) For any natural number $n$, consider GCD of $n ^ { 2 } + 1$ and $( n + 1 ) ^ { 2 } + 1$. As $n$ ranges over all natural numbers, the largest possible value of this GCD is 5. (28) If $n$ is the largest natural number for which 20! is divisible by $80 ^ { n }$, then $n \geq 5$.

[14 points] Suppose an integer $n > 1$ is such that $n + 1$ is not a multiple of 4 (i.e., such that $n$ is not congruent to $3 \bmod 4$). Prove that there exist $1 \leq i < j \leq n$ such that the following is a perfect square.
$$\frac { 1 ! 2 ! \cdots n ! } { i ! j ! }$$
Hint (use this or your own method): Make cases and first treat the case $n = 4k$.

Statements
(25) To divide an integer $b$ by a nonzero integer $d$, define a quotient $q$ and a remainder $r$ to be integers such that $b = q d + r$ and $| r | < | d |$. Such integers $q$ and $r$ always exist and are both unique for given $b$ and $d$. (26) To divide a polynomial $b ( x )$ by a nonzero polynomial $d ( x )$, define a quotient $q ( x )$ and a remainder $r ( x )$ to be polynomials such that $b = q d + r$ and $\deg ( r ) < \deg ( d )$. (Here $b ( x )$ and $d ( x )$ have real coefficients and the 0 polynomial is taken to have negative degree by convention.) Such polynomials $q ( x )$ and $r ( x )$ always exist and are both unique for given $b ( x )$ and $d ( x )$. (27) Suppose that in the preceding question $b ( x )$ and $d ( x )$ have rational coefficients. Then $q ( x )$ and $r ( x )$, if they exist, must also have rational coefficients. (28) The least positive number in the set $$\left\{ \left( a \times 2023 ^ { 2020 } \right) + \left( b \times 2020 ^ { 2023 } \right) \right\}$$ as $a$ and $b$ range over all integers is 3.

We want to find odd integers $n > 1$ for which $n$ is a factor of $2023 ^ { n } - 1$.
(a) Find the two smallest such integers.
(b) Prove that there are infinitely many such integers.

Starting with any given positive integer $a > 1$ the following game is played. If $a$ is a perfect square, take its square root. Otherwise take $a + 3$. Repeat the procedure with the new positive integer (i.e., with $\sqrt { a }$ or $a + 3$ depending on the case). The resulting set of numbers is called the trajectory of $a$. For example the set $\{ 3, 6, 9 \}$ is a trajectory: it is the trajectory of each of its members.
Which numbers have a finite trajectory? Possible hint: Find the set $$\{ n \mid n \text{ is the smallest number in some trajectory } S \}.$$
If you wish, you can get partial credit by solving the following simpler questions.
(a) Show that there is no trajectory of cardinality 1 or 2.
(b) Show that $\{ 3, 6, 9 \}$ is the only trajectory of cardinality 3.
(c) Show that for any integer $k \geq 3$, there is a trajectory of cardinality $k$.
(d) Find an infinite trajectory.

Let $F$ be a field and $R$ a subring of $F$ that is not a field. Let $x$ be a variable. Let $S = \left\{ a _ { 0 } + a _ { 1 } x + \cdots + a _ { n } x ^ { n } \mid n \geq 0 \text{ and } a _ { 0 } \in R , a _ { 1 } , \cdots a _ { n } \in F \right\}$.
(A) (2 marks) Show that, with the natural operations of addition and multiplication of polynomials, $S$ is an integral domain.
(B) (4 marks) Let $I = \{ f ( x ) \in S \mid f ( 0 ) = 0 \}$. Determine whether $I$ is a prime ideal.
(C) (4 marks) Determine whether $S$ is a PID.

Let $A$ be a non-trivial subgroup of $\mathbb { R }$ generated by finitely many elements. Let $r$ be a real number such that $x \longrightarrow r x$ is an automorphism of $A$. Show that $r$ and $r ^ { - 1 }$ are zeros of monic polynomials with integer coefficients.

Find all solutions of the following equation where it is required that $x, k, y, n$ are positive integers with the exponents $k$ and $n$ both $> 1$. $$20x^k + 24y^n = 2024$$