I recently came across a question that required logic and coding skills to solve. It went a little something like this:
Let there be a stick of length 1. Pick 2 points uniformly at random along the stick, and break the stick at those points. What is the probability of the three resulting pieces being able to form a triangle?
Interesting i thought. I do enjoy these types of challenges, and had fun trying to solve this problem. It took me a while to understand that the longest side (or one of the longest sides in the case of an isosceles triangle) had to be smaller than the sum of the 2 smaller sides. In pseudo code a triangle would be possible IF:
Length of longest side < sum of other 2 sides, which is true IF
Length of longest side < 0.5 (half the length of the stick)
When i saw (in my mind’s eye) me breaking a stick in half and folding it so that both pieces overlap, it became obvious that i needed one of the pieces to be longer and then break that piece into 2 pieces of any length to form a would-be triangle. As a side note, i have been hoping to create my first gif for a while and this might be a useful one to animate a stick being broken into half, folded over and then one half growing in length and then breaking into 2 and forming a triangle.
I turned to the statistical computing language R to solve my problem, knowing i could randomly draw values from a uniform distribution with the runif() function.
The function takes 3 arguments, namely;
- n – for number of observations (mandatory)
- min – for minimum value to be drawn from the distribution (optional, with default of 0)
- max – for maximum value to be drawn from the distribution (optional, with default of 1)
With 18 lines of uncommented code, i was able to generate 1 million random observations for each of the 2 random points on the stick between 0 and 1 and test the condition for forming a triangle. In other words test that the longest side is < 0.5. This took just over 1min, with most of the delay coming from line 15 where i sort each of the n number of rows. I ran the simulation 10, 100, 1k, 10k, 100k and 1m times (ie. the value for n) and noticed the higher n was the more the formula in line 31, which is the probability of forming a triangle, would converge to 25%.
My R code is below:
t1 = Sys.time() # define lower and upper bounds for the stick lb = 0 ub = 1 # randomly generate sides from a uniform distribution n = 1000000 # randomly generate n points from a uniform distribution # ran1 will be a vector of n random values for point 1 on the stick ran1 = runif(n, lb, ub) # ran2 will be a vector of n random values for point 2 on the stick ran2 = runif(n, lb, ub) # randpts will be our matrix of n point 1 and n point 2 randpts = cbind(ran1, ran2) # now to sort each row so that point 1 is lower down the stick than point 2 randpts = t(apply(randpts, 1, sort)) # every triangle has 3 sides, so # side 1 length = value of point 1 side1 = randpts[,1] # side 2 length = distance between point 1 and point 2 side2 = randpts[,2] - randpts[,1] # side 3 length = distance between point 2 and max size of stick of length 1 side3 = 1 - randpts[,2] # add the 3 sides and make sure each observation of the sum of the sides equals 1 sumsides = side1 + side2 + side3 any(sumsides != 1) # create a matrix of 1,000 rows and 3 columns for the 3 sides tripts = t(rbind(side1, side2, side3)) # compute the max side of each observation max = apply(tripts, 1, max) # what proportion of observations meets the criteria for the formation of a triangle length(which(max < 0.5) == TRUE) / length(max) t2 = Sys.time() difftime(t2,t1)
I tried sampling 1 billion observations, which worked for ran1 but i ran out of memory for ran2. Apparently my PC reached its total allocation of 8143Mb and i need to see help (memory size)…
Only way to learn is to hack.
Happy hacking!
