(a) If we list all the elements in the rows followed by all the elements in the columns, then we have listed every element in the array twice, so each number in S must appear an even number of times. But considering the ith row with the ith column, we have also given n complete copies of S together with an additional copy of the numbers on the diagonal. If n is odd, then each of the 2n-1 numbers appears an odd number of times in the n complete copies, and at most n numbers can have this converted to an even number by an appearance on the diagonal. So there are no silver matrices for n odd. In particular, there is no silver matrix for n = 1997. (b) Let Ai,j be an n x n silver matrix with 1s down the main diagonal. Define the 2n x 2n matrix Bi,j with 1s down the main diagonal as follows: Bi,j = Ai,j; Bi+n,j+n = Ai,j; Bi,j+n = 2n + Ai,j; Bi+n,j = 2n + Ai,j for i not equal j and Bi+n,i = 2n. We show that Bi,j is silver. Suppose i ≤ n. Then the first half of the ith row is the ith row of Ai,j, and the top half of the ith column is the ith column of Ai,j, so between them those two parts comprise the numbers from 1 to 2n - 1. The second half of the ith row is the ith row of Ai,j with each element increased by 2n, and the bottom half of the ith column is the ith column of Ai,j with each element increased by 2n, so between them they give the numbers from 2n + 1 to 4n - 1. The only exception is that Ai+n,i = 2n instead of 2n + Ai,i. We still get 2n + Ai,i because it was in the second half of the ith row (these two parts do not have an element in common). The 2n fills the gap so that in all we get all the numbers from 1 to 4n - 1. An exactly similar argument works for i > n. This time the second half of the row and the second half of the column (which overlap by one element) give us the numbers from 1 to 2n - 1, and the first halves (which do not overlap) give us 2n to 4n - 1. So Bi,j is silver. Hence there are an infinite number of silver matrices.

Well, it is possible to prove that $n \times n$ silver matrices exists for any even $n$.

a) $ (2k+1)^2 < (k+1)(4k+1)$ for $ k>0$, so if $ n=2k+1$ there exists a number from $ S$ which only is used at most $ k$ times, so it can only occur in at most $ 2k$ columns or rows. So there must be an $ i: 1\leq i \leq 2k+1$ for which it isn't in the $ i$th row or column. b) For n even just do it. Let $ n=2m$. It's fairly obvious that we can partition the set of unordered pairs $ \{i,j\}$ from $ \{1,2,....,2m\}$ into $ 2m-1$ disjoint sets $ T_1, T_2,....,T_{2m-1}$ of size $ m$ such that each $ i$ is found precisely once in each set. Then take a matrix $ (a_{xy})$ with major diagonal filled with 1s and for each pair $ \{i,j\}, i<j$ in $ T_k$, set $ a_{ij} = 2k, a_{ji}=2k+1$. This gives a silver n by n matrix.

Sorry for reviving a really old topic but I know, in official solution and @Lagrangia 's one, they had just proven that $n$ is power of $2$ so what about $n$ is even, can anyone help me?, @llthigore 's solution doesn't satisfy me at all!

