Combinatorics

Combinatorics is the art of counting. It deals with selections, arrangements, and combinations of objects. Questions involve determining the number of ways to perform tasks, arrange items (permutations), or choose subsets (combinations), often using principles like the product rule and sum rule.

Pigeonhole Principle Double Counting Binomial Coefficients and Pascal's Triangle Product Rule / Rule of Product Graph Theory Matchings Induction (Mathematical Induction) Game Theory Combinatorial Geometry Invariants Case Analysis / Checking Cases Processes / Procedures Number Tables Colorings

  • THE ANTIQUARY'S CHAIN

    An antiquary possessed a number of curious old links, which he took to a blacksmith, and told him to join together to form one straight piece of chain, with the sole condition that the two circular links were not to be together. The following illustration shows the appearance of the chain and the form of each link. Now, supposing the owner should separate the links again, and then take them to another smith and repeat his former instructions exactly, what are the chances against the links being put together exactly as they were by the first man? Remember that every successive link can be joined on to another in one of two ways, just as you can put a ring on your finger in two ways, or link your forefingers and thumbs in two ways. Sources:

  • THE FIFTEEN DOMINOES

    In this case we do not use the complete set of twenty-eight dominoes to be found in the ordinary box. We dispense with all those dominoes that have a five or a six on them and limit ourselves to the fifteen that remain, where the double-four is the highest.

    In how many different ways may the fifteen dominoes be arranged in a straight line in accordance with the simple rule of the game that a number must always be placed against a similar number—that is, a four against a four, a blank against a blank, and so on? Left to right and right to left of the same arrangement are to be counted as two different ways.

    Sources:

  • THE CROSS TARGET

    In the illustration we have a somewhat curious target designed by an eccentric sharpshooter. His idea was that in order to score you must hit four circles in as many shots so that those four shots shall form a square. It will be seen by the results recorded on the target that two attempts have been successful. The first man hit the four circles at the top of the cross, and thus formed his square. The second man intended to hit the four in the bottom arm, but his second shot, on the left, went too high. This compelled him to complete his four in a different way than he intended. It will thus be seen that though it is immaterial which circle you hit at the first shot, the second shot may commit you to a definite procedure if you are to get your square. Now, the puzzle is to say in just how many different ways it is possible to form a square on the target with four shots. Sources:

  • THE FOUR POSTAGE STAMPS

    "It is as easy as counting," is an expression one sometimes hears. But mere counting may be puzzling at times. Take the following simple example. Suppose you have just bought twelve postage stamps, in this form—three by four—and a friend asks you to oblige him with four stamps, all joined together—no stamp hanging on by a mere corner. In how many different ways is it possible for you to tear off those four stamps? You see, you can give him `1, 2, 3, 4`, or `2, 3, 6, 7`, or `1, 2, 3, 6`, or `1, 2, 3, 7`, or `2, 3, 4, 8`, and so on. Can you count the number of different ways in which those four stamps might be delivered? There are not many more than fifty ways, so it is not a big count. Can you get the exact number? Sources:

  • PAINTING THE DIE

    In how many different ways may the numbers on a single die be marked, with the only condition that the `1` and `6`, the `2` and `5`, and the `3` and `4` must be on opposite sides? It is a simple enough question, and yet it will puzzle a good many people.
    Topics:
    Combinatorics
    Sources:

  • AN ACROSTIC PUZZLE

    In the making or solving of double acrostics, has it ever occurred to you to consider the variety and limitation of the pair of initial and final letters available for cross words? You may have to find a word beginning with A and ending with B, or A and C, or A and D, and so on. Some combinations are obviously impossible—such, for example, as those with Q at the end. But let us assume that a good English word can be found for every case. Then how many possible pairs of letters are available?

    Topics:
    Combinatorics
    Sources:

  • CHEQUERED BOARD DIVISIONS

    I recently asked myself the question: In how many different ways may a chessboard be divided into two parts of the same size and shape by cuts along the lines dividing the squares? The problem soon proved to be both fascinating and bristling with difficulties. I present it in a simplified form, taking a board of smaller dimensions. It is obvious that a board of four squares can only be so divided in one way—by a straight cut down the centre—because we shall not count reversals and reflections as different. In the case of a board of sixteen squares—four by four—there are just six different ways. I have given all these in the diagram, and the reader will not find any others. Now, take the larger board of thirty-six squares, and try to discover in how many ways it may be cut into two parts of the same size and shape. Sources:

  • LIONS AND CROWNS

    The young lady in the illustration is confronted with a little cutting-out difficulty in which the reader may be glad to assist her. She wishes, for some reason that she has not communicated to me, to cut that square piece of valuable material into four parts, all of exactly the same size and shape, but it is important that every piece shall contain a lion and a crown. As she insists that the cuts can only be made along the lines dividing the squares, she is considerably perplexed to find out how it is to be done. Can you show her the way? There is only one possible method of cutting the stuff. Sources:

  • BOARDS WITH AN ODD NUMBER OF SQUARES

    We will here consider the question of those boards that contain an odd number of squares. We will suppose that the central square is first cut out, so as to leave an even number of squares for division. Now, it is obvious that a square three by three can only be divided in one way, as shown in Fig. `1`. It will be seen that the pieces A and B are of the same size and shape, and that any other way of cutting would only produce the same shaped pieces, so remember that these variations are not counted as different ways. The puzzle I propose is to cut the board five by five (Fig. `2`) into two pieces of the same size and shape in as many different ways as possible. I have shown in the illustration one way of doing it. How many different ways are there altogether? A piece which when turned over resembles another piece is not considered to be of a different shape. Sources:

  • THE GRAND LAMA'S PROBLEM

    Once upon a time there was a Grand Lama who had a chessboard made of pure gold, magnificently engraved, and, of course, of great value. Every year a tournament was held at Lhassa among the priests, and whenever any one beat the Grand Lama it was considered a great honour, and his name was inscribed on the back of the board, and a costly jewel set in the particular square on which the checkmate had been given. After this sovereign pontiff had been defeated on four occasions he died—possibly of chagrin. Now the new Grand Lama was an inferior chess-player, and preferred other forms of innocent amusement, such as cutting off people's heads. So he discouraged chess as a degrading game, that did not improve either the mind or the morals, and abolished the tournament summarily. Then he sent for the four priests who had had the effrontery to play better than a Grand Lama, and addressed them as follows: "Miserable and heathenish men, calling yourselves priests! Know ye not that to lay claim to a capacity to do anything better than my predecessor is a capital offence? Take that chessboard and, before day dawns upon the torture chamber, cut it into four equal parts of the same shape, each containing sixteen perfect squares, with one of the gems in each part! If in this you fail, then shall other sports be devised for your special delectation. Go!" The four priests succeeded in their apparently hopeless task. Can you show how the board may be divided into four equal parts, each of exactly the same shape, by cuts along the lines dividing the squares, each part to contain one of the gems? Sources: