2024 Putnam B1

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

w

2 users

TOPICS

No tags match your search

M

No tags match your search

M

2024 Putnam B1

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

411 posts

#1 h Dec 10, 2024, 5:01 PM • 1 Y

Y by GeoKing

Let $n$ and $k$ be positive integers. The square in the $i$ th row and $j$ th column of an $n$ -by- $n$ grid contains the number $i+j-k$ . For which $n$ and $k$ is it possible to select $n$ squares from the grid, no two in the same row or column, such that the numbers contained in the selected squares are exactly $1,\,2,\,\ldots,\,n$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

890 posts

#2 h Dec 10, 2024, 5:16 PM • 1 Y

Y by GeoKing

The answer is all odd integers $n$ and $k=\frac{n+1}{2}$

Construction:

Let $n=2m+1$ , select $(1,2m+1), (3, 2m)....(2m+1,m+1); (2m,1), (2m-2, 2)... (2,m)$ . We could see it maps all columns and rows without having two squares in the same row or column. And the sum for odd columns are $2m+2, 2m+3...3m+2$ the sum for even columns are $2m+1...m+2$ . Then, we subtract $k=\frac{2m+1+1}{2}=m+1$ and we could get the $i+j-k$ for each square is $1,2...2m+1=n$ and we are done.

Now we prove even $n$ can't work. Let $n=2t$ , the sum of $i+j$ for all $2t\cdot 2t$ square would be $2(1+2+...+2t)$ . Then we subtract $2t$ for $k$ times, the remaining numbers are $1,2...n=2t$ , so we get $2kt+(1+2+...2t)=2(1+2...+2t), 2kt=\frac{2t(2t+1)}{2}, k=\frac{2t+1}{2}$ which is not an integer.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

187 posts

#3 h Dec 10, 2024, 6:17 PM • 2 Y

Y by GeoKing, avocadotuna

Answer is $(n,k)=(n,\frac{n+1}{2})$ for all odd integers $n$ . This is the same invariant as 2001 B1. Since no two squares are in the same row or column, the row and column coordinates must be $1,2,\ldots,n$ . Thus summing all $n$ squares we get $\frac{n(n+1)}{2}+\frac{n(n+1)}{2}-nk=\frac{n(n+1)}{2}$ which means that $k=\frac{n+1}{2}$ . Since $k$ is a positive integer, $n$ must be odd.

Correctness can be checked routinely.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4 posts

#4 h Dec 10, 2024, 6:45 PM

Y by

Since we must select squares such that our selections are $1, 2, \ldots, n$ , we know that the sum of our selections must be equal to $\sum_{i=1}^n i = \frac{n(n+1)}{2}$ . Since we make $n$ selections, and we must make one selection from each row and column, we have the invarient $\left(\sum_{i=1}^n i\right) + \left(\sum_{j=1}^n j\right) - nk = \frac{n(n+1)}{2}$ . Converting to a closed form, we get $\frac{n(n+1)}{2} + \frac{n(n+1)}{2} - nk = \frac{n(n+1)}{2}$ . Now, factoring out an $n$ , we get $\frac{n+1}{2} + \frac{n+1}{2} - k = \frac{n+1}{2}$ . Finally, simplifying we get $k = \frac{n+1}{2}$ . Now, since both $n$ and $k$ must be positive integers, we know that $n$ must be odd. Thus far, we have proved that for any solution, $n$ must be odd, and $k$ must be equivalent to $\frac{n+1}{2}$ . For a construction, start by selecting the square in row $n$ column $\frac{n+1}{2}$ . By construction, we know that this square has a value of $n + \frac{n+1}{2} - \frac{n+1}{2} = n$ . Now, for our following selections, increment our column index by 1, and decrement our row index by 2. Such a selection guarantees a unique row and column from our selections thus far, and must contain precisely $n-1$ by construction. Now, repeat this selection process of incrementing the column by one and decrementing the row by two until reaching the first row. Since $n$ is odd, we will be precisely in the first row and $nth$ column. By construction, this square will have value $1 + n - \frac{n+1}{2} = \frac{n+1}{2}$ . Now, select the square in the $n-1$ th row, and first column. By construction this square will have value $n-1 + 1 - \frac{n+1}{2} = \frac{n-1}{2}$ . Note that this value is precisely one less than the previous value, and that such a square is in a previously unselected row and column. Now, repeat the process of decrementing the row by two, and incrementing the column by 1. Repeat this process until $n$ total squares have been selected. Now, since each subsequent selection represents a decrement of 1 for $n$ total selections starting with $n$ , we know that we must have selected precisely $1, 2, \ldots, n$ . Further, since we have selected from exclusively odd indexed rows in the first leg of our selection process, and exclusively even rows in the second leg, we could not have repeated rows. Since we selected exclusively from the columns $\frac{n+1}{2}$ to $n$ in the first leg of our selection process, and 1 to $\frac{n-1}{2}$ in the second leg of our selection process, we could not have repeated columns. Thus, for any positive odd $n$ with $k = \frac{n+1}{2}$ , we can select $n$ squares from the grid, no two in the same row or column, such that the numbers contained in the selected squares are exactly $1, 2, \ldots, n$ as desired $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1742 posts

#5 h Dec 10, 2024, 8:49 PM • 1 Y

Y by KevinYang2.71

All solutions are of the form $(n,k) = (2k-1, k),$ where $k \in \mathbb{N}.$

First, we provide a construction for $(n,k) = (2k-1, k)$ . Take the squares $(1,k), (2,k+1), \dots, (k, 2k-1), (k+1, 1), \dots, (2k-1, k-1).$ We do not repeat $x$ or $y$ coordinates, so we can choose these squares. Furthermore, the value of the square $(i, i + k -1)$ for $1 \le i \le k$ is $i + (i+k-1) - k = 2i - 1$ , and the value of the square $(k + i, i)$ for $1 \le i \le k - 1$ is $k + 2i - k = 2i.$ Therefore, we get the values $1,3,5,\dots,2k-1$ and $2,4,\dots,2k-2,$ so this construction works.

Now we show that there are no other solutions. Assume that it were possible for some $n,k.$ We calculate the sum of the values in each square we choose in two ways. One way is direct: it is just $1 + 2 + \dots + n = \frac{n(n+1)}{2}.$ For the other way, let $\sigma$ be a permutation of $1,2,\dots,n$ corresponding to our choice of squares, so that we choose squares in positions $(1, \sigma(1)), \dots, (n, \sigma(n)).$ Then the value of the $i$ th square we choose is $i + \sigma(i) - k.$ Summing over all $i,$ the sum of the values in each square we choose is $(1 + 2 + \dots + n) + (\sigma(1) + \sigma(2) + \dots + \sigma(n)) - nk = n(n+1) - nk = \frac{n(n+1)}{2}.$ Dividing both sides by $n$ and solving for $n$ gives $n = 2k - 1.$

Therefore, the only solutions are those described at the beginning.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

214 posts

#6 h Dec 11, 2024, 10:43 AM

Y by

Solution: Easily by Invariance we get $\sum (i+j-k) = 2.\frac{n(n+1)}{2}-nk = 1+2+3+\cdots +n=\frac{n(n+1)}{2} \Longrightarrow k=\frac{n+1}{2}$ giving us that $n$ being even is obsolete, so $n$ must be odd . Suppose $n=2l+1$ then $k=l+1$ . We choose first odd numbers for our ease $(l+1,1),(l+2,2),(l+3,3),(l+4,4).....$ which contains $1,3,5,7,\cdots$ respectively. Then choose $(1,l+2),(2,l+3),(3,l+4),\cdots$ which contains $2,4,6,8,\cdots$ respectively. Note that these squares contains these numbers can be checked by $i+j-k$ and this construction is valid since odd numbers are chosen diagonally and similarly even numbers too . Induction can easily prove that no rows or columns overlapp . So we are done ! I spent much time for construction :wallbash_red:

:wallbash_red:

:wallbash_red:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

225 posts

#7 h Dec 14, 2024, 9:27 AM

Y by

Consider the case when $n$ is odd, i.e. $n=2t-1$ . Observe that $k=t$ works. The cells $(t, 1), (t+1, 2), \cdots (n, n+1-t)$ and $(1, n+2-t), (2,n+3-t) \cdots (t-1, n)$ work as one of the many constructions.
Now observe that for any $n$ we need $2 \leq k \leq n-1$ , and the possible values of $k$ are symmetric about $\frac{n+1}{2}$ .
Now notice that if the number $r$ is on the long diagonal, then for each of $1, 2, \cdots r-1$ two new copies of $r$ on the long diagonal cannot be selected. Thus $2(r-1) < n$ so $r< n/2 + 2$ but $r=n+1-k$ which gives $n/2 < k$ . If $n$ is even, then any solution $k$ more then $n/2$ gives a solution less than $n/2$ by symmetry about $\frac{n+1}{2}$ which we established. Impossible.
If $n$ is odd, then the only possible solution is $\frac{n+1}{2}$ . If there was a bigger solution then there would be a solution smaller than $n/2$ by symmetry which is impossible.
Thus, $n$ odd and $k=\frac{n+1}{2}$ is the only possibility.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

