AMC 2000, Problem 16

Question

A checkerboard of  $13$ rows and  $17$ columns has a number written in each square, beginning in the upper left corner, so that the first row is numbered $1,2,3,4,...,17$ , the second row $18,19,20...34$, and so on down the board. If the board is renumbered so that the left column, top to bottom, is $1,2,3,....13$ , the second column $14,15,16,17,...26$ and so on across the board, some squares have the same numbers in both numbering systems. Find the sum of the numbers in these squares (under either system).

The answer was 555, with the solution provided below

Index the rows with  $ i=1,2,3,...13$ Index the columns with $ j=1,2,3,4,...17$ For the first row number the cells $1,2,3...17$ For the second, $18,19,20..34$ and so on So the number in row = $i$ and column = $j$ is  $f(i,j) = 17(i-1)+j$ Similarly, numbering the same cells columnwise we find the number in row = $i$ and column = $j$ is $g(i,j)= i+13j-13$ So we need to solve $f(i,j) =g(i,j)$ Which gives $i=(1+3j)/4$      We get the solutions $1, 56, 111, 166,221$ which sums to $555$.    

The question is why would there be $17(i-1)+j $ being equated as follows? Is it necessarily unique? How did the author derived it to find the solutions? And is there another way?

Answer 1

Imagine first that we are number along the rows. What number will we place in the cell in row $i,$ column $j?$ We have already full numbered $i-1$ rows, and since there are $17$ numbers in a row, in these rows we have used the first $17(i-1)$ numbers. In row $i,$ column $1$ we therefore place $17(i-1)+1,$ in row $i,$ column $2$ we place $17(i-1)+2,$ ... and in row $i,$ column $j$ we place $17(i-1)+j$. This explains the formula for $f(i,j),$ and a wholly analogous argument explains the formula for $g(i,j).$

I don't fully understand all of your questions. We equate $f(i,j)$ and $g(i,j)$ because the question asks for the cells where the two numbers are the same. We easily get the solution $$i={3j+1\over4}$$ Since $i$ and $j$ are integers, we need $3j+1$ to be divisible by $4,$ which happens when $j\in\{1,5,9,13,17\}$

Solving for the corresponding $i$ values and plugging into the the formula for $f(i,j)$ (or $g(i,j),$) should give you the five numbers that the author claims, but I haven't checked this.

Answer 2

Let $f\left(i,j\right)$ be the integer written in each cell according to the first numbering system, such that: \begin{equation*} f\left(i,j\right)=17(i-1)+j \end{equation*} where $1\leq i\leq 13$ is the row value, and $1\leq j\leq 17$ is the column value.

This formula means that each cell is the sum of the column value $j$ with a multiple of $17$ that depends on the row value.

The same idea applies to the second numbering system, with $g\left(i,j\right)$ being the writter integer in this case, such that: \begin{equation*} g\left(i,j\right)=13(j-1)+i \end{equation*} This second formula means that each cell is the sum of the row value $i$ with a multiple of $13$ that depends on the column value this time.

Anyway we are interested on coincident values on both numbering systems. then: \begin{equation*} f\left(i,j\right)=g\left(i,j\right) \end{equation*} \begin{equation*} 17(i-1)+j=13(j-1)+i \end{equation*} \begin{equation*} 16i-12j=4 \end{equation*} \begin{equation*} 4i-3j=1 \end{equation*} Thus, a multiple of $4$ subtracted by a multiple of $3$ that is equal to $1$, which happens to: \begin{equation*} 4-3=1\rightarrow\left(i,j\right)=\left(1,1\right) \end{equation*} \begin{equation*} 16-15=1\rightarrow\left(i,j\right)=\left(4,5\right) \end{equation*} \begin{equation*} 28-27=1\rightarrow\left(i,j\right)=\left(7,9\right) \end{equation*} \begin{equation*} 40-39=1\rightarrow\left(i,j\right)=\left(10,13\right) \end{equation*} \begin{equation*} 52-51=1\rightarrow\left(i,j\right)=\left(13,17\right) \end{equation*} Thus, the sum of these cells is: \begin{equation*} \sum=f\left(1,1\right)+f\left(4,5\right)+f\left(7,9\right)+f\left(10,13\right)+f\left(13,17\right) \end{equation*} \begin{equation*} \sum=g\left(1,1\right)+g\left(4,5\right)+g\left(7,9\right)+g\left(10,13\right)+g\left(13,17\right) \end{equation*} \begin{equation*} \sum=1+56+111+166+221=555 \end{equation*}