Problem1E

Problem1E: Let ${A_{1},\ldots ,A_{n}}$ be ${n}$ distinct subsets of the ${n}$ -set ${N:=\left\{ 1,\ldots ,n\right\} .}$ Show that there is an element ${x\in N}$ such that the sets ${A_{i}\backslash \left\{ x\right\} ,\ 1\leq i\leq n,}$ are all distinct.

Solution1: The problem can be reformulated as follows: Show that a column can be deleted from a ${n}$ by ${n}$ matrix over ${\mathbb{F}_{2}}$ having pairwise distinct rows, such that the rows are still pairwise distinct. We prove it by induction. It is not difficult to show that the statement is true for ${n=2.}$ Suppose it is true for ${n=k.}$ Note that this implies that the statement is also true for an ${l}$ by ${k}$ matrix ( ${1\leq l\leq k}$ ) having pairwise distinct rows. For a ${k+1}$ by ${k+1}$ matrix, omit the last column, if the rows are pairwise distinct for the remaining ${k+1}$ by ${k}$ matrix, just delete the last row. Otherwise, suppose there are ${2m}$ rows ${(m\geq 1)}$ are pairwise same. Without affecting deleting a column, we can delete ${m}$ rows, one from each pair of rows. Hence now the remaining is a ${l}$ by ${k}$ matrix ( ${l\leq k}$ ), with rows pairwise distinct, by assumption, a column can be deleted. The induction completes.

Solution2: Form a graph ${G}$ on the vertices ${A_{i}}$ with an edge with ‘color’ ${x}$ between ${A_{i}}$ and ${A_{j}}$ iff the symmetric difference of the sets ${A_{i}}$ and ${A_{j}}$ is ${\left\{ x\right\} .}$ The task is to show the existence of ${y\in }$ ${N}$ such that there is no edge with color ${y.}$ If it does, ${y}$ can be deleted, and ${A_{i}\backslash \left\{ y\right\} }$ are still all distinct. Since two vertices are adjacent iff the symmetric difference is a 1-element-set, a polygon in the graph must have even length and each color also appears even number of times. Delete an edge if there is another edge with the same color, then the number of colors remain the same, and no polygon is left. Since the graph is simple without polygons as subgraphs, and not necessarily connected, by Problem 1C, the number of edges is at most ${n-1.}$ So the number of different colors is at most ${n-1,}$ which implies that at least one color, say ${y,}$ is not included in the graph, and then we can delete ${y}$ .