Consider the sixteen tiles fixed on a wall as shown below. How many ways are there to write either or on each tile so that the product of the two numbers written on every neighboring pair of tiles (sharing a common side) is always ?

Consider the sixteen tiles fixed on a wall as shown below. How many ways are there to write either or on each tile so that the product of the two numbers written on every neighboring pair of tiles (sharing a common side) is always ?

When or is written on each tile in such a way that the product of the two numbers written on every neighboring pair of tiles is always , we'll call the status a z-pattern. First, we prove a couple of lemmas.
Lemma 1. Let be the number of z-patterns for tiles laid in a row. Then
for all , where is the -th Fibonacci number defined by , , and for all .
Proof. We prove by induction on . It is clear that the lemma holds for and . Assume the lemma for all , , where . If is written on the tile at one end, then any number ( or ) can be written on the next tile and hence there are such z-patterns. If is written there, then should be written on the next tile and hence there are such z-patterns. Thus we get
which proves the lemma.
Lemma 2. Let be the number of z-patterns for tiles fixed on a wall in a ring shape. Then
for all .
Proof. Let and choose any tile among the tiles fixed on a wall in a ring shape. If is written on the tile, then any number can be written on the neighboring tiles and hence there are such z-patterns. If is written on the tile, then should be written on the neighboring two tiles and hence there are such z-patterns. Thus we get
which proves the lemma.
We now return to the problem. Consider the tiles in the center. Observe that the number of 's that can be written on these four tiles equals , or .
Case 1) Four 's:
We may apply Lemma 2 to the tiles surrounding the four tiles in the center because any number can be written on the tiles. Therefore, the number of z-patterns in this case equals
Case 2) Three 's:
In each of the four subcases, only can be written on two neighboring tiles of the tile marked by . For the remaining tiles, it is clear that the number of z-patterns equals to . Therefore, the total number of z-patterns in this case equals
Case 3) Two 's:
In each of the two subcases, only can be written on four neighboring tiles of the two tiles marked by . For the remaining tiles, it is clear that the number of z-patterns equals to . Therefore, the total number of z-patterns in this case equals
Combining the three cases, the answer is: .