# IB DP Maths Topic 10.1 Discrete mathematics-Pigeon-hole principle. HL Paper 3

## Question

Consider the integers $$a = 871$$ and $$b= 1157$$, given in base $$10$$.

(i)     Express $$a$$ and $$b$$ in base $$13$$.

(ii)     Hence show that $${\text{gcd}}(a,{\text{ }}b) = 13$$.

[7]
a.

A list $$L$$ contains $$n+ 1$$ distinct positive integers. Prove that at least two members of $$L$$leave the same remainder on division by $$n$$.

[4]
b.

Consider the simultaneous equations

$$4x + y + 5z = a$$

$$2x + z = b$$

$$3x + 2y + 4z = c$$

where $$x,{\text{ }}y,{\text{ }}z \in \mathbb{Z}$$.

(i)     Show that 7 divides $$2a + b – c$$.

(ii)     Given that a = 3, b = 0 and c = −1, find the solution to the system of equations modulo 2.

[6]
c.

Consider the set $$P$$ of numbers of the form $${n^2} – n + 41,{\text{ }}n \in \mathbb{N}$$.

(i)     Prove that all elements of P are odd.

(ii)     List the first six elements of P for n = 0, 1, 2, 3, 4, 5.

(iii)     Show that not all elements of P are prime.

[6]
d.

## Markscheme

(i)     METHOD 1

using a relevant list of powers of 13: (1), 13, 169, (2197)     M1

$$871 = 5 \times {13^2} + 2 \times 13$$     A1

$$871 = {520_{13}}$$     A1

$$1157 = 6 \times {13^2} + 11 \times 13$$     A1

$$1157 = 6{\text{B}}{{\text{0}}_{13}}$$     A1

METHOD 2

attempted repeated division by 13     M1

$$871 \div 13 = 67;{\text{ }}67 \div 13 = 5{\text{rem}}2$$     A1

$$871 = {520_{13}}$$     A1

$$1157 \div 13 = 89;{\text{ }}89 \div 13 = 6{\text{rem11}}$$     A1

$$1157 = 6{\text{B}}{{\text{0}}_{13}}$$     A1

Note:     Allow (11) for B only if brackets or equivalent are present.

(ii)     $$871 = 13 \times 67;{\text{ }}1157 = 13 \times 89$$     (M1)

67 and 89 are primes (base 10) or they are co-prime     A1

So $$\gcd (871,{\text{ }}1157) = 13$$     AG

Note:     Must be done by hence not Euclid’s algorithm on 871 and 1157.

[7 marks]

a.

let K be the set of possible remainders on division by n     (M1)

then $$K = \{ {\text{0, 1, 2, }} \ldots n – 1\}$$ has n members     A1

because $$n < n + 1{\text{ }}\left( { = n(L)} \right)$$     A1

by the pigeon-hole principle (appearing anywhere and not necessarily mentioned by name as long as is explained)     R1

at least two members of L correspond to one member of K     AG

[4 marks]

b.

(i)     form the appropriate linear combination of the equations:     (M1)

$$2a + b – c = 7x + 7z$$     A1

$$= 7(x + z)$$     R1

so 7 divides $$2a + b – c$$     AG

(ii)     modulo 2, the equations become     M1

$$y + z = 1$$

$$z = 0$$     A1

$$x = 1$$

solution: (1, 1, 0)     A1

Note:     Award full mark to use of GDC (or done manually) to solve the system giving $$x = – 1,{\text{ }}y = – 3,{\text{ }}z = 2$$ and then converting mod 2.

[6 marks]

c.

(i)     separate consideration of even and odd n     M1

$${\text{eve}}{{\text{n}}^2} – {\text{even}} + {\text{odd is odd}}$$     A1

$${\text{od}}{{\text{d}}^2} – {\text{odd}} + {\text{odd is odd}}$$     A1

all elements of P are odd     AG

Note:     Allow other methods eg, $${n^2} – n = n(n – 1)$$ which must be even.

(ii)     the list is [41, 41, 43, 47, 53, 61]     A1

(iii)     $${41^2} – 41 + 41 = {41^2}$$ divisible by 41     A1

but is not a prime     R1

the statement is disproved (by counterexample)  AG

[6 marks]

d.

[N/A]

a.

[N/A]

b.

[N/A]

c.

[N/A]

d.

## Question

Use the pigeon-hole principle to prove that for any simple graph that has two or more vertices and in which every vertex is connected to at least one other vertex, there must be at least two vertices with the same degree.

[4]
a.

Seventeen people attend a meeting.

Each person shakes hands with at least one other person and no-one shakes hands with

the same person more than once. Use the result from part (a) to show that there must be at least two people who shake hands with the same number of people.

[4]
b.

Explain why each person cannot have shaken hands with exactly nine other people.

[2]
c.

## Markscheme

let there be $$v$$ vertices in the graph; because the graph is simple the degree of each vertex is $$\le v – 1$$     A1

the degree of each vertex is $$\ge 1$$     A1

there are therefore $$v – 1$$ possible values for the degree of each vertex     A1

given there are $$v$$ vertices by the pigeon-hole principle there must be at least two with the same degree     R1

[4 marks]

a.

consider a graph in which the people at the meeting are represented by the vertices and two vertices are connected if the two people shake hands     M1

the graph is simple as no-one shakes hands with the same person more than once (nor can someone shake hands with themselves)     A1

every vertex is connected to at least one other vertex as everyone shakes at least one hand     A1

the degree of each vertex is the number of handshakes so by the proof above there must be at least two who shake the same number of hands     R1

Note: Accept answers starting afresh rather than quoting part (a).

[4 marks]

b.

(the handshaking lemma tells us that) the sum of the degrees of the vertices must be an even number     A1

the degree of each vertex would be $$9$$ and $$9 \times 17$$ is an odd number (giving a contradiction)     A1

[2 marks]

Total [10 marks]

c.

## Examiners report

Generally there were too many “waffly” words and not enough precise statements leading to conclusions.

Misconceptions were: thinking that a few examples constituted a proof, thinking that the graph had to be connected, taking the edges as the pigeons not the degrees. The pigeon-hole principle was known but not always applied well.

a.

Generally there were too many “waffly” words and not enough precise statements leading to conclusions.

Similar problems as in (a).

b.

Generally there were too many “waffly” words and not enough precise statements leading to conclusions.

Many spurious reasons were given but good candidates went straight to the hand-shaking lemma.

c.

## Question

The Fibonacci sequence can be described by the recurrence relation $${f_{n + 2}} = {f_{n + 1}} + {f_n}$$ where $${f_0} = 0,\,{f_1} = 1$$.

Write down the auxiliary equation and use it to find an expression for $${f_n}$$ in terms of $$n$$.

[7]
a.

It is known that $${\alpha ^2} = \alpha + 1$$ where $$\alpha = \frac{{1 + \sqrt 5 }}{2}$$.

For integers $$n$$ ≥ 3, use strong induction on the recurrence relation $${f_{n + 2}} = {f_{n + 1}} + {f_n}$$ to prove that $${f_n} > {\alpha ^{n – 2}}$$.

[8]
b.

## Markscheme

attempt to find the auxiliary equation ($${\lambda ^2} – \lambda – 1 = 0$$)     M1

$$\lambda = \frac{{1 \pm \sqrt 5 }}{2}$$     (A1)

the general solution is $${f_n} = A{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)^n} + B{\left( {\frac{{1 – \sqrt 5 }}{2}} \right)^n}$$    (M1)

imposing initial conditions (substituting $$n$$ = 0,1)     M1

A + B = 0 and $$A\left( {\frac{{1 + \sqrt 5 }}{2}} \right) + B\left( {\frac{{1 – \sqrt 5 }}{2}} \right) = 1$$       A1

$$A = \frac{1}{{\sqrt 5 }},\,\,B = – \frac{1}{{\sqrt 5 }}$$     A1

$${f_n} = \frac{1}{{\sqrt 5 }}{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)^n} – \frac{1}{{\sqrt 5 }}{\left( {\frac{{1 – \sqrt 5 }}{2}} \right)^n}$$     A1

Note: Condone use of decimal numbers rather than exact answers.

[7 marks]

a.

let P($$n$$) be $${f_n} > {\alpha ^{n – 2}}$$ for integers $$n$$ ≥ 3

consideration of two consecutive values of $$f$$     R1

$${f_3} = 2$$ and $${\alpha ^{3 – 2}} = \frac{{1 + \sqrt 5 }}{2}\left( {1.618 \ldots } \right) \Rightarrow {\text{P}}\left( 3 \right)$$ is true     A1

$${f_4} = 3$$ and $${\alpha ^{4 – 2}} = \frac{{3 + \sqrt 5 }}{2}\left( {2.618 \ldots } \right) \Rightarrow {\text{P}}\left( 4 \right)$$ is true    A1

Note: Do not award A marks for values of $$n$$ other than $$n$$ = 3 and $$n$$ = 4.

(for $$k$$ ≥ 4), assume that P($$k$$) and P($$k$$ − 1) are true     M1

required to prove that P($$k$$ + 1) is true

Note: Accept equivalent notation. Needs to start with 2 general consecutive integers and then prove for the next integer. This will affect the powers of the alphas.

$${f_{k + 1}} = {f_k} + {f_{k – 1}}$$ (and $${f_k} > {\alpha ^{k – 2}},\,{f_{k – 1}} > {\alpha ^{k – 3}}$$)    M1

$${f_{k + 1}} > {\alpha ^{k – 2}} + {\alpha ^{k – 3}} = {\alpha ^{k – 3}}\left( {\alpha + 1} \right)$$    A1

$$= {\alpha ^{k – 3}}{\alpha ^2} = {\alpha ^{k – 1}} = {\alpha ^{\left( {k + 1} \right) – 2}}$$     A1

as P(3) and P(4) are true, and P($$k$$) , P($$k$$ − 1) true ⇒ P($$k$$ + 1) true then P($$k$$) is true for $$k$$ ≥ 3 by strong induction      R1

Note: To obtain the final R1, at least five of the previous marks must have been awarded.

[8 marks]

b.

[N/A]

a.

[N/A]

b.