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.

  • THE LANGUISHING MAIDEN

    A wicked baron in the good old days imprisoned an innocent maiden in one of the deepest dungeons beneath the castle moat. It will be seen from our illustration that there were sixty-three cells in the dungeon, all connected by open doors, and the maiden was chained in the cell in which she is shown. Now, a valiant knight, who loved the damsel, succeeded in rescuing her from the enemy. Having gained an entrance to the dungeon at the point where he is seen, he succeeded in reaching the maiden after entering every cell once and only once. Take your pencil and try to trace out such a route. When you have succeeded, then try to discover a route in twenty-two straight paths through the cells. It can be done in this number without entering any cell a second time. Sources:

  • A DUNGEON PUZZLE

    A French prisoner, for his sins (or other people's), was confined in an underground dungeon containing sixty-four cells, all communicating with open doorways, as shown in our illustration. In order to reduce the tedium of his restricted life, he set himself various puzzles, and this is one of them. Starting from the cell in which he is shown, how could he visit every cell once, and only once, and make as many turnings as possible? His first attempt is shown by the dotted track. It will be found that there are as many as fifty-five straight lines in his path, but after many attempts he improved upon this. Can you get more than fifty-five? You may end your path in any cell you like. Try the puzzle with a pencil on chessboard diagrams, or you may regard them as rooks' moves on a board. Sources:

  • THE LION AND THE MAN

    In a public place in Rome there once stood a prison divided into sixty-four cells, all open to the sky and all communicating with one another, as shown in the illustration. The sports that here took place were watched from a high tower. The favourite game was to place a Christian in one corner cell and a lion in the diagonally opposite corner and then leave them with all the inner doors open. The consequent effect was sometimes most laughable. On one occasion the man was given a sword. He was no coward, and was as anxious to find the lion as the lion undoubtedly was to find him. The man visited every cell once and only once in the fewest possible straight lines until he reached the lion's cell. The lion, curiously enough, also visited every cell once and only once in the fewest possible straight lines until he finally reached the man's cell. They started together and went at the same speed; yet, although they occasionally got glimpses of one another, they never once met. The puzzle is to show the route that each happened to take. Sources:

  • AN EPISCOPAL VISITATION

    The white squares on the chessboard represent the parishes of a diocese. Place the bishop on any square you like, and so contrive that (using the ordinary bishop's move of chess) he shall visit every one of his parishes in the fewest possible moves. Of course, all the parishes passed through on any move are regarded as "visited." You can visit any squares more than once, but you are not allowed to move twice between the same two adjoining squares. What are the fewest possible moves? The bishop need not end his visitation at the parish from which he first set out. Sources:

  • A NEW COUNTER PUZZLE

    Here is a new puzzle with moving counters, or coins, that at first glance looks as if it must be absurdly simple. But it will be found quite a little perplexity. I give it in this place for a reason that I will explain when we come to the next puzzle. Copy the simple diagram, enlarged, on a sheet of paper; then place two white counters on the points `1` and `2`, and two red counters on `9` and `10`, The puzzle is to make the red and white change places. You may move the counters one at a time in any order you like, along the lines from point to point, with the only restriction that a red and a white counter may never stand at once on the same straight line. Thus the first move can only be from `1` or `2` to `3`, or from `9` or `10` to `7`. Sources:

  • A NEW BISHOP'S PUZZLE

     

    This is quite a fascinating little puzzle. Place eight bishops (four black and four white) on the reduced chessboard, as shown in the illustration. The problem is to make the black bishops change places with the white ones, no bishop ever attacking another of the opposite colour. They must move alternately—first a white, then a black, then a white, and so on. When you have succeeded in doing it at all, try to find the fewest possible moves.

    If you leave out the bishops standing on black squares, and only play on the white squares, you will discover my last puzzle turned on its side.

    Sources:

  • THE STAR PUZZLE

     

    Put the point of your pencil on one of the white stars and (without ever lifting your pencil from the paper) strike out all the stars in fourteen continuous straight strokes, ending at the second white star. Your straight strokes may be in any direction you like, only every turning must be made on a star. There is no objection to striking out any star more than once.

    In this case, where both your starting and ending squares are fixed inconveniently, you cannot obtain a solution by breaking a Queen's Tour, or in any other way by queen moves alone. But you are allowed to use oblique straight lines—such as from the upper white star direct to a corner star.

    Sources:

  • THE SCIENTIFIC SKATER

     

    It will be seen that this skater has marked on the ice sixty-four points or stars, and he proposes to start from his present position near the corner and enter every one of the points in fourteen straight lines. How will he do it? Of course there is no objection to his passing over any point more than once, but his last straight stroke must bring him back to the position from which he started.

    It is merely a matter of taking your pencil and starting from the spot on which the skater's foot is at present resting, and striking out all the stars in fourteen continuous straight lines, returning to the point from which you set out.

    Sources:

  • THE FORTY-NINE STARS

    The puzzle in this case is simply to take your pencil and, starting from one black star, strike out all the stars in twelve straight strokes, ending at the other black star. It will be seen that the attempt shown in the illustration requires fifteen strokes. Can you do it in twelve? Every turning must be made on a star, and the lines must be parallel to the sides and diagonals of the square, as shown. In this case we are dealing with a chessboard of reduced dimensions, but only queen moves (without going outside the boundary as in the last case) are required. Sources:

  • ST. GEORGE AND THE DRAGON

    Here is a little puzzle on a reduced chessboard of forty-nine squares. St. George wishes to kill the dragon. Killing dragons was a well-known pastime of his, and, being a knight, it was only natural that he should desire to perform the feat in a series of knight's moves. Can you show how, starting from that central square, he may visit once, and only once, every square of the board in a chain of chess knight's moves, and end by capturing the dragon on his last move? Of course a variety of different ways are open to him, so try to discover a route that forms some pretty design when you have marked each successive leap by a straight line from square to square. Sources: