The Latin Square (Tuklas Vol. 17, No. 3 - October 3, 2015)

THE LATIN SQUARE

Try filling the table above with numbers from the set \(\{1,2,3\}\) such that no row or column contains the same number. If you have played Sudoku, you might be familiar with solving puzzles like this. These square puzzles, called Latin squares, have been around for a long time, even predating the game of Sudoku.

What is a Latin square? A Latin square of order \(n\) is an \(n\times n\) array of \(n\) symbols such that each symbol appears exactly once in each row and once in each column. If you were able to solve the above square, the result is a Latin square of order \(3\). Here are some examples of Latin squares:

D	A	C	B
B	C	A	D
C	D	B	A
A	B	D	C

D

A

C

B

B

C

A

D

C

D

B

A

A

B

D

C

,   

1	2	3	4	5	6
2	1	4	3	6	5
3	5	1	6	2	4
4	6	2	5	3	1
5	4	6	2	1	3
6	3	5	1	4	2

1

2

3

4

5

6

2

1

4

3

6

5

3

5

1

6

2

4

4

6

2

5

3

1

5

4

6

2

1

3

6

3

5

1

4

2

Figure 1: Latin squares of order 4 and 6.

Why is it called a “Latin” square? Though Latin squares had already existed for centuries, it was Leonhard Euler who formally introduced and developed the concept in 1783 in his mathematical paper entitled "nouveau espece de carres magiques". He used Latin characters as symbols, hence the term Latin square. Of course nowadays, one can use any other symbol to form a Latin square and not just Latin characters.

One of the most interesting problems involving a Latin square is the search for its orthogonal mate. It was again Euler who developed the definition of orthogonal Latin squares. Two Latin squares are said to be orthogonal if when superimposed (joined together), the ordered pairs in the resulting array are all distinct. When two Latin squares are orthogonal to each other, we call them orthogonal mates. Figure 2 shows two orthogonal Latin squares and their join. Notice that the elements of their join are all distinct.

\(A=\)

1	2	3	4
2	1	4	3
3	4	1	2
4	3	2	1

1

2

3

4

2

1

4

3

3

4

1

2

4

3

2

1

, \(B=\)

1	2	3	4
4	3	2	1
2	1	4	3
3	4	1	2

1

2

3

4

4

3

2

1

2

1

4

3

3

4

1

2

 

\((A,B) =\)

(1,1)	(2,2)	(3,3)	(4,4)
(2,4)	(1,3)	(4,2)	(3,1)
(3,2)	(4,1)	(1,4)	(2,3)
(4,3)	(3,4)	(2,1)	(1,2)

(1,1)

(2,2)

(3,3)

(4,4)

(2,4)

(1,3)

(4,2)

(3,1)

(3,2)

(4,1)

(1,4)

(2,3)

(4,3)

(3,4)

(2,1)

(1,2)

Figure 2: 2 orthogonal Latin squares, denoted by A and B, alongside their join.

A classic problem that involves orthogonal Latin squares is the problem posted by Euler involving 36 officers from six ranks and six regiments. He claimed that it was impossible to arrange six regiments, each with six ranks (a colonel, a lieutenant-colonel, a major, a captain, a lieutenant, and a sub-lieutenant) in a \(6 \times 6\) array such that no row or column duplicates a rank or a regiment. Thus, a Latin square of order \(6\) does not have an orthogonal mate. Notice also that a Latin square of order \(2\) does not have an orthogonal mate either (see Figure 3).

A	B
B	A

A

B

B

A

,   

B	A
A	B

B

A

A

B

Figure 3: The two Latin squares of order 2.

With this, Euler conjectured that no orthogonal Latin squares of order \(6\) exist, nor does one exist whenever \(n \equiv 2 \mod 4\). This remained as a conjecture for more than 100 years until 1960 when Bose, Shrikhande and Parker disproved it.

A Latin square has so many important characteristics and it has many applications in science, engineering, statistics and most importantly, in mathematics. In abstract algebra, Cayley tables of quasigroups and the addition table of integers modulo \(n\) form a Latin square. In statistics, the Latin square design is used to control (or eliminate) two sources of the variation in an experiment. In coding theory, a pair of orthogonal Latin squares is used to design new techniques for what we call error correcting codes. In games, Sudoku puzzles and magic square puzzles are just two of most famous games that is related to Latin squares.

