Exercise 4 - Candidates who have followed the specialization course

For each of the five following propositions, indicate whether it is true or false and justify the answer chosen. One point is awarded for each correct answer correctly justified. An unjustified answer is not taken into account. An absence of answer is not penalized.

Proposition 1:

For every natural integer $n$, the units digit of $n ^ { 2 } + n$ is never equal to 4.

Proposition 2:

We consider the sequence $u$ defined, for $n \geqslant 1$, by $$u _ { n } = \frac { 1 } { n } \operatorname { gcd } ( 20 ; n ) .$$ The sequence $\left( u _ { n } \right)$ is convergent.

Proposition 3:

For all square matrices $A$ and $B$ of dimension 2, we have $A \times B = B \times A$.

Proposition 4:

A mobile can occupy two positions $A$ and $B$. At each step, it can either remain in the position it is in or change it. For every natural integer $n$, we denote $a_n$ (resp. $b_n$) the probability that the mobile is in position $A$ (resp. $B$) at step $n$.

Exercise 4 — For candidates who have followed the speciality course
We consider the matrix $M = \left( \begin{array} { l l } 2 & 3 \\ 1 & 2 \end{array} \right)$ and the sequences of natural numbers $\left( u _ { n } \right)$ and $\left( v _ { n } \right)$ defined by: $u _ { 0 } = 1 , v _ { 0 } = 0$, and for every natural number $n , \binom { u _ { n + 1 } } { v _ { n + 1 } } = M \binom { u _ { n } } { v _ { n } }$. The two parts can be treated independently.

Part A

The first terms of the sequence $\left( v _ { n } \right)$ have been calculated:

$n$	0	1	2	3	4	5	6	7	8	9	10	11	12
$v _ { n }$	0	1	4	15	56	209	780	2911	10864	40545	151316	564719	2107560

