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 TWO ROOKS

    This is a puzzle game for two players. Each player has a single rook. The first player places his rook on any square of the board that he may choose to select, and then the second player does the same. They now play in turn, the point of each play being to capture the opponent's rook. But in this game you cannot play through a line of attack without being captured. That is to say, if in the diagram it is Black's turn to play, he cannot move his rook to his king's knight's square, or to his king's rook's square, because he would enter the "line of fire" when passing his king's bishop's square. For the same reason he cannot move to his queen's rook's seventh or eighth squares. Now, the game can never end in a draw. Sooner or later one of the rooks must fall, unless, of course, both players commit the absurdity of not trying to win. The trick of winning is ridiculously simple when you know it. Can you solve the puzzle? Sources:

  • PUSS IN THE CORNER

     

    This variation of the last puzzle is also played by two persons. One puts a counter on No. `6`, and the other puts one on No. `55`, and they play alternately by removing the counter to any other number in a line. If your opponent moves at any time on to one of the lines you occupy, or even crosses one of your lines, you immediately capture him and win. We will take an illustrative game.

    A moves from `55` to `52`; B moves from `6` to `13`; A advances to `23`; B goes to `15`; A retreats to `26`; B retreats to `13`; A advances to `21`; B retreats to `2`; A advances to `7`; B goes to `3`; A moves to `6`; B must now go to `4`; A establishes himself at `11`, and B must be captured next move because he is compelled to cross a line on which A stands. Play this over and you will understand the game directly. Now, the puzzle part of the game is this: Which player should win, and how many moves are necessary?

    Sources:

  • A WAR PUZZLE GAME

    Here is another puzzle game. One player, representing the British general, places a counter at B, and the other player, representing the enemy, places his counter at E. The Britisher makes the first advance along one of the roads to the next town, then the enemy moves to one of his nearest towns, and so on in turns, until the British general gets into the same town as the enemy and captures him. Although each must always move along a road to the next town only, and the second player may do his utmost to avoid capture, the British general (as we should suppose, from the analogy of real life) must infallibly win. But how? That is the question. Sources:

  • A MATCH MYSTERY

    Here is a little game that is childishly simple in its conditions. But it is well worth investigation.

    Mr. Stubbs pulled a small table between himself and his friend, Mr. Wilson, and took a box of matches, from which he counted out thirty.

    "Here are thirty matches," he said. "I divide them into three unequal heaps. Let me see. We have `14, 11`, and `5`, as it happens. Now, the two players draw alternately any number from any one heap, and he who draws the last match loses the game. That's all! I will play with you, Wilson. I have formed the heaps, so you have the first draw."

    "As I can draw any number," Mr. Wilson said, "suppose I exhibit my usual moderation and take all the `14` heap."

    "That is the worst you could do, for it loses right away. I take `6` from the `11`, leaving two equal heaps of `5`, and to leave two equal heaps is a certain win (with the single exception of `1, 1`), because whatever you do in one heap I can repeat in the other. If you leave `4` in one heap, I leave `4` in the other. If you then leave `2` in one heap, I leave `2` in the other. If you leave only `1` in one heap, then I take all the other heap. If you take all one heap, I take all but one in the other. No, you must never leave two heaps, unless they are equal heaps and more than `1, 1`. Let's begin again."

    "Very well, then," said Mr. Wilson. "I will take `6` from the `14`, and leave you `8, 11, 5`."

    Mr. Stubbs then left `8, 11, 3`; Mr. Wilson, `8, 5, 3`; Mr. Stubbs, `6, 5, 3`; Mr. Wilson,`4, 5, 3`; Mr. Stubbs, `4, 5, 1`; Mr. Wilson, `4, 3, 1`; Mr. Stubbs, `2, 3, 1`; Mr. Wilson, `2, 1, 1`; which Mr. Stubbs reduced to `1, 1, 1`.

    "It is now quite clear that I must win," said Mr. Stubbs, because you must take `1`, and then I take `1`, leaving you the last match. You never had a chance. There are just thirteen different ways in which the matches may be grouped at the start for a certain win. In fact, the groups selected, `14, 11, 5`, are a certain win, because for whatever your opponent may play there is another winning group you can secure, and so on and on down to the last match."

    Sources:

  • THE MONTENEGRIN DICE GAME

    It is said that the inhabitants of Montenegro have a little dice game that is both ingenious and well worth investigation. The two players first select two different pairs of odd numbers (always higher than `3`) and then alternately toss three dice. Whichever first throws the dice so that they add up to one of his selected numbers wins. If they are both successful in two successive throws it is a draw and they try again. For example, one player may select `7` and `15` and the other `5` and `13`. Then if the first player throws so that the three dice add up `7` or `15` he wins, unless the second man gets either `5` or `13` on his throw.

    The puzzle is to discover which two pairs of numbers should be selected in order to give both players an exactly even chance.

    Sources:

  • THE CIGAR PUZZLE

    I once propounded the following puzzle in a London club, and for a considerable period it absorbed the attention of the members. They could make nothing of it, and considered it quite impossible of solution. And yet, as I shall show, the answer is remarkably simple.

    Two men are seated at a square-topped table. One places an ordinary cigar (flat at one end, pointed at the other) on the table, then the other does the same, and so on alternately, a condition being that no cigar shall touch another. Which player should succeed in placing the last cigar, assuming that they each will play in the best possible manner? The size of the table top and the size of the cigar are not given, but in order to exclude the ridiculous answer that the table might be so diminutive as only to take one cigar, we will say that the table must not be less than `2` feet square and the cigar not more than `4`½ inches long. With those restrictions you may take any dimensions you like. Of course we assume that all the cigars are exactly alike in every respect. Should the first player, or the second player, win?

    Sources:

  • THE TROUBLESOME EIGHT

    Nearly everybody knows that a "magic square" is an arrangement of numbers in the form of a square so that every row, every column, and each of the two long diagonals adds up alike. For example, you would find little difficulty in merely placing a different number in each of the nine cells in the illustration so that the rows, columns, and diagonals shall all add up `15`. And at your first attempt you will probably find that you have an `8` in one of the corners. The puzzle is to construct the magic square, under the same conditions, with the `8` in the position shown. Sources:

  • EIGHT JOLLY GAOL BIRDS

     

    The illustration shows the plan of a prison of nine cells all communicating with one another by doorways. The eight prisoners have their numbers on their backs, and any one of them is allowed to exercise himself in whichever cell may happen to be vacant, subject to the rule that at no time shall two prisoners be in the same cell. The merry monarch in whose dominions the prison was situated offered them special comforts one Christmas Eve if, without breaking that rule, they could so place themselves that their numbers should form a magic square.

    Now, prisoner No. `7` happened to know a good deal about magic squares, so he worked out a scheme and naturally selected the method that was most expeditious—that is, one involving the fewest possible moves from cell to cell. But one man was a surly, obstinate fellow (quite unfit for the society of his jovial companions), and he refused to move out of his cell or take any part in the proceedings. But No. `7` was quite equal to the emergency, and found that he could still do what was required in the fewest possible moves without troubling the brute to leave his cell. The puzzle is to show how he did it and, incidentally, to discover which prisoner was so stupidly obstinate. Can you find the fellow?

    Sources:

  • NINE JOLLY GAOL BIRDS

    Shortly after the episode recorded in the last puzzle occurred, a ninth prisoner was placed in the vacant cell, and the merry monarch then offered them all complete liberty on the following strange conditions. They were required so to rearrange themselves in the cells that their numbers formed a magic square without their movements causing any two of them ever to be in the same cell together, except that at the start one man was allowed to be placed on the shoulders of another man, and thus add their numbers together, and move as one man. For example, No. `8` might be placed on the shoulders of No. `2`, and then they would move about together as `10`. The reader should seek first to solve the puzzle in the fewest possible moves, and then see that the man who is burdened has the least possible amount of work to do. Sources:

  • THE SPANISH DUNGEON

    Not fifty miles from Cadiz stood in the middle ages a castle, all traces of which have for centuries disappeared. Among other interesting features, this castle contained a particularly unpleasant dungeon divided into sixteen cells, all communicating with one another, as shown in the illustration.

    Now, the governor was a merry wight, and very fond of puzzles withal. One day he went to the dungeon and said to the prisoners, "By my halidame!" (or its equivalent in Spanish) "you shall all be set free if you can solve this puzzle. You must so arrange yourselves in the sixteen cells that the numbers on your backs shall form a magic square in which every column, every row, and each of the two diagonals shall add up the same. Only remember this: that in no case may two of you ever be together in the same cell."

    One of the prisoners, after working at the problem for two or three days, with a piece of chalk, undertook to obtain the liberty of himself and his fellow-prisoners if they would follow his directions and move through the doorway from cell to cell in the order in which he should call out their numbers. 

     

    He succeeded in his attempt, and, what is more remarkable, it would seem from the account of his method recorded in the ancient manuscript lying before me, that he did so in the fewest possible moves. The reader is asked to show what these moves were.

    Sources: