**Problem1E: Let **** be **** distinct subsets of the ****-set ** ** Show that there is an element **** such that the sets **** are all distinct.**

**Solution1:** The problem can be reformulated as follows: Show that a column can be deleted from a by matrix over 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 Suppose it is true for Note that this implies that the statement is also true for an by matrix () having pairwise distinct rows. For a by matrix, omit the last column, if the rows are pairwise distinct for the remaining by matrix, just delete the last row. Otherwise, suppose there are rows are pairwise same. Without affecting deleting a column, we can delete rows, one from each pair of rows. Hence now the remaining is a by matrix (), with rows pairwise distinct, by assumption, a column can be deleted. The induction completes.

**Solution2: **Form a graph on the vertices with an edge with ‘color’ between and iff the symmetric difference of the sets and is The task is to show the existence of such that there is no edge with color If it does, can be deleted, and 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 So the number of different colors is at most which implies that at least one color, say is not included in the graph, and then we can delete .