This puzzle was inspired by a lovely result called the “cycle lemma,” first described by Aryeh Dvoretzky and Theodore Motzkin in their 1947 paper, “A problem of arrangements.” (Duke Mathematical Journal, 14(20), pp: 305-313). You can also learn about the cycle lemma in this fun video.

Let’s play a different version the game, using left parentheses “(“ and right parentheses “)” from algebra class.

Arranging Parentheses

In any valid algebraic expression, each left parenthesis is meant to be matched with a right parenthesis to its right. For example, in this string of six symbols, three parentheses of each kind,( ( ) ( ) )there are two inner-most pairs that match—a left parenthesis with a right parenthesis immediately to its right—and when they are taken away (“annihilate”), they leave an outermost pair that also match, and so also annihilate. This means that the initial expression was algebraically valid.

( ( ) ( ) ) à  ( _ _ _ _  )   à  Gone!

The string( ) ) ( ) (is algebraically invalid. If we annihilate each left parenthesis with a right parenthesis to its immediate right, we are left with ) ( , which is invalid algebraically, and fails to annihilate.

             ( ) ) ( ) (    à   _ _ ) _ _ (    à  Stuck!

Can you see that the expressions ( ( ) ) ( ) ( ( ) ) ( ) and ( ( ) ( ) ( ( ) ( ) ) ) are each algebraically valid?

There is 1 way to arrange one left parenthesis and one right parenthesis in an algebraically valid way:( ).There are 2 ways to appropriately arrange two left parenthesis and two right parentheses: ( ) ( ) and ( ( ) ) .There are 5 ways to arrange three left parenthesis and three right parentheses: ( ) ( ) ( ) , ( ( ) ) ( ),   ( ) ( ( ) ),  ( ( ) ( ) ), and ( ( ( ) ) ) ,and 42 ways to arrange four left parentheses and four right parentheses in a valid manner. (Care to write them all out?)

Counting the number of algebraically valid sets of left and right parentheses leads to a famous sequence of numbers in mathematics called the Catalan Numbers: 1, 1, 2, 5, 14, 42, 132, 429, 1430, … . (Some people might also say that there is 1 way to arrange zero parentheses, namely, to leave the page blank!)

During the 18^th- and 19^th- centuries several mathematicians noticed the same sequence of numbers arising in different contexts. Belgian mathematician Eugene Catalan (1814-1894) counted the number of different ways to divide a regular polygon into triangles by drawing non-intersecting lines that connect corners of the polygon. (There are 2 ways to so divide a square, 5 ways to divide a pentagon, and 14 ways to divide a hexagon. Try it!) His name became attached to the sequence.

There is a formula for the nth Catalan number. It’s (2n)! divided by the product of (n+1)! and n!. Here 1! = 1 and 2! = 2x1 = 2 and 3! = 3x2x1 = 6 and 4! = 4x3x2x1 =24, and so on. If you are up for it, you can see a derivation of this formula in the video mentioned.

Connection to the Big Bang Puzzle

In the matter/antimatter particle puzzle of the animation, each place you could stand in the ring that leaves you as the last particle standing leads to a valid algebraic expression of left and right parentheses. How? Look to your right and read each matter particle as a left parenthesis and each antimatter particle as a right parenthesis. And conversely, any valid algebraically valid string of left and right parentheses can be bent into a ring of symbols for which, regarding each left parenthesis as a particle of matter, each right one as a particle of matter, and standing in the space between the original ends of the string, provides a safe spot to stand. This connection between the game of the animation and arrangements of parentheses in algebra class is lovely.

Here’s an example to show how you can play the Big Bang puzzle with parentheses.

Consider this algebraically valid string of four left parentheses and four right parentheses.

( ( ) ) ( ) ( ) 

At the blow of a whistle, each left parentheses “(“ with a right parentheses “)” immediately to its right will annihilate with that right parentheses. The whistle blows again, and the game is repeated. All the parentheses are annihilated after two blows of the whistle. (Do you see this?)

You are a left parentheses ( and can insert yourself in any of the nine spaces around the eight symbols: at the leftmost position, at the rightmost position, or at any of the seven positions between two symbols.

When the game is played with the repeated blow of the whistle, you want to be the last symbol standing. Of the nine options, do you see that four of them are “safe” for you to stand?

Do you see that his arrangement of parentheses offers just two safe spots for a left parenthesis to stand?( ( ) ( ( ( ) ) ) )

An Additional Puzzle

Write down an arbitrary string of three left parentheses and three right parentheses, not worrying whether or not it is algebraically valid. For example, I’ll write

                            ) ) ( ( ( ).

In my example, I can see there is a spot between two symbols that, if I were to switch the left and right parts of the string around that spot, the result would be an algebraically valid expression.

) )  ( ( ( )   à switch à  ( ( ( ) ) )

As another example, try fixing the following with a switch of two parts.

( ( ) ( ) ) (  )  )  ( 

Do you see just moving the final left parenthesis to the front does the trick: ( ( ) ( ) ) ( ) )  (   ?

Question: Is it always the case that in any string of an equal number of left parentheses and right parentheses it is possible to split the string into two parts and switch those parts to obtain an algebraically valid string? (If the string is already algebraically valid, no switch would be needed.)

(Do you see that this question is really a “where is it safe to stand” issue again?)

Next Section »