11
$\begingroup$

Over on PPCG I've just made a question that involves arranging the numbers 1 to 9 on a 3 by 3 grid such that every 2 by 2 subgrid has the same sum. I'm calling such 3 by 3 grids and their N by N counterparts "sturdy squares".

For example

1 5 3
9 8 7
4 2 6

is a sturdy square because the four 2 by 2 subgrids

1 5
9 8
5 3
8 7
9 8
4 2
8 7
2 6

all sum to 23.

When I first broached the topic in our chatroom the other day, a lengthy discussion ensued (and continues to do so) about the properties of these squares and how to generate larger ones and so on. An OEIS sequence has even been drafted.

My question is, are there any mathematical publications that have considered this problem (the general N by N case and variants, not just 3 by 3)? Or else are there related topics in mathematics that could aid in our discussion of these "sturdy squares"?

(I'd also be interested to know what gleanings any of you have about sturdy squares.)

(My apologies that I'm very uncertain how to tag this.)

$\endgroup$
8
  • 1
    $\begingroup$ Which generalization do you have in mind? Do you want $2\times 2$ subsquares to have the same sum or $(N-1)\times (N-1)$? $\endgroup$ Commented Oct 22, 2015 at 6:00
  • $\begingroup$ Is it clear that solution exists for all N? $\endgroup$
    – joro
    Commented Oct 22, 2015 at 6:26
  • 2
    $\begingroup$ @AnthonyQuas: $2 \times 2$ for now. $\endgroup$ Commented Oct 22, 2015 at 7:30
  • 1
    $\begingroup$ @El'endiaStarman do you mean 51,840 for 5x5? $\endgroup$ Commented Oct 22, 2015 at 14:12
  • 2
    $\begingroup$ I have a suggestion. Relax the condition that the entries comprise the numbers from 1 to $N^2$ and allow the entries to be arbitrary positive (or nonnegative) integers. I suspect that these objects will be more tractable to analyze mathematically. Perhaps one can prove an analogue of Anand-Dumir-Gupta (Google if you don't recognize their names) for example. $\endgroup$ Commented Oct 22, 2015 at 18:43

1 Answer 1

2
$\begingroup$

I don't know what exists in literature (probably recreational math, if anywhere; this construction does not seem natural elsewhere). However, here are some observations that seem very relevant to what I perceive to be the most natural relaxation of the problem. (I'm assuming the generalization means $2 \times 2$ subsquares are checked, as opposed to $k \times k$ subsquares, although some of my observations can be extended to these generalizations as well)

(as I'm typing this, I realized Tim Chow made a comment that may have been spurred by similar instincts) Conditions like "have $1$ through $N^2$ each appear exactly once" are not very mathematically natural. They can be forced (which is why people do sometimes study magic squares) but are likely to be fairly ad-hoc in the attacks. A natural extension is to make sure the entries are arbitrary; i.e. the more general class of matrices with same $2 \times 2$ sums, without the uniqueness constraint. Let's call these "semi-sturdy squares", or "SSS." I believe I can describe these much more easily and naturally, and will do so below. I understand (and apologize!) that this is not exactly the problem you are solving, but it does provide structure that may be useful for you, since you are studying a special case).

One good strategy to start is to get some canonical form. Consider the following $4$ matrices, labeled by $M(a,b)$, where $a, b \in \{0,1\}$. Define $M(a,b)$ to have a $1$ in a coordinate $(x,y)$ if and only if $(x,y) = (a,b) \pmod{2}$ coordinatewise. Note that adding a linear combination of the $M(a,b)$ to your matrix does not change the sum condition (although it does change things like uniqueness of numbers). Thus, one thing we can do for free is to change the upper left $2 \times 2$ matrix to all $0$'s by shifting by whatever $M(a,b)$ you desire.

Now, I claim the following (somewhat nice!) statement:

Suppose you fixed the entire first row and first column (i.e. coordinates $(x,0)$ and $(0, y)$) to any integers of your choice. Then, selecting any integer as the value of $(1,1)$ gives a unique SSS.

Proving this isn't that hard, I'll give a short sketch: consider the case where you selected entries for coordinates $(0, y)$ and $(x, 0)$ for all $x$ and $y$, and you also fill in $(1,1)$. Then you now have the $2 \times 2$ sum, and from it you can determine $(1,2)$ (from $(1,1), (0,1),(0,2)$), $(1,3)$, etc. until you get that entire column. Similarly, you can get all the $(x,1)$ in the second row as well. Repeating this, you can fill the entire square. Note that if you chose the value of $s$ for $(1,1)$, what you are really doing is assigning a linear function of $s$ for every other coordinate, where $s$ appears with coefficient $1$ or $0$. (the $0$'s correspond to entries which do not depend on $s$, which in our case corresponds to those entries with either coordinate being even; for example, the moment you know $(0,0)$ and $(0,1)$ and $(2,0)$, you also know $(2, 1)$ without having to know $(1,1)$ or even $(1,0)$ explcitly).

Combining these two observations, the classification of SSS is quite easy: any SSS comes from a unique "zeroed SSS" which corresponds to making the top $2 \times 2$ matrix all $0$. The remaining choices are the first row and column, giving $2n-4$ remaining squares. Alternatively,

SSS's are in bijection with ordered lists of $2n$ integers; $2n-1$ integers for the choices of the first row and column, and the last integer for selecting the coordinate $(1,1)$. Any such set of values can be completed into a unique SSS.

I hope this is helpful as a first step. If I have more thoughts I'll add them. The next natural extension (although from my experiences working with things like anti-magic graphs, I would bet on this being very difficult) is to have the entries be all distinct. I suspect using the fact that they are $1$ through $N^2$ may be hard to encode in a useful way outside of simple modular arithmetic, so the real "meat" is the distinctness. But I'm happy to be proven wrong.

(for those with theoretical interest, what I'm doing in somewhat colloquial language above is linear algebra; I'm in effect considering a vector space where the vectors are $2 \times 2$ submatrices, and looking at the dimension of this vector space)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .