7.01j Selections with several constraints

2 questions

Sort by: Default | Easiest first | Hardest first
OCR FD1 AS 2018 March Q5
8 marks Challenging +1.2
5
  1. How many arcs does the complete bipartite graph \(K _ { 5,5 }\) have? A subgraph of \(K _ { 5,5 }\) contains 5 arcs joining each of the elements of the set \(\{ 1,2,3,4,5 \}\) to an element in a permutation of the set \(\{ 1,2,3,4,5 \}\). Suppose that \(r\) is connected to \(p ( r )\) for \(r = 1,2,3,4,5\).
  2. How many permutations would have \(p ( 1 ) \neq 1\) ?
  3. Using the pigeonhole principle, show that for every permutation of \(\{ 1,2,3,4,5 \}\), the product \(\Pi _ { r = 1 } ^ { 5 } ( r - p ( r ) )\) is even (i.e. an integer multiple of 2, including 0 ).
  4. Is the result in part (iii) true when the permutation is of the set \(\{ 1,2,3,4,5,6 \}\) ? Give a reason for your answer.
OCR Further Discrete 2018 March Q3
8 marks Standard +0.8
50 people are at a TV game show. 21 of the 50 are there to take part in the game show and the others are friends who are in the audience, 22 are women and 20 are from London, 2 are women from London who are there to take part in the game show and 15 are men who are not from London and are friends who are in the audience.
  1. Deduce how many of the 50 people are in two of the categories 'there to take part in the game show', 'is a woman' and 'is from London', but are not in all three categories. [3]
The 21 people who are there to take part in the game show are moved to the stage where they are seated in two rows of seats with 20 seats in each row. Some of the seats are empty.
  1. Show how the pigeonhole principle can be used to show that there must be at least one pair of these 21 people with no empty chair between them. [2]
The 21 people are split into three sets of 7. In each round of the game show, three of the people are chosen. The three people must all be from the same set of 7 but once two people have played in the same round they cannot play together in another round. For example, if A plays with B and C in round 1 then A cannot play with B or with C in any other round.
  1. By first considering how many different rounds can be formed using the first set of seven people, deduce how many rounds there can be altogether. [3]