Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In how many ways three white square can be selected on a 8 * 8 chessboard such that no two squares are in same row or column.

I am not able to reach on a conclusion for three squares. I have solved the problem for 2 squares.

Please help me out and if possible provide a detailed explanation.

share|improve this question
add comment

4 Answers 4

up vote 3 down vote accepted

Assume that $(0,0)$ is a white square. Call a white square even if it has even coordinates and odd, if it has odd coordinates; there are $4^2=16$ of each. The first square you can choose in $32$ ways; assume you pick an even one. The second square either is even, and there are $3^2=9$ left of these, or it is odd, and there are still $16$ of these. In the first case for the third choice $2^2=4$ even and $16$ odd squares remain, in the second case $9$ even and $9$ odd squares remain. Since the order in which the squares are selected is irrelevant there are $${32\bigl(9\cdot(4+16)+16\cdot(9+9)\bigr)\over 6}=2496$$ possibilities in all.

share|improve this answer
add comment

Let's first choose the three columns. There are four cases,

  1. all columns even
  2. two columns even, one odd
  3. one column even, two odd
  4. all columns odd

It either of cases (1) and (4), we have four rows we could choose for the lowest numbered column, three for the next lowest numbered column, and two for the highest numbered column. This gives $$ 2\cdot\binom{4}{3}\cdot(4\cdot3\cdot2) $$ selections.

Now look at case (2). We have four row choices for the lower even column, and three for the higher even column. We have four row choices for the odd column. Case (3) is similar, so we get $$ 2\binom{4}{2}\binom{4}{1}\cdot(4\cdot3\cdot4) $$ selections.

share|improve this answer
add comment

First one can be placed in $8^2$ ways, given it second one can be placed in $7^2$ ways, given the first two third one can be placed in $6^2$ ways. Divide by $3!$ to account for the fact that the points could have been picked in any order. So total number of ways = $\frac{8^2.7^2.6^2}{3!} = 18816$

EDIT: Sorry did not realize it was a chessboard. Way to do it here would be to notice that once you choose parity of column you also choose parity of row of white square. So a square with odd row parity will never clash with square with even row parity. Now, either all three squares have same row parity or one is different from other two. In both cases we basically have disjoint instances of smaller problems like what I had earlier solved it as. In first case, number of ways = $\frac{4^2.3^2.2^2}{3!} = 96$. In second case, number of ways = $\frac{4^2.3^2}{2!} * \frac{4^2}{1!}= 72 * 16 = 1152$. So total = $1152+96=1248$. Now just notice that both of these cases can happen in two ways for two row parities, eg. for the first one it can be all odd row parities or all even row parities. So we need to double this to get $2 * 1248 = 2496$.

share|improve this answer
    
Dennis's method works also as long as you realize that after you get the 3x3 grid you can only choose the points in a way which corressponds to a permutation of 3 elements. So we get the last factor as 3! instead of $9 \choose 3$. –  Wonder May 9 '12 at 10:24
1  
All the squares have to be white, so you don't have $64$ choices for the first one. You have 32 choices for the first square, then 25 for the second (7 white squares are in the same row or column as the one you chose). But then how many squares are left to choose the third one from depends on how you chose the second one (specifically on whether the row/column it's in meets the row/column of the first square chosen in a black or a white square). –  Matt Pressland May 9 '12 at 10:26
    
Oops, didn't realize it was a chessboard, thought it was all white. Will edit. –  Wonder May 9 '12 at 10:33
    
Nice answer! Thanks for pointing out the problem with my (now deleted to avoid clutter) answer also - I thought it was an attractive idea but unfortunately it wasn't to be! –  Matt Pressland May 9 '12 at 11:01
add comment

Here's a computational solution. We can generate all such triples using this code in GAP:

S:=Filtered(Tuples([1..8],2),c->(c[1]+c[2]) mod 2=0);
T:=Filtered(Combinations(S,3),i->i[1][1]<>i[2][1] and i[1][1]<>i[3][1] and i[2][1]<>i[3][1] and i[1][2]<>i[2][2] and i[1][2]<>i[3][2] and i[2][2]<>i[3][2]);

This code gives 2496 triples of white squares, as per Wonder and Will Orrick's answers.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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