0
$\begingroup$

You have a $2m$ by $2n$ grid of squares coloured in the same way as a standard checkerboard. Find the total number of ways to place $mn$ counters on white squares so that each square contains at most one counter and no two counters are in diagonally adjacent white squares.

Solution- Split the entire grid into $2 \times 2$ squares. The first key observation to be made is that none of these squares contain more than $1$ counter. In fact, since there are $mn$ counters, there must be exactly $1$ counter per $2 \times 2$ square. First, observe that if a counter is placed in the bottom right cell of a $2 \times 2$ square, then all counters to the right and under the cell are fixed; they must be in the bottom right position. Otherwise, we are free to decide.

Now, view the entire grid as an $m \times n$ board, where we color a square blue if it's counter is in the bottom right position, and red otherwise. Observe that the amount of ways to color this grid bijects to a path taken from the bottom left corner to the top right corner, so the answer is ${m + n \choose n}$ as requested

I don't see the bijection between the two ,pls someone guide me with this.

thankyou

$\endgroup$
4
  • 1
    $\begingroup$ Please insert here all the details (describe the bijection) instead of refering to an other post on a foreign page, that is not so easy to isolate. Please do not use abbreviations like "no of ways". (The answerer will write full words. Just respect this in advance.) Also, the question "...in the last how there is bijection between no of ways to colur the grid and going from bottom left to top right ?" makes no sense. What is "in the last how"?! $\endgroup$
    – dan_fulea
    Dec 17, 2020 at 13:11
  • $\begingroup$ @dan_fulea sorry,I will keep in mind next time,edited $\endgroup$
    – Ishan
    Dec 17, 2020 at 13:20
  • $\begingroup$ Can you add a picture? $\endgroup$
    – Burt
    Dec 17, 2020 at 13:25
  • 4
    $\begingroup$ I think the solution is saying that you will end up with a board divided into a red region and a blue region, and the boundary between the two regions forms a path from the lower left to the upper right. Try an example. $\endgroup$
    – awkward
    Dec 17, 2020 at 13:50

1 Answer 1

3
$\begingroup$

Here is an example that may make the things clear. (It is not a solution by example, but a way to visualize the solution using a special example.)

Note: In an initial version of the question, the solution was linked to

AOPS Problem + Solutions .

This page may have a shorter or longer life, but next days it will be there, so the reader may want to look at the many solutions having one common idea.


Let us build a configuration, by placing some stars on the white fields of the following empty board, already divided in $2\times2$-squares.

The fill-in-rule wants that no two (at a corner) touching white fields (from the same and/or touching $2\times2$-squares) get stars in the same time. And each $2\times2$-square has exactly one star (in a white field).

$$ \begin{array}{|cc|cc|cc|cc|cc|} \hline & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare \\ \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & \\\hline & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare \\ \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & \\\hline & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare \\ \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & \\\hline & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare \\ \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & \\\hline & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare \\ \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & \\\hline & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare \\ \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & \\\hline \end{array} $$ In this choice, the left upper corner is white. If the checker board is "the other one", just use a vertical reflection to reduce to this case (since the right upper corner is than white, so the reflection fits the above pattern).

When we use the left/upper field, than we also use the red color: $$ \begin{array}{|cc|} \hline \color{red}*& \blacksquare \\ \blacksquare & \\\hline \end{array} \text{ and abbreviate this as } \color{red}{\blacksquare} $$

When we use the right/lower field, than we also use the blue color: $$ \begin{array}{|cc|} \hline & \blacksquare \\ \blacksquare & \color{blue}* \\\hline \end{array} \text{ and abbreviate this as } \color{blue}{\blacksquare} $$


Now we will fill in first the first row only, one $2\times2$-square after the next one, starting from left to right.

A first observation is that if somewhere on this row we use the blue pattern, than all (right) following $2\times2$-squares are blue.

So the first row may be

$$ \begin{array}{|cc|cc|cc|cc|cc|} \hline \color{red}*& \blacksquare & \color{red}*& \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare \\ \blacksquare & & \blacksquare & & \blacksquare & \color{blue}* & \blacksquare & \color{blue}* & \blacksquare & \color{blue}* \\\hline \end{array} $$ and we encode it for short simply as: $$ \color{red}{\blacksquare \blacksquare }\color{blue}{\blacksquare \blacksquare \blacksquare } $$ This "simple scheme" to represent the filling is the key to the solution.


