# Problem 19

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?

$[asy] unitsize(2cm); path box = (-0.5,-0.2)--(-0.5,0.2)--(0.5,0.2)--(0.5,-0.2)--cycle; draw(box); label("+",(0,0)); draw(shift(1,0)*box); label("-",(1,0)); draw(shift(2,0)*box); label("+",(2,0)); draw(shift(3,0)*box); label("-",(3,0)); draw(shift(0.5,0.4)*box); label("-",(0.5,0.4)); draw(shift(1.5,0.4)*box); label("-",(1.5,0.4)); draw(shift(2.5,0.4)*box); label("-",(2.5,0.4)); draw(shift(1,0.8)*box); label("+",(1,0.8)); draw(shift(2,0.8)*box); label("+",(2,0.8)); draw(shift(1.5,1.2)*box); label("+",(1.5,1.2)); [/asy]$

$\textbf{(A) } 2 \qquad \textbf{(B) } 4 \qquad \textbf{(C) } 8 \qquad \textbf{(D) } 12 \qquad \textbf{(E) } 16$

## Solution 1

Instead of + and -, let us use 1 and 0, respectively. If we let $a$, $b$, $c$, and $d$ be the values of the four cells on the bottom row, then the three cells on the next row are equal to $a+b$, $b+c$, and $c+d$ taken modulo (mod) 2 (this is exactly the same as finding $a \text{ XOR } b$, and so on). The two cells on the next row are $a+2b+c$ and $b+2c+d$ taken modulo (mod) 2, and lastly, the cell on the top row gets $a+3b+3c+d \pmod{2}$.

Thus, we are looking for the number of assignments of 0's and 1's for $a$, $b$, $c$, $d$ such that $a+3b+3c+d \equiv 1 \pmod{2}$, or in other words, is odd. As $3 \equiv 1 \pmod{2}$, this is the same as finding the number of assignments such that $a+b+c+d \equiv 1 \pmod{2}$. Notice that, no matter what $a$, $b$, and $c$ are, this uniquely determines $d$. There are $2^3 = 8$ ways to assign 0's and 1's arbitrarily to $a$, $b$, and $c$, so the answer is $\boxed{\textbf{(C) } 8}$.

## Solution 2

The sign of the next row on the pyramid depends on previous row. There are two options for the previous row, - or +. There are three rows to the pyramid that depend on what the top row is. Therefore, the ways you can make a + on the top is $2^3=8$, which is C. -totoro.selsel