Mathematics 11.

We have seen such problems also earlier, when we denoted certain things by points and the relations between them by lines or possibly by arrows. Such figures help with understanding the long text during the solution of the following example.

Let us denote the teams by points. If a team wins against another team, then let us draw an arrow from this point pointing to the point corresponding to the loser team. A tie is denoted by a line connecting the points corresponding to the two teams.

The Timbertoes won against the Shortlegs and lost against the Goalkickers, thus the tie must have been the result against the Offsiders (Figure 7). As there have been no more ties yet, both the Shortlegs and the Goalkickers have won and lost one match each. Two cases are possible:
CASE I: The Shortlegs and the Goalkickers have not played against each other yet. In this case the Offsiders would already have played all their matches, however Dan is going to their last match, so this case is not possible. (Figure 8)

Every member of the company can have at most \latex{ 5 } acquaintances in the company. Let us choose one person from the company, let him be Albert (\latex{ A }).

Two cases are possible based on the pigeonhole principle.
CASE I: Albert knows at least \latex{ 3 } other people (for example Bruce, Chris and Dave).

If there are two among Bruce, Chris and Dave, who know each other, for example Bruce and Chris, then we found three people, who know each other mutually (\latex{ A,\, B,\, C }). (Figure 10)

If there are no two among Bruce, Chris and Dave, who would know each other, then they do not know each other mutually. (Figure 11)

CASE II: Albert does not know at least \latex{ 3 } other people (for example Bruce, Chris and Dave).

If there are two among Bruce, Chris and Dave, who do not know each other, for example Bruce and Chris, then we found three people, who do not know each other mutually (\latex{ A,\, B,\, C }). (Figure 12)

If there are no two among Bruce, Chris and Dave, who would not know each other, then they know each other mutually. (Figure 13)

In the case of a company of five it is possible that there are no three people, who know each other mutually and there are no three people, who do not know each other mutually.

Figure 14 shows such a possibility: the points mean the people, and the points corresponding to two people are connected, if the two people know each other.

Then every person of the company knows exactly two other people and does not know exactly two other people in the company.

During the solution of the example we used figures in which points were corresponding to the people, and if two people knew each other, then the points corresponding to them were connected. The connecting line could be a straight or a curved line, the only important thing was which two points were connected. This type of “figure” can be useful when solving other exercises too.

Now we generally deal with simple graphs. If for example a simple graph has five points, then it can have at most as many edges in as many ways we can choose two out of five,  i.e. \latex{\frac{5\times4}{2}}

Two people take part in a handshake; therefore two people count it to the number of their handshakes. So the sum of the number of handshakes noted down by the secretary should be the double of the number of hand shakes, therefore it cannot be odd. There are \latex{ 5 } odd numbers among the listed ones, therefore their sum is odd, and so the notes were incorrect.

In order for the handshakes to be achievable, it is necessary that the sum of the number of handshakes is even.

It is possible, if the last person shook hands with everyone and the first and the second people shook hands with each other beside the last person. (Figure 16)

If someone said \latex{ 0 }, then this person did not shake hands with anyone, if someone said \latex{ 9 }, then this person shook hands with everyone. There cannot be two people like these in the same company, so there is an error in the notes; \latex{ 0 } and \latex{ 9 } cannot be listed simultaneously.

As this time there are \latex{ 6 } odd numbers, the sum of the number of hand shakes is even, so the necessary condition is satisfied. The handshakes are still not achievable, because there are \latex{ 5 } people, who shook hands with \latex{ 9 } other people, that is with everyone. So everyone in the company shook hands with these \latex{ 5 } people, thus there cannot be a person, who shook hands with less than \latex{ 5 } people.

In order for the handshakes to be achievable, it is necessary but not sufficient that the sum of the number of handshakes is even.

Every edge was counted to the sum of the degrees at both end-points; therefore the sum of the degrees is twice the number of edges.

It can also be seen in Figure (a) that there are two classes \latex{ 6 } students of which participated. We know \latex{ 8 } answers, so \latex{ 4 } students of those with the missing answers said \latex{ 5 }. There is one class with \latex{ 5 } participants (b), the \latex{ 3 } missing answers are: \latex{ 4 }. There are two classes with \latex{ 4 } participants (c), the \latex{ 3 } missing answers are: \latex{ 3 }. \latex{ 3 } students remain (d). If all three of them came from different classes, or two of them came from one class and one of them from another class, then it would not be possible that everyone had a classmate among the participants. So the three of them came from one class; all three of them said \latex{ 2 }.

Thus the missing \latex{ 13 } answers are: \latex{ 4 } students said \latex{ 5 }, \latex{ 3 } students said \latex{ 4 }, \latex{ 3 } students said \latex{ 3 } and \latex{ 3 } students said \latex{ 2 }.

As there is an edge between any two points, the number of the edges is as many in as many ways we can choose two points out of n so that the order of choice does not matter. And it is  \latex{\frac{n\times (n-1)}{2} = \dbinom{n}{2}.}

The representation with graphs might also help with solving logic exercises.

Let us take a graph the points of which denote the suspects, and those are connected with an edge, who are named in the same statement. (Figure 20)

Thus one of the end-points of every edge – except for one – is a thief, the other one is not, and none of the end-points of the remaining edge are thieves. It means that the total degree of the two points representing the thieves is \latex{ 4: 1 } from each of the four statements and \latex{ 0 } from the fifth one. As none of the statements names two thieves, the points corresponding to the thieves are not connected with an edge.

The two points with degree \latex{ 2 } are connected with an edge, thus the total degree of \latex{ 4 } is only possible if one of the points is the one with degree three, and we have to choose a point with degree one for this. \latex{ C } is the point with degree three, it is not connected only with the point \latex{ J } out of the points with degree one. So the two thieves are Chris and John.

Let us try to find a route in this graph that can pass through a point several times, under the following circumstances:

Four directed routes meet these conditions all of which consist of \latex{ 11 } steps. The first two and the last two steps can be performed in two different ways each, the steps in between are the same in each case. (Figure 22)

The first solution written down with text is the following:

\latex{ 2 } cannibals cross the river, \latex{ 1 } takes the boat back, again \latex{ 2 } cannibals cross the river, \latex{ 1 } takes the boat back, gets out and now \latex{ 2 } missionaries cross the river. \latex{ 1 } missionary and \latex{ 1 } cannibal row back, then again \latex{ 2 } missionaries cross the river. \latex{ 1 } cannibal goes back, \latex{ 2 } cannibals row across, they do it once more, and thus all six of them will have crossed the river by meeting the conditions.

The advantage of the graph based solution is that we have a better overview of the possibilities; the example cannot be solved in fewer steps than these, and these are all the possible solutions.

The solution can be seen in Figure 24.