The Broken Stick Puzzle

Recently I was watching a YouTube video in which a person was investigating the so-called Broken Stick Puzzle using GeoGebra. I realised that it would be interesting to investigate the problem using SageMath, which is what I'll demonstrate in this post. 

However, firstly let's state what this puzzle is about:

Two points are chosen independently and at random on a stick. The stick is broken at those points to form three smaller sticks. What is the probability these three sticks can form a triangle?

My first thought was that the probability would be 0.5 but that turned out to be wrong. Figure 1 shows the variables that I used in my SageMath algorithm, namely pos1, pos2, side1, side2 and side3 for the case where pos1<pos2.

Figure 1

The code runs as follows, in which the variable YES, NO and trials are used as well:

YES,NO=0,0
trials=100000
for i in [1..trials]:
    pos1=RR.random_element(0,1)
    pos2=RR.random_element(0,1)
    side1=min(pos1, pos2)
    side2=abs(pos1-pos2)
    side3=1-(side1+side2)
    if max(side1, side2, side3)>0.5:
        NO+=1
    else:
        YES+=1
print("Relative Frequency of Triangles", n(YES/trials, digits=4))
print("Relative Frequency of non-Triangles", n(NO/trials, digits=4))

 The result, for 100,000 trials, are as follows:

Relative Frequency of Triangles 0.2515
Relative Frequency of non-Triangles 0.7485

Here is the permalink to SageMathCell. Of course, this doesn't prove that the probability of forming a triangle is 0.25. However, it can be shown why the probability is 0.25. This proof is taken from this site:

This altitude theorem can be used to find an answer to a famous probability problem:  If a stick of length x is broken into three pieces, what is the probability that the three pieces can be used to construct a triangle? 

This problem is more difficult than it may originally seem because the sum of the two smaller sides of the triangle must be greater than the third side.  For instance, if the stick is broken into pieces of 2 inches, 3 inches, and 10 inches it will be impossible to construct a triangle. 

Given an equilateral triangle with altitude x, it is possible to use geometry to solve the problem.

 

Any point within the triangle can represent how the stick is broken into three pieces.  For instance, if point P is selected, that represents that the stick is being broken into pieces with length a, b, and c.  By the altitude theorem, it is known that a + b + c = x. 

In this example it would not be possible to make a triangle, because a + b < c .

To find the probability that the two smaller sides will sum to be larger than the third side it is helpful to divide the equilateral triangle into four smaller equilateral triangles, by connecting the midpoints of the sides.

  

As long as point P is selected in the middle triangle, it will be possible to create a triangle from the three pieces.  (Why?)  The probability that randomly selected P is in the middle triangle is 1/4 so the probability that a triangle can be created from breaking a stick into three pieces is 1/4.

In this proof, the "altitude theorem" referred to is better known as Viviani's Theorem. It's easy to show, using the diagram, that \(s+t+u=h\) where \(h\) is the altitude of the triangle. To do this, suppose the equilateral triangle has a side length of \(a\). Then:$$ \text{Area of Triangle }=\frac{a \times h}{2}=\frac{a \times s}{2}+\frac{a \times t}{2}+\frac{a \times u}{2}$$The 2's and a's cancel out to leave the result of the theorem.

For any interior point P, the sum of the lengths s + u + t
equals the height of the equilateral triangle.

There are variations on this puzzle. Here is one of them taken from this source:

Suppose point A is chosen first, at random, and the stick is broken at this location. Point B is then chosen at random from the longer of the two resulting sticks. What is the probability these three sticks form a triangle? 

Here is the code for this situation (permalink):

YES,NO=0,0
trials=1000000
for i in [1..trials]:
    pos1=RR.random_element(0,1)
    if pos1>0.5:
        pos2=RR.random_element(0, pos1)
        side1=pos2
        side2=pos1-pos2
    else:
        side1=pos1
        pos2=RR.random_element(0,1-pos1)
        side2=pos2
    side3=1-(side1+side2)
    if max(side1, side2, side3)>0.5:
        NO+=1
    else:
        YES+=1