Let us fill now the first two rows, and observe the constraints. First of all we must have in the simple scheme blue under blue, i.e. $$ \color{red}{\blacksquare \blacksquare }\color{blue}{\blacksquare \blacksquare \blacksquare } \\ \color{gray}{\blacksquare \blacksquare }\color{blue}{\blacksquare \blacksquare \blacksquare } $$ and the gray squares have some choices. But each choice should give connected intervals of $\color{red}{\blacksquare}$ and of $\color{blue}{\blacksquare}$ pieces in the "simple scheme".


With this convention, the possible solution $$ \begin{array}{|cc|cc|cc|cc|cc|} \hline \color{red}*& \blacksquare & \color{red}*& \blacksquare & \color{red}*& \blacksquare & \color{red}*& \blacksquare & \color{red}*& \blacksquare \\ \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & \\\hline \color{red}*& \blacksquare & \color{red}*& \blacksquare & \color{red}*& \blacksquare & & \blacksquare & & \blacksquare \\ \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & \color{blue}*& \blacksquare & \color{blue}* \\\hline \color{red}*& \blacksquare & \color{red}*& \blacksquare & \color{red}*& \blacksquare & & \blacksquare & & \blacksquare \\ \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & \color{blue}*& \blacksquare & \color{blue}* \\\hline \color{red}*& \blacksquare & \color{red}*& \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare \\ \blacksquare & & \blacksquare & & \blacksquare & \color{blue}*& \blacksquare & \color{blue}*& \blacksquare & \color{blue}* \\\hline \color{red}*& \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare \\ \blacksquare & & \blacksquare & \color{blue}*& \blacksquare & \color{blue}*& \blacksquare & \color{blue}*& \blacksquare & \color{blue}* \\\hline & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare \\ \blacksquare & \color{blue}*& \blacksquare & \color{blue}*& \blacksquare & \color{blue}*& \blacksquare & \color{blue}*& \blacksquare & \color{blue}* \\\hline \end{array} $$ is translated in simple scheme as $$ \begin{array}{ccccc} \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare \\ \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare & \color{blue}\blacksquare & \color{blue}\blacksquare \\ \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare & \color{blue}\blacksquare & \color{blue}\blacksquare \\ \color{red}\blacksquare & \color{red}\blacksquare & \color{blue}\blacksquare & \color{blue}\blacksquare & \color{blue}\blacksquare \\ \color{red}\blacksquare & \color{blue}\blacksquare & \color{blue}\blacksquare & \color{blue}\blacksquare & \color{blue}\blacksquare \\ \color{blue}\blacksquare & \color{blue}\blacksquare & \color{blue}\blacksquare & \color{blue}\blacksquare & \color{blue}\blacksquare \end{array} $$ and the social distancing of red and blue translates further as a record or the right most red square, its column number, considered row after row.

So the above simple scheme translates as the tuple: $$ (5,3,3,2,1,0)\ . $$ There are $6$ entries, so many as the rows, and the entries are non-increasing.


Since we hate repetitions in the tuple, we will do the following new translation. Add on its last entry $\color{magenta}1$, on the forelast entry $\color{magenta}2$, and so on, $\color{magenta}3,\color{magenta}4,\color{magenta}5,\color{magenta}6$, so that the new tuple becomes $$ (5+\color{magenta}6, 3+\color{magenta}5,3+\color{magenta}4,2+\color{magenta}3,1+\color{magenta}2,0+\color{magenta}1)= (11, 8,7,5,3,1)\ . $$ This last tuple has six different entries between $1$ and $5+\color{magenta}6$.


By following this encoding process in reverse order, we observe that this makes sense (injectivity of the map), and decoding each tuple obtained from decreasingly rearranging an element of the appropriate $\binom {5+6}6$ combinations also makes sense (surjectivity of the encoding, when the codomain is made out of these combinations).


The general case works along the same lines. Just use $m,n$ instead of $6,5$.

$\endgroup$

You must log in to answer this question.

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