There are still so many things to discover about Latin squares - from construction, existence of orthogonal mate, up to the discovery of new applications. For instance, if we define a transversal of a Latin square as a set of entries which includes exactly one entry from each row and column and one of each symbol, one may try to solve this conjecture: Every Latin square of odd order has a transversal. Enjoy!

ABOUT THE AUTHOR:
Pejie Santillan is a graduate assistant at the Ateneo de Manila University. He is currently taking his Master's degree at the same university.

REFERENCES:

- Colbourn, C. J. and J. H. Dinitz (eds). The CRC Handbook of Combinatorial Designs, CRC Press, Boca Raton (1996).
- Arshaduzzaman, Md. "Connections between Latin Squares and Geometries." IOSR Journal of Mathematics, Vol. 9, Issue 5 (Jan 2014). Retrieved from http://iosrjournals.org/iosr-jm/papers/Vol9-issue5/C0951419.pdf.
- Waheed, Ali Makki Sagheer Makarim. Error-Correcting Code using Latin Square, Abdul-Jabbar. College of Computer, University of Anbar.

OLYMPIAD CORNER

from the Italian Mathematical Olympiad, 2014

Problem:  Prove that there exists a positive integer that can be written as a sum of \(2015\) distinct \(2014\)th powers of positive integers \( x_{1} < x_{2} < \cdots < x_{2015}\) in at least two ways.

Solution: 

Let \(N\) be a positive integer greater than or equal to \(2015\). The total number of increasing sequences \(x_{1} < x_{2} < \cdots < x_{2015}\) such that all the terms are less than or equal to \(N\) is given by \(\binom{N}{2015}\). For each of these sequences, we find the sum \(x_{1}^{2014}+x_{2}^{2014}+\cdots+x_{2015}^{2014}\). Since \(x_{i}^{2014}\leq N^{2014}\) for any \(i=1,2,...,2015\), it follows that the sum will be at most \(2015N^{2014}\). Therefore we have \(\binom{N}{2015}\) sums, and each sum is less than or equal to \(2015N^{2014}\).

We claim that \(\binom{N}{2015} > 2015N^{2014}\) for some \(N\). Note that \[ \binom{N}{2015}=\frac{N\left( N-1\right) \left( N-2\right) \cdots \left(N-2014\right) }{2015!} \]Also consider\[ P\left( N\right) =\frac{N\left( N-1\right) \left( N-2\right) \cdots \left(N-2014\right) }{2015!}-2015N^{2014} \]Since \(P\left( N\right)\) is a \(2015\)th degree polynomial with a positive leading coefficient, its graph will just conitinue to move up as \(N\) goes to infinity. This means there exists an \(N\) large enough so that \(P\left(N\right) > 0\Rightarrow \binom{N}{2015} > 2015N^{2014}\).

Since there are more sums compared to the possible values for the sum, then by the pigeonhole principle, there exists at least two sums that have the same value.

PROBLEMS

10. Find all values of \(x\), \(y\), and \(z\) such that \(x^4+y^4+z^4-4xyz=-1\).
11. Find the number of ways to color \(2015\) points on a circle with \(3\) colors such that any two neighboring points have distinct colors.
12. Determine the minimum value of \(\dfrac{a+b+c}{b-a}\) given that for all \(x\), \(ax^2+bx+c\geq 0\) and \(a < b\).

We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions may ONLY be submitted online via vantonio1992@gmail.com. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is 12:30 PM October 10, 2015.

SOLUTIONS

(for September 26, 2015)

