# 4.E: Systems of Distinct Representatives (Exercises)

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

## 4.2: Existence of SDRs

##### Exercise $$\PageIndex{2.1}$$

How many different systems of distinct representatives are there for $$A_1=\{1,2\}$$, $$A_2=\{2,3\}$$, …, $$A_n=\{n,1\}$$?

##### Exercise $$\PageIndex{2.2}$$

How many different systems of distinct representatives are there for the sets $$A_i=[n]\backslash{i}$$, $$i=1,2,\ldots,n$$, $$n\ge2$$?

##### Exercise $$\PageIndex{2.3}$$

Suppose the set system $$A_1,A_2,\ldots,A_n$$ has an sdr, and that $$x\in A_i$$. Show the set system has an sdr containing $$x$$. Show that $$x$$ cannot necessarily be chosen to represent $$A_i$$.

##### Exercise $$\PageIndex{2.4}$$

Suppose the set system $$A_1,A_2,\ldots,A_n$$ satisfies $$|\bigcup_{j=1}^k A_{i_j}|\ge k+1$$ for every $$1\le k< n$$ and $$\{i_1,i_2,\ldots,i_k\}\subseteq [n]$$, and that $$x\in A_i$$. Show the set system has an sdr in which $$x$$ represents $$A_i$$.

##### Exercise $$\PageIndex{2.5}$$

An $$m\times n$$ chessboard, with $$m$$ even and both $$m$$ and $$n$$ at least 2, has one white and one black square removed. Show that the board can be covered by dominoes.

## 4.3: Partial SDRs

##### Exercise $$\PageIndex{3.1}$$

Find the size of a maximum sdr for $A_1=\{a,b,c\}, A_2=\{a,b,c,d,e\}, A_3=\{a,b\}, A_4=\{b,c\}, A_5=\{a\}, A_6=\{a,c,e\}.\nonumber$ Justify your answer.

## 4.4: Latin Squares

##### Exercise $$\PageIndex{4.1}$$

Show that there is only one reduced Latin square of order 3.

##### Exercise $$\PageIndex{4.2}$$

Verify that the isotopy relation is an equivalence relation.

##### Exercise $$\PageIndex{4.3}$$

Find all 4 reduced Latin squares of order 4. Show that there are at most 2 isotopy classes for order 4.

##### Exercise $$\PageIndex{4.4}$$

Show that the second set system defined in Example 4.4.5 has an sdr as claimed.

##### Exercise $$\PageIndex{4.5}$$

Show that there are no orthogonal Latin squares of order 2.

##### Exercise $$\PageIndex{4.6}$$

Find the two orthogonal Latin squares of order $$5$$ as described in Theorem 4.4.1. Show your answer as in Example 4.4.6.

##### Exercise $$\PageIndex{4.7}$$

Prove that to construct orthogonal Latin squares of order $$2^m$$, $$m\ge2$$, it suffices to find two orthogonal Latin squares of order $$4=2^2$$ and two of order $$8=2^3$$.

##### Exercise $$\PageIndex{4.8}$$

An $$n\times n$$ Latin square $$A$$ is symmetric if it is symmetric around the main diagonal, that is, $$A_{i,j}=A_{j,i}$$ for all $$i$$ and $$j$$. It is easy to find symmetric Latin squares: every addition table modulo $$n$$ is an example, as in Example 4.4.4. A Latin square is idempotent if every symbol appears on the main diagonal. Show that if $$A$$ is both symmetric and idempotent, then $$n$$ is odd. Find a $$5\times 5$$ symmetric, idempotent Latin square.

##### Exercise $$\PageIndex{4.9}$$

The transpose $$A^\top$$ of a Latin square $$A$$ is the reflection of $$A$$ across the main diagonal, so that $$A_{i,j}^\top=A_{j,i}$$. A Latin square is self-orthogonal if $$A$$ is orthogonal to $$A^\top$$. Show that there is no self-orthogonal Latin square of order 3. Find one of order 4.

## 4.6: Matchings

##### Exercise $$\PageIndex{5.1}$$

In this bipartite graph, find a maximum matching and a minimum vertex cover using the algorithm of this section. Start with the matching shown in red. Copies of this graph are available in this pdf file.

##### Exercise $$\PageIndex{5.2}$$

Show directly that that the size of a minimum vertex cover in $$G$$ is the minimum value of $$n-k+|\bigcup_{j=1}^k A_{i_j}|$$, as mentioned above.

This page titled 4.E: Systems of Distinct Representatives (Exercises) is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by David Guichard via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.