9
$\begingroup$

The question is:

How many ways can you arrange six $X$s in the given figure so that each row has at least one $X$?

enter image description here

(Image taken from the same question from Math Exchange.)

My solution: To have $3$ $X$s in $3$ rows, there are $2 \cdot 4 \cdot 2$ ways to place them. Now there remain $5$ places more and we have $3$ $X$s remaining. So to fill the remaining places, there are $C^5_3$ ways. So total number of ways $= 16 \cdot 10 = 160$. But the answer is $26$. Where am I wrong? Thank you.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Just to clarify. So you are supposed to put the 'X's inside of the squares and each square can only contain a single 'X' and the 'X's all look the same?? $\endgroup$ – Ove Ahlman Nov 16 '17 at 8:27
  • 7
    $\begingroup$ There are $8$ cells, so $6$ will have X's and $2$ will be blank. There are $\binom82=28$ ways to place the $2$ blanks. But we don't want a whole row of blanks, i.e., we can't have both blanks on the top row or the bottom row. That rules out $2$ of the $28$ configurations. The final answer is $28-2=26.$ $\endgroup$ – bof Nov 16 '17 at 8:34
  • $\begingroup$ @Ram Isn't this a R.D. Sharma (JEE Maths) question? Just brought back old memories :) $\endgroup$ – bat_of_doom Nov 16 '17 at 18:50
13
$\begingroup$

You are overcounting the arrangements. For example, by choosing three $X$s in the three rows and then filling the remaining places with three $x$s, we consider the following equivalent arrangements as different

 Xo    Xo    Xo    Xo
Xxxx  xXxx  xxXx  xxxX 
 Xo    Xo    Xo    Xo

Note that we have $\binom{8}{6}$ ways to place six $X$s in the eight cells. From this number we subtract $2$, the ways to have a row empty (the first and the third): $$\binom{8}{6}-2=\frac{8\cdot 7}{2}-2=28-2=26.$$

|cite|improve this answer
$\endgroup$
  • 4
    $\begingroup$ This answer would be better if you gave a more detailed explanation of why the OP's solution is wrong, rather than simply giving your own solution. $\endgroup$ – jwg Nov 16 '17 at 11:13
  • 2
    $\begingroup$ @jwg Is it better now? $\endgroup$ – Robert Z Nov 16 '17 at 11:39
11
$\begingroup$

The problem with your solution is that you count a lot of the combinations twice. For instance, if we first add

 xo
xooo
 xo

and then add the rest of the three to form

 xo
xxxx
 xo

it is the same as starting with 

 xo
ooxo
 xo

and then adding the rest of the x to form 

 xo
xxxx
 xo

Now instead of doing the difficult thing and removing the duplicates of your solution do it like this: Just place all x. This can be done in $8 \choose 6$ ways. However when we fill the top row and the middle row, or the bottom row and the middle row, there is one row without an x. Thus we have to subtract $2$. Hence the solution is ${8 \choose 6 } - 2 = 26$.

|cite|improve this answer
$\endgroup$

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.