1. Conjecture the possible values of the units digit of the terms of the sequence $\left( v _ { n } \right)$.
2. It is admitted that for every natural number $n , \binom { u _ { n + 3 } } { v _ { n + 3 } } = M ^ { 3 } \binom { u _ { n } } { v _ { n } }$. a. Justify that for every natural number $n , \left\{ \begin{array} { l } u _ { n + 3 } = 26 u _ { n } + 45 v _ { n } \\ v _ { n + 3 } = 15 u _ { n } + 26 v _ { n } \end{array} \right.$. b. Deduce that for every natural number $n : v _ { n + 3 } \equiv v _ { n } [ 5 ]$.
3. Let $r$ be a fixed natural number. Prove, using a proof by induction, that, for every natural number $q , v _ { 3 q + r } \equiv v _ { r }$ [5].
4. Deduce that for every natural number $n$ the term $v _ { n }$ is congruent to 0, to 1 or to 4 modulo 5.
5. Conclude regarding the set of values taken by the units digit of the terms of the sequence $\left( v _ { n } \right)$.

Part B

The objective of this part is to prove that $\sqrt { 3 }$ is not a rational number using the matrix $M$.
To do this, we perform a proof by contradiction and assume that $\sqrt { 3 }$ is a rational number. In this case, $\sqrt { 3 }$ can be written in the form of an irreducible fraction $\frac { p } { q }$ where $p$ and $q$ are non-zero natural numbers, with $q$ the smallest possible natural number.

1. Show that $q < p < 2 q$.
2. It is admitted that the matrix $M$ is invertible. Give its inverse $M ^ { - 1 }$ (no justification is expected). Let the pair $\left( p ^ { \prime } ; q ^ { \prime } \right)$ be defined by $\binom { p ^ { \prime } } { q ^ { \prime } } = M ^ { - 1 } \binom { p } { q }$.
3. a. Verify that $p ^ { \prime } = 2 p - 3 q$ and that $q ^ { \prime } = - p + 2 q$. b. Justify that ( $p ^ { \prime } ; q ^ { \prime }$ ) is a pair of relative integers. c. Recall that $p = q \sqrt { 3 }$. Show that $p ^ { \prime } = q ^ { \prime } \sqrt { 3 }$. d. Show that $0 < q ^ { \prime } < q$. e. Deduce that $\sqrt { 3 }$ is not a rational number.

Find a 4-digit number $N$ such that $N = 4M$, where $M$ is the number obtained by reversing the digits of $N$.

Find the $n$-th non-square positive integer, and show that it equals $n + \lfloor \sqrt{n} + \frac{1}{2} \rfloor$.

The digit at the unit place of $$(1! - 2! + 3! - \ldots + 25!)^{(1! - 2! + 3! - \ldots + 25!)}$$ is
(a) 0
(b) 1
(c) 5
(d) 9

Find the last digit of $9! + 3^{9966}$.

The last digit of $( 2004 ) ^ { 5 }$ is
(A) 4
(B) 8
(C) 6
(D) 2

The digit in the unit's place of the number $1! + 2! + 3! + \ldots + 99!$ is
(A) 3
(B) 0
(C) 1
(D) 7

The last digit of $( 2004 ) ^ { 5 }$ is:
(a) 4
(b) 8
(c) 6
(d) 2

The digit in the units' place of the number $1 ! + 2 ! + 3 ! + \ldots + 99 !$ is
(a) 3
(b) 0
(c) 1
(d) 7.

The last digit of $( 2004 ) ^ { 5 }$ is:
(a) 4
(b) 8
(c) 6
(d) 2

The digit in the units' place of the number $1 ! + 2 ! + 3 ! + \ldots + 99 !$ is
(a) 3
(b) 0
(c) 1
(d) 7.

The last digit of $( 2004 ) ^ { 5 }$ is
(A) 4
(B) 8
(C) 6
(D) 2

The digit in the unit's place of the number $1! + 2! + 3! + \ldots + 99!$ is
(A) 3
(B) 0
(C) 1
(D) 7

The last digit of $( 2004 ) ^ { 5 }$ is
(A) 4
(B) 8
(C) 6
(D) 2

The digit in the unit's place of the number $1 ! + 2 ! + 3 ! + \ldots + 99 !$ is
(A) 3
(B) 0
(C) 1
(D) 7

Let $g : \mathbb { N } \rightarrow \mathbb { N }$ with $g ( n )$ being the product of the digits of $n$.
(a) Prove that $g ( n ) \leq n$ for all $n \in \mathbb { N }$.
(b) Find all $n \in \mathbb { N }$, for which $n ^ { 2 } - 12 n + 36 = g ( n )$.

Any positive real number $x$ can be expanded as $x = a _ { n } \cdot 2 ^ { n } + a _ { n - 1 } \cdot 2 ^ { n - 1 } + \cdots + a _ { 1 } \cdot 2 ^ { 1 } + a _ { 0 } \cdot 2 ^ { 0 } + a _ { - 1 } \cdot 2 ^ { - 1 } + a _ { - 2 } \cdot 2 ^ { - 2 } + \cdots$, for some $n \geq 0$, where each $a _ { i } \in \{ 0,1 \}$. In the above-described expansion of 21.1875, the smallest positive integer $k$ such that $a _ { - k } \neq 0$ is:
(A) 3
(B) 2
(C) 1
(D) 4

Determine all integers $n > 1$ such that every power of $n$ has an odd number of digits.

Let $N$ be a positive integer. Both when it is written in base 5 and when it is written in base 9, it is a 3-digit number, but the order of the numerals is reversed. We are to represent $N$ in base 10 (decimal) and in base 4.
Let $N$ be $abc$ in base 5 and $cba$ in base 9. Then we have
$$\mathbf { A } \leq a \leq \mathbf { B } , \quad \mathbf { C } \leq b \leq \mathbf { D } , \quad \mathbf { E } \leqq c \leqq \mathbf { F } \text {. }$$
Since we also have
$$N = \mathbf { G H } a + \mathbf { I } \quad b + c = \mathbf { J K } c + \mathbf { L } \quad b + a ,$$
we obtain
$$b = \mathbf { M } a - \mathbf { N O } c .$$
The $a$, $b$ and $c$ satisfying (1) and (2) are
$$a = \mathbf { P } , \quad b = \mathbf { Q } , \quad c = \mathbf { R } .$$
Thus $N$ expressed in base 10 is $\mathbf { S T U }$, and $N$ expressed in base 4 is $\mathbf { V W X Y }$.

What is the representation in base 2 of the number $(15)_8$ given in base 8?
A) $(1001)_2$
B) $(1011)_2$
C) $(1101)_2$
D) $(1110)_2$
E) $(1111)_2$

For a positive integer n, the greatest odd divisor of n is denoted by $\overline{n}$. The terms of the sequence $( a _ { n } )$ are defined for $n = 1,2 , \ldots$ as
$$a _ { n } = \begin{cases} n + 1 , & \text{if } n \equiv 1 ( \bmod 4 ) \\ n - 1 , & \text{if } n \equiv 3 ( \bmod 4 ) \end{cases}$$
Given this, what is the difference $a _ { 18 } - a _ { 12 }$?
A) 2
B) 4
C) 6
D) 8
E) 10

Three-digit natural numbers $ADB$, $ADC$, $DAA$, $DAD$ $$\begin{aligned}& \mathrm{ADB} < \mathrm{DAA} \\& \mathrm{DAD} < \mathrm{ADC}\end{aligned}$$ satisfy the inequalities.\ Accordingly, which of the following orderings is correct?\ A) A $=$ D $<$ B $<$ C\ B) C $<$ A $=$ B $<$ D\ C) D $<$ A $=$ B $<$ C\ D) B $<$ A $=$ D $<$ C\ E) C $<$ A $=$ D $<$ B

Furkan measures his height against a wall every five years and marks it on the wall, writing it as a three-digit natural number in centimeters.
It is known that Furkan's height increased by 36 cm in the first five years and by 40 cm in the second five years. Given that $A$, $B$, and $C$ are non-zero digits, what is the sum $A + B + C$?
A) 15
B) 14
C) 13
D) 11
E) 10