The Source Code

Number Theory Level 5

Colter is a designated spy on a mission. His mission is to dismantle a suitcase bomb on a train to Chicago. In order to do that, he has to break The Source Code . The Source Code is a $2015\times 2015$ table with buttons labelled from 1 to $2015^2$ in a snake-like fashion (see below for details). The code can be broken if and only if Colter has pushed all the button whose number $x$ satisfies the following conditions:

$a$ is adjacent to $x$ from the top, and $a \equiv 1 \pmod{2}$
$b$ is adjacent to $x$ from the right, and $b \equiv 2 \pmod {3}$
$c$ is adjacent to $x$ from the bottom, and $c \equiv 3 \pmod{4}$
$d$ is adjacent to $x$ from the left, and $d \equiv 4 \pmod{5}$ .

How many button numbers $x$ does Colter have to push in order to break The Source Code?

Clarifications :

Snake like fasion: For a $n\times n$ table $(n>2)$ containing $n^2$ buttons, each marked by a natural number from $1$ to $n^2$ , the order the numbers are written is as follows: On the first line, the numbers $1,2,\ldots,n$ are in ascending order, whereas on the next line $n+1,\ldots,2n$ are in descending order. Here is an example of a $3\times3$ table:

Hint : Chinese remainder theorem is going to be useful in this.

The answer is 67436.

1 solution

Leah Jurgens
Jun 27, 2016

Suppose $x$ lie in line $n, (2\le n \le 2014)$ . We have:

$a=4030(n-1)+1-x$ and $4030(n-1)+1-x \equiv 1(mod2)$

$c=4030n-x+1$ and $4030n-x+1 \equiv 3(mod4)$

$\Rightarrow x \equiv 0(mod2)$ and $x \equiv 4030n - 2(mod4)$

For $x$ in lines of desending order, we have $mod(n,2)=0$ $\Rightarrow n \equiv 2(mod4)$ . We have:

$mod(b,3)=2 \Rightarrow x \equiv 0(mod3)$

$mod(d,5)=4 \Rightarrow x \equiv 3(mod5)$

By applying the Chinese remainder theorem, we have $x \equiv 18(mod60)$ .

The number of the numbers $60x+18$ in $(2017,4029);(6047,8059);(10077,12089);(14107,16119);(18137,20149);(22167,24179)$ are $33,34,34,34,34,33$ respectively.

For $x$ in lines of asending order, we have $mod(n,2)=1$ $\Rightarrow n \equiv 0(mod4)$ . We have:

$mod(b,3)=2 \Rightarrow x \equiv 1(mod3)$

$mod(d,5)=4 \Rightarrow x \equiv 0(mod5)$

By applying the Chinese remainder theorem, we have $x \equiv 40(mod60)$ .

The number of the numbers $60x+40$ in $(4032,6044);(8062,10074);(12092,14104);(16122,18134);(20152,22164);(24182,26194)$ are $34,34,34,33,33,33$ respectively.

Therefore, the number of numbers $x$ is:

$[\frac{1008}{6}.(33.2+34.4)-33]+[\frac{1008}{6}.(33.3+34.2)-33.2]=\boxed{67605}$

I have several issues/concerns with your approach

(fixed) Originally, it wasn't clear that the numbers of the code were in the alternating manner. I initially thought that they were randomly placed.
(fixed) Originally, the terminology wasn't standardized, and it wasn't explicitly clear what had to be done / calculated. I have now defined it as "push buttons to break the code".
(fixed) Originally, you did not use consistent terminology to express the modular arithmetic.
If the button is on the edge, it is not clear what the adjacent number is.
I do not understand your final step. Can you elaborate on what you are doing? I'm guessing that $33 . 3$ refers to $33 \times 3$ .

This is a somewhat interesting problem. Unfortunately, because of the unclear phrasing, it discourages others from interacting with it further. I originally was considering featuring this problem, which is why I made all of these edits. If you can simplify/clarify the problem even more so that others will excitedly work on it, I will feature the problem.

Calvin Lin Staff - 4 years, 11 months ago

The Source Code

The answer is 67436.

1 solution

0 pending reports