Exercise 4 — Candidates who have chosen the specialization option

In the mountains, a hiker made reservations in two types of accommodations: Accommodation A and Accommodation B. One night in accommodation A costs $24 €$ and one night in accommodation B costs $45 €$. He remembers that the total cost of his reservation is $438 €$. We wish to find the numbers $x$ and $y$ of nights spent respectively in accommodation $A$ and accommodation $B$.

1. a. Show that the numbers $x$ and $y$ are respectively less than or equal to 18 and 9. b. Copy and complete lines (1), (2) and (3) of the following algorithm so that it displays the possible pairs ( $x ; y$ ).
   

   Input: Processing:	\begin{tabular}{l} $x$ and $y$ are numbers
   For $x$ varying from $0$ to $\ldots$ (1)
   For $y$ varying from $0$ to $\ldots$ (2)
   If $\ldots$ (3) Display $x$ and $y$ End If End For End For

   \hline \end{tabular}
   
2. Justify that the total cost of the reservation is a multiple of 3.
   
3. a. Justify that the equation $8 x + 15 y = 1$ admits at least one solution in integers. b. Determine such a solution. c. Solve the equation (E): $8 x + 15 y = 146$ where $x$ and $y$ are integers.
   
4. The hiker remembers having spent at most 13 nights in accommodation A. Show then that he can find the exact number of nights spent in accommodation A and that of nights spent in accommodation B. Calculate these numbers.

Part A

We consider the equation (E): $15 x - 26 k = m$ where $x$ and $k$ denote relative integers and $m$ is a non-zero integer parameter.

1. Justify, by stating a theorem, that there exists a pair of relative integers $( u ; v )$ such that $15 u - 26 v = 1$. Find such a pair.
2. Deduce a particular solution ( $x _ { 0 } ; k _ { 0 }$ ) of equation (E).
3. Show that ( $x ; k$ ) is a solution of equation (E) if and only if $15 \left( x - x _ { 0 } \right) - 26 \left( k - k _ { 0 } \right) = 0$.
4. Show that the solutions of equation (E) are exactly the pairs ( $x$; $k$ ) of relative integers such that: $$\left\{ \begin{array} { l } x = 26 q + 7 m \\ k = 15 q + 4 m \end{array} \text { where } q \in \mathbb { Z } . \right.$$

Part B

We associate with each letter of the alphabet an integer as indicated in the table below.

A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	3	4	5	6	7	8	9	10	11	12
N	O	P	Q	R	S	T	U	V	W	X	Y	Z
13	14	15	16	17	18	19	20	21	22	23	24	25

We define an encoding system:

• to each letter of the alphabet, we associate the corresponding integer $x$,
• we then associate to $x$ the integer $y$ which is the remainder of the Euclidean division of $15 x + 7$ by 26,
• we associate to $y$ the corresponding letter.

Thus, by this method, the letter E is associated with 4, 4 is transformed into 15 and 15 corresponds to the letter P, and therefore the letter E is encoded by the letter P.

1. Encode the word MATHS.
2. Let $x$ be the number associated with a letter of the alphabet using the initial table and $y$ be the remainder of the Euclidean division of $15 x + 7$ by 26. a. Show then that there exists a relative integer $k$ such that $15 x - 26 k = y - 7$. b. Deduce that $x \equiv 7 y + 3 ( \bmod 26 )$. c. Deduce a description of the decoding system associated with the encoding system considered.
3. Explain why the letter W in an encoded message will be decoded by the letter B. Decode the word WHL.
4. Show that, by this encoding system, two different letters are encoded by two different letters.

We consider the following equation with unknowns $x$ and $y$ integers: $$7x - 3y = 1 \tag{E}$$

1. An incomplete algorithm is given below. Copy it and complete it, writing its missing lines (1) and (2) so that it gives the integer solutions $(x; y)$ of the equation (E) satisfying $-5 \leqslant x \leqslant 10$ and $-5 \leqslant y \leqslant 10$.
   

   Variables:

   X is an integer

   Y is an integer

   Start:

   For X varying from $-5$ to 10

   (1) \ldots

   (2) \ldots

   Then Display X and Y

   End If

   End For

   End

   
   
2. a. Give a particular solution of equation (E). b. Determine the set of pairs of integers solutions of equation (E). c. Determine the set of pairs $(x; y)$ of integers solutions of equation (E) such that $-5 \leqslant x \leqslant 10$ and $-5 \leqslant y \leqslant 10$.

For every pair of non-zero integers $(a, b)$, we denote by $\operatorname{gcd}(a, b)$ the greatest common divisor of $a$ and $b$. The plane is equipped with a coordinate system $(\mathrm{O}; \vec{\imath}, \vec{\jmath})$.

1. Example. Let $\Delta_{1}$ be the line with equation $y = \frac{5}{4}x - \frac{2}{3}$. a. Show that if $(x, y)$ is a pair of integers then the integer $15x - 12y$ is divisible by 3. b. Does there exist at least one point on the line $\Delta_{1}$ whose coordinates are two integers? Justify.

Generalization: We now consider a line $\Delta$ with equation $(E): y = \frac{m}{n}x - \frac{p}{q}$ where $m, n, p$ and $q$ are non-zero integers such that $\operatorname{gcd}(m, n) = \operatorname{gcd}(p, q) = 1$. Thus, the coefficients of equation $(E)$ are irreducible fractions and we say that $\Delta$ is a rational line. The purpose of the exercise is to determine a necessary and sufficient condition on $m, n, p$ and $q$ for a rational line $\Delta$ to contain at least one point whose coordinates are two integers.

1. We suppose here that the line $\Delta$ contains a point with coordinates $(x_{0}, y_{0})$ where $x_{0}$ and $y_{0}$ are integers. a. By noting that the number $ny_{0} - mx_{0}$ is an integer, prove that $q$ divides the product $np$. b. Deduce that $q$ divides $n$.
2. Conversely, we suppose that $q$ divides $n$, and we wish to find a pair $(x_{0}, y_{0})$ of integers such that $y_{0} = \frac{m}{n}x_{0} - \frac{p}{q}$. a. We set $n = qr$, where $r$ is a non-zero integer. Prove that we can find two integers $u$ and $v$ such that $qru - mv = 1$. b. Deduce that there exists a pair $(x_{0}, y_{0})$ of integers such that $y_{0} = \frac{m}{n}x_{0} - \frac{p}{q}$.
3. Let $\Delta$ be the line with equation $y = \frac{3}{8}x - \frac{7}{4}$. Does this line have a point whose coordinates are integers? Justify.

Exercise 4 (For candidates who have followed the specialty course)

We denote $\mathbb{Z}$ the set of integers. In this exercise, we study the set $S$ of matrices that can be written in the form $A = \left(\begin{array}{cc} a & b \\ c & d \end{array}\right)$, where $a, b, c$ and $d$ belong to the set $\mathbb{Z}$ and satisfy: $ad - bc = 1$. We denote $I$ the identity matrix $I = \left(\begin{array}{ll} 1 & 0 \\ 0 & 1 \end{array}\right)$.

Part A

1. Verify that the matrix $A = \left(\begin{array}{rr} 6 & 5 \\ -5 & -4 \end{array}\right)$ belongs to the set $S$.
2. Show that there exist exactly four matrices of the form $A = \left(\begin{array}{ll} a & 2 \\ 3 & d \end{array}\right)$ belonging to the set $S$; state them explicitly.
3. a. Solve in $\mathbb{Z}$ the equation $(E): 5x - 2y = 1$. We may note that the pair $(1; 2)$ is a particular solution of this equation. b. Deduce that there exist infinitely many matrices of the form $A = \left(\begin{array}{cc} a & b \\ 2 & 5 \end{array}\right)$ that belong to the set $S$. Describe these matrices.

Part B

In this part, we denote $A = \left(\begin{array}{ll} a & b \\ c & d \end{array}\right)$ a matrix belonging to the set $S$. We recall that $a$, $b$, $c$ and $d$ are integers such that $ad - bc = 1$.

1. Show that the integers $a$ and $b$ are coprime.
2. Let $B$ be the matrix: $B = \left(\begin{array}{rr} d & -b \\ -c & a \end{array}\right)$ a. Calculate the product $AB$. It is admitted that $AB = BA$. b. Deduce that the matrix $A$ is invertible and give its inverse matrix $A^{-1}$. c. Show that $A^{-1}$ belongs to the set $S$.
3. Let $x$ and $y$ be two integers. We denote $x'$ and $y'$ the integers such that $\binom{x'}{y'} = A\binom{x}{y}$. a. Show that $x = dx' - by'$. It is admitted that likewise $y = ay' - cx'$. b. We denote $D$ the GCD of $x$ and $y$ and we denote $D'$ the GCD of $x'$ and $y'$. Show that $D = D'$.
4. We consider the sequences of natural numbers $(x_n)$ and $(y_n)$ defined by: $x_0 = 2019$, $y_0 = 673$ and for any natural number $n$: $$\left\{\begin{array}{l} x_{n+1} = 2x_n + 3y_n \\ y_{n+1} = x_n + 2y_n \end{array}\right.$$ Using the previous question, determine, for any natural number $n$, the GCD of the integers $x_n$ and $y_n$.

Let $k \in \mathbb{N}^*$ and $(a_1, \ldots, a_k) \in (\mathbb{N}^*)^k$ a $k$-tuple of strictly positive integers. When $k \geq 2$, we assume they are coprime as a set. We define a function $P : \mathbb{N} \rightarrow \mathbb{C}$ by setting for all $n \in \mathbb{N}$: $$P(n) = \operatorname{Card}\left\{(n_1, \ldots, n_k) \in \mathbb{N}^k : n_1 a_1 + \cdots + n_k a_k = n\right\}.$$ We assume $k = 2$. Prove that $$P(n) = \frac{n}{ab} - \left\{\frac{b^* n}{a}\right\} - \left\{\frac{a^* n}{b}\right\} + 1$$ for all integer $n \geq 0$, where $a^*$ and $b^*$ are integers satisfying $a^* a = 1$ modulo $b$ and $b^* b = 1$ modulo $a$ respectively.
Hint. One may use the formula $(*)$ for $b = 1$.

Let $n_1, n_2, \ldots, n_k$ be positive integers with $\gcd(n_1, n_2, \ldots, n_k) = 1$. Show that every sufficiently large positive integer $n$ can be represented as $n = \sum_i c_i n_i$ with $c_i \geq 0$ integers.

Let $a _ { 1 } < a _ { 2 } < a _ { 3 } < a _ { 4 }$ be positive integers such that
$$\sum _ { i = 1 } ^ { 4 } \frac { 1 } { a _ { i } } = \frac { 11 } { 6 }$$
Then, $a _ { 4 } - a _ { 2 }$ equals
(A) 11
(B) 10
(C) 9
(D) 8 .

The number of triples $( a , b , c )$ of positive integers satisfying the equation $$\frac { 1 } { a } + \frac { 1 } { b } + \frac { 1 } { c } = 1 + \frac { 2 } { a b c }$$ and such that $a < b < c$, equals:
(A) 3
(B) 2
(C) 1
(D) 0

Q2 Let $p$ be a prime number, and let $x$ and $y$ be positive integers. Then we are to find all triples of $p$, $x$ and $y$ which satisfy
$$\frac{p}{x} + \frac{7}{y} = p.$$
We can transform this equation into
$$(x - \mathbf{N})(py - \mathbf{OO}) = \mathbf{OP}.$$
From this, we obtain
$$x - \mathbf{N} = \mathbf{Q} \text{ or } \mathbf{R}, \quad (\text{note: have } \mathbf{Q} < \mathbf{R})$$
and hence
$$x = \mathbf{S} \text{ or } \mathbf{T}. \quad (\text{note: have } S < T)$$
First, if $x = S$, then
$$p = \mathbf{U}, \quad y = \mathbf{V}$$
or
$$p = \mathbf{W}, \quad y = \mathbf{X}. \quad (\text{note: have } \mathbf{U} < \mathbf{W})$$
Next, if $x = T$, then
$$p = \mathbf{Y}, \quad y = \mathbf{Z}.$$

We are to find a two-digit natural number $a$ such that $a + 9$ is a multiple of 7 and $a + 8$ is a multiple of 13.
First of all, $a + 9$ and $a + 8$ can be represented as
$$a + 9 = \mathbf { M } m , \quad a + 8 = \mathbf { N O } n ,$$
where $m$ and $n$ are natural numbers. From these two equalities, we have
$$\mathbf { M } m - \mathbf { N O } n = \mathbf { P } .$$
Since the pair of $m = \mathbf { Q }$ and $n = \mathbf { R }$ is an integral solution of (1), we have
$$\mathbf { M } ( m - \mathbf { Q } ) = \mathbf { NO } ( n - \mathbf { R } ) .$$
From (2), a natural number $n$ satisfying (1) can be represented as
$$n = \mathbf { S }$$
where $k$ is an integer. Thus
$$a = \mathbf { U V } k + \mathbf { W } ,$$
and since $a$ is a two-digit natural number, $a = \mathbf { X Y }$.

For natural numbers $x$ and $y$
$$\begin{array} { r | r | r } x & \frac { 10 } { m } \\ { } ^ { - } & = ^ { y } \frac { 15 } { 3 } \end{array}$$
Given this, what is the remainder when the product $x \cdot y$ is divided by 5?
A) 0
B) 1
C) 2
D) 3
E) 4

