# Avoiding arithmetic progressions in square grids

a) Is it possible to place the integers 1 to 25 in a 5 x 5 grid so that no column or row contains an increasing or decreasing 3-term arithmetic progression (A.P.)?

b) Can this be done in a 6 x 6 grid with integers 1 to 36?

Note: Rows or columns can contain numbers which belong to an A.P., but not themselves be in a monotone arithmetic progression, i.e. 13 25 17 15 23 can be a row, but not 25 13 15 23 17, as the latter has 13 15 17 (adjacency does not matter when finding arithmetic progressions, just order)

• What about a 7x7 with numbers 1 to 49? ;) Aug 12 at 0:29
• It turns out the problem is quite easy for larger grids. I can find solutions up to 30x30 in a few seconds with a program. Aug 12 at 14:42
• Hi Bernardo. My answer is currently the accepted one, but I believe the checkmark ought to be awarded to @RobPratt - his answer is very impressive. Aug 15 at 3:08
• @Brandon_J Thanks! If you say so... Aug 15 at 17:30
• Thanks @Brandon_J and Bernardo! Aug 15 at 18:10

Via integer linear programming with a binary decision variable $$x_{i,j,k}$$ that indicates whether cell $$(i,j)$$ takes values $$k$$, I found solutions where each row or column is increasing. For the even ones, I also imposed a symmetry constraint $$x_{i,j,k} = x_{n+1-i,n+1-j,n^2+1-k}$$. For the odd ones, that is impossible because it would introduce an AP in the middle row and column.

$$5 \times 5$$:

$$\begin{matrix}1 & 3 & 4 & 8 & 9\\2 & 6 & 7 & 13 & 14\\5 & 10 & 12 & 17 & 18\\11 & 16 & 19 & 20 & 23\\15 & 21 & 22 & 24 & 25\end{matrix}$$

$$6 \times 6$$:

$$\begin{matrix}1 & 2 & 4 & 5 & 10 & 11\\3 & 6 & 7 & 12 & 13 & 16\\8 & 9 & 15 & 18 & 20 & 23\\14 & 17 & 19 & 22 & 28 & 29\\21 & 24 & 25 & 30 & 31 & 34\\26 & 27 & 32 & 33 & 35 & 36\end{matrix}$$

$$7 \times 7$$:

$$\begin{matrix}1 & 3 & 4 & 9 & 10 & 12 & 18\\2 & 5 & 6 & 13 & 14 & 17 & 19\\7 & 11 & 16 & 20 & 22 & 23 & 27\\8 & 15 & 24 & 25 & 29 & 31 & 32\\21 & 26 & 30 & 33 & 35 & 41 & 42\\28 & 34 & 37 & 38 & 43 & 44 & 47\\36 & 39 & 40 & 45 & 46 & 48 & 49\end{matrix}$$

$$8 \times 8$$:

$$\begin{matrix}1 & 2 & 4 & 5 & 10 & 11 & 13 & 23\\3 & 6 & 7 & 12 & 14 & 15 & 19 & 28\\8 & 9 & 16 & 18 & 21 & 25 & 30 & 31\\17 & 20 & 24 & 26 & 27 & 29 & 33 & 43\\22 & 32 & 36 & 38 & 39 & 41 & 45 & 48\\34 & 35 & 40 & 44 & 47 & 49 & 56 & 57\\37 & 46 & 50 & 51 & 53 & 58 & 59 & 62\\42 & 52 & 54 & 55 & 60 & 61 & 63 & 64\end{matrix}$$

$$10 \times 10$$:

$$\begin{matrix}1 & 2 & 4 & 5 & 10 & 11 & 13 & 14 & 28 & 29\\3 & 6 & 7 & 12 & 15 & 19 & 20 & 22 & 30 & 39\\8 & 9 & 17 & 18 & 21 & 23 & 31 & 32 & 36 & 42\\16 & 24 & 25 & 27 & 33 & 37 & 45 & 46 & 51 & 54\\26 & 34 & 35 & 38 & 40 & 52 & 53 & 57 & 58 & 60\\41 & 43 & 44 & 48 & 49 & 61 & 63 & 66 & 67 & 75\\47 & 50 & 55 & 56 & 64 & 68 & 74 & 76 & 77 & 85\\59 & 65 & 69 & 70 & 78 & 80 & 83 & 84 & 92 & 93\\62 & 71 & 79 & 81 & 82 & 86 & 89 & 94 & 95 & 98\\72 & 73 & 87 & 88 & 90 & 91 & 96 & 97 & 99 & 100\\\end{matrix}$$

• Dude, that's awesome. Should definitely be the new accepted answer. Is it possible above 8x8? Aug 13 at 13:35
• @Brandon_J I added a symmetric $10 \times 10$ to my answer. Aug 14 at 1:37

@Prim3numbah has found a 5x5 grid. See their solution here

Below is the 6x6 grid that I have found

+--+--+--+--+--+--+
|11|06|09|08|15|20|
+--+--+--+--+--+--+
|05|28|26|27|34|25|
+--+--+--+--+--+--+
|07|29|01|02|36|23|
+--+--+--+--+--+--+
|16|27|03|04|35|24|
+--+--+--+--+--+--+
|13|32|30|31|33|22|
+--+--+--+--+--+--+
|12|10|17|18|21|14|
+--+--+--+--+--+--+



My strategy was to

Place very high and very low numbers near the middle of the square, and then place the middle numbers around the edge. Since I was able to successfully implement this strategy on my first attempt, I feel confident that there are multiple other arrangements that would work, although I have no proof of this.

Note that

I did my best to double-check my answer, but I may have missed a progression, since I was trying to do this without a computer. Please drop a comment if you find an error.

I found this grid for a)

  1  2  23 24 15
3  5  9  10 18
6  7  11 13 12
14 16 17 19 25
21 22 4  8  20