Math 116: Final Exam Study Guide Chapter 6

Chapter 6: Latin Squares and SDRs
Exercise 1 Consider the following incomplete Latin square:

    \[\begin{array}{|c|c|c|c|c|} \hline 2 & 3 & 5 & 4 & 1 \\ \hline 1 & 2 & 3 & 5 & 4 \\ \hline \text{?} & \text{?} & \text{?} & 3 & 5 \\ \hline \text{?} & \text{?} & \text{?} & \text{?} & \text{?} \\ \hline \text{?} & \text{?} & \text{?} & \text{?} & \text{?} \\ \hline \end{array}\]

Complete the Latin square.
 Possible Solution:

    \[\begin{array}{|c|c|c|c|c|} \hline 2 & 3 & 5 & 4 & 1 \\ \hline 1 & 2 & 3 & 5 & 4 \\ \hline 4 & 1 & 2 & 3 & 5 \\ \hline 5 & 4 & 1 & 2 & 3 \\ \hline 3 & 5 & 4 & 1 & 2 \\ \hline \end{array}\]

Exercise 2 How many 4\times 4 Latin squares begin as:

    \[\begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \\ \hline 2 & 1 & 4 & 3 \\ \hline \text{?} & \text{?} & \text{?} & \text{?} \\ \hline \text{?} & \text{?} & \text{?} & \text{?} \\ \hline \end{array}\]

 There are four solutions:

    \[\begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \\ \hline 2 & 1 & 4 & 3 \\ \hline 3 & 4 & 1 & 2 \\ \hline 4 & 3 & 2 & 1 \\ \hline \end{array}\]

    \[\begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \\ \hline 2 & 1 & 4 & 3 \\ \hline 4 & 3 & 1 & 2 \\ \hline 3 & 4 & 2 & 1 \\ \hline \end{array}\]

    \[\begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \\ \hline 2 & 1 & 4 & 3 \\ \hline 3 & 4 & 2 & 1 \\ \hline 4 & 3 & 1 & 2 \\ \hline \end{array}\]

    \[\begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \\ \hline 2 & 1 & 4 & 3 \\ \hline 4 & 3 & 2 & 1 \\ \hline 3 & 4 & 1 & 2 \\ \hline \end{array}\]

Exercise 3 How many 4\times 4 Latin squares begin as:

    \[\begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \\ \hline 4 & 1 & 2 & 3 \\ \hline \text{?} & \text{?} & \text{?} & \text{?} \\ \hline \text{?} & \text{?} & \text{?} & \text{?} \\ \hline \end{array}\]

 There are two solutions:

    \[\begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \\ \hline 4 & 1 & 2 & 3 \\ \hline 3 & 4 & 1 & 2 \\ \hline 2 & 3 & 4 & 1 \\ \hline \end{array}\]

    \[\begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \\ \hline 4 & 1 & 2 & 3 \\ \hline 2 & 3 & 4 & 1 \\ \hline 3 & 4 & 1 & 2 \\ \hline \end{array}\]

Exercise 4 If there are 3 boys and 3 girls, how many ways can we arrange a sequence of three dances so that each boy and girl dance together exactly once? This is the number of 3\times 3 Latin squares, which is 12.
Exercise 5 How many possible first rows are there for a 5 \times 5 Latin square? This is the number of permutations of five letters (as there is no constraints the order in which they can be placed), i.e. 120 possible first rows.
Exercise 6 How many possible second rows are there for a 5 \times 5 Latin square for a given fixed first row? We can think of the first row as: 1 \; 2\;3\;4\;5. And, we want to permute these numbers such that no position is fixed. Permutations satisfying this condition are derangements. Apply the formula for derangements:

    \[d(5)=5!\left(\sum_{i=0}^5 \frac{(-1)^i}{i!}\right)=44\]

Therefore, there are 44 possible second rows for any given fixed first row.
Exercise 7 Find a system of distinct representatives for the family of finite sets given below. If it is not possible, state it.

    \begin{align*} A_1&=\{a,b,c\} & A_2 &= \{a,c\} \\ A_3 &= \{a,b,d\} & A_4 & \{c,d\} \end{align*}

 Possible Solution: (a,c,b,d).
Exercise 8 Find a system of distinct representatives for the family of finite sets given below. If it is not possible, state it.

    \begin{align*} A_1&=\{a,b\} & A_2 &= \{a,c\} \\ A_3 &= \{bc\} & A_4 & \{a,b,c\} \end{align*}

 No solution.
Exercise 9 Find all systems of distinct representatives for the family of finite sets given below.

    \begin{align*} A_1&=\{a,b,c\} & A_2 &= \{a,b\} \\ A_3 &= \{b,c\} \end{align*}

 Solutions:
(a,b,c)
(b,a,c)
(c,a,b)