Solutions for Issue 2

Party Friends

American Mathematical Monthly1958

Imagine the dinner party as a graph with edges connecting everyone. Each person is connected to five others, and the edge between any two can be colored blue if mutual acquaintances and red if mutual strangers.

Consider the edges extending from one person, which are five in some amount of blue or red. If less than three of them are blue, at least three of them will be red, and the reverse is also true. This is an example of the pigeonhole principle.

Suppose the people at the end of three blue edges are A, B, and C. If a single edge AB, BC, or CA is blue, we can form a solid blue triangle going back to the original person, implying three mutual acquaintances. If none of AB, BC, and CA are blue, they are all red, and form the solid red triangle ABC, implying three mutual strangers.

The result is called the "theorem on friends and strangers", and I encourage reading about the theorem if you are excited by graphs.

Full House

Erich Friedman2005
Solution to Full House puzzle


G. Chang and T. W. Sederberg1997

Alexander Bogomolny shared an excellent solution on Cut the Knot. In short, mathematical induction and infinite descent prove a finite number of such operations can move all the pennies into one or two containers.


Henry Ernest Dudeney1919

Gooseville offers the following facts to determine its population:

1. No two inhabitants have exactly the same number of hairs.

2. No inhabitant has exactly 384,270 hairs.

3. There are more inhabitants than there are hairs on the head of any one inhabitant.

There are different answers depending on which assumptions are made. For this solution, let’s assume Gooseville inhabitants only grow hair on their heads.

Reframing the puzzle as a smaller problem helps. If we change Fact 2 to be “exactly 5 hairs”, we can consider a population with hair counts of 1, 2, 3, 4 and 5.

Whoops. Fact 2 states we can’t have exactly 5 hairs. Also, Fact 3 says the population size must be greater than the largest count of hair. They can’t both be 5. What happens if we make our first person bald? We get hair counts of 0, 1, 2, 3 and 4.

All facts are satisfied. Each inhabitant has a unique count of hair, none of which equal the population of 5, and the population is greater than the largest count of hair. If we return to the original framing where Fact 2 says “exactly 384,270 hairs”, we can expand our population to have hairs of 0, 1, 2, …, 384268, and 384269. The facts are still satisfied by the larger population, and the original puzzle with our assumptions is solved.

If we remove the assumption and consider any hair on the body, we struggle to find the population. Let’s again reframe Fact 2 to be “exactly 5 hairs.” We return to a population with hairs of 0, 1, 2, 3, and 6. How? Imagine the last one as bald, meaning the 6 are body hairs. Fact 3 is specifically about head hair. We can push that to 7, 8, 9, and beyond as long as hair is predominantly below their heads. The exact population with this assumption is both entertaining and unbounded.

The largest possible population of Gooseville is either exactly one less than the number posed in Fact 2 or is infinite.

Victor Klee1973

This is a classic problem in computational geometry.

Václav Chvátal proved in 1975 an upper bound for guards inside a simple n-vertex polygon to be FLOOR(n/3). Steve Fisk simplied Chvátal's theorem in 1978 with the following proof:

First, the polygon is triangulated (without adding extra vertices), which is possible, because the existence of triangulations is proven under certain verified conditions. The vertices of the resulting triangulation graph may be 3-colored. Clearly, under a 3-coloring, every triangle must have all three colors. The vertices with any one color form a valid guard set, because every triangle of the polygon is guarded by its vertex with that color. Since the three colors partition the n vertices of the polygon, the color with the fewest vertices defines a valid guard set with at most FLOOR(n/3) guards.

Philipp Kindermann posted YouTube lectures on the art gallery problem which dig into the problem visually.

To find the minimal number of guards, which is more than 0 and less than or equal to FLOOR(n/3), approximations must be done. I recommend a thorough reading of H. Brönnimann & M. T. Goodrich's 1995 paper.