On Completing Latin Rectangles

Lindner, Charles C.

Canadian mathematical bulletin, Tome 13 (1970) no. 1, pp. 65-68

Résumé

By an (incomplete) r × s latin rectangle is meant an r × s array such that (in some subset of the rs cells of the array) each of the cells is occupied by an integer from the set 1, 2, ..., s and such that no integer from the set 1,2, ..., s occurs in any row or column more than once. This definition requires that r≦s. If r=s we will replace the word rectangle by square. It is easy to see that for any n≧2 there is an incomplete n × 2n latin rectangle with 2n cells occupied which cannot be completed to a n × 2n latin rectangle. In this paper we prove the following theorem.Theorem 1. An incomplete n × 2n latin rectangle with 2n—1 cells occupied can be completed to a n × 2n latin rectangle.

Détail

DOI : 10.4153/CMB-1970-013-x