When he was a 5-year-old boy, Russian mathematician Andrey Kolmogorov asked questions like
How many patterns can you create with a thread while sewing on a four-hole button?
Unfortunately, there is no information on the Web what the answer is and had Kolmogorov found it himself. In a book about Grigori Perelman, author Masha Gessen admits that two professional mathematicians, both students of Kolmogorov, have given different answers.
In the beginning, I found the number of patterns in three cases where single-color thread was involved. Then I found the number of patterns in case of different-color threads where the buttonholes were located on a straight line. Now, let me explore a more realistic situation where the buttonholes are located on the vertices of a convex n-gon. In order to temporarily avoid some difficulties let me reword the Kolmogorov’s problem:
There are n cities located on the vertices of a convex n-gon. There are c types of communication lines available. Any city can be connected to any other one by only one communication line (that can be of any type). A network exists if at least 2 cities are connected by a communication line. How many different networks (p) can be built?
From our last exercise with the Kolmogorov’s button we know that the number of networks (p) depends on: a) the number of communication-line types (c) and b) the number of possible communication lines (m). In the case of a convex n-gon (with n edges and (n2-3n)/2) diagonals)
m=n+(n2-3n)/2=(n-1)n/2
Therefore, the number of networks is
p=(c+1)m-1=(c+1)(n-1)n/2-1
For example, in the case of 2 types of communication lines and 4 cities (in the language of Kolmogorov’s button problem: a button with 4 buttonholes and threads with 2 different colors), the number of different networks is
p=(2+1)(4-1)4/2-1=728
Unlike the communication lines of different type (that are unseen by the user), the differently colored threads can make different patterns when diagonals intersect (red-over-black looks different than black-over-red). This is a subject I will expand on in the future.
This is a copyrighted material. See Copyright Notice, Legal Disclaimer and Commenting Rules.
