Thanic Nur Samin wrote:$\text{Problem 6:}$
Each square of a $2^n - 1 \times 2^n - 1$ square board contains either $+1$ or a $-1$. Such an arrangement is deemed successful if each number is the product of its neighbours. Find the number of successful arrangements.
Solution to problem 6
First, lets define some terms.
1. A arrangement with at least one $-1$ will be called a nontrivial arrangement.
2. A arrangement that remains unchanged when its reflected by its middle column will be called vertically symmetric. Similarly, horizontally symmetric is defined.
3. A arrangement that is both vertically and horizontally symmetric will be called bisymmetric.
Now, we have to prove some lemmas.
Lemma 1: A nontrivial bisymmetric arrangement has all $1$'s on its middle row and middle column.
Proof: We prove for rows. Due to symmetry and the problem statement, the center cell must contain $1$.
Now, if the cell directly next to the center cell has a $1$, then its clear that the whole row must contain $1$ and we are done.
Now, assume that the cell directly next to the center cell has a $-1$. Some speculation and simple logic tells us that then it would go like $1,-1,-1,1,-1,-1\ldots 1,-1,-1$. But that would imply that $3|2^{n-1}$. Impossible. So we are done.
Lemma 2: If there exists a nontrivial vertically assymetric arrangement, there exists a nontrivial vertically symmetric arrangement.
Proof: Reflect the arrangement wrt the middle column, and multiply the overlapping numbers. We are done.
Lemma 3: If there exists a nontrivial arrangement, then there exists a nontrivial bisymmetric arrangement.
Proof: Its an obvious consequence of lemma 2.
Now we are ready to solve the problem. We claim that there exists $2$ arrangements for $n=1$ and only one arrangement, namely the trivial arrangement for $n>1$. We use induction. The $n=2$ case is easy to prove. Now, assume that its true for $n-1$.
If there exists a nontrivial arrangement for $n$, then there exists a nontrivial bisymmetric arrangement for $n$. But the middle row and middle column divides the board into four parts of size $2^{n-1}-1\times 2^{n-1}-1$. Because the middle row and column only contains $1$s, There exists a nontrivial arrangement for $n-1$. But thats not true. So, by induction, for all $n>1$, there exists only one successful arrangement. [Proved]
First, lets define some terms.
1. A arrangement with at least one $-1$ will be called a nontrivial arrangement.
2. A arrangement that remains unchanged when its reflected by its middle column will be called vertically symmetric. Similarly, horizontally symmetric is defined.
3. A arrangement that is both vertically and horizontally symmetric will be called bisymmetric.
Now, we have to prove some lemmas.
Lemma 1: A nontrivial bisymmetric arrangement has all $1$'s on its middle row and middle column.
Proof: We prove for rows. Due to symmetry and the problem statement, the center cell must contain $1$.
Now, if the cell directly next to the center cell has a $1$, then its clear that the whole row must contain $1$ and we are done.
Now, assume that the cell directly next to the center cell has a $-1$. Some speculation and simple logic tells us that then it would go like $1,-1,-1,1,-1,-1\ldots 1,-1,-1$. But that would imply that $3|2^{n-1}$. Impossible. So we are done.
Lemma 2: If there exists a nontrivial vertically assymetric arrangement, there exists a nontrivial vertically symmetric arrangement.
Proof: Reflect the arrangement wrt the middle column, and multiply the overlapping numbers. We are done.
Lemma 3: If there exists a nontrivial arrangement, then there exists a nontrivial bisymmetric arrangement.
Proof: Its an obvious consequence of lemma 2.
Now we are ready to solve the problem. We claim that there exists $2$ arrangements for $n=1$ and only one arrangement, namely the trivial arrangement for $n>1$. We use induction. The $n=2$ case is easy to prove. Now, assume that its true for $n-1$.
If there exists a nontrivial arrangement for $n$, then there exists a nontrivial bisymmetric arrangement for $n$. But the middle row and middle column divides the board into four parts of size $2^{n-1}-1\times 2^{n-1}-1$. Because the middle row and column only contains $1$s, There exists a nontrivial arrangement for $n-1$. But thats not true. So, by induction, for all $n>1$, there exists only one successful arrangement. [Proved]