|Arrange the pieces so that every row and column contain one piece of each shape (or colour).|
|Arrange the pieces so that every row and column contain one piece of each shape and one piece of each colour.|
|How many solutions are possible? What about grids of other sizes?|
A 4×4 grid with a piece of each colour in every row and column is called a Latin Square. If we also have a piece of each shape in every row and column, so that every combination appears exactly once, it is called a Graeco-Latin Square. There are many possible solutions, but all solutions have the same structure. Graeco-Latin squares are also possible for 3×3 grids and 5×5 grids, but impossible for 2×2 and 6×6 grids. Graeco-Latin Squares are possible for all sizes greater than 6.
Latin Squares go back thousands of years. However, the first person to study Graeco-Latin squares was Leonard Euler in the 1780s. Euler was able to find squares of various sizes, but could not find a grid of size 6, and he believed a Graeco-Latin Square of size 6 was impossible. Euler believed Graeco-Latin Squares of size 10, 14, 18, and so on, were also impossible.
In 1901, a French mathematician called Gaston Tarry proved a Graeco-Latin Square of size 6 was impossible by checking all 9408 possibilities! (Along with a general proof).
Finally, in 1959, Indian mathematicians Raj Bose and Sharadchandra Shrikhande with American mathematician Ernest Parker proved that all other sizes of Graeco-Latin Squares were possible, so only size 2 and 6 are impossible
Graeco-Latin Squares have many surprising applications in many different areas of maths. For example, when sending messages on the internet mistakes can occur in transmission, which can then be fixed by your computer. Some of these error-correcting codes use Graeco-Latin Squares.
Graeco-Latin Squares are also used when designing tournaments, so that each player plays each match against a different opponent and in a different location.
Graeco-Latin Squares are used when designing experiments, so that the items in the experiment are all tested in different locations, in different combinations, so that they can be fairly compared.
Maths at Home
Take all the Jacks, Queens, Kings and Aces from a pack of cards, and arrange them into a 4×4 grid so that each row and column (and optionally, the two diagonals) contain one card of each type, and one card of each suit. How many solutions can you find?