Game and interaction modeling

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.

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.

1 Alfred, Ben, Charles and David meet, and some handshaking takes place.

• Alfred shakes hands with David.
• Ben shakes hands with Charles and David.
• Charles shakes hands with Ben and David.
  1. Complete the bipartite graph in your answer book showing A (Alfred), B (Ben), C (Charles) and D (David), and the number of people each shakes hands with.
  2. Explain why, whatever handshaking takes place, the resulting bipartite graph cannot contain both an arc terminating at 0 and another arc terminating at 3 .
  3. Explain why, whatever number of people meet, and whatever handshaking takes place, there must always be two people who shake hands with the same number of people.

2 A small party is held in a country house. There are 10 men and 10 women, and there are 10 dances. For each dance a number of pairings, each of one man and one woman, are formed. The same pairing can appear in more than one dance. A graph is to be drawn showing who danced with whom during the evening, ignoring repetitions.

1. Name the type of graph which is appropriate.
2. What is the maximum possible number of arcs in the graph? Dashing Mr Darcy dances with every woman except Elizabeth, who will have nothing to do with him. She dances with eight different men. Prince Charming only dances with Cinderella. Cinderella only dances with Prince Charming and with Mr Darcy. The three ugly sisters only have one dance each.
3. Add arcs to the graph in your answer book to show this information.
4. What is the maximum possible number of arcs in the graph?

1 Two students draw graphs to represent the numbers of pairs of shoes owned by members of their class. Andrew produces a bipartite graph, but gets it wrong. Barbara produces a completely correct frequency graph. Their graphs are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Draw a correct bipartite graph.
2. How many people are in the class?
3. How many pairs of shoes in total are owned by members of the class?
4. Which points on Barbara's graph may be deleted without losing any information? Charles produces the same frequency graph as Barbara, but joins consecutive points with straight lines.
5. Criticise Charles's graph.

1 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. \includegraphics[max width=\textwidth, alt={}, center]{50697293-6cdc-475f-981f-71a351b0ff5a-2_387_618_589_246}

1. Construct a complete graph \(\mathrm { K } _ { 4 }\), with vertices representing the four children and arcs weighted to show the number of parties each pair of children went to.
2. 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 \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D .