OCR MEI D1 (Decision Mathematics 1)

1 The bipartite graph in Fig. 1 represents a board game for two players. At each turn a player tosses a coin and moves their counter. The graph shows which square the counter is moved to if the coin shows heads, and which square if it shows tails. Each player starts with their counter on square 1. Play continues until one player gets their counter to square 9 and wins. \begin{figure}[h] \end{figure}

1. Draw a tree to show all of the possibilities for the player's first three moves.
2. Show how a player can win in 3 turns.
3. List all squares which it is possible for a counter to occupy after 3 turns.
4. Show that a game can continue indefinitely.

2 Answer this question on the insert provided.

1. Use Dijkstra's algorithm to find the least weight route from A to G in the network shown in Fig. 2.1. Show the order in which you label vertices, give the route and its weight. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_458_586_525_758} \captionsetup{labelformat=empty} \caption{Fig. 2.1}
   \end{figure}
2. Fig. 2.2 shows a partially completed application of Kruskal's algorithm to find a minimum spanning tree for the network. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_417_524_1309_786} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
   \end{figure} Complete the algorithm and give the total weight of your minimum spanning tree.

3 The following algorithm finds the highest common factor of two positive integers. ("int (x)" stands for the integer part of x, e.g. int (7.8) = 7.) \begin{figure}[h] \end{figure}

1. Run the algorithm with \(\mathrm { A } = 84\) and \(\mathrm { B } = 660\), showing all of your calculations.
2. Run the algorithm with \(\mathrm { A } = 660\) and \(\mathrm { B } = 84\), showing as many calculations as are necessary.
3. The algorithm is run with \(\mathrm { A } = 30\) and \(\mathrm { B } = 42\), and the result is shown in Table 3.2 below. \begin{table}[h]

   A	B	Q	R 1	R 2
   30	42	1	12
   12	30	2		6
   			6
   6	12	2		0

   \captionsetup{labelformat=empty} \caption{Print 6}
   \end{table} Table 3.2 The first line of the table shows that \(12 = 42 - 1 \times 30\).
   Use the second line to obtain a similar expression for 6 in terms of 30 and 12.
   Hence express 6 in the form \(\mathrm { m } \times 30 - \mathrm { n } \times 42\), where m and n are integers.