Posts Tagged 'Combinatorics'

The Chromatic Number of the Plane

To introduce the problem in the title, we begin with a quotation from the Foreword, written by Branko  Grünbaum, to the book by Alexander Soifer (2009): The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators:

If each point of the plane is to be given a color, how many colors do we need if every two points at unit distance are to receive distinct colors?

About 70 years ago it was shown that the least number of colours needed for such a colouring is one of 4, 5, 6 and 7. But which of these is the correct number? Despite efforts by many very clever people, some of whom had solved problems that appeared to be much harder, no advance has been made to narrow the gap

{4\le\chi\le 7}.

Continue reading ‘The Chromatic Number of the Plane’

Derangements and Continued Fractions for e

We show in this post that an elegant continued fraction for {e} can be found using derangement numbers. Recall from last week’s post that we call any permutation of the elements of a set an arrangement. A derangement is an arrangement for which every element is moved from its original position.

Continue reading ‘Derangements and Continued Fractions for e’

Arrangements and Derangements

Six students entering an examination hall place their cell-phones in a box. After the exam, they each grab a phone at random as they rush out. What is the likelihood that none of them gets their own phone? The surprising answer — about 37% whatever the number of students — emerges from the theory of derangements.

Continue reading ‘Arrangements and Derangements’

Order in the midst of Chaos

We open with a simple mathematical puzzle that is easily solved using only elementary reasoning. Imagine a party where some guests are friends while others are unacquainted. Then the following is always true:

No matter how many guests there are at the party, there are
always two guests with the same number of friends present.

If you wish, try proving this before reading on. The proof is outlined at the end of this post.

Complete-Graphs-6-10

Complete graphs with 6 to 10 vertices.

Continue reading ‘Order in the midst of Chaos’

Folding Maps: A Simple but Unsolved Problem

Paper-folding is a recurring theme in mathematics. The art of origami is much-loved by many who also enjoy recreational maths. One particular folding problem is remarkably easy to state, but the solution remains elusive:

Given a map with M × N panels, how many different ways can it be folded?

Each panel is considered to be distinct, so two foldings are equivalent only when they have the same vertical sequence of the L = M × N layers.

Continue reading ‘Folding Maps: A Simple but Unsolved Problem’

Last 50 Posts

Categories