In this article we will consider an old and rather obscure puzzle known as the Mecca Problem, discuss some of its interesting generalizations, and see how it relates to the modern day Sudoku puzzle and indeterminate systems.
What does an old riddle of a seventeenth century mathematician, Ali bin Veli Ibn Hamza al-Cezâirî (d. 1614), commonly known as Ibn Hamza Al-Maghribî, have to do with Sudoku, a modern-day popular Japanese puzzle that is a staple of our daily newspapers? Before we give an answer, let us first describe the old riddle.
Ibn Hamza was born in Algiers – in fact, the title Al Maghribî (the one from the west) seems to be given to him because of his Algerian origins. Towards the end of the sixteenth century he moved to Istanbul, then the capital of the Ottoman Empire, to complete his education and most likely stayed there until his death. He was an algebraist who also made important contributions to probability, hydrodynamics, mechanics, medicine, and geology.
The only written work Ibn Hamza left behind was a treatise called Tuhfetu'l – Âdâd lizevil Rüşd ve's – Sedad (The Ornament of Numbers). This was a 500-page book written in Ottoman Turkish containing some elementary theorems of Euclid and solutions of various Diophantine problems, and even some form of logarithms (Djebbar 2003). It comprised an introduction, four sections, and an appendix. The first section was on the properties of integers and the four basic operations on integers. The second section was devoted to developing rules of computations with rational and irrational numbers and methods of finding square, cube, and fourth roots. The third section dealt with approximate solutions of equations by various techniques such as the method of proportions or the regula falsi method (see Note). The fourth section presented some theorems of elementary geometry, and some formulas to calculate the areas of triangles, rectangles, circles, and volumes of regular solids. The Appendix – more or less the most original part of the book – contained several fascinating problems, including the one we are about to discuss, which the author solved using some peculiar methods.
The problem we are interested in can be stated as follows:
A landowner who has 81 trees, gets every year 1 unit of fruit from the first tree, 2 units from the second tree, … , and 81 units from the eighty-first tree. How should he divide these trees among 9 inheritors so that each inheritor gets 9 trees and an equal amount of yearly produce?
In his book, Ibn Hamza referred to this problem as the “Mecca problem,” possibly because it was suggested to him by an amateur Indian mathematician, Molla Mohammed, on the way to Mecca circa 1590 (Dilgan 1957).
Since the 81 trees will yield a total of \(1+\cdots+81=\frac{81\cdot82}{2}=3321\) units per year, each inheritor should get \(\frac{3321}{9}=369\) units of fruit per year. Thus, the problem is equivalent to solving a 9 x 81 indeterminate system of equations, where each variable is a unique integer between 1 and 81:
| \(x_{11}+x_{12}+\cdots+x_{19}\) | \(=369\) | |||
| \(x_{21}+x_{22}+\cdots+x_{29}\) | \(=369\) | |||
| \(\ddots\) | \(\vdots\) | |||
| \(x_{91}+x_{92}+\cdots+x_{99}\) | \(=369\) |
where \(x_{ij}\) stands for the number of units of fruit produced annually by the \(j\)th tree inherited by the \(i\)th heir, subject to the condition \(x_{ij}\not=x_{i^{\prime}j^{\prime}}\) for \(i\not=i^{\prime}\) or \(j\not=j^{\prime}.\)
Here is Al-Maghribî’s rather elegant original solution (Dilgan 1957): Number the trees 1, … , 81 according to the amount they yield, and place these numbers in a 9 x 9 table in the following way: Put 1 in the (1,1) position, then continue to the right along the first row, placing the numbers 2, 3, … , 9 in consecutive cells. Now move to cell (2,2) and put the next number, 10, in this position. Continue to the right along the second row, placing the numbers 11, … , 17 in the cells. Place the next integer, 18, in cell (2,1). Then start at cell (3,3) with the integer 19 and continue to the right by placing successive integers to fill up the remaining cells in the third row. Fill in the first two positions of this row with integers 26 and 27. Continue in this fashion to obtain the following table:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 18 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 26 | 27 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| 34 | 35 | 36 | 28 | 29 | 30 | 31 | 32 | 33 |
| 42 | 43 | 44 | 45 | 37 | 38 | 39 | 40 | 41 |
| 50 | 51 | 52 | 53 | 54 | 46 | 47 | 48 | 49 |
| 58 | 59 | 60 | 61 | 62 | 63 | 55 | 56 | 57 |
| 66 | 67 | 68 | 69 | 70 | 71 | 72 | 64 | 65 |
| 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 73 |
Table 1
Note that the sum of each column is equal to 369. Thus, a solution to the problem is that the first inheritor gets trees numbered 1, 18, 26, 34, … , 74; the second inheritor gets the trees numbered 2, 10, … , 75; … ; and the ninth inheritor gets the trees numbered 9, 17, 25, … , 73.
We notice that along with the column sums being 369, the secondary diagonal sum is also 369. However, this table is not a magic square: the numbers in the rows (except for the fifth row) and along the main diagonal do not add up to 369. Strictly speaking, it is not a Latin square either, for although we have an \(n\times n\) matrix where no entry occurs twice in any row or column, these entries do not satisfy the condition \(1\le x_{ij}\le n.\) Nor could it possibly be a completed Sudoku puzzle for the same reason: it contains entries other than 1 through 9.
However, there is a simpler way of perceiving the table representing Al Maghribî’s solution, a way that involves Latin squares. Let us subtract 0 from each entry of the first row of Table 1, 9 from each entry of the second row, 18 from each entry of the third row, and so on, until we subtract 72 from each entry of the last row. That is, let us construct a table with entries \(y_{ij}\) defined by the equation \[y_{ij} = x_{ij} - 9(i-1)\] for \(1\le i\le 9\) and \(1\le j\le 9,\) as depicted below:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 9 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 8 | 9 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 7 | 8 | 9 | 1 | 2 | 3 | 4 | 5 | 6 |
| 6 | 7 | 8 | 9 | 1 | 2 | 3 | 4 | 5 |
| 5 | 6 | 7 | 8 | 9 | 1 | 2 | 3 | 4 |
| 4 | 5 | 6 | 7 | 8 | 9 | 1 | 2 | 3 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1 | 2 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1 |
Table 2
We note that Table 2 consists of nine rows and nine columns of permutations of the first nine integers, a property that any finished Sudoku puzzle shares. Although Table 2 is not a solution to a Sudoku puzzle (why not?), it is a 9 x 9 Latin square. Moreover, if we start with any other 9 x 9 Latin square with entries 1 through 9 – in particular, any completed Sudoku puzzle – and add 0 to each entry of the first row, 9 to each entry of the second row, 18 to each entry of the third row, … , and 72 to each entry of the ninth row, we would obtain a different solution to Al-Maghribî’s problem. Try it next time you complete a Sudoku puzzle!
This gives us a multitude of solutions to the original problem, namely 5524751496156892842531225600 solutions – the number of different 9 x 9 Latin squares (Bammel and Rothstein 1975) – assuming inheritors are distinct.
_______________________________________
Note. In the third section of Tuhfetu'l – Âdâd lizevil Rüşd ve's – Sedad, Ibn Hamza also described some algebraic manipulations such as al-jabr, a word which originally referred to mending a broken bone and which can be best translated as “restoration or reunion of broken parts” – that is, combining like terms on one side of an equation – and al-muqabala, which literally means a “face-off” and can be better translated as “confrontation” or “reduction” – that is, reducing terms appearing on both sides of an equation to a single term on one side of the equation. These ideas, of course, originated in the Hisab al-jabr w'âl muqabala of al-Khwarizmi (780–circa 850). It is likely that Ibn Hamza actually learned them from more contemporary works. Back to top
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):
| 1 | 2 | 3 | 4 | 5 | 6 | \(\cdots\) | \(n-1\) | \(n\) |
| \(2n\) | \(n+1\) | \(n+2\) | \(n+3\) | \(n+4\) | \(n+5\) | \(\cdots\) | \(2n-2\) | \(2n-1\) |
| \(3n-1\) | \(3n\) | \(2n+1\) | \(2n+2\) | \(2n+3\) | \(2n+4\) | \(\cdots\) | \(3n-3\) | \(3n-2\) |
| \(4n-2\) | \(4n-1\) | \(4n\) | \(3n+1\) | \(3n+2\) | \(3n+3\) | \(\cdots\) | \(4n-4\) | \(4n-3\) |
| \(5n-3\) | \(5n-2\) | \(2n-1\) | \(5n\) | \(4n+1\) | \(4n+2\) | \(\cdots\) | \(5n-5\) | \(5n-4\) |
| \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\ddots\) | \(\vdots\) | \(\vdots\) |
| \(n^2-2n+3\) | \(n^2-2n+4\) | \(n^2-2n+5\) | \(n^2-2n+6\) | \(n^2-2n+7\) | \(n^2-2n+8\) | \(\cdots\) | \(n^2-2n+1\) | \(n^2-2n+2\) |
| \(n^2-n+2\) | \(n^2-n+3\) | \(n^2-n+4\) | \(n^2-n+5\) | \(n^2-n+6\) | \(n^2-n+7\) | \(\cdots\) | \(n^2-n\) | \(n^2-n+1\) |
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:
| 1 | 2 | 3 | 4 |
| 8 | 5 | 6 | 7 |
| 11 | 12 | 9 | 10 |
| 14 | 15 | 16 | 13 |
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,
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.\)
Remark 1. None of the Tables 1, 2, 3, or 4 need start with 1. If we start with any natural number \(r,\) \(1\le r\le 9\) for Tables 1 and 2, \(1\le r\le n\) for Table 3, or \(1\le r\le 4\) for Table 4, all the above results (with obvious translations) would remain the same.
Remark 2. Here is a simpler generalization of the problem. Again, suppose \(n^2>1\) trees are to be divided among \(n\) inheritors, where tree \(k\) yields \(k\) units of produce per year. Let us start out by writing \(n\) mutual derangements of the first \(n\) integers as in the following table.
| 1 | 2 | 3 | 4 | \(\cdots\) | \(n\) |
| 2 | 3 | 4 | 5 | \(\cdots\) | 1 |
| 3 | 4 | 5 | 6 | \(\cdots\) | 2 |
| \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\ddots\) | \(\vdots\) |
| \(n\) | 1 | 2 | 3 | \(\cdots\) | \(n-1\) |
Table 5
Now, let us add \(0\) to all entries in row 1, \(n\) to all entries in row 2, \(2n\) to all entries in row 3, \(\dots,\) and \((n-1)n\) to all entries in row \(n.\) Each column of the new table so generated from Table 5 has the common sum \[[1+2+\cdots+n]+n[1+2+\cdots+(n-1)]=\frac{n(n^2+1)}{2},\] and the trees designated for inheritor \(j\) are the trees with labels in column \(j.\)
Remark 3. The generalized problem is equivalent to finding a solution of the following \(n\times n^2\) indeterminate system of equations with each variable a unique integer between 1 and \(n^2\):
| \(x_{11}+x_{12}+\cdots+x_{1n}\) | \(={\sigma}_n\) | |||
| \(x_{21}+x_{22}+\cdots+x_{2n}\) | \(={\sigma}_n\) | |||
| \(\ddots\) | \(\vdots\) | |||
| \(x_{n1}+x_{n2}+\cdots+x_{nn}\) | \(={\sigma}_n\) |
Exercise 1. Prove Proposition 1.
Exercise 2. Prove Corollary 1.
Exercise 3. Here is a variation a la Sudoku on Al-Maghribî’s puzzle proposed by Andrew Simoson of King College:
The landowner labeled his trees 1 to 81 according to their fruitfulness. On a sandy region of his orchard, he drew a 9 × 9 grid. After much trial and error he succeeded in entering all 81 integers into the grid so that the column sums were all the same. Thus, the first son would receive the trees labeled as in the first column, the second son the trees labeled as in the second column, and so on. As he was admiring his solution and before he could write it on some valuable paper, an infrequent rain rendered some cell numbers illegible. He recovered the first row easily enough. But what about the empty cells in the grid below. Can you help him recover his solution?
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 15 | 16 | 17 | ||||||
| 26 | 22 | |||||||
| 28 | 30 | 31 | ||||||
| 45 | 43 | 38 | 41 | |||||
| 47 | 48 | 51 | 49 | |||||
| 60 | 56 | 57 | 58 | |||||
| 71 | 68 | 69 | 64 | |||||
| 75 | 80 | 73 | 78 |
Is the solution unique?
Exercise 4. Use Latin squares to find all genuinely different solutions to Ibn Hamza’s problem in cases of \(n=2\) and \(n=3.\) Can you conjecture as to the number of genuinely different solutions for \(n=4\)?
Exercise 5. Show that not every solution of Ibn Hamza’s problem is generated by a Latin square in the case \(n=4.\)
Hint. Show that the following solution can never be generated by a Latin square.
| 1 | 2 | 3 | 4 |
| 9 | 5 | 6 | 7 |
| 10 | 11 | 12 | 8 |
| 14 | 16 | 13 | 15 |
Bammel, S. E. and Rothstein, J. (1975). The Number of 9 x 9 Latin Squares. In Discrete Mathematics 11, 93-95.
Dilgan, Hamit (1957). A la Mémoire de George Sarton: Sur Un Problème Indéterminé d'Ibni Hamza. In İstanbul Teknik Üniversitesi (ITÜ) Bülteni, Vol. X, No. 31-35.
Djebbar, A. (2003). A Panorama of Research on the History of Mathematics in al-Andalus and the Maghrib between the Ninth and Sixteenth Centuries. In Hogendijk, J. P.; Sabra, A. I. The Enterprise of Science in Islam: New Perspectives. Cambridge, Massachusetts: MIT Press.
The author wishes to extend his most profound thanks to the reviewer whose meticulously constructed critiques and thorough and rigorous corrections made this paper markedly better.
Ilhan Izmirli studied mathematics at Bosphorus University, Istanbul. After completing his M.Sc. at University of Istanbul, he conducted further graduate studies at the University of South Carolina, Columbia, S.C. He earned his Ph.D. at The American University, Washington, D.C.
His major research interests are mathematics education; statistics education; history of statistics; history of mathematics; relations between mathematics and other disciplines, such as physics, philosophy, and music; and chaos theory. He has presented numerous papers on these and related topics at international conferences throughout the world.
When he is not teaching his classes at GMU or conducting his research, he can be found taking long walks with his dogs or playing music with the Washington Balalaika Society and the folk music ensemble, Samovar.
For more information please see his webpage at http://statistics.gmu.edu/people_pages/Izmirli/