Sign Pyramid - AMC 8 2018 Problem 19

Big idea - stabilization

In a counting problem, you may need to stabilize the number of cases. This means, by letting some of the variables change, one may fix the remaining cases.

This is the central idea in the following problem from American Mathematical Contest 8 (AMC 8, 2018, Problem 9).

Problem

In a sign pyramid a cell gets a "+" if the two cells below it have the same sign, and it gets a "-" if the two cells below it have different signs. The diagram below illustrates a sign pyramid with four levels. How many possible ways are there to fill the four cells in the bottom row to produce a "+" at the top of the pyramid?

Sequential Hints

(How to use this discussion: Do not read the entire solution at one go. First, read more on the Key Idea, then give the problem a try. Next, look into Step 1 and give it another try and so on.)

Hint 1

Start from the top! Fix the + sign at the top of the pyramid and try filling in the second row from left. Do you see any pattern?

(What happens if you plugin a + sign in the left most block of second row from top?)

Hint 2

If we fix a + sign in the left most block of second row from top, the other box must contain a + sign. (Why?)

On the other hand fixing a - sign in the left most block of second row from top will force the remaining block to contain - sign.

Thus by varying the left most block of the second row, we can fix the entire row.

Will this work for the third row?

Hint 3

In fact the same trick will work for third row.

Try this. Fix a plus sign in the first row. Then fix second row as well ( plus, plus or minus, minus).

Then try to plugin some sign in the third row's first block. And check that the remaining two blocks get automatically fixed. This is precisely known as stabilization.

Final Hint

Thus, we should only worry about the first block of second, third and fourth. Fixing them fixes the entire row.

There are 2 choices for the first block of second row, 2 choices for first block of third row and 2 choices for first block of third row. Hence in total we have \( 2 \times 2 \times 2 = 8 \) cases.

Principles and Techniques in Combinatorics Kindle Edition by Chen Chuan-Chong

Try chapter 1.