Combinatorics

Charlie has a set of 100 cards. On each card one of the integers from 1 to 100 is printed without any repeats.

Use the inclusion-exclusion principle to determine how many of Charlie’s cards show a

number that is a multiple of 2, 3 or 5.

Charlie then chooses one or more cards at random and arranges them next to each other to form a number with n digits where n ⩾ 1.

Determine the total number of different arrangements of cards that will produce a 3-digit

number.

At the end of each year the workers at an office take part in a gift exchange. Each worker randomly chooses the name of one other worker and buys a small gift for that person.

Each worker’s name is chosen by exactly one of the others. A worker cannot choose their own name.

In the first year there were four workers, A, B, C and D. There are 9 ways in which A, B, C and D can choose the names for the gift exchange. One of these is already given in the table in the Printed Answer Booklet.

Complete the table in the Printed Answer Booklet to show the remaining 8 ways in which the

names can be chosen.

During the second year, worker D left and was replaced with worker E. The organiser of the gift exchange wants to know whether it is possible for the event to happen for another 3 years (starting with the second year) with none of the workers choosing a name they have chosen before, assuming that there are no further changes in the workers.

Classify the organiser’s problem as an existence, construction, enumeration or optimisation

problem.

After the second year, the organiser drew a graph showing who each worker chose in the first two years of the gift exchange. None of the workers chose the same name in the first and second years.

The vertices of the graph represented the workers, A, B, C, D and E, and the arcs showed who had been chosen by each worker.

Explain why the graph must be a digraph.

State the number of arcs in the digraph that shows the choices for the first two years.

Assuming that the digraph created in part (d) is planar, use Euler’s formula to calculate how

many regions it has.

The first 20 consecutive positive integers include the 8 prime numbers 2, 3, 5, 7, 11, 13, 17 and 19.

Emma randomly chooses 5 distinct numbers from the first 20 consecutive positive integers. The order in which Emma chooses the numbers does not matter.

Calculate the number of possibilities in which Emma’s 5 numbers include exactly 2 prime

numbers and 3 non-prime numbers.

Calculate the number of possibilities in which Emma’s 5 numbers include at least 2 prime

numbers.

The pairs {3, 13} and {7, 17} each consist of numbers with a difference of exactly 10.

Calculate the number of possibilities in which Emma’s 5 numbers include at least one pair of

prime numbers in which the difference between them is exactly 10.

A new set of 20 consecutive positive integers, each with at least two digits, is chosen. This set of 20 numbers contains 5 prime numbers.

Use the pigeonhole principle to show that there is at least one pair of these prime numbers for

which the difference between them is exactly 10.

Four children, A, B, C and D, discuss how many of the 23 birthday parties held by their classmates they had gone to. Each party was attended by at least one of the four children.

The results are shown in the Venn diagram below.

Construct a complete graph K₄, with vertices representing the four children and arcs

weighted to show the number of parties each pair of children went to.

State a piece of information about the number of parties the children went to that is shown in

the Venn diagram but is not shown in the graph.

A fifth child, E, also went to some of the 23 parties shown in the Venn diagram. Every party that E went to was also attended by at least one of A, B, C and D.

• A was at 8 of these parties, B at 7, C at 5 and D at 8.

• These include 5 parties attended by both A and B, 2 by both A and C, 3 by both A and D, 3 by both B and D and 4 by both C and D.

• These include 1 party attended by A, B and D and 1 party attended by A, C and D.

Use the inclusion‑exclusion principle to determine the number of parties that E went to.

A para relay team of 4 swimmers needs to be chosen from a group of 7 swimmers.

How many ways are there to choose 4 swimmers from 7?

There are no restrictions on how many men and how many women are in the team. The group of 7 swimmers consists of 5 men and 2 women.

How many ways are there to choose a team with more men than women?

The physical impairment of each swimmer is given a score. The scores for the swimmers are 3 4 4 6 7 8 9

The total score for the team must be 20 or less.

How many different valid teams are possible?

The order of the swimmers in the team is now taken into consideration.

In total, how many different arrangements are there of valid teams?

In how many of these valid teams are the scores of the swimmers in increasing order?

For example, 3, 4, 4, 8 but not 4, 3, 4, 8.

Six people play a game with 150 cards. Each player has a stack of cards in front of them and the remainder of the cards are in another stack on the table.

Use the pigeonhole principle to explain why at least one of the stacks must have at least 22

cards in it.

The set of cards is numbered from 1 to 150.

Each digit ‘2’, ‘3’ and ‘5’, whether as a units digit or a tens digit, is coloured red. So, for example

• the card numbered 25 has two red digits,

• the card numbered 26 has one red digit,

• the card numbered 148 has no red digits.

By considering the cards with one digit, two digits and three digits, or otherwise, determine

how many cards have no red digits.

Given that, for the cards with no red digits, n (B) = 21, n (C) = 9 and n (A ∩ B) = 12, use the inclusion-exclusion principle to determine how many of the cards with no red digits are in

none of the sets A, B or C.

Five cards are selected at random without replacement.

Determine the probability that the letters on at least three of the cards are vowels.

All 26 cards are arranged in a line, in random order.

Show that the probability that all the vowels are next to one another is

Determine the probability that three of the vowels are next to each other, and the other

two vowels are next to each other, but the five vowels are not all next to each other.

Show that there are 127 ways to partition a set of 8 distinct elements into two non-empty

subsets.

A group of 8 people (A, B, …) have 8 reserved seats (1, 2, …) on a coach. Seat 1 is reserved for person A, seat 2 for person B, and so on. The reserved seats are labelled but the individual people do not know which seat has been reserved for them.

The first 4 people, A, B, C and D, choose their seats at random from the 8 reserved seats.

Determine how many different arrangements there are for the seats chosen by A, B, C and D.

The group organiser moves A, B, C and D to their correct seats (A in seat 1, B in seat 2, C in seat 3 and D in seat 4). The other 4 people (E, F, G and H) then choose their seats at random from the remaining 4 reserved seats (5, 6, 7 and 8).

List the 9 derangements of {E, F, G, H}, where none of these four people is in the seat that has

been reserved for them.

Suppose, instead, that the 8 people had chosen their seats at random from the 8 reserved seats, without the organiser intervening.

Determine the total number of ways in which the seats can be chosen so that 4 of the people

are in their correct seats and 4 are not in their correct seats.