Al-Maghribî’s Mecca Problem Meets Sudoku – A Generalization of the Mecca Problem

In this section we will consider a generalization of the problem. To maintain the historic flavor of the topic, our generalization will be structured after Al-Maghribî’s original solution. A simpler version of this generalization will be given in our “Remarks” on the next page.

Let \(i,j,k,m,n,\) and \(p\) denote positive integers. Suppose we have \(m=n^2 >1\) trees, such that each year one gets 1 unit of produce from the first tree, 2 units from the second tree, … , and \(m\) units from the \(m\)th tree. How should these trees be divided among \(n\) inheritors so that each inheritor gets \(n\) trees and an equal amount of yearly produce?

Equipped with our experience of the solution of the special case \(n=9,\) let us establish an \(n\times n\) matrix with entries \(x_{jk}\) defined as

\[ x_{jk}=\begin{cases}(j-1)n + (k+1-j)\,\,{\rm{if}}\,\,j\le k,\\{\hphantom{xxxxx}}jn + (k+1-j)\,\,{\rm{if}}\,\,j > k,\end{cases}\quad(*)\] as depicted in the following table (Table 3):

Table 3

We will now study some interesting properties of Table 3. The first property shows us that this table has, in fact, some of the characteristics of an odd magic square starting with 1.

Property 1. Let \({\sigma}_n = {\frac{1}{2}}n(n^2+1).\) Then, all column sums are equal to \({\sigma}_n.\)

Proof. Let the sum of the numbers in the \(k\)th column be denoted by \(S_k.\) Then \[S_1 = 1 + 2n + [3n-1]+[4n-2] +\cdots [jn-(j-2)] +\cdots +[n\cdot n-(n-2)]\] \[=1+n\left(\frac{n^2+n-2}{2}\right)-\frac{n^2-3n+2}{2}\] \[=\frac{n(n^2+1)}{2}.\] The definition of the \(x_{jk}\)'s gives \( x_{j2} = x_{j1} +1,\) except for the diagonal position where \( x_{22} = x_{21} –(n-1).\) Thus, \[S_2 = S_1 +(n-1)-(n-1) = S_1.\]

Proceeding inductively, it also can be shown that \( x_{jk} = x_{j,k-1} +1,\) except for the diagonal position where \( x_{kk} = x_{k,k-1} –(n-1).\) Thus, \[S_k = S_{k-1} +(n-1)-(n-1) = S_{k-1}\] for all \(k=3,\dots,n,\) proving the property.

Property 2. If \(n\) is odd, the sum of the entries along the secondary diagonal is \({\sigma}_n.\)

Proof. Note that \(x_{1,n} =n\) and \(x_{n,1} =n^2+(2-n).\) Thus, \(x_{1,n} + x_{n,1} =n^2+2.\)

Similarly, \(x_{2,n-1} =n+n-2\) and \(x_{n-1,2} =(n-1)n+(3-n+1).\) Thus, \(x_{2,n-1} + x_{n-1,2} =n^2+2.\)

Proceeding in this manner, we see that if \(n\) is odd, by formula (*), above, for \(k=1,\dots ,\frac{n-1}{2},\) the elements in the secondary diagonal corresponding to rows \(k\) and \((n-k+1)\) add up to \(n^2 +2.\) Adding all of these we get \[\left(\frac{n-1}{2}\right)(n^2+2).\]

The only element along the secondary diagonal that is unaccounted for in this sum is \(x_{{\frac{n+1}{2}},\frac{n+1}{2}},\) which by formula (*) is equal to \[n\left({\frac{n+1}{2}}-1\right) +1 = \frac{n^2-n+2}{2}.\] Thus, the sum of the elements along the secondary diagonal is \[\left(\frac{n-1}{2}\right)(n^2+2) + \frac{n^2-n+2}{2} = {\frac{1}{2}}n(n^2+1) = {\sigma}_n.\] This completes the proof.

Property 2 does not hold when \(n\) is even. A simple counterexample is provided by the 4 x 4 matrix in Table 4:

Table 4

Here, \({\sigma}_4 =34,\) whereas the secondary diagonal sum is 36.

However, even in the case \(n\) is even, something can be said about the secondary diagonal sum:

Property 3. If \(n\) is even, the sum of the elements along the secondary diagonal is \({\sigma}_n +\frac{n}{2}.\)

Proof. If \(n\) is even, the elements on the subdiagonal corresponding to rows \(k\) and \(n-k,\) for \(k=1,2,\dots,\frac{n}{2}\) all add up to \(n^2+2\); hence, the sum of these numbers will be \[{\frac{n}{2}}(n^2+1)={\sigma}_n +\frac{n}{2}.\]

As we remarked earlier, the elements along the main diagonal do not add up to \({\sigma}_n.\)

Property 4. For any integer \(p\ge1,\) let \(T_p={\frac{1}{2}}p(p+1).\) Then, the sum of the elements along the main diagonal is \({\sigma}_n –T_{n-1}.\) That is, the main diagonal sum can never be \({\sigma}_n.\)

Proof. In case \(n\) is odd, the elements on the main diagonal corresponding to rows \(k\) and \(n-k+1\) for \(k=1,2,\dots,\frac{n-1}{2},\) add up to \(n^2-n+2.\) Summing, we get \[\left({\frac{n-1}{2}}\right)\left(n^2-n+2\right).\] This sum accounts for every element along the main diagonal except for \(x_{{\frac{n+1}{2}},\frac{n+1}{2}}.\) Since \[x_{{\frac{n+1}{2}},\frac{n+1}{2}}={\frac{1}{2}}\left(n^2-n+2\right),\] the sum of all the numbers along the main diagonal will be \[\left({\frac{n-1}{2}}\right)\left(n^2-n+2\right)+{\frac{1}{2}}\left(n^2-n+2\right)={\sigma}_n-T_{n-1}.\]

In case \(n\) is even, a similar argument shows that we have \(\frac{n}{2}\) elements adding up to \({\frac{n}{2}}\left(n^2-n+2\right),\) proving the result.

So far, we have not said anything about the row sums except to remark that, in general, they are not equal to \({\sigma}_n.\) We remedy that situation by the following results:

Proposition 1. Let \(j\) and \(k\) be any two integers satisfying \(1\le j\le{n-1}\) and \(1\le k\le{n-1}.\) Let \(x_{jk}\) denote the entry in Table 3 in the \(j\)th row and \(k\)th column. Then,

1. If \(j\not=k,\,\) \(x_{j+1,k}-x_{jk}=n-1.\)
2. If \(j=k,\,\) \(x_{j+1,k}-x_{jk}=2n-1.\)
3. For all \(j,\,\) \(x_{j+1,n}-x_{jn}=n-1.\)

Property 5. The sum of the elements along the \(k\)th row is \[\frac{(2k-1)n^2+n}{2}.\]

Proof. Since, by construction, the smallest number in the \(n\)th row is \((k-1)n+1,\) and the largest one is \(kn,\) and since each number in between occurs once and only once, by rearranging these in ascending order, we see that the elements in the \(k\)th row are \[(k-1)n+1, (k-1)n+2,\dots, (k-1)n+n.\] Summing, we get \[(k-1)n^2+(1+2+\cdots+n) = \frac{(2k-1)n^2+n}{2},\] which completes the proof.

Property 5 can be used to show that the fact that the sum of the elements in the fifth row of Table 1 equals the column sum is not a mere coincidence:

Corollary 1. For each odd integer \(n,\) there exists a row, namely, the \(\frac{n+1}{2}\)th row, such that the row sum is \({\sigma}_n.\)