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:


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

Where did I make a mistake?

  • 1
    $\begingroup$ 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. $\endgroup$ – Arthur Dec 30 '16 at 19:18
  • $\begingroup$ @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). $\endgroup$ – 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$.

  • $\begingroup$ But why they are distinct they are all full black. $\endgroup$ – Taha Akbari Dec 30 '16 at 19:57
  • $\begingroup$ No: consider $\{1,\dots,8\} \times \{1\}$, for example—that's only a single column of black. $\endgroup$ – Greg Martin Dec 30 '16 at 20:01
  • $\begingroup$ But all of other cells should be colored because we have a colored cell in every column then all of them should be colored. $\endgroup$ – Taha Akbari Dec 30 '16 at 20:04
  • $\begingroup$ Well, that goes back to the fact that I'm only guessing at the problem statement (the original post has some English ambiguities). Under that interpretation, I don't see why there aren't only two possible answers (all black or all white), as Arthur commented originally. $\endgroup$ – Greg Martin Dec 30 '16 at 20:05
  • $\begingroup$ Oh yes sorry I personally get the wrong meaning. $\endgroup$ – Taha Akbari Dec 30 '16 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.