Issue 001 Solutions

Many thanks to all readers who submitted answers to this issue’s puzzles!

 


A Linux Rebus

Tom Hebb and Harry Hochheiser both submitted the same correct solution to the pop-culture rebus from the movie Alien:

In space, no one can hear you scream

Solution Source

 


Divide By 3

An implementation can be found here and is reproduced below:

 


3 Stacks

A simple solution would be to partition the array and utilize variables corresponding to the indices in the array that are the “top” and “bottom” of each stack. However, this requires that we keep 6 auxiliary variables. A potentially more space efficient solution would be to interleave the stacks. That is, the elements of the first stack would be at indices i where i % 3 is equal to 0, the elements of the second stack would be at indices j where j % 3 is equal to 1, and the elements of the third stack would be at indices k where k % 3 is equal to 2. This algorithm allows us to use only one counter for the top of each stack, halving the additional space we need.

 


Deconstructing Triangles

To remove the minimal number of edges, we can treat the triangle as a graph. Each point where lines meet is a vertex and of course lines are edges. If we perform Breadth First Search from any arbitrary vertex, we will get a spanning tree of the graph. Any edges that are not in the spanning tree can be removed to eliminate cycles (and by extension any complete polygons in the original shape).

 


 

Sticks and Triangles

We take the length of our stick to be 1 unit, as such, we can use X to denote the location of the first break and Y to denote the location of the second break. We now know that (X, Y) is uniformly distributed on:

For the broken pieces of the stick to form a triangle, the sum of the lengths of two pieces must be greater than the length of the third. This occurs when T1T2:

This event is given by the plot below, which shows us that the total probability is 1/4.

Triangle.png

 

Solution Source

 


Thumbnail Image Provided by Maraya Rodostianos via Flickr

Sunjay Bhatia on linkedinSunjay Bhatia on instagramSunjay Bhatia on githubSunjay Bhatia on facebookSunjay Bhatia on email2
Sunjay Bhatia
Lead Editor & Web Developer.
Sunjay Bhatia is a Junior at Tufts majoring in Computer Science and minoring in Philosophy.

Leave a Reply

Your email address will not be published. Required fields are marked *