123 posts

#8 h Apr 2, 2025, 9:27 AM

Y by

We claim that $(n,k)$ is a solution if and only if $n$ is odd and $k=\lceil n/2\rceil$ .
Let the of locations (following the usual convention used in matrices) of $n$ numbers we are interested be $(a_{1}, b_1,), (a_2, b_2),\ldots, (a_n, b_n)$ . One might see that $(a_1, a_2,\ldots, a_n)=\sigma(1,2,\ldots, n)$ and $(b_1, b_2,\ldots, b_n)=\sigma(1,2,\ldots, n)$ (where $\sigma$ represents a permutation). So we now have a nice relation i.e,
$\sum_{1\le i\le n}(a_i+b_i)-nk=n(n+1)-nk=\cfrac{n(n+1)}{2}.$ Clearly $n$ is odd and $k=(n+1)/2$ and we are just halfway there. For motivating a general construction consider $n=3,5,7,9$ . All we can hope for is a nice pattern.
$\underbrace{\begin{matrix} 2 & 3 & \textcolor{blue}{4}\\ \textcolor{blue}{3} & 4 & 5\\ 4 & \textcolor{blue}{5} & 6\\ \end{matrix}}_{\text{$n=3$}}\qquad \underbrace{\begin{matrix} 2 & 3 & 4 & 5 & \textcolor{blue}{6}\\ 3 & \textcolor{blue}{4} & 5 & 6 & 7\\ 4 & 5 & 6 & \textcolor{blue}{7} & 8\\ \textcolor{blue}{5} & 6 & 7 & 8 & 9\\ 6 & 7 & \textcolor{blue}{8} & 9 & 10 \end{matrix}}_{\text{$n=5$}}\qquad \underbrace{\begin{matrix} 2 & 3 & 4 & 5 & 6 & 7 & \textcolor{blue}{8}\\ 3 & 4 & \textcolor{blue}{5} & 6 & 7 & 8 & 9\\ 4 & 5 & 6 & 7 & 8 & \textcolor{blue}{9} & 10\\ 5 & \textcolor{blue}{6} & 7 & 8 & 9 & 10 & 11\\ 6 & 7 & 8 & 9 & \textcolor{blue}{10} & 11 & 12\\ \textcolor{blue}{7} & 8 & 9 & 10 & 11 & 12 & 13\\ 8 & 9 & 10 & \textcolor{blue}{11} & 12 & 13 &14 \end{matrix}}_{\text{$n=7$}}\qquad \underbrace{\begin{matrix} 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \textcolor{blue}{10}\\ 3 & 4 & 5 & \textcolor{blue}{6} & 7 & 8 & 9 & 10 & 11\\ 4 & 5 & 6 & 7 & 8 & 9 & 10 & \textcolor{blue}{11} & 12\\ 5 & 6 & \textcolor{blue}{7} & 8 & 9 & 10 & 11 & 12 & 13\\ 6 & 7 & 8 & 9 & 10 & 11 & \textcolor{blue}{12} & 13 & 14\\ 7 & \textcolor{blue}{8} & 9 & 10 & 11 & 12 & 13 & 14 & 15\\ 8 & 9 & 10 & 11 & 12 & \textcolor{blue}{13} & 14 & 15 & 16\\ \textcolor{blue}{9} & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17\\ 10 & 11 & 12 & 13 & \textcolor{blue}{14} & 15 & 16 & 17 & 18 \end{matrix}}_{\text{$n=9$}}\qquad\cdots$ Shifting all the numbers in the respective grid by $\lceil n/2\rceil$ , the blue ones yield a valid construction. So the generalised construction from our observation is to pick the numbers from the location $(a_1, b_n), (a_3, b_{n-1}), (a_5, b_{n-2}),\ldots, (a_{n}, b_{\lceil n/2\rceil})$ and $(a_{n-1}, b_1), (a_{n-3}, b_2), \ldots, (a_2, b_{\lfloor n/2\rfloor})$ which is indeed valid. $\square$

This post has been edited 2 times. Last edited by anudeep, Apr 2, 2025, 9:30 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a