print("Relative Frequency of Triangles", n(YES/trials, digits=4))
print("Relative Frequency of non-Triangles", n(NO/trials, digits=4))

The result, this time for 1,000,000 trials, is as follows:

Relative Frequency of Triangles 0.3865
Relative Frequency of non-Triangles 0.6135

Thus the likelihood of forming a triangle increases because we never break the shorter stick, as was possible in the first instance. At the moment I can't explain the numbers that have been thrown up. Here is the second variant:

Suppose point A is chosen first, at random, and the stick is broken at this location. One of the two resulting sticks is then chosen at random and split at a random location. What is the probability these three sticks form a triangle? This may sound the same as the original problem, but it isn’t!

Here is the algorithm I developed for this situation (permalink). Again it's for a million trials:

YES,NO=0,0
trials=1000000
for i in [1..trials]:
    pos1=RR.random_element(0,1)
    pos2=RR.random_element(0,pos1)
    side1=pos1
    side2=pos2
    side3=1-(side1+side2)
    if max(side1,side2,side3)>0.5:
        NO+=1
    else:
        YES+=1
    pos2=RR.random_element(0,1-pos1)
    side1=pos1
    side2=pos2
    side3=1-(side1+side2)
    if max(side1,side2,side3)>0.5:
        NO+=1
    else:
        YES+=1
YES=int(YES/2)
NO=int(NO/2) 
print("Relative Frequency of Triangles", n(YES/trials, digits=4))
print("Relative Frequency of non-Triangles", n(NO/trials, digits=4)) 

This time the results are:

Relative Frequency of Triangles 0.1730
Relative Frequency of non-Triangles 0.8270

This situation produces the least likelihood of a triangle being formed. After the first break, the shorter of the two pieces can be chosen and broken again but this is futile because the other piece is already greater than 0.5. The longer of the two pieces can also be chosen with equal probability and broken. I can't explain the numbers that have been thrown up. I'll keep investigating.

A much harder question is:

Five points are chosen independently and at a random on a stick. The stick is broken at those points to form six smaller sticks. What is the probability these six sticks can form a tetrahedron?

Here is a recent undergraduate student paper about the topic: link.

Knight Tours

I've already made several posts relating mathematics and chess. These are:

• More on the Mathematics of Chess on Thursday, 14th November 2019
• The Mathematics of Chess on Sunday, 6th January 2019
• Hogben Numbers on Wednesday, 28th November 2018
• Chess960 on Monday, 12th February 2018
• The Mathematics of Chess Pairings on Sunday, 11th February 2018

Today I turned 25983 days old and my investigation of the number 25983 revealed an interesting chess connection. Suppose we number the squares on an infinite chess board starting with 0 and then counting in an anticlockwise spiral as shown in Figure 1.

Figure 1

Suppose we devise a Knight Tour such that the Knight starts on square 0 and then moves always to the unvisited square closest to the origin. "Closest to the origin" is meant in the sense of Euclidean distance, and in case of a tie, the square coming earliest on the spiral is chosen.

On the first move, the Knight could move to squares 9, 11, 13, 15, 17, 19, 21 or 23. All these squares are the same distance from the 0 square but 9 is chosen because it comes first in the spiral. From 9, subsequent squares are 2, 5, 8, 3, 6, 1, 4, 7, 10, 13 and so on. 

These numbered squares form OEIS A326924:

A326924

Squares visited by a knight on a spirally numbered board, moving always to the unvisited square closest to the origin.

Figure 2 shows a slightly different depiction of the squares with more squares viewable:

Figure 2

The initial terms are of the sequence are:

