(a) A computer program prints out all integers from 0 to ten thousand in base 6 using the numerals $0,1,2,3,4$ and 5. How many numerals it would have printed?
(b) A 3-digit number $abc$ in base 6 is equal to the 3-digit number $cba$ in base 9. Find the digits.

We say that two subsets $X$ and $Y$ of $\mathbb{R}$ are order-isomorphic if there is a bijective map $\phi : X \longrightarrow Y$ such that for every $x_1 \leq x_2 \in X$, $\phi(x_1) \leq \phi(x_2)$, where '$\leq$' denotes the usual order on $\mathbb{R}$. Choose the correct statement(s) from below:
(A) $\mathbb{N}$ and $\mathbb{Z}$ are not order-isomorphic;
(B) $\mathbb{N}$ and $\mathbb{Q}$ are order-isomorphic;
(C) $\mathbb{Z}$ and $\mathbb{Q}$ are order-isomorphic;
(D) The sets $\mathbb{N}$, $\mathbb{Z}$ and $\mathbb{Q}$ are pairwise non-order-isomorphic.

Let $U \subseteq \mathbb{R}$ be a non-empty open subset. Choose the correct statement(s) from below:
(A) $U$ is uncountable;
(B) $U$ contains a closed interval as a proper subset;
(C) $U$ is a countable union of disjoint open intervals;
(D) $U$ contains a convergent sequence of real numbers.

Four children $\mathrm{K}$, $\mathrm{L}$, $\mathrm{M}$ and R are about to run a race. They make some predictions as follows.
K says: M will win. Myself will come second. R says: M will come second. L will be third. M says: L will be last. R will be second. After the race, it turns out that each person has made exactly one correct and one incorrect prediction. Write the result of the race in the order from first to the last.

A country's GDP grew by $7.8\%$ within a period. During the same period the country's per-capita-GDP ($=$ ratio of GDP to the total population) increased by $10\%$. During this period, the total population of the country increased/decreased by $\_\_\_\_$ \%. (Choose the correct option and fill in the blank if possible.)

A function $f(x)$ is defined by the following formulas
$$f(x) = \begin{cases} x^{2} + 1 & \text{when } x \text{ is irrational} \\ \tan(x) & \text{when } x \text{ is rational} \end{cases}$$
At how many $x$ in the interval $[0, 4\pi]$ is $f(x)$ continuous?

We want to construct a nonempty and proper subset $S$ of the set of non-negative integers. This set must have the following properties. For any $m$ and any $n$,
if $m \in S$ and $n \in S$ then $m + n \in S$ and if $m \in S$ and $m + n \in S$ then $n \in S$.
For each statement below, state if it is true or false.
(i) 0 must be in $S$.
(ii) 1 cannot be in $S$.
(iii) There are only finitely many ways to construct such a subset $S$.
(iv) There is such a subset $S$ that contains both $2015^{2016}$ and $2016^{2015}$.

Let $A$ be a non-empty finite sequence of $n$ distinct integers $a_{1} < a_{2} < \cdots < a_{n}$. Define
$$A + A = \left\{ a_{i} + a_{j} \mid 1 \leq i, j \leq n \right\}$$
i.e, the set of all pairwise sums of numbers from $A$. E.g., for $A = \{1,4\}$, $A + A = \{2,5,8\}$.
(a) Show that $|A + A| \geq 2n - 1$. Here $|A + A|$ means the number of elements in $A + A$.
(b) Prove that $|A + A| = 2n - 1$ if and only if the sequence $A$ is an arithmetic progression.
(c) Find a sequence $A$ of the form $0 < 1 < a_{3} < \cdots < a_{10}$ such that $|A + A| = 20$.

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?

[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.

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 }$.

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.

Two mighty frogs jump once per unit time on the number line as described in the question.
The second frog starts at $x=0$ and jumps $i+1$ steps to the right just after $t=i$, so that at times $t=0,1,2,3,\ldots$ this frog is at positions $x=0,1,3,6,\ldots$ respectively. How many numbers of the form $7n+1$ (with $n$ an integer) does the frog visit from $t=0$ to $t=99$ (both endpoints included)? [3 points]

As shown in the figure below, for a natural number $n$, $n$ terms $$\left[ \frac { n } { 1 } \right] \left[ \frac { n } { 2 } \right] \left[ \frac { n } { 3 } \right] , \cdots , \left[ \frac { n } { n } \right]$$ are arranged in the $n$-th row from column 1 to column $n$ in order. (Here, $[ x ]$ is the greatest integer not exceeding $x$.)
Select all correct statements from . [4 points]
ㄱ. In row $n$, the number of terms with value 1 is $\left[ \frac { n + 1 } { 2 } \right]$. ㄴ. In row 100, the number of terms with value 3 is 8. ㄷ. In column 3, the number of terms with value 5 is 5.
(1) ㄱ
(2) ㄴ
(3) ㄷ
(4) ㄱ, ㄴ
(5) ㄱ, ㄴ, ㄷ

As shown in the figure below, for a natural number $n$, the $n$ terms $$\left[ \frac { n } { 1 } \right] , \left[ \frac { n } { 2 } \right] , \left[ \frac { n } { 3 } \right] , \cdots , \left[ \frac { n } { n } \right]$$ are arranged in the $n$-th row from column 1 to column $n$ in order. (Here, $[ x ]$ is the greatest integer not exceeding $x$.)
Which of the following in $\langle$Remarks$\rangle$ are correct? [4 points]
$\langle$Remarks$\rangle$ ㄱ. In the $n$-th row, the number of terms with value 1 is $\left[ \frac { n + 1 } { 2 } \right]$. ㄴ. In the 100th row, the number of terms with value 3 is 8. ㄷ. In the 3rd column, the number of terms with value 5 is 5.
(1) ㄱ
(2) ㄴ
(3) ㄷ
(4) ㄱ, ㄴ
(5) ㄱ, ㄴ, ㄷ

