Combinatorics, Graph Theory

Graph Theory studies graphs, which are structures made of vertices (nodes) and edges connecting them. It's used to model relationships. Questions cover topics like paths, cycles, connectivity, graph coloring, trees, and analyzing properties of various types of graphs.

  • FARMER LAWRENCE'S CORNFIELDS

    One of the most beautiful districts within easy distance of London for a summer ramble is that part of Buckinghamshire known as the Valley of the Chess—at least, it was a few years ago, before it was discovered by the speculative builder. At the beginning of the present century there lived, not far from Latimers, a worthy but eccentric farmer named Lawrence. One of his queer notions was that every person who lived near the banks of the river Chess ought to be in some way acquainted with the noble game of the same name, and in order to impress this fact on his men and his neighbours he adopted at times strange terminology. For example, when one of his ewes presented him with a lamb, he would say that it had "queened a pawn"; when he put up a new barn against the highway, he called it "castling on the king's side"; and when he sent a man with a gun to keep his neighbour's birds off his fields, he spoke of it as "attacking his opponent's rooks." Everybody in the neighbourhood used to be amused at Farmer Lawrence's little jokes, and one boy (the wag of the village) who got his ears pulled by the old gentleman for stealing his "chestnuts" went so far as to call him "a silly old chess-protector!"

    One year he had a large square field divided into forty-nine square plots, as shown in the illustration. The white squares were sown with wheat and the black squares with barley. When the harvest time came round he gave orders that his men were first to cut the corn in the patch marked `1`, and that each successive cutting should be exactly a knight's move from the last one, the thirteenth cutting being in the patch marked `13`, the twenty-fifth in the patch marked `25`, the thirty-seventh in the one marked `37`, and the last, or forty-ninth cutting, in the patch marked `49`. This was too much for poor Hodge, and each day Farmer Lawrence had to go down to the field and show which piece had to be operated upon. But the problem will perhaps present no difficulty to my readers.

    Sources:

  • THE FOUR KANGAROOS

    In introducing a little Commonwealth problem, I must first explain that the diagram represents the sixty-four fields, all properly fenced off from one another, of an Australian settlement, though I need hardly say that our kith and kin "down under" always do set out their land in this methodical and exact manner. It will be seen that in every one of the four corners is a kangaroo. Why kangaroos have a marked preference for corner plots has never been satisfactorily explained, and it would be out of place to discuss the point here. I should also add that kangaroos, as is well known, always leap in what we call "knight's moves." In fact, chess players would probably have adopted the better term "kangaroo's move" had not chess been invented before kangaroos.

    The puzzle is simply this. One morning each kangaroo went for his morning hop, and in sixteen consecutive knight's leaps visited just fifteen different fields and jumped back to his corner. No field was visited by more than one of the kangaroos. The diagram shows how they arranged matters. What you are asked to do is to show how they might have performed the feat without any kangaroo ever crossing the horizontal line in the middle of the square that divides the board into two equal parts.

    Sources:

  • THE BOARD IN COMPARTMENTS

     

    We cannot divide the ordinary chessboard into four equal square compartments, and describe a complete tour, or even path, in each compartment. But we may divide it into four compartments, as in the illustration, two containing each twenty squares, and the other two each twelve squares, and so obtain an interesting puzzle. You are asked to describe a complete re-entrant tour on this board, starting where you like, but visiting every square in each successive compartment before passing into another one, and making the final leap back to the square from which the knight set out. It is not difficult, but will be found very entertaining and not uninstructive.

    Whether a re-entrant "tour" or a complete knight's "path" is possible or not on a rectangular board of given dimensions depends not only on its dimensions, but also on its shape. A tour is obviously not possible on a board containing an odd number of cells, such as `5` by `5` or `7` by `7`, for this reason: Every successive leap of the knight must be from a white square to a black and a black to a white alternately. But if there be an odd number of cells or squares there must be one more square of one colour than of the other, therefore the path must begin from a square of the colour that is in excess, and end on a similar colour, and as a knight's move from one colour to a similar colour is impossible the path cannot be re-entrant. But a perfect tour may be made on a rectangular board of any dimensions provided the number of squares be even, and that the number of squares on one side be not less than `6` and on the other not less than `5`. In other words, the smallest rectangular board on which a re-entrant tour is possible is one that is `6` by `5`.

    A complete knight's path (not re-entrant) over all the squares of a board is never possible if there be only two squares on one side; nor is it possible on a square board of smaller dimensions than `5` by `5`. So that on a board `4` by `4` we can neither describe a knight's tour nor a complete knight's path; we must leave one square unvisited. Yet on a board `4` by `3` (containing four squares fewer) a complete path may be described in sixteen different ways. It may interest the reader to discover all these. Every path that starts from and ends at different squares is here counted as a different solution, and even reverse routes are called different.

    Sources:

  • THE FOUR KNIGHTS' TOURS

    I will repeat that if a chessboard be cut into four equal parts, as indicated by the dark lines in the illustration, it is not possible to perform a knight's tour, either re-entrant or not, on one of the parts. The best re-entrant attempt is shown, in which each knight has to trespass twice on other parts. The puzzle is to cut the board differently into four parts, each of the same size and shape, so that a re-entrant knight's tour may be made on each part. Cuts along the dotted lines will not do, as the four central squares of the board would be either detached or hanging on by a mere thread. Sources:

  • THE CUBIC KNIGHT'S TOUR

    Some few years ago I happened to read somewhere that Abnit Vandermonde, a clever mathematician, who was born in `1736` and died in `1793`, had devoted a good deal of study to the question of knight's tours. Beyond what may be gathered from a few fragmentary references, I am not aware of the exact nature or results of his investigations, but one thing attracted my attention, and that was the statement that he had proposed the question of a tour of the knight over the six surfaces of a cube, each surface being a chessboard. Whether he obtained a solution or not I do not know, but I have never seen one published. So I at once set to work to master this interesting problem. Perhaps the reader may like to attempt it. Sources:

  • EXERCISE FOR PRISONERS

    The following is the plan of the north wing of a certain gaol, showing the sixteen cells all communicating by open doorways. Fifteen prisoners were numbered and arranged in the cells as shown. They were allowed to change their cells as much as they liked, but if two prisoners were ever in the same cell together there was a severe punishment promised them.

     

    Now, in order to reduce their growing obesity, and to combine physical exercise with mental recreation, the prisoners decided, on the suggestion of one of their number who was interested in knight's tours, to try to form themselves into a perfect knight's path without breaking the prison regulations, and leaving the bottom right-hand corner cell vacant, as originally. The joke of the matter is that the arrangement at which they arrived was as follows:—

    8 3 12 1
    11 14 9 6
    4 7 2 13
    15 10 5

    The warders failed to detect the important fact that the men could not possibly get into this position without two of them having been at some time in the same cell together. Make the attempt with counters on a ruled diagram, and you will find that this is so. Otherwise the solution is correct enough, each member being, as required, a knight's move from the preceding number, and the original corner cell vacant.

    The puzzle is to start with the men placed as in the illustration and show how it might have been done in the fewest moves, while giving a complete rest to as many prisoners as possible.

    As there is never more than one vacant cell for a man to enter, it is only necessary to write down the numbers of the men in the order in which they move. It is clear that very few men can be left throughout in their cells undisturbed, but I will leave the solver to discover just how many, as this is a very essential part of the puzzle.

    Sources: