XRDS

Crossroads The ACM Magazine for Students

Sign In

Association for Computing Machinery

Combing Three Arrays (Spring 2012)

Puzzle:

You are given three sorted arrays A, B, and C. You must find an a in A, b in B, and c in C such that a <= b <= c and c-a is minimal (or determine that no such 3-tuple exists). If we let n denote the length of the longest array, we can solve the problem trivially in O(n^3) time by trying all possible combinations. Can you find an optimal algorithm to solve the problem?

Solution:

Store one index for each array — x, y, and z — and initialize all these to zero. Also store a value called "distance", which is initialized to infinity.

Whenever A[x] <= B[y] <= C[z], we will compute C[z]-A[x], and if this value is smaller than distance, we update distance to be equal to it. Now, on each iteration increment the index pointing to the min of {A[x], B[y], C[z]}. In the worst case we will make one pass through all three arrays, giving a O(n) solution to the problem. Note that we can stop early if x becomes the upper bound of A. Bonus question: Can you find a loop invariant to prove that this algorithm is correct?

Source: Sanket Tavargeri, The Ohio State University

Number Games (Summer 2012)

Puzzle:

Two players alternatively erase some nine numbers from the sequence 1,2,...,101 until only two remain. The player that starts wins x−54 dollars from the player that plays second. Here x is the difference between the remaining two numbers. Would you rather be the first or the second player?

 

Solution:

The first player has a winning strategy. At his first turn the first player can delete numbers 47-55. The remaining numbers can now be paired up into 46 pairs (1-56, 2-57,…, 46-101). Then at every pair of turns (second player, first player) the first player has to make sure that exactly 9 of these pairs get erased. At the end of play there will be one pair left and the first player will win one dollar.

Source: The Puzzle Toad

[http://www.cs.cmu.edu/puzzle]

Grandma's Famous Cake (Fall 2012)

Puzzle:

One day, grandma baked a cake with a square top and dimensions 30cm x 30cm x 10cm. What is a simple strategy for cutting the cake into nine equal pieces? The next day, grandma baked another cake with the same dimensions. This time, she put a thin layer of icing on top and on all four sides but not on the bottom. What is a simple strategy for cutting such a cake into nine pieces such that all pieces have the same amount of cake by volume and the same amount of icing by surface area?

Solution:

Let the dimensions of the cake with a square top be s x s x h. Let p denote the number of pieces. The problem can be solved for any values of s, h and p as follows:
Cake without icing: Pieces of size (s/p) x s x h may be carved out with p-1 cuts.
Cake with icing: Identify p points on the edges of the square top that divide its perimeter into p equal lengths. For each of these p points, slice the cake vertically (from top to bottom using a knife) along the line segment joining the center of the square top to these points. To convince yourself that the resulting pieces have equal amounts of cake (by volume) and equal amounts of icing (by surface area), please see the figure attached for p = 7. Draw additional line segments from the vertices of the square top to its center. Now the top of each piece is either a triangle or the union of two triangles. Since the area of a triangle is half the product of its base and height, it is easy to see why the p pieces divide the square equally by area.

Source: MathOverflow

Visibility (Winter 2012)

Puzzle:

Which number follows in the series 10, 9, 60, 90, 70, 66?

Solution:

Solution: Forget math. Spell out the numbers in plain English, which gives you the following: ten, nine, sixty, ninety, seventy, sixty-six. The numbers are in order of how many letters are in their names. Moreover, ten is not the only number you can spell with 3 letters. There is also one, two, and six. Nine is not the only four-letter digit; there is zero, four, and five. This is a list of the LARGEST numbers that can be spelled in a given number of letter. So, what number comes next? The largest nine-letters number (not counting a possible hyphen): 96, i.e., ninety-six)

Source:  The Visibility Blog