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 SAILOR'S PUZZLE

    The sailor depicted in the illustration stated that he had since his boyhood been engaged in trading with a small vessel among some twenty little islands in the Pacific. He supplied the rough chart of which I have given a copy, and explained that the lines from island to island represented the only routes that he ever adopted. He always started from island A at the beginning of the season, and then visited every island once, and once only, finishing up his tour at the starting-point A. But he always put off his visit to C as long as possible, for trade reasons that I need not enter into. The puzzle is to discover his exact route, and this can be done with certainty. Take your pencil and, starting at A, try to trace it out. If you write down the islands in the order in which you visit them—thus, for example, A, I, O, L, G, etc.—you can at once see if you have visited an island twice or omitted any. Of course, the crossings of the lines must be ignored—that is, you must continue your route direct, and you are not allowed to switch off at a crossing and proceed in another direction. There is no trick of this kind in the puzzle. The sailor knew the best route. Can you find it? Sources:

  • THE GRAND TOUR

    One of the everyday puzzles of life is the working out of routes. If you are taking a holiday on your bicycle, or a motor tour, there always arises the question of how you are to make the best of your time and other resources. You have determined to get as far as some particular place, to include visits to such-and-such a town, to try to see something of special interest elsewhere, and perhaps to try to look up an old friend at a spot that will not take you much out of your way. Then you have to plan your route so as to avoid bad roads, uninteresting country, and, if possible, the necessity of a return by the same way that you went. With a map before you, the interesting puzzle is attacked and solved. I will present a little poser based on these lines.

    I give a rough map of a country—it is not necessary to say what particular country—the circles representing towns and the dotted lines the railways connecting them. Now there lived in the town marked A a man who was born there, and during the whole of his life had never once left his native place. From his youth upwards he had been very industrious, sticking incessantly to his trade, and had no desire whatever to roam abroad. However, on attaining his fiftieth birthday he decided to see something of his country, and especially to pay a visit to a very old friend living at the town marked Z. What he proposed was this: that he would start from his home, enter every town once and only once, and finish his journey at Z. As he made up his mind to perform this grand tour by rail only, he found it rather a puzzle to work out his route, but he at length succeeded in doing so. How did he manage it? Do not forget that every town has to be visited once, and not more than once.

    Sources:

  • WATER, GAS, AND ELECTRICITY

    There are some half-dozen puzzles, as old as the hills, that are perpetually cropping up, and there is hardly a month in the year that does not bring inquiries as to their solution. Occasionally one of these, that one had thought was an extinct volcano, bursts into eruption in a surprising manner. I have received an extraordinary number of letters respecting the ancient puzzle that I have called "Water, Gas, and Electricity." It is much older than electric lighting, or even gas, but the new dress brings it up to date. The puzzle is to lay on water, gas, and electricity, from W, G, and E, to each of the three houses, A, B, and C, without any pipe crossing another. Take your pencil and draw lines showing how this should be done. You will soon find yourself landed in difficulties. Sources:

  • A PUZZLE FOR MOTORISTS

    Eight motorists drove to church one morning. Their respective houses and churches, together with the only roads available (the dotted lines), are shown. One went from his house A to his church A, another from his house B to his church B, another from C to C, and so on, but it was afterwards found that no driver ever crossed the track of another car. Take your pencil and try to trace out their various routes. Sources:

  • A BANK HOLIDAY PUZZLE

    Two friends were spending their bank holiday on a cycling trip. Stopping for a rest at a village inn, they consulted a route map, which is represented in our illustration in an exceedingly simplified form, for the puzzle is interesting enough without all the original complexities. They started from the town in the top left-hand corner marked A. It will be seen that there are one hundred and twenty such towns, all connected by straight roads. Now they discovered that there are exactly `1,365` different routes by which they may reach their destination, always travelling either due south or due east. The puzzle is to discover which town is their destination. Of course, if you find that there are more than `1,365` different routes to a town it cannot be the right one. Sources:

  • THE MOTOR-CAR TOUR

    In the above diagram the circles represent towns and the lines good roads. In just how many different ways can a motorist, starting from London (marked with an L), make a tour of all these towns, visiting every town once, and only once, on a tour, and always coming back to London on the last ride? The exact reverse of any route is not counted as different. Sources:

  • THE LEVEL PUZZLE

    This is a simple counting puzzle. In how many different ways can you spell out the word LEVEL by placing the point of your pencil on an L and then passing along the lines from letter to letter. You may go in any direction, backwards or forwards. Of course you are not allowed to miss letters—that is to say, if you come to a letter you must use it.
    Topics:
    Combinatorics
    Sources:

  • THE DIAMOND PUZZLE

    IN how many different ways may the word DIAMOND be read in the arrangement shown? You may start wherever you like at a D and go up or down, backwards or forwards, in and out, in any direction you like, so long as you always pass from one letter to another that adjoins it. How many ways are there?
    Topics:
    Combinatorics
    Sources:

  • THE DEIFIED PUZZLE

    In how many different ways may the word DEIFIED be read in this arrangement under the same conditions as in the last puzzle, with the addition that you can use any letters twice in the same reading? Sources:

  • THE VOTERS' PUZZLE

    Here we have, perhaps, the most interesting form of the puzzle. In how many different ways can you read the political injunction, "RISE TO VOTE, SIR," under the same conditions as before? In this case every reading of the palindrome requires the use of the central V as the middle letter. Sources: