N08/5/MATHL/HP3/ENG/TZ0/DM

mathematics

higher level

PaPer 3 – Discrete mathematics

Thursday 13 November 2008 (afternoon)

iNsTrucTioNs To cANDiDATEs



Do not open this examination paper until instructed to do so.



Answer all the questions.



unless otherwise stated in the question, all numerical answers must be given exactly or correct

to three significant figures.

8808-7203

4 pages

1 hour

© international Baccalaureate organization 2008

88087203

N08/5/MATHL/HP3/ENG/TZ0/DM

8808-7203

– 2 –

Please start each question on a new page. Full marks are not necessarily awarded for a correct answer

with no working. Answers must be supported by working and/or explanations. In particular, solutions

found from a graphic display calculator should be supported by suitable working, e.g. if graphs are used to

find a solution, you should sketch these as part of your answer. Where an answer is incorrect, some marks

may be given for a correct method, provided this is shown by written working. You are therefore advised

to show all working.

1.

[Maximum mark: 19]

(a) Convert the decimal number

51966

to base 16.

[4 marks]

(b) (i) Using the Euclidean algorithm, find the greatest common divisor,

d ,

of 901 and 612.

(ii) Find integers

p and q such that

901

612

p

q d

+

= .

(iii) Find the least possible positive integers s and t such that

901 612 85

s

t

−

= .

[10 marks]

(c) In each of the following cases find the solutions, if any, of the given linear

congruence.

(i)

9

3

x ≡ (mod18);

(ii)

9

3

x ≡ (mod15).

[5 marks]

N08/5/MATHL/HP3/ENG/TZ0/DM

8808-7203

– 3 –

Turn over

2.

[Maximum mark: 12]

(a) Use Kruskal’s algorithm to find the minimum spanning tree for the following

weighted graph and state its length.

[5 marks]

A

B

C

G

F

D

E

8

9

7

12

12



5

6

20

11

17

16

13

(b) Use Dijkstra’s algorithm to find the shortest path from A to D in the following

weighted graph and state its length.

[7 marks]

A

B

C

D

E

F

11

9

1

15

1

3

3

2

13

N08/5/MATHL/HP3/ENG/TZ0/DM

8808-7203

–  –

3.

[Maximum mark: 12]

(a) Write

57128

as a product of primes.

[4 marks]

(b) Numbers of the form

F

n

n

n

=

+

∈

2

1

2

,



are called Fermat numbers.

Find the smallest value of n for which the corresponding Fermat number has

more than a million digits.

[4 marks]

(c) Prove that

22 5

17

11

11

+

.

[4 marks]

4.

[Maximum mark: 17]

(a) A connected planar graph

G

has e edges and v vertices.

(i) Prove that

e v

≥ −1

.

(ii) Prove that

e v

= −1

if and only if

G

is a tree.

[4 marks]

(b) A tree has k vertices of degree 1, two of degree 2, one of degree 3 and one of

degree . Determine k and hence draw a tree that satisfies these conditions.

[6 marks]

(c) The graph

H

has the adjacency matrix given below.

0 1 1
1 0 0
1 0 0

0 0 0
1 1 0
0 1 1

0 1 0
0 1 1
0 0 1

0 0 0
0 0 0
0 0 0





































(i) Explain why

H

cannot be a tree.

(ii) Draw the graph of

H

.

[3 marks]

(d) Prove that a tree is a bipartite graph.

[4 marks]