1987 Paper 3 Q5

Year: 1987
Paper: 3
Question Number: 5

Course: UFM Additional Further Pure
Section: Number Theory

Difficulty: 1500.0 Banger: 1500.0

Problem

A secret message consists of the numbers \(1,3,7,23,24,37,39,43,43,43,45,47\) arranged in some order as \(a_{1},a_{2},\ldots,a_{12}.\) The message is encoded as \(b_{1},b_{2},\ldots,b_{12}\) with \(0\leqslant b_{j}\leqslant49\) and \begin{alignat*}{1} b_{2j} & \equiv a_{2j}+n_{0}+j\pmod{50},\\ b_{2j+1} & \equiv a_{2j+1}+n_{1}+j\pmod{50}, \end{alignat*} for some integers \(n_{0}\) and \(n_{1}.\) If the coded message is \(35,27,2,36,15,35,8,40,40,37,24,48,\) find the original message, explaining your method carefully.

Solution

Considering the odd numbers, we have \begin{array}{l|rrrrrr} b_{2j+1} & 35 & 2 & 15 & 8 & 40 & 24 \\ a_{2j+1}+n_1 & 35 & 1 & 13 & 5 & 36 & 19 \end{array} Considering the even numbers, we have \begin{array}{l|rrrrrr} b_{2j} & 27& 36 & 35 & 40 & 37 & 48 \\ a_{2j}+n_0 & 27 & 35 & 33 & 37 & 33 & 43 \end{array} There are three numbers in the original sequence which are repeated (\(43\)). By the pigeonhole principle, one of the odds or evens must have at least two of them. We can see that the even numbers have some number repeated twice (\(33\)). Therefore these must be the \(43\)s. Therefore \(n_0 = -10\) \begin{array}{l|rrrrrr} b_{2j} & 27& 36 & 35 & 40 & 37 & 48 \\ a_{2j}+n_0 & 27 & 35 & 33 & 37 & 33 & 43 \\ a_{2j} & 37 & 45 & 43 & 47 & 43 & 3 \end{array} This leaves the remaining numbers to be decoded from the original sequence as \(1,7,23,24,39,43\). Two of these numbers are consecutive (\(23\) and \(24\)), and two numbers in our sequence are \(35\) and \(36\). Therefore \(n_1\) must be \(12\). \begin{array}{l|rrrrrr} b_{2j+1} & 35 & 2 & 15 & 8 & 40 & 24 \\ a_{2j+1}+n_1 & 35 & 1 & 13 & 5 & 36 & 19 \\ a_{2j+1} & 23 & 39 & 1 &43 & 24& 7 \end{array} Therefore the original sequence was: \(23, 37, 39, 45, 1, 43, 43, 47, 24, 43, 7, 3\)
Rating Information

Difficulty Rating: 1500.0

Difficulty Comparisons: 0

Banger Rating: 1500.0

Banger Comparisons: 0

Show LaTeX source
Problem source
A secret message consists of the numbers $1,3,7,23,24,37,39,43,43,43,45,47$ arranged in some order as $a_{1},a_{2},\ldots,a_{12}.$ The message is encoded as $b_{1},b_{2},\ldots,b_{12}$ with $0\leqslant b_{j}\leqslant49$ and 
\begin{alignat*}{1}
b_{2j} & \equiv a_{2j}+n_{0}+j\pmod{50},\\
b_{2j+1} & \equiv a_{2j+1}+n_{1}+j\pmod{50},
\end{alignat*}
for some integers $n_{0}$ and $n_{1}.$ If the coded message is $35,27,2,36,15,35,8,40,40,37,24,48,$
find the original message, explaining your method carefully. 
Solution source
Considering the odd numbers, we have

\begin{array}{l|rrrrrr}
b_{2j+1} & 35 & 2 & 15 & 8 & 40 & 24 \\
a_{2j+1}+n_1 & 35 & 1 & 13 & 5 & 36 & 19 
\end{array}

Considering the even numbers, we have

\begin{array}{l|rrrrrr}
b_{2j} & 27& 36 & 35 & 40 & 37 & 48 \\
a_{2j}+n_0 & 27 & 35 & 33 & 37 & 33 & 43 
\end{array}

There are three numbers in the original sequence which are repeated ($43$). By the pigeonhole principle, one of the odds or evens must have at least two of them. We can see that the even numbers have some number repeated twice ($33$). Therefore these must be the $43$s. Therefore $n_0 = -10$

\begin{array}{l|rrrrrr}
b_{2j} & 27& 36 & 35 & 40 & 37 & 48 \\
a_{2j}+n_0 & 27 & 35 & 33 & 37 & 33 & 43 \\
a_{2j} & 37 & 45 & 43 & 47 & 43 & 3
\end{array}

This leaves the remaining numbers to be decoded from the original sequence as $1,7,23,24,39,43$. Two of these numbers are consecutive ($23$ and $24$), and two numbers in our sequence are $35$ and $36$. Therefore $n_1$ must be $12$.

\begin{array}{l|rrrrrr}
b_{2j+1} & 35 & 2 & 15 & 8 & 40 & 24 \\
a_{2j+1}+n_1 & 35 & 1 & 13 & 5 & 36 & 19 \\
a_{2j+1} & 23 & 39 & 1 &43 & 24& 7
\end{array}


Therefore the original sequence was: $23, 37, 39, 45, 1, 43, 43, 47, 24, 43, 7, 3$