There is a nice recursive construction: If you have a silver matrix of size $n$, you can construct a silver matrix of size $2n$ by taking two copies of the original matrix on the diagonal and adding Latin Squares in the two other corners But you can also obtain a silver matrix of size $2n-2$ by taking the original matrix in the upper left corner, reflecting it over the diagonal and filling the rest appropriately (this reflection works because you can assume that there are only 1's on the diagonal). And starting from $2$ with the steps $n \to 2n$ and $n \to 2n-2$ you can obtain any even number.

Tintarn wrote: But you can also obtain a silver matrix of size $2n-2$ by taking the original matrix in the upper left corner, reflecting it over the diagonal and filling the rest appropriately (this reflection works because you can assume that there are only 1's on the diagonal). And starting from $2$ with the steps $n \to 2n$ and $n \to 2n-2$ you can obtain any even number. Yes, this is exactly what I need but the red part, I don't know how you reflected, can you clarify, thanks!

I'll show you the example $4 \to 6$. You start with the construction for $n=4$ which canonically looks like \[\begin{pmatrix} 1 & 2 & 4 & 5\\3 & 1 & 5 & 4\\6 & 7 & 1 & 2\\7 & 6 & 3 & 1 \end{pmatrix}\]Now, you do the reflection over the diagonal: \[\begin{pmatrix} 1 & 2 & 4 & & & \\3 & 1 & 5 & & & \\6 & 7 & 1 & 2 & & \\ & & 3 & 1 & 5 &4\\& & & 7 & 1 & 2\\ & & & 6 & 3 & 1\end{pmatrix}\](Here of course you need to delete some entries.) And then fill in the gaps: \[\begin{pmatrix} 1 & 2 & 4 & 8 & 9 & 5 \\3 & 1 & 5 & 9 & 4 & 8 \\6 & 7 & 1 & 2 & 8 & 9\\10 & 11 & 3 & 1 & 5 &4\\11 & 6 & 10 & 7 & 1 & 2\\7 &10 &11 & 6 & 3 & 1\end{pmatrix}\]Of course there some technicalities to describe the general procedure, but hopefully the idea should be clear.

If the silver matrix $a(i,j)$ of size $2^k$ is defined, using the elements $\{-2^k+1, ..., 0, ..., 2^k-1\}$, then you can get a silver matrix of size $2^{k+1}$ by setting $a(i,j+2^k) = a(i,j)+2^k$ if $a(i,j) \geq 0$ $a(i,j+2^k) = a(i,j)-2^k$ if $a(i,j) < 0$ $a(i+2^k,j) = a(i,j) - 2^k$ if $a(i,j) \leq 0$ $a(i+2^k,j) = a(i,j) + 2^k$ if $a(i,j) > 0$ $a(i+2^k, j+2^k) = a(i,j)$. It has a lot of nice symmetries, such as $a(i,j) = - a(i,j)$ for all $i,j$.

I really enjoyed this problem iandrei wrote: An $ n \times n$ matrix whose entries come from the set $ S = \{1, 2, \ldots , 2n - 1\}$ is called a silver matrix if, for each $ i = 1, 2, \ldots , n$, the $ i$-th row and the $ i$-th column together contain all elements of $ S$. Show that: (a) there is no silver matrix for $ n = 1997$; (b) silver matrices exist for infinitely many values of $ n$. (a) We will show that there exists no silver matrix for an odd $n$. Call the union of the $ i$-th row and the $ i$-th column as the $i$-th block. Hence, each block must contain all the elements from $1$ to $2n-1$, and clearly, each element in a block must be different from the others (in the same block). Note that any element in the matrix contributes to at most $2$ blocks. Hence, each element $i$ appears at least $\left \lceil \frac{n}{2} \right \rceil =\frac{n+1}{2}$ times in the matrix. But since there are $2n-1$ elements, hence the total number of elements in the matrix is at least $\frac{(2n-1)(n+1)}{2} >n^2$, a contradiction. $\blacksquare$ (b) We will prove by induction on $n$ that for any $n \geq 1$, there exists a $2^n \times 2^n$ silver matrix. A $2 \times 2$ silver matrix is shown as the base case. $$\begin{pmatrix} 1 & 2 \\ 3 & 1 \\ \end{pmatrix}$$Now, asume that we have found a silver matrix $\{a_{ij}\}$ where $1 \le i, j \le 2^k$ for some $n=k$. For simplicity, set $m=2^{k}$. Then the silver matrix for $n=k+1$ is $$\begin{pmatrix} a_{11} & a_{12} & \dots & a_{1m} & a_{11}+2m & a_{12}+2m & \dots & a_{1m}+2m \\ a_{21} & a_{22} & \dots & a_{2m} & a_{21}+2m & a_{22}+2m & \dots & a_{2m}+2m \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mm} & a_{m1}+2m & a_{m2}+2m & \dots & a_{mm}+2m \\ 2m & a_{12}+2m & \dots & a_{1m}+2m & a_{11} & a_{12} & \dots & a_{1m} \\ a_{21}+2m & 2m & \dots & a_{2m}+2m & a_{21} & a_{22} & \dots & a_{2m} \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{m1}+2m & a_{m2} +2m& \dots & 2m & a_{m1} & a_{m2} & \dots & a_{mm} \\

building from the case $n=1$ to $n=2$ to $n=3$, but just for completeness, I will provide a formal explanation as to why this works.

Hence, we are done by induction. $\blacksquare$

Very nice problem! And a good practice of my proof-writing skills... a) Let $n=2k+1$. Call an $i$th row and $i$th column together a $i$-rolumn. Suppose a silver matrix does exist for $n$. Consider any number $m\in\{1,2,\dots, 4k+1\}$. Say it is present in the $a$th row and $b$th column of the matrix. Then it is part of the $a$-rolumn and the $b$-rolumn. Thus one instance of an entry in the matrix only satisfies being part of two rolumns. Thus to be part of $2k+1$ total rolumns, each of $\{1,2,\dots, 4k+1\}$ must appear at least $\left\lceil\frac{2k+1}{2}\right\rceil=k+1$ times. So there will be at least a total of $(k+1)(4k+1)=4k^2+5k+1$ entries in the matrix. However we only have $(2k+1)^2<4k^2+5k+1$ slots for the numbers, and we have a contradiction. Thus there are no silver matrices for odd $n$, and specifically for $n=1997$. $\square$ b) We will show that there exists a silver matrix for $n=2^k$, $k\geq 1$. We will prove this by induction on $k$, where $2^k\times 2^k$ is the dimension of the matrix. For $k=1$, consider the matrix $\left(\begin{array}{cc} 1&2\\3&1\end{array}\right)$. We assume that a silver matrix exists for $n=2^k$. Call it $A$. Now we wish to prove that a silver matrix exists for $2^{k+1}=2n$. We divide the $2n\times 2n$ matrix into four $n\times n$ matrices. We call them $B_1,B_2,B_3,B_4$ clockwise. Let $B_1=B_3=A$. Then $A$ contains the numbers $1,2,\dots, 2n-1$. The rest of the numbers $2n,2n+1,\dots, 4n-1$ must be filled in $B_2$ and $B_4$. Let $X=\{2n,2n+1,\dots, 3n-1\}$ and $Y=\{3n,3n+1,\dots, 4n-1\}$. So $|X|=|Y|=n$. Lemma 1: Any $n\times n$ matrix can be filled with the distinct numbers $a_1,a_2,\dots, a_n$, so that each row and each column contains all the numbers $a_1,a_2,\dots, a_n$. Proof: Simply consider the matrix $\begin{pmatrix}a_1&a_2&a_3&\dots&a_n\\a_n&a_1&a_2&\dots&a_{n-1}\\a_{n-1}&a_n&a_1&\dots&a_{n-2}\\.&.&.&\dots&.\\.&.&.&\dots&.\\.&.&.&\dots&.\\a_2&a_3&a_4&\dots&a_1 \end{pmatrix}$, where the $k$th row is formed by shifting the $(k-1)$th row to the right by one entry, and the last entry in the $(k-1)$th row is the first entry in the $k$th row. $\square$ Now going back to the main problem and using Lemma 1, we fill $B_2$ with the elements of $X=\{2n,2n+1,\dots, 3n-1\}$ so that each row and each column contains all the elements of $X$, and $B_4$ with the elements of $Y=\{3n,3n+1,\dots, 4n-1\}$ in a similar fasion. Then our $2n\times 2n$ ($n=2^k$) matrix is $$\begin{array}{cc}A&B_2\\B_4&A\end{array}.$$Note that if $1\leq i\leq 2^k$, then the $i$th row contains the elements of the $i$th rows of the upper left corner $A$ and the $i$th row of $B_2$. The $i$th column contains the elements of the $i$th column of the upper left corner $A$ and the $i$th column of $B_4$. We know that the "$A$ elements" contain all of ${1,2,\dots,2n-1}$ by the induction hypothesis. The "$B_2$ elements" contain all of $2n,2n+1,\dots, 3n-1$ and the "$B_4$ elements" contain all of $3n,3n+1,\dots, 4n-1$. A similar argument goes for $2^k<i\leq 2^{k+1}$. Thus the $i$th row and the $i$th column of the $2n\times 2n$ matrix contains all the numbers $1,2,\dots, 4n-1$, and is thus a silver matrix. Thus we are done by induction. $\blacksquare$

In the first step we define a machine. our machine is called a matrix permutation : if we give the matrix A to this , our machine add $+x$ to all elements of matrix $A$ except left large diameter elements ( this diameter $\begin{bmatrix} *& \\ &* \end{bmatrix}$ ) and fill in the left large diameter elements with $y$ and $z$ respectively. we show the new matrix $A$ in $A^{+x}_{y,z}$ form. for example : $$A : \begin{pmatrix} \bold{1}&2&3&4 \\ 5&\bold{6}&7&8 \\ 9&10&\bold{11}&12 \\ 13&14&15&\bold{16} \end{pmatrix} \rightarrow A^{+2}_{4,5} : \begin{pmatrix} \bold{4}&4&5&6 \\ 7&\bold{5}&9&10 \\ 11&12&\bold{4}&14 \\ 15&16&17&\bold{5} \end{pmatrix}$$now, for the for machine a new silver matrix, it's sufficient to convert the silver matrix $A$ in this way : $$ \begin{bmatrix} A&A^{+2n}_{n,n+1} \\ A^{+2n}_{n+1,n}&A \end{bmatrix} $$that's clearly gives the silver matrix because matrix $A$ makes numbers from $1$ to $2n-1$ and matrix permutation makes number for $2n$ to $4n-1$. the proof for moving $n$ and $n+1$ in matrix is row $i$_th and column $i$_th $(n < i)$ are same as $+2n$ and they can completely cover numbers $2n$ to $4n-1$ because $A$ was a silver matrix. And if it was in the form of $A^{+2n}_{n,n}$, makes numbers $2n+1$ to $4n-1$ that doesn't give us silver matrix. $\begin{pmatrix} 1&2 \\ 3&1 \end{pmatrix} \rightarrow \begin{pmatrix} 1&2&4&6 \\ 3&1&7&5 \\ 5&6&1&2 \\ 7&4&3&1 \end{pmatrix} \rightarrow \begin{pmatrix} 1&2&4&6&8&10&12&14 \\ 3&1&7&5&11&9&15&13 \\ 5&6&1&2&13&14&8&10 \\ 7&4&3&1&15&12&11&9 \\ 9&10&12&14&1&2&4&6 \\ 11&8&15&13&3&1&7&5 \\ 13&14&9&10&5&6&1&2 \\ 15&12&11&8&7&4&3&1 \end{pmatrix}$

$(\text a)$ FTSOC, let $M=(a_{i,j})$ be a $n\times n$ silver matrix. For odd $n$, we have: $$2\sum_{i=1}^n\sum_{j=1}^na_{i,j}=\sum_{i=1}^n\left(\sum_{j=1}^n(a_{i,j}+a_{j,i})-a_{i,i}\right)>\sum_{i=1}^n\sum_{j=1}^{2n-1}j=n^2(2n-1),$$which is a contradiction since $n^2(2n-1)$ is odd. Since $1997$ is odd, there is no such silver matrix. Got the minor hint to do induction for $(b)$. $(\text b)$ We claim that there exists a silver matrix for all powers of $2$. Proceed by induction. Base case: $2\times2$ We will use the matrix $\begin{pmatrix}1&2\\3&1\end{pmatrix}$. Induction step: $n\times n\Rightarrow2n\times2n$ For any silver $2^n\times2^n$ matrix $M$, we consider the transformation $$M\mapsto\begin{pmatrix}M&A\\B&M\end{pmatrix},$$where $A=M+2^{n+1}J_{2^n}$ and $B$ is the matrix obtain by replacing instances of $2^{n+1}+1$ with $2^{n+1}$ in $A$. For instance: $$\begin{pmatrix}1&2\\3&1\end{pmatrix}\to\begin{pmatrix}1&2&5&7\\3&1&6&5\\4&7&1&2\\6&4&3&1\end{pmatrix}\to\begin{pmatrix}1&2&5&7&9&10&13&15\\3&1&6&5&11&9&14&13\\4&7&1&2&12&15&9&10\\6&4&3&1&14&12&11&9\\8&10&13&15&1&2&5&7\\11&8&14&13&3&1&6&5\\12&15&8&10&4&7&1&2\\14&12&11&8&6&4&3&1\end{pmatrix}$$ Firstly, we can show that this process, iterated from $\begin{pmatrix}1&2\\3&1\end{pmatrix}$, always produces a matrix with all ones on the main diagonal. Then the main diagonal of $A$ is replaced when we form $B$. Now we can easily show that the resulting matrix is silver.

