Combi Solution Writing Threadie

For discussing Olympiad Level Combinatorics problems
User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am
Re: Combi Solution Writing Threadie

Unread post by Thanic Nur Samin » Thu Feb 23, 2017 6:09 pm

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]
While the solution isn't mine, I did the write-up. Critisims will be appreciated.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Post Reply