7
$\begingroup$

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)

$\endgroup$
5
  • 1
    $\begingroup$ What about a 7x7 with numbers 1 to 49? ;) $\endgroup$ Aug 12 at 0:29
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 12 at 14:42
  • $\begingroup$ 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. $\endgroup$
    – Brandon_J
    Aug 15 at 3:08
  • 1
    $\begingroup$ @Brandon_J Thanks! If you say so... $\endgroup$ Aug 15 at 17:30
  • 1
    $\begingroup$ Thanks @Brandon_J and Bernardo! $\endgroup$
    – RobPratt
    Aug 15 at 18:10

3 Answers 3

7
$\begingroup$

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}

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

@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.

$\endgroup$
0
4
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.