0, 9, 2, 5, 8, 3, 6, 1, 4, 7, 10, 13, 28, 31, 14, 11, 26, 23, 44, 19, 22, 43, 40, 17, 34, 37, 18, 15, 32, 29, 52, 25, 46, 21, 76, 47, 50, 27, 12, 33, 16, 39, 20, 45, 24, 51, 48, 77, 114, 73, 70, 105, 38, 35, 60, 93, 30, 53, 84, 49, 78, 115, 74, 41, 68, 103, 36, 61, 94, 57, 54, 85, 124, 81, ...

What's really interesting about this tour is that the knight gets trapped at the 22325th move, where it can't reach any unvisited square. The square on which the Knight is stuck is 25983!

So nothing in this post of deep mathematical significance but it always strikes me as fascinating how numbers can be associated with such diverse phenomena. In this case, it is a Knight's tour of an infinite, spirally numbered chessboard.

For information on other Knight tours visit https://oeis.org/wiki/Knight_tours. 

On the Randomness of Pi's Digits

Much has been written about the randomness of the \(\pi\)'s digits but usually in the context of the decimal number system. Looking at \(\pi\) in terms of the binary number system however, introduces a simplification that can be exploited to investigate its randomness.

The first ten decimal digits of \(\pi\) are 3.141592654 which is represented in binary as:

11.00100100001111110110101010001000100

SageMathCell enables us to examine the first one million decimal digits of \(\pi\), convert these to binary and then graph the cumulative balance between the number of 0's and 1's. The first two 1's are ignored and only the 0's and 1's following the decimal point are considered. Figure 1 shows the result:

Figure 1

Figure 2 shows the code that I used to generate this graph:

Figure 2: permalink

How does this graph compare to that of a sequence of randomly generated 0's and 1's? It's easy enough to undertake this comparison. To this end, I looked at a string of three million randomly generated 0's and 1's because this is approximately the number of binary digits resulting from the conversion of one million decimal digits. The result is shown in Figure 3. Of course, successive repetitions of this algorithm will produce different graphs whereas the graph for \(\pi\) will be always the same. However, it's the general form of the two graphs that I want to compare.

Figure 3: permalink

Figure 4 shows the code that was used to produce this result.

Figure 4: permalink

Not surprisingly, the form of the two graphs is very similar. The point of the exercise is that the conversion of \(\pi\) to binary digits provides an easy visual comparison of its digits with randomly generated 0's and 1's.

ADDENDUM: March 17th 2021

There are of course many interesting facts concerning \(\pi\). Here are some of them:

• The number pi is literally infinitely long. But the number 123456 doesn’t appear anywhere in the first million digits of \( \pi \). It is a bit shocking because if a million digits of \( \pi \) don’t have the sequence 124356, it definitely is the most unique number. Source.
  
  
• Did you know there is actually an entire language based entirely on \( \pi\)? Called Pilish, the numbers of letters in successive words match the digits in \(\pi\). Mike Keith, a devoted Pilish-lover, even wrote an entire book in Pilish called "Not a Wake." The rules of the language and its variants are described here.
  
  
• Rivers bend to \( \pi\): The way a river meanders is described by its sinuosity; the length of its winding path divided by the distance from the source to the ocean as measured in a straight line. Strange as it may be, the average river has a sinuosity of around 3.14, according to the journal Science. Source.

If you hold a mirror to a circle, it looks like a circle. If you hold a mirror up to 3.14, it spells PIE! See Figure 2.

Figure 2: source

Someone has developed a search engine that can be used to find digit sequences in \( \pi \) in the first \(2 \times 10^0 \) digits of \pi. Figure 3 shows the output if 123456789 is input.

Figure 3

Pressing the next link bring brings up what is shown in Figure 4:

Figure 4

      

The site can also be used to find positions of e, \(\sqrt{2} \) and \(\phi\) where SageMath for example struggles with one million decimal places.

Here is a GeoGebra link that will allows the user to use a slider to display decimal places of \(\pi\).