Ways in which $3^{rd}$ square has a side common with either of two squares in a grid

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.

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.

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$$