From Twitch Solves ISL: For (a), define a cross to be the union of the $i$th row and $i$th column. Every cell of the matrix not on the diagonal is contained in exactly two crosses, while each cell on the diagonal is contained in one cross. On the other hand, if a silver matrix existed for $n=1997$, then each element of $S$ is in all $1997$ crosses, so it must appear at least once on the diagonal since $1997$ is odd. However, $|S| = 3993$ while there are only $1997$ diagonal cells. This is a contradiction. For (b), we construct a silver matrix $M_e$ for $n = 2^e$ for each $e \ge 1$. We write the first three explicitly for concreteness: \begin{align*} M_1 &= \begin{bmatrix} 1 & 2 \\ 3 & 1 \end{bmatrix} \\ M_2 &= \begin{bmatrix} {\color{red}1} & {\color{red}2} & 4 & 5 \\ {\color{red}3} & {\color{red}1} & 6 & 7 \\ 7 & 5 & {\color{red}1} & {\color{red}2} \\ 6 & 4 & {\color{red}3} & {\color{red}1} \end{bmatrix} \\ M_3 &= \begin{bmatrix} {\color{red}1} & {\color{red}2} & {\color{red}4} & {\color{red}5} & 8 & 9 & 11 & 12\\ {\color{red}3} & {\color{red}1} & {\color{red}6} & {\color{red}7} & 10 & 15 & 13 & 14 \\ {\color{red}7} & {\color{red}5} & {\color{red}1} & {\color{red}2} & 14 & 12 & 8 & 9 \\ {\color{red}6} & {\color{red}4} & {\color{red}3} & {\color{red}1} & 13 & 11 & 10 & 15 \\ 15 & 9 & 11 & 12 & {\color{red}1} & {\color{red}2} & {\color{red}4} & {\color{red}5} \\ 10 & 8 & 13 & 14 & {\color{red}3} & {\color{red}1} & {\color{red}6} & {\color{red}7} \\ 14 & 12 & 15 & 9 & {\color{red}7} & {\color{red}5} & {\color{red}1} & {\color{red}2} \\ 13 & 11 & 10 & 8 & {\color{red}6} & {\color{red}4} & {\color{red}3} & {\color{red}1} \\ \end{bmatrix} \end{align*}The construction is described recursively as follows. Let \[ M_e' = \left[ \begin{array}{c|c} {\color{red}M_{e-1}} & M_{e-1} + (2^e-1) \\ \hline M_{e-1} + (2^e-1) & {\color{red}M_{e-1}} \\ \end{array} \right]. \]Then to get from $M_e'$ to $M_e$, replace half of the $2^e$'s with $2^{e+1}-1$: in the northeast quadrant, the even-indexed ones, and in the southwest quadrant, the odd-indexed ones.

I found an alternative construction for part b on the competition itself. On the main diagonal place all $1$s. Divide the remaining numbers into $n-1$ pairs. Let an $i$-diagonal be all the fields of the form $(x,x+i)$ modulo $n$. Thus, for example, the main diagonal is the $0$-diagonal (though we discount it from further analysis). Within an $i$-diagonal, $i=1,2,\dots,n-1$, let us define the relation of connectedness if two fields of the same $i$-diagonal belong to a common cross ($k$-th row+$k$-th column for some $k$). Note that each cross intersects each $i$-diagonal in exactly two fields. One easily proves that each field is connected to exactly two others, decomposing the $i$-diagonal into cycles. Due to translational symmetry, these cycles are of equal length. If $n=2^m$ for some $m$, these cycles will be of even length. Thus, for each $i$-diagonal we can select a pair of numbers and place them alternately along a cycle, ensuring that for each cross both numbers appear in it. This completes the proof.

Is this a well-written solution for part b?

(a) Let $n=2k+1$, so $S = \{1, 2, \dots, 4k+1\}$. Call the $i$-th row combined with the $i$-th column the $i$-th grass. Notice that each element in the matrix is in at most $2$ grasses. Therefore, to be in $2k+1$ grasses, there must be at least $\left\lceil\frac{2k+1}2\right\rceil = k+1$ copies of each element of $S$ in the matrix. However, this means we have at least $(4k+1)(k+1) > (2k+1)^2$ entries in the matrix, which is clearly impossible. Since $1997$ is odd, there is no silver matrix for $n = 1997$. (b) (stolen from WOOT induction handout). We prove that there is a silver matrix for $\boxed{n = 2^k}$ for all positive integers $k$. In particular, we will prove the case where there is a diagonal of $1$s going from $a_{11}$ to $a_{nn}$, which we'll call $M_n$. We proceed with induction. For the base case, notice that \[ \begin{bmatrix} 1 & 2 \\ 3 & 1 \end{bmatrix} \]works for $k=1$. Now suppose $M_k$ is a valid silver matrix with $1$s on the diagonal. Define $A_k$ as the matrix $M_k$ with $2^{k+1}$ added to each entry, and $B_k$ as $A_k$ but with all instances of $2^{k+1}+1$ with $2^{k+1}$. Then we can construct $M_{k+1}$ as follows: \[ M_{k+1} = \begin{bmatrix} M_k & A_k \\ B_k & M_k \end{bmatrix} \]Now each grass contains all integers $1, 2, \dots, 2n-1$ (since each grass contains a grass of $M_k$, which is silver), along with $2^{k+1}+1, 2^{k+1}+2, \dots, 2^{k+1}+2\cdot 2^k-1=2\cdot (2^{k+1}) - 1$ and $2^{k+1}$. Thus, each grass has all elements in $S$, and we are done.

For (a), we get a parity issue for $n$ odd. For (b), we prove that powers of $2$ work. Proceed with induction, with $\left|\begin{matrix}1&2\\3&1\end{matrix}\right|$ as the base case for $2$ by $2$. Let $M_k$ be the silver matrix at $n=2^k$. Consider a new matrix $A_k$, split into four quadrants $NW_k, NE_k, SW_k, SE_k$ with the labeling describing the location. We define $NW_k=SE_k=M_{k-1}$ and $SW_k=NE_k=M_{k-1}+2^k-1$. Transform $A_k$ into $M_k$ by replacing half of the squares in $NE_k, SW_k$ by the indexes' parity. Remark. Why did this feel so hard.. I got like 10000 hints on it including basically being given the construction.

Let a \textbf{structure} be the combined row and column of each $i$-th row and $i$-th column cell and the $i$-th row and $i$-th column cells be called the \textbf{$i$-th center} Part (a) Note that there must be at least $n-1$ numbers that aren't on the diagonal of \textbf{centers} because the maximum number of distinct numbers on the diagonal of \textbf{centers} is $n$ and there are $2n-1$ numbers in total. Now note that when a number isn't on the diagonal, it must be in $2$ \textbf{structures} and it must appear in each \textbf{structure}. A number can't have two instances in one structure but there are an odd number of \textbf{structures} because $1997$ is odd. Thus, we have a contradiction because the parities don't match up. Part (b) We claim that every $n = 2^{k}$ works. We wish for every number to be in a structure. We induct on $k$. First, note that \[\begin{tabular}{|c|c|} \hline 1 & 3 \\ \hline 2 & 1 \\ \hline \end{tabular}\]works for $k = 1$. Assume that $n = 2^{k}$ has a working construction. For $2^{k+1}$, we have two of the $2^{k}$ constructions on the diagonal of \textbf{centers}. Then, we replace each number in the $2^{k}$ construction with a new number, keeping which numbers on which spaces are equal to each other. We place this new construction on one of the other $2$ places to put a $2^{k}$. Then for the last place to put a $2^{k}$, we just copy the previous construction but change the number on the diagonal of \textbf{centers} to be the only number that hasn't been used. This construction works, which thus concludes the proof.

For any matrix, the numbers on the diagonal are referred to as rich numbers and the numbers not on the diagonal are poor. (a) We show that there is no silver matrix for any odd $n$. A $i$ group has the the row $i$ and column $i$ numbers. Suppose for contradiction, there is a silver matrix for odd $n$. Any number on $(i,j)$ occupies the row $i$ column $i$ and row $j$ column $j$ group. So, if $i\ne j$ then this number is in exactly two groups. Suppose this number is poor. Then every occurence of this number is in two groups. Since we need a total of $n$ groups, we need exactly $\frac n2$ occurences of each poor number, which is absurd as $n$ is odd. This gives a contradiction. $\blacksquare$ (b) The consturctions for $n=4$ is: \[\begin{pmatrix} 1 & 4 & 2 & 7\\5 & 1 & 6 & 3\\3 & 7 & 1 & 5\\6 & 2 & 4 & 1 \end{pmatrix}\]Suppose $n$ is even, so $n=2k$. Construct a $4k-2\times k$ table with entries as ordered pairs $(i,j)$ with $1\leq i,j\leq n$ such that each entry is distinct, and in any row, for any two entries, we have four distinct numbers; i.e. $(i,j)$ and $(i,k)$ must be in different rows. It is possible to construct such a table using a greedy algorithm. Then, each entry in the matrix on $(i,j)$ hosts the row number of $(i,j)$ in our table. It is easy to check that this satisfies all conditions required. $\blacksquare$

Define the $\textit{i-th cross}$ as the set of entries in either the $i$-th row or $i$-th column. a. We will show that there is no silver matrix for odd numbers $n$. Let $n=2k+1$. Each element is in at most $2$ crosses so there must be at least $k+1$ copies of every element in order to be in $n$ crosses. This implies that the number of elements in the matrix is \[(4k+1)(k+1)>(2k+1)^2,\] a contradiction. Thus, for $n=1997$ there cannot be a silver matrix. $\square$ b. For $n=2^k$ there will always be a silver matrix. To see this, we define a recursive sequence: $$ M_1 = \begin{bmatrix} 1 & 2 \\ 3 & 1 \end{bmatrix} $$$$ M_k' = \left[ \begin{array}{c|c} M_{k-1} & M_{k-1} + (2^k-1) \\ \hline M_{k-1} + (2^k-1) & M_{k-1} \\ \end{array} \right]. $$ Then to get from $M_k'$ to $M_k$, replace half of the $2^k$'s with $2^{k+1}-1$: in the northeast quadrant, the even-indexed ones, and in the southwest quadrant, the odd-indexed ones. $\square$

$\textbf{(a)}$ We use a bounding argument for odd $n>1$. Note that each integer $1, \ldots, 2n+1$ appears in at most two $\text{row } i \cup \text{col } i$ sets, so we require at least $\left \lceil \frac n2 \right \rceil = \frac{n+1}{2}$ of them. Thus the total number of integers needed is at least \[(2n-1)\left(\frac{n+1}{2}\right) = \frac{2n^2+n-1}{2},\] which is greater than $n^2$, contradiction. ${\color{blue} \Box}$ $\textbf{(b)}$ We construct matrices for $n=2^k$ inductively, where we assume $A_{k-1}$ satisfies the given conditions to show $A_k$ does too. Our recursion can be expressed as \[A_0 = [1], \quad A_1 = \begin{bmatrix} 1 & 3 \\ 2 & 1 \end{bmatrix}, \quad A_{i+1} = \begin{bmatrix} A_i & B_i \\ C_i & A_i \end{bmatrix},\] where $B_i$ represents the matrix $A_i$ with each cell increased by $2^{i+1}$ and $C_i$ represents the matrix $B_i$ with each cell of value $2^{i+1}+1$ with $2^{i+1}$. Our inductive assumption tells us this matrix indeed works. $\blacksquare$

(a) To show that there is no silver matrix for $n = 1997$, consider the number of distinct elements that must appear in the rows and columns. For an $n \times n$ matrix where the entries are from $S = {1, 2, \ldots, 2n - 1}$, there are $2n - 1$ distinct elements. In a silver matrix, each row and each column must contain all elements of $S$. However, in a $1997 \times 1997$ matrix, there are only $1997$ rows and columns. Therefore, it's impossible to cover all $2 \times 1997 - 1 = 3993$ distinct elements of $S$ in just $1997$ rows and columns. Hence, no silver matrix exists for $n = 1997$. (b) To show that silver matrices exist for infinitely many values of $n$, we can construct a silver matrix for any $n$ such that $n = 2k$ for some positive integer $k$. Consider an $n \times n$ matrix where the rows and columns are labeled $1, 2, \ldots, n$. For each row $i$, fill the entries of the $i$th row as follows: $$i,i+1,i+2,\dots,2n-1,1,2,\dots,i-1$$This arrangement ensures that each row contains all elements of $S = {1, 2, \ldots, 2n - 1}$. Now, consider each column. For the $j$th column, fill the entries as follows: $$j,j+1,j+2,\dots,2n-1,1,2,\dots,j-1$$This arrangement ensures that each column also contains all elements of $S$. Therefore, for any $n = 2k$, we can construct a silver matrix using this method, ensuring that each row and each column contains all elements of $S$. Since there are infinitely many values of $n = 2k$, silver matrices exist for infinitely many values of $n$.

Part a) There is no silver matrix for odd $n$ : Suppose for the sake of contradiction that such a matrix exists. For $i=1,2\dots n,$ list all the entries of the column $i$ and then all the entries of column $i.$ On one hand, for each $i,$ the list is exactly the elements of the set $S$ and one element repeated and that is the one in cell $(i,i)$ i.e on the diagonal. So in total there are exatcly $n$ copies of all the elements of $S$ plus one copy of the entries of the diagonal. On the other hand, we can look at once at all the columns's entries listed and then at all the rows to see that each entry appeared twice. As there are $n$ cells on the diagonal, pick one element of $S$ that does not appear on the diagonal, it appeared an even number of times (twice the number of cells having that element as entry). However it appeared exactly $n$ times as element of $S$ for each $1\leq i\leq n$ and that is the contradiction. Part b) An inductive construction for powers of two : For the base case $n=1,2$ let $A_1=[1]$ and $A_2=\begin{pmatrix} 1 & 2 \\ 2 & 3 \end{pmatrix}.$ Now, inductively define $$A_{i+1}=\begin{pmatrix} A_i & B_i \\ B_i & C_i \end{pmatrix}$$Where $B_i$ is $A_i$ increased by $2^i$ and $C_i$ is the result of $A_i$ when you change all the entries of its digonal to $2^i.$