Combinatorics

16.1.3.1 Proof. Let \(\displaystyle L\) be an \(\displaystyle n \times n\) Latin square whose entries come from a set \(\displaystyle N\) of cardinality \(\displaystyle n\text{,}\) and let \(\displaystyle L'\) be the result of exchanging row \(\displaystyle i\) with row \(\displaystyle j\text{.}\)

Let \(\displaystyle k \in \{1, \ldots, n\}\) be arbitrary, and consider column \(\displaystyle k\) of \(\displaystyle L'\text{.}\) Its entries are exactly the same as the entries of column \(\displaystyle k\) of \(\displaystyle L\text{,}\) except that the \(\displaystyle i\)th entry has been exchanged with the \(\displaystyle j\)th entry. Since every element of \(\displaystyle N\) appears exactly once in column \(\displaystyle k\) of \(\displaystyle L\text{,}\) it also appears exactly once in column \(\displaystyle k\) of \(\displaystyle L'\) (although possibly in a different position). Since \(\displaystyle k\) was arbitrary, every element of \(\displaystyle N\) appears exactly once in each column of \(\displaystyle L'\text{.}\)

Now consider row \(\displaystyle k\) of \(\displaystyle L'\text{.}\) If \(\displaystyle k \neq i,j\text{,}\) then this row is exactly the same as row \(\displaystyle k\) of \(\displaystyle L\text{.}\) Since every element of \(\displaystyle N\) appears exactly once in row \(\displaystyle k\) of \(\displaystyle L\text{,}\) it also appears exactly once (and in the same position even) in row \(\displaystyle k\) of \(\displaystyle L'\text{.}\) If \(\displaystyle k=i\) or \(\displaystyle k=j\text{,}\) then row \(\displaystyle k\) of \(\displaystyle L'\) is the same as some other row (the \(\displaystyle j\)th or \(\displaystyle i\)th row, respectively) of \(\displaystyle L\text{.}\) Since every element of \(\displaystyle N\) appears exactly once in that row of \(\displaystyle L\text{,}\) it also appears exactly once in row \(\displaystyle k\) of \(\displaystyle L'\text{.}\)

Thus, \(\displaystyle L'\) satisfies the definition of a Latin square. ◾

16.1.3.2 There are three different ways to complete the square:So the completion is not unique.

16.2.9.2 As explained in the first paragraph of the proof of Theorem 16.2.4, we may assume the first row is \(\displaystyle 1,2,3,4\text{.}\)

Now, we use the idea that is explained in the second paragraph of the proof of Theorem 16.2.4. For any position in a row after the first row, the entry in our new Latin square cannot be the same as the entry in this position of either of the two given squares (because, for any \(\displaystyle j\text{,}\) the ordered pair \(\displaystyle (j,j)\) has already appeared in the top row of the given square and our new square), and it also cannot be the same as the entry in the first row of the column. This eliminates three possibilities for the entry in this position, so there is only one possibility left. Putting this remaining entry into each position yields the following Latin square, which must be the one that was requested:

16.3.6.2 This collection has no system of distinct representatives, because the five sets \(\displaystyle A_2\text{,}\) \(\displaystyle A_3\text{,}\) \(\displaystyle A_4\text{,}\) \(\displaystyle A_5\text{,}\) and \(\displaystyle A_6\) have union \(\displaystyle A_2 \cup A_3 \cup A_4\cup A_5 \cup A_6=\{v,w,x,y\}\text{,}\) which has cardinality \(\displaystyle 4\text{.}\)

16.3.6.4 This collection does have a system of distinct representatives: \(\displaystyle x\text{,}\) \(\displaystyle y\text{,}\) and \(\displaystyle z\text{,}\) for \(\displaystyle A_1\text{,}\) \(\displaystyle A_2\text{,}\) and \(\displaystyle A_3\) (respectively).

16.3.12.1 Adam, Ella, Justin, and Bryant are the only friends that have visited either England, Scotland, Ireland, France, or Italy. Therefore, Onyx has only 4 friends to choose from to answer the questions for these 5 countries. Since the number of friends is less than the number of countries, Onyx cannot choose a different friend for each of these countries.

16.3.12.2 No, this cannot be completed to a \(\displaystyle 4\times 4\) Latin square:

• The third entry in the third row must be \(\displaystyle 1\text{,}\) because \(\displaystyle 2\text{,}\) \(\displaystyle 3\text{,}\) and \(\displaystyle 4\) already appear in either the third row or the third column.

• The last entry in the third row must also be \(\displaystyle 1\text{,}\) because \(\displaystyle 2\text{,}\) \(\displaystyle 3\text{,}\) and \(\displaystyle 4\) already appear in either the third row or the last column.

So we cannot complete the third row: we are forced to have \(\displaystyle 1\) appear twice in this row, but that is not allowed.

Hall's Theorem does not apply to this situation, because, as we have seen, the third column and fourth column must both choose their entry for the third row from the set \(\displaystyle \{1\}\text{,}\) which has less than two elements. (Theorem 16.3.8 does not apply because the partial Latin square does not consist only of complete rows — it has a row that has only been partially filled in.)