Question

The number 1, 2, ...., $n^2$ are arranged in an $n\times n$ array in the following way

1	2	3	....	n
n+1	n+2	n+3	....	2n
...				...
$n^2-n+1$	$n^2-n+2$	$n^2-n+3$	....	$n^2$

Pick n numbers from the array such that any two numbers are in different rows and different columns. Find the sum of these numbers

• A. $\frac{n(n+1)}{3}$
• B. $\frac{n(n+1)}{2}$
• C. $\frac{n(n^2-1)}{2}$
• D. $\frac{n(n^2+1)}{2}$

Answer 1

The correct option is B $\frac{n(n+1)}{2}$

If we denote by $a_{ij}$ the number in the ith row and jth column then
$a_{ij}=(i-1)n+j$
for all i, $j=1,2,...,n$. Because any two numbers are in different rows and different columns, it follows that from each row and each column exactly one number is chosen. Let $a_{1_{j_1}},a_{2_{j_2}},....,a_{n_{j_n}}$ be the chosen numbers, where $j1,j2,....,jn$ is a permulation of indices 1, 2, ...., n. We have
$\sum _{k=1}^n{a}_{k_{j_k}}=\sum _{k=1}^n\left(\right(k-1)n+j_k)=n\sum _{k=1}^n(k-1)+\sum _{k=1}^n{j}_k$
But
$\sum _{k=1}^{n}jk=\frac{n(n+1)}{2}$