$$\frac { x + \frac { 1 } { x + 2 } } { 1 - \frac { 1 } { x + 2 } } = \frac { 1 } { 4 }$$
What is the value of $x$ that satisfies this equality?
A) $\frac { - 3 } { 2 }$
B) $\frac { - 3 } { 4 }$
C) $\frac { - 1 } { 4 }$
D) $\frac { - 5 } { 4 }$
E) $\frac { - 3 } { 8 }$

Two friends sitting in a café drank 5 cups of tea, 1 cup of orange juice, and ate dessert. Part of the bill that the two friends paid is given in the figure.
Accordingly, if these two friends had drunk how many more cups of tea, would the total bill they would pay equal $\frac{2}{7}$ of the amount they paid for dessert?
A) 5
B) 7
C) 9
D) 11
E) 13

A stationery store sells red and blue colored pens with the same tag prices. In a campaign conducted at this stationery store, red pens are sold with the second one at 50\% discount, and blue pens are sold at 30\% discount from the tag price.
A person who bought 2 of each of the red and blue pens from this stationery store paid 4.5 TL less for the blue pens than for the red pens.
Accordingly, what is the tag price of one of these pens in TL?
A) 45
B) 40
C) 35
D) 30
E) 25

Two vehicles, one from city $A$ and one from city $B$, start moving towards each other at constant speeds on the road between these two cities and meet after some time. The vehicle starting from city $A$ reaches city $B$ 250 minutes after their meeting, and the vehicle starting from city $B$ reaches city $A$ 160 minutes after their meeting.
Accordingly, how many minutes after starting did these vehicles meet?
A) 170
B) 180
C) 190
D) 200
E) 210

For each person attending an event, either a meat or vegetable menu will be ordered for lunch. After the order was placed, 10 different people wanted to change their menu, and due to this change, the total amount to be paid increased by 80 TL.
Given that the price of the meat menu is 20 TL more than the price of the vegetable menu, how many people wanted to change their menu from vegetable to meat?
A) 5
B) 6
C) 7
D) 8
E) 9