# ways to color black a $8*8$ square that all of the $1*1$ square that are in the same line or column with a $1*1$ black should be colored?

ways to color black a $8*8$ square that all of the $1*1$ square that are in the same line or column with a $1*1$ black should be colored?

My attempt:Except the all $8$ lines colored and non of the lines colored we can color $1,2,3,\dots ,7$ columns which gives us the answer:

$(\binom{8}{1}+\binom{8}{2}+\dots+\binom{8}{7})(\binom{8}{1}+\binom{8}{2}+\dots+\binom{8}{7})+2=(2^8-2)(2^8-2)+2=64518$

But the book gives the answer $65026$ which is equal to $(2^8-1)(2^8-1)+1$.

Where did I make a mistake?

• I don't understand. If you start with a white grid, and you colour one cell black, all other cells in that same column should be black. But then all other cells are in the same row as one of the black cells from that column, so they should be black too. Therefore, I can find two ways of doing it: all white or all black. – Arthur Dec 30 '16 at 19:18
• @Arthur So I wrote two because of all black or all white.More explain:assemble that one of the row is colored because of the cells then that sells can make $254$ ways to color(without counting the all black case). – Taha Akbari Dec 30 '16 at 19:34

I'm going to make an educated guess that the question is the following: How many ways are there to blacken some squares on an $8\times8$ board, in such a way that if a square has a black square in its row and a black square in its column then it too is black? We quickly see that this is equivalent to: How many subsets of $\{1,\dots,8\}\times\{1,\dots,8\}$ are of the form $A\times B$ for some $A,B\subseteq \{1,\dots,8\}$?
The intended solution would then be: if either $A$ or $B$ is empty, then $A\times B=\emptyset$, which should only be counted once. Otherwise, distinct $A$ or distinct $B$ yields distinct $A\times B$. Since there are $2^8-1$ distinct nonempty $A$ and the same for $B$, the total number of nonempty subsets of the form $A\times B$ is $(2^8-1)(2^8-1)$, hence the total number of (possibly empty) subsets is $(2^8-1)(2^8-1)+1$.
My guess is that you mistakenly thought that the cases $A=\{1,\dots,8\}$ or $B=\{1,\dots,8\}$ were also special cases that should be combined like the empty-set case (that would yield $(2^8-2)(2^8-2)+2$). But $A=\{1,\dots,8\}$ doesn't mean that $A\times B$ is the whole board; indeed, all the $\{1,\dots,8\}\times B$ are distinct for distinct $B$.
• No: consider $\{1,\dots,8\} \times \{1\}$, for example—that's only a single column of black. – Greg Martin Dec 30 '16 at 20:01