Following are a couple of related puzzles, motivated by this holiday season:

1. You are standing at the very end of a line of 100 holiday travelers (you and 99 others) waiting to board an airplane.  Each passenger in line has a boarding pass assigning him or her to one of the 100 seats on the airplane.  However, the first person in line is rather confused, and so instead of sitting in her assigned seat, she boards the airplane and simply selects a seat at random (possibly her own).  As each subsequent passenger boards the airplane, he sits in his assigned seat if it is empty, or selects an empty seat at random if it is not.  What is the probability you, the last person to board, will be able to sit in your assigned seat?

2. Preparing to return home after the holiday, you find yourself once again last in a line of 100 travelers waiting to board an airplane.  This time, it is not just the first person in line who is confused; after a stressful holiday with their families, now every person in line is not just confused but deranged.  That is, each passenger in turn boards the airplane and selects a seat at random from all currently empty seats, excluding their own.  What is the probability that you, the last person to board, will be forced to sit in your assigned seat?

The first problem is an oldie but a goodie.  I like it because it can be approached in several different ways.  It is easy to simulate using a computer, which quickly leads to conjecture at the solution.  Given the conjecture, the proof is a nice application of mathematical induction.  But there are also nice symmetry arguments via which the problem may be solved more directly.

The second problem is more difficult, and is the real motivation for this post.  Solutions to both are welcome in the comments– until then, consider in what other way(s) this second problem might arise in relation to the holidays?

Last week’s puzzle asked for the largest regular polygon in a “cycle,” or a collection of regular polygons all with side length 1 sharing a common central vertex, with consecutive pairs of polygons sharing exactly a common edge.  I had tackled a simpler version of this problem before, with exactly 3 polygons each with a distinct number of sides.  With this slight generalization– any number of polygons, possibly with equal numbers of sides– this already nice mathematical problem acquires a nice computational twist.

Following is Mathematica code that enumerates all possible cycles, unique up to permutations.  It is essentially a lexicographic enumeration of cycles of polygons, where .  (We need at least 3 polygons, since the interior angle of any regular polygon is strictly less than 180 degrees.  There can be at most 6 polygons, since the smallest interior angle of any regular polygon is 60 degrees.)  The idea is to enumerate “candidate prefixes” of polygons, since the number of sides in the -th polygon is determined by the others:

Do[
    n=Table[3,{m-1}]; (* Start with all triangles *)
    While[True,
        s=Total[180-360/n]; (* Compute sum of interior angles *)
        k=Length[n];        (* Usually we increment the last polygon *)
        If[s>180,           (* Remaining polygon contributes < 180 deg *)
            p=360/(s-180);  (* Compute number of sides of remaining polygon *)
            If[p<Last[n],
                t=Split[n]; (* Remaining polygon is too small *)
                If[Length[t]>1,
                    k=k-Length[t//Last], (* Increment at last difference *)
                    Break[]              (* Stop if all polygons are equal *)
                ],
                If[IntegerQ[p],Print[Append[n,p]]] (* Record valid cycles *)
            ]
        ];
        n[[Range[k,Length[n]]]]=n[[k]]+1 (* Move to next candidate cycle *)
    ],
    {m,3,6}
]

This yields the following output, where it turns out that the desired largest polygon is realized in the lexicographically first cycle:

{3,7,42}
{3,8,24}
{3,9,18}
{3,10,15}
{3,12,12}
{4,5,20}
{4,6,12}
{4,8,8}
{5,5,10}
{6,6,6}
{3,3,4,12}
{3,3,6,6}
{3,4,4,6}
{4,4,4,4}
{3,3,3,3,6}
{3,3,3,4,4}
{3,3,3,3,3,3}

Another reason that I like this problem– beyond the fact that its solution is the answer to “Life, the Universe, and Everything”– is that the answer, 42, is… well, large.  That is, my own intuition would not have suggested a cycle might involve a polygon with that many sides.

This phenomenon of “surprisingly large numbers” in mathematics is what reminded me of this problem and motivated the last couple of posts.  The subject of conversation was actually “surprisingly large minimal counterexamples,” or the dangers of “poor man’s induction:” observing a property for many values of n, and supposing that the property then holds for all n.

There are a lot of interesting examples of this sort of thing, from Polya’s conjecture (the smallest value of n for which the conjecture fails: 906,150,257) to the Chebyshev Bias or “prime race” (23,338,590,792).  And although Graham’s number is not exactly the same thing– it is “merely” a proven upper bound on a minimum solution to an easily stated problem in graph theory– as far as mathematically relevant large numbers go, it’s one of the more mind-blowing ones.

You have an unlimited supply of regular polygons, each with side length 1: triangles, squares, pentagons, etc.  Some combinations of these polygons may be arranged in a “cycle” so that they all share a common vertex and any consecutive pair of polygons share exactly a common edge.  (See the example below.)  What is the largest n-gon in such a cycle?

Example using 3 triangles and 2 squares.

Hint (sort of): There is a much better title for this post, but unfortunately it would give away the solution to the problem.