Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Combinatorics question

  1. Jun 6, 2010 #1
    1. The problem statement, all variables and given/known data
    My professor has 50 questions. In the begining 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

    2. Relevant equations

    3. 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.
    1. The problem statement, all variables and given/known data

    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. Jun 6, 2010 #2
    To clarify: the question asks you to show there are 10 questions that appear in the same numbered spot (between 1 and 5) on the old sheet and new sheet?
  4. Jun 6, 2010 #3
    No. That there are ten questions such that in total every sheet out of twenty has exactly one question representing it.
  5. Jun 6, 2010 #4
    I still don't understand. What does it mean for a question to represent a sheet?
  6. Jun 6, 2010 #5
    I'll rephrase it, i apologize, I'm translating.
    There are 50 questions. The profesor takes 5 and puts them ona sheet and then the next five and the next five until 10 sheets are created. Lets cal it group A. Each sheet has different questions on it.
    Aftrewards, he takes the same 50 questions and makes different work sheets with them, again 10 sheets with 5 questions each. This is group B
    You (I) need to prove that there is some group of 10 questions such that each question belongs to one sheet in group A and one sheet in group B and each sheet in each group is represented, i.e. a question from each sheet is in the group.
  7. Jun 6, 2010 #6
    In a 10 by 10 matrix, there are 55 entries including the main diagonal, so the matrix can be triangular purely on those grounds. I haven't thought this through, but you should use the fact that every test has five questions.
  8. Jun 6, 2010 #7
    Ok, I got it.
    The determinant can only be zero if there are two different permutations, each of which satisfies the problem. So either way we are done.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook