Nets, Puzzles, and Postmen: An exploration of mathematical connections
Peter M Higgins
Format: PDF / Kindle (mobi) / ePub
What do road and railway systems, electrical circuits, mingling at parties, mazes, family trees, and the internet all have in common?
All are networks - either people or places or things that relate and connect to one another. Only relatively recently have mathematicians begun to explore such networks and connections, and their importance has taken everyone by surprise.
The mathematics of networks form the basis of many fascinating puzzles and problems, from tic-tac-toe and circular sudoku to the 'Chinese Postman Problem' (can he deliver all his letters without traversing the same street twice?). Peter Higgins shows how such puzzles as well as many real-world phenomena are underpinned by the same deep mathematical structure. Understanding mathematical networks can give us remarkable new insights into them all.
accepts the word, but if the word puts it in a bad mood, then it rejects it. The languages that we talk about in this context are not generally thought to be ordinary languages, although they are by no means excluded. Formal languages, taken in full generality, consist of arbitrary strings of symbols from some alphabet. Usually our automata are out to detect patterns, or the absence of them, within these strings, which are referred to as words despite not necessarily having a meaning in
C are of the one tribe (lying brothers), this would mean that A would also be lying, something he just never does. Hence we have reached another contradiction and so C is a truth teller and the remaining path, T LT, is the correct one. We should check that T LT is really consistent with what we have been told, just in case we have somehow misheard what A and B have said. In this pathway, B is lying about what A would say: A would not say that B and the taciturn C are brothers, and since B is a
prepared to follow the mathematical signposts they encounter. The feature of real research that all mathematicians know but which is difﬁcult to convey to the general public is that mathematics needs to be free to dip in and out of applications as the mood requires. A lot of good mathematics arises from practical problems. However, the mathematics that results often transcends the original problem and sheds light elsewhere, ﬁrst in other parts of mathematics, and eventually in entirely different
than the girls, a solution can be found, a very happy outcome. This pattern of solution we have seen on previous occasions when an obvious necessary condition has turned out to be enough to solve a problem. Just recently we saw that it is possible to have a particular ﬂow through a network as long as the value of the ﬂow does not exceed the capacity of any cutset. These similarities are not just coincidental but stem from the same root, for it is possible to view Hall’s Lemma as a special case of
credit for. In setting up our tree of possibilities, I began with A at the top because I analysed the situation ﬁrst by looking at what A was saying. However we could similarly analyse all this beginning with what B has to say, an exercise you might care to try yourself. This is all reminiscent of the ancient paradox of Epimenides of Knossus (c.600 BC) who famously asserted that ‘Cretans always lie,’ even though he himself was a Cretan. If Epimenides had only said that Cretans are liars, simply