0
$\begingroup$

In an $8\times 8$ square grid we randomly choose $3$ of the $64$ unit squares. If two of these share a side, then the number of ways such that the third does not share a side with either of the first two, is

What I tried : Here out of $3$ squares, we must have two squares consecutive meaning, two squares chosen must be side by side.

For each row or column, we have $7$ possibilities. So ways in which two squares are consecutive is $7\cdot 8+7\cdot 8=112$

But I did not understand how to find number of ways such that $3^{rd}$ chosen square does not have a side common with either of these two consecutive squares.

Please help me. Thanks.

$\endgroup$

2 Answers 2

2
$\begingroup$

Let's call the squares with which a chosen square can share edge with, its neighbor. Note that depending on its location, the number of neighbors will vary. A corner square will have two neighbors, a square on edge will have three and a square somewhere in the middle will have four. This suggests casework.

You derived number of pairs of consecutive squares correctly - 112 pairs. Let's break it into cases :

  • 8 pairs in corner, each having 3 neighbors
  • 20 pairs on edges, aligned along the border. Each has 4 neighbors.
  • 24 pairs on edges, perpendicular to the border. Each has 5 neighbors.
  • 60 pairs in middle, each having 6 neighbors.

Now to choose 3rd square such that it is not a neighbor, subtract from 64, number of neighbors in each case and then subtract further 2, because we can't select from already chosen pair. This gives

  • $8\times(64-3-2)$
  • $20\times(64-4-2)$
  • $24\times(64-5-2)$
  • $60\times(64-6-2)$

which should sum to final answer.

$\endgroup$
1
$\begingroup$

It can also be done with complimentary counting. Take all the ways to choose $3$ squares so that at least two share a side, then subtract the ways where all three are connected.

Instead of choosing $3$ identical squares, it helps to choose three squares labeled A, B, and C, and then divide by $3!$ in the end. Let us first count the number of ways where $A$ and $B$ share a side. The domino $AB$ can be placed in $2\times 2\times 7\times 8$ ways (why? Don't forget $AB$ is different than $BA$). Then, square $C$ can be placed in $62$ ways. We then multiply by $3$ to also include the ways $AC$ and $BC$ can be adjacent. So far, we are at $$ 2\times 2\times 7\times 8\times 62\times 3 $$ and we must now subtract the ways where all three squares are joined. In fact, each must be subtracted twice; for example, the arrangement where $A,B,C$ are all adjacent in the left of the first row was counted once when counting arrangements where $A$ is next to $B$, and once when counting arrangements where $B$ is next to $C$.

Arrangements with all three joined come in two flavors; three in a row, and an "L" shape. The number of ways to choose $A,B,C$ in each shape is:

  • for three in a row, $2\times 8\times 6\times 3!$ (why?),
  • for an "L" shape, $4\times 7\times 7\times 3!$ (why?).

Therefore, the number of ways is $$ \frac1{3!}\big(2\times 2\times 7\times 8\times 62\times 3-2(2\times 8\times 6\times 3!+4\times 7\times 7\times 3!)\big)=6360 $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .