- #1
talolard
- 125
- 0
Homework Statement
My professor has 50 questions. In the beginning of the semester he makes 10 work sheets each with 5 questions. At the end of the semester, he makes 10 new worksheets from the same quetions, this tiem sorted by difficulty.
Prove that there exists a subset of 10 question in which each question apeared exactly once in one of the original worksheets and in one of the new worksheets
Homework Equations
The Attempt at a Solution
The question is isomorphic to taking 50 different balls, labeling 5 with the number 1, labeling 5 with the number 2 etc until 10, and then repeating the process with a different colored pen.
We have created 50 unique ordered pairs. We can create a 10 by 10 matrix and label 1 in the i,jth place if that ordered pair exists in our collection and 0 if it does not. Then we have a 10 by 10 binary matrix.
We can notice that if the determinant of the matrix is non 0 then there exists some sub-group of the 50 balls that has two appearances of each of the numbers 1 to 10. This is from the definition of the determinant:
In our case, the determinant sums the number of permutations who's product is not zero. If such a permutation exists then a sub-set such as we are looking for exists.
The determinant is zero if the matrix is triangular (without entries on the diagonal) or if there are exactly two permutation, one even, one odd, whos product is non zero.
The matrix can not be triangular sicne there are 50 entries but only 45 entries in each triangle.
How do I prove that there can not be a pair of an even and odd permutation.