We assume that for all $d \geqslant 0$, $\mathbb{P}(X \in d\mathbb{Z}) < 1$. Show that the set $\Lambda_X$ defined in question 8a is closed under addition and that $r\left(\Lambda_X\right) = 0$.

Let $n$ be a non-zero natural number. We set $$\Phi_n : \left\lvert\, \begin{aligned} \{0,1\}^n &\rightarrow \llbracket 0, 2^n - 1 \rrbracket \\ (x_j)_{j \in \llbracket 1,n \rrbracket} &\mapsto \sum_{j=1}^{n} x_j 2^{n-j} \end{aligned} \right.$$
Show that $\Phi_n$ is well-defined by verifying $\operatorname{Im} \Phi_n \subset \llbracket 0, 2^n - 1 \rrbracket$.

We have $D = \bigcup_{n \in \mathbb{N}^{\star}} D_n$ where $D_n = \left\{\sum_{j=1}^{n} \frac{x_j}{2^j}, (x_j)_{j \in \llbracket 1,n \rrbracket} \in \{0,1\}^n\right\}$.
Is the set $D$ countable?

Suppose that there exists $f : \mathbb{N} \rightarrow \mathcal{P}(\mathbb{N})$ bijective. By considering $A = \{x \in \mathbb{N} \mid x \notin f(x)\}$, establish a contradiction.

Let $n$ be a non-zero natural number. We set $$\Phi_n : \left|\, \begin{aligned} \{0,1\}^n &\rightarrow \llbracket 0, 2^n - 1 \rrbracket \\ (x_j)_{j \in \llbracket 1,n \rrbracket} &\mapsto \sum_{j=1}^{n} x_j 2^{n-j} \end{aligned} \right.$$
Show that $\Phi_n$ is well-defined by verifying $\operatorname{Im} \Phi_n \subset \llbracket 0, 2^n - 1 \rrbracket$.

We denote $D = \bigcup_{n \in \mathbb{N}^{\star}} D_n$ where $D_n = \left\{ \sum_{j=1}^{n} \frac{x_j}{2^j},\, (x_j)_{j \in \llbracket 1,n \rrbracket} \in \{0,1\}^n \right\}$.
Is the set $D$ countable?

Using the results of the previous questions (in particular that $\Lambda$ is a bijection from $\{0,1\}^{\mathbb{N}}$ to $[0,1[$, and that $\mathcal{P}(\mathbb{N})$ is not countable), conclude that $[0,1[$ is not countable.

5. In the remainder of this part, $p$ denotes a fixed odd prime integer. One may use without proof Wilson's theorem: $$(p-1)! + 1 \equiv 0 \quad [p]$$ We denote by $\mathbb{Z}_p$ the field $\mathbb{Z}/p\mathbb{Z}$ and if $a \in \mathbb{Z}$, we denote by $\bar{a}$ its class in $\mathbb{Z}_p$. For $1 \leq k \leq e_p$, we denote by $\mathcal{P}_k$ the set of subsets $P$ with $k$ elements of $\mathbb{Z}_p$ satisfying the condition $$\forall \alpha \in P, \quad \alpha + 1 \notin P.$$ a. For $P = \{\alpha_1, \ldots, \alpha_k\} \in \mathcal{P}_k$ and $\alpha \in \mathbb{Z}_p$, we set $\tau_\alpha(P) = \{\alpha_1 + \alpha, \ldots, \alpha_k + \alpha\}$. Show that the map $\alpha \mapsto \tau_\alpha$ is a homomorphism from $(\mathbb{Z}_p, +)$ to the group of bijections of $\mathcal{P}_k$. b. We define a relation $\mathscr{R}$ between elements of $\mathcal{P}_k$ as follows: if $A, B$ are in $\mathcal{P}_k$, $A \mathscr{R} B$ if and only if there exists $\alpha \in \mathbb{Z}_p$ such that $B = \tau_\alpha(A)$. Show that $\mathscr{R}$ is an equivalence relation on $\mathcal{P}_k$, and that each equivalence class has cardinality $p$ and admits a representative of the form $\{\bar{0}, \bar{a}_2, \ldots, \bar{a}_k\}$ with $0 < a_2 < \cdots < a_k < p$. We choose such a representative for each class and we denote by $R$ the set of representatives thus chosen. c. Prove that $$\overline{c_{p-1,k}} = \sum_{\{0, \ldots, a_k\} \in R} \sum_{1 \leq \ell \leq p-1} \bar{\ell}\, \overline{\ell+1}\, \overline{a_2 + \ell}\, \overline{a_2 + \ell + 1} \cdots \overline{a_k + \ell}\, \overline{a_k + \ell + 1}$$

We call a cycle of length $k$ with values in $\llbracket 1,n \rrbracket$, any $(k+1)$-tuple $\vec{\imath} = (i_{1}, i_{2}, \ldots, i_{k}, i_{1})$ of elements of $\llbracket 1,n \rrbracket$. We denote $|\vec{\imath}|$ the number of distinct vertices of the cycle $\vec{\imath}$.
Show that the number of cycles of length $k$ in $\llbracket 1,n \rrbracket$ passing through $\ell$ distinct vertices is at most $n^{\ell} \ell^{k}$.