7. Let \(ABCD\) be a rhombus with \(\angle A=120^{\circ}\) and \(P\) is any point on the plane of the rhombus. Prove that \[ PA+PC >\frac{BD}{2}. \](Taken from Mathematical Olympiad Challenges (2nd Edition) by Andreescu and Gelca)
   (solved by Jarrett Ian G. Lim [Philippine Academy of Sakya], Carissa Elaine Varon [Falcon School], and Steven Reyes [Saint Jude Catholic School]; partial credit for Joyce Heidi Ong [Chiang Kai Shek College], Madeline L. Tee [Chiang Kai Shek College], and Trisha T. Huang [Chiang Kai Shek College])
   
   
   SOLUTION: 
   First we prove that given an equilateral triangle \(XYZ\) and a point \(P\) not on the circumcircle of this triangle, then we can construct a triangle with side lengths \(PX\), \(PY\), and \(PZ\). Moreover, if \(P\) lies on the circumcircle, then one of the three lengths is equal to the other two. This is known as Pompeiu's Theorem.
   
   We rotate \(\triangle XYZ\) \(60^{\circ}\) clockwise around \(X\). As seen in the figure below, \(Y\) will rotate to \(Z\), while \(Z'\) and \(P'\) are images of \(Z\) and \(P\), respectively.
   
   

   

   
   Note that \(P'Z\) is the image of \(PY\). In addition, because of the rotation, \(PP'X\) is an equilateral triangle, so \(PP'\) is actually equal to \(PX\). This means that we have \(\triangle PP'Z\) as our desired triangle.
   
   If, on the other hand, \(P\) is on the circumcircle, then we have the following figure.
   
   

   

   
   Note that if \(P\) is on arc \(XZ\), then \(\angle ZPX\) is \(120^{\circ}\). Because \(\triangle PP'X\) is equilateral, then \(\angle XPP'=60^{\circ}\), which means that \(\angle ZPX\) and \(\angle XPP'\) form a linear pair, so \(Z\), \(P\), and \(P'\) are collinear.
   
   If \(P\) is on arc \(XYZ\), then \(\angle ZPX=60^{\circ}\), and \(\angle P'PX\) is also \(60^{\circ}\) because \(\triangle P'PX\) is equilateral. This means that \(Z\), \(P\), and \(P'\) are collinear.
   
   This means that if \(P\) is on arc \(XZ\), then \[ \begin{align} ZP' & = ZP+PP'\\ YP & = ZP+XP. \end{align} \]If \(P\) is on arc \(XY\), then \[ \begin{align} ZP & = ZP'+P'P\\ ZP & = YP+XP. \end{align} \]And finally, if \(P\) is on arc \(YZ\), then \[ \begin{align} PP' & = PZ+ZP'\\ XP & = ZP+YP. \end{align} \]Now we go to the problem. Since \(\angle A=120^{\circ}\), then \(\angle B\) must be \(60^{\circ}\). This means that \(\triangle ABC\) is isosceles with vertex angle \(60^{\circ}\), which implies that \(\triangle ABC\) is equilateral.
   
   If \(P\) is not on the circumcircle of \(\triangle ABC\), then a triangle exists with sides \(PA\), \(PB\), and \(PC\). This means that, by triangle inequality, \(PA+PC > PB\). On the other hand, if \(P\) is on the circumcircle of \(\triangle ABC\), then \(PA+PC=PB\). In general, we have \(PA+PC\ge PB\).
   
   Similarly, since \(\triangle ACD\) is also equilateral, we can have \(PA+PC\geq PD\). Combining the two inequalities, we have \[ 2\left(PA+PC\right)\geq PB+PD. \]Considering \(\triangle PBD\), \(PB+PD > BD\). This means that \[ \begin{align} 2\left(PA+PC\right) & > BD\\ PA+PC & > \frac{BD}{2}. \end{align} \]
   
   
8. Determine, with proof, the values of \(a\), \(b\), and \(c\), with \(a < b < c\) such that \(2015=a^{2}+b^{2}-c^{2}\). (Modified problem from 104 Number Theory Problems by Andreescu, Andrica, and Zuming)
   (solved by Jarrett Ian G. Lim [Philippine Academy of Sakya], Steven Reyes [Saint Jude Catholic School]; partial credit for Joyce Heidi Ong [Chiang Kai Shek College], Ryan Jericho Sy [Chiang Kai Shek College], and Madeline L. Tee [Chiang Kai Shek College])
   
   
   SOLUTION: 
   We prove this for a general value of \(n\) and divide the solution into cases depending on the parity of \(n\).
   
   If \(n\) is even, then \(n=2k\) for some \(k\). Note that if \(n=0\), then we have\[ \begin{align} 0 & = a^{2}+b^{2}-c^{2}\\ c^{2} & = a^{2}+b^{2}, \end{align} \]which means any Pythagorean Triple will hold. On the other hand, if \(n=2\), then\[ 2=5^{2}+11^{2}-12^{2}. \]Now, if \(n\geq4\), that is, if \(k > 1\), then\[ 5k-1 > 4k-1 \]and\[ \begin{align} 1 & < k\\ 3k+1 & < 4k\\ 3k & < 4k-1. \end{align} \]So now we have candidates \(a=3k\), \(b=4k-1\), and \(c=5k-1\). It can be verified that\[ \begin{align} \left(3k\right)^{2}+\left(4k-1\right)^{2}-\left(5k-1\right)^{2} & = 2k\\ & = n. \end{align} \]Now we consider the case when \(n\) is odd, then it can be written in the form \(n=2k+1\). First, if \(n=1\), then\[ \begin{align} 1 & = 4^{2}+7^{2}-8^{2}\\ 3 & = 4^{2}+6^{2}-7^{2}\\ 5 & = 4^{2}+5^{2}-6^{2}\\ 7 & = 6^{2}+14^{2}-15^{2}. \end{align} \]Now, if \(k > 3\) (that is, \(n > 7\)), then, first,\(5k-4 > 4k-4\). In addition,\[ \begin{align} k & > 3\\ 4k & > 3k+3\\ 4k-4 & > 3k-1. \end{align} \]This means that our candidates are \(a=3k-1\), \(b=4k-4\), and \(c=5k-4\). It can be verified that\[ \begin{align} \left(3k-1\right)^{2}+\left(4k-4\right)^{2}-\left(5k-4\right)^{2} & = 2k+1\\ & = n. \end{align} \]In that case, if \(n=2015=2\left(1007\right)+1\), then we just have \(a=3020\), \(b=4024\), and \(c=5031\).
9. Consider \(2015\) nonnegative real numbers \(a_{1},a_{2},\dots,a_{2015}\) whose sum is \(1\). Define \(M\) to be \[ M=\max_{1\leq k\leq}a_{k}+a_{k+1}+a_{k+2}. \]As \(a_{k}\) varies, \(M\) varies as well. Find the minimum value of \(M\). (Canadian Mathematical Olympiad, 1981)
   (partial credit for Jarrett Ian G. Lim [Philippine Academy of Sakya], Joyce Heidi Ong [Chiang Kai Shek College], and Madeline L. Tee [Chiang Kai Shek College])
   
   
   SOLUTION: 
   Since all the numbers are nonnegative, then \(a_{1}\leq a_{1}+a_{2}\leq a_{1}+a_{2}+a_{3}\) and \(a_{7}\leq a_{6}+a_{7}\leq a_{5}+a_{6}+a_{7}\). This means that\[ \begin{align*} M & = \max_{1\leq k\leq2009}a_{k}+a_{k+1}+a_{k+2}.\\ & = \max_{1\leq k\leq2009}\left\{ a_{1},a_{1}+a_{2},a_{7},a_{6}+a_{7},a_{k}+a_{k+1}+a_{k+2}\right\} . \end{align*} \]If we add all the 2013 quantities, we have\[ \begin{align*} \text{sum} & = a_{1}+\\ & \left(a_{1}+a_{2}\right)+\\ & \left(a_{1}+a_{2}+a_{3}\right)+\\ & \left(\hphantom{a_{1}+}a_{2}+a_{3}+a_{4}\right)+\\ & \vdots\\ & \left(a_{2009}+a_{2010}+a_{2011}\right)+\\ & \left(\hphantom{a_{2009}+}a_{2010}+a_{2011}\right)+\\ & \left(\hphantom{a_{2009}+a_{2010}+}a_{2011}\right)\\ & = 3\left(a_{1}+a_{2}+\cdots+a_{2011}\right)\\ & = 3. \end{align*} \]We then take the average of these 2013 quantities, and we get \(\dfrac{3}{2013}=\dfrac{1}{671}\). If all the quantities are less than \(\dfrac{1}{671}\), then the average should be less than \(\dfrac{1}{671}\). This means that at least one quantitity should be greater than or equal to \(\dfrac{1}{671}\). This implies that \(M\geq\dfrac{1}{671}\). This means that the minimum value for \(M\) is \(\dfrac{1}{671}\). Specifically, this can be achieved by letting \(a_{k}=\dfrac{1}{671}\) if \(k\equiv1\mod3\), and \(a_{k}=0\) otherwise.

ERRATA

Madeline L. Tee [Chang Kai Shek College] and Carissa Elaine Varon [Falcon School] were not properly recognized for their solutions to the questions from the previous weeks. The previous issues have been updated to rectify this error.