# MAT Q5 1996 Solution Verification (Combinatorics)

I have been doing some MAT past papers and I have got to papers where there is no official mark scheme. I checked on the student room but there seem to be no answers for the very old mat past papers. Here is the question I want to answer:

My solution:

a): There could be two values for each of the $$4\times4=16$$ places. Thus the total number of different arrangements is $$2^{16}$$

b): Picture the $$4$$ rows and let us consider the cases: " one $$\times$$ in each row", two $$\times$$ in each row, "three $$\times$$ in each row" and "four $$\times$$ in each row".

In the first case, we have $$(^4C_1)^4$$ different arrangements.

In the second case, we have $$(^4C_2)^4$$ different arrangements.

In the third case, we have $$(^4C_3)^4$$ different arrangements.

In the fourth case, we have $$(^4C_4)^4$$ different arrangements.

And thus the total number of different arrangements is $$=1809$$ (adding all of the above).

c): Consider the cases

$$\begin{pmatrix} \times & \text{either} & \text{either} & 0 &\\ \text{either}& \times & 0 & \text{either} & \\ \text{either} & 0 & \times & \text{either} &\\ 0& \text{either} & \text{either} & \times & \\ \end{pmatrix} \text{and} \begin{pmatrix} 0 & \text{either} & \text{either} & \times &\\ \text{either}& 0 & \times & \text{either} & \\ \text{either} & \times & 0 & \text{either} &\\ \times& \text{either} & \text{either} & 0 & \\ \end{pmatrix}$$ In each of the cases, we have $$8$$ available positions giving $$2^8$$ possible arrangements. We need only now consider the case when

$$\begin{pmatrix} \times & \text{either} & \text{either} & \times &\\ \text{either}& \times & \times & \text{either} & \\ \text{either} & \times & \times &\text{either} &\\ \times& \text{either} & \text{either} & \times & \\ \end{pmatrix}$$

in which case we have yet again $$2^8$$ different arrangements. Thus the total number of different arrangements is $$3\times 2^8=768$$

Is this correct?

EDIT: I have realised I have interpreted the question way more generally than I should have. I thought that for each position I have a nought and across available. Anyways, I would like to ask if my generalization is correct.

• a) $2^{16}$ would be the number of arrangements if there could be any number of noughts and crosses, but the question specifies $12$ and $4$ Oct 28, 2020 at 21:32
• @J.W.TannerI completely misread the question. Now I see that I have made it much, much more complicated. Well, people do say it is better to generalize... . On another note, does my work if each place could be filled by either a nought or cross? Oct 28, 2020 at 21:34
• @MathsWizzard Under the alternative assumption that you have 16 noughts and 16 crosses to choose from, so that each cell has 2 possibilities, your answer in part (a) of $2^{(16)}$ is correct. In part(b), it is unclear what you intend. Are you assuming that there must be the same # of crosses in each row? Even if there are 16 crosses, why can't row 1 have 1 cross, and row 2 have 2 crosses? Oct 28, 2020 at 21:44
• Hi, sorry. I meant under the assumption that I have 16 places to fill and infinitely many crosses and noughts. Apologies for the unclarity. Oct 28, 2020 at 21:45
• Out of curiosity, where did you find the 1996 past paper? I too am preparing for the MAT, but I can only find past papers that go back as far as 2003.
– Joe
Oct 28, 2020 at 22:08

Part (a) is wrong, because you are constrained by having only 4 crosses.

Therefore, the answer is $$\binom{16}{4}.$$

Part (b) is also wrong, for much the same reason.

There are 4 choices where to put the cross in each row.

Therefore, the answer is $$4^4.$$

Part (c) is trickier.

Going from the top down, you will have to place a cross in each row.

In the 1st row, you have 4 columns to choose from.

Having made that choice, in the 2nd row, you have 3 remaining columns to choose from.

Final answer here is $$4!$$.

Assume that crosses and noughts are unlimited.

For part (a), your answer of $$2^{(16)}$$ is correct.

Part (b) is complex. I assumed that you intended that each row has at least one cross, but that you can have a different # of crosses from one row to the next.

I got

$$2^{(16)} - \binom{4}{1}2^{(12)} + \binom{4}{2}2^8 - \binom{4}{3}2^4 + \binom{4}{4}2^0.$$

The above formula employs the principle of Inclusion-Exclusion, as discussed at https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle.

The idea is to start will all possible possible placements, deduct possible placements of all noughts in the 1st row, with the other 12 rows unconstrained, multiplying this by 4, since the blanked out row could be any of the 4 rows.

Then you add back possible ways of blanking out two rows, since this have been over-counted by previous running total. Then you continue adding and then deducting, in accordance with Inclusion Exclusion.

My answer actually agrees with Phicar's answer. This can be verified by doing binomial expansion on

$$(2^4 - 1)^4.$$

Part C.
I again used Inclusion-Exclusion, but in a much more convoluted fashion. This answer is very complicated to explain. Consider the following chart.

$$\begin{array}{| l | l c l c l c l c l |} \hline T_0 & \binom{4}{0}\binom{4}{0}\times 2^{(16)} \\[8pt] \hline T_1 & \binom{4}{1}\binom{4}{0}\times 2^{(12)} &+& \binom{4}{0}\binom{4}{ 1}\times 2^{(12)}\\[8pt] \hline T_2 & \binom{4}{2}\binom{4}{0}\times 2^{(8)} &+& \binom{4}{1}\binom{4}{ 1}\times 2^{(9)} &+& \binom{4}{0}\binom{4}{ 2}\times 2^{(8)}\\[8pt] \hline T_3 & \binom{4}{3}\binom{4}{0}\times 2^{(4)} &+& \binom{4}{2}\binom{4}{1}\times 2^{(6)} &+& \binom{4}{1}\binom{4}{2}\times 2^{(6)} &+& \binom{4}{0}\binom{4}{ 3}\times 2^{(4)}\\[8pt] \hline T_4 & \binom{4}{4}\binom{4}{0}\times 2^{(0)} &+& \binom{4}{3}\binom{4}{1}\times 2^{(3)} &+& \binom{4}{2}\binom{4}{2}\times 2^{(4)} &+& \binom{4}{1}\binom{4}{3}\times 2^{(3)} &+& \binom{4}{0}\binom{4}{4}\times 2^{(4)}\\[8pt] \hline T_5 & \binom{4}{4}\binom{4}{1}\times 2^{(0)} &+& \binom{4}{3}\binom{4}{2}\times 2^{(2)} &+& \binom{4}{2}\binom{4}{3}\times 2^{(2)} &+& \binom{4}{1}\binom{4}{4}\times 2^{(0)}\\[8pt] \hline T_6 & \binom{4}{4}\binom{4}{2}\times 2^{(0)} &+& \binom{4}{3}\binom{4}{3}\times 2^{(1)} &+& \binom{4}{2}\binom{4}{4}\times 2^{(0)}\\[8pt] \hline T_7 & \binom{4}{4}\binom{4}{3}\times 2^{(0)} &+& \binom{4}{3}\binom{4}{4}\times 2^{(0)}\\[8pt] \hline T_8 & \binom{4}{4}\binom{4}{4}\times 2^{(0)}\\[8pt] \hline \end{array}$$

Out of the $$2^{(16)}$$ possible configurations, you have to compute how many of them will have a cross in very row and also a cross in every column.

I construe the 4 rows and 4 columns as 8 "straight paths". In the chart, you will see entries that look like this:

$$\binom{4}{a}\binom{4}{b} \times 2^c.$$

In the first factor, $$a$$ corresponds to how many rows (from 0 through 4) inclusive are presumed to be filled with noughts. Similarly, in the second factor, $$b$$ corresponds to how many columns (from 0 through 4) inclusive are presumed to be filled with noughts. The $$c$$ exponent represents the # of unconstrained cells when $$a$$ rows and $$b$$ columns are presumed to be filled with noughts.

As an example, consider the following entry from row $$T_4$$:

$$\binom{4}{2}\binom{4}{2} \times 2^4.$$

If there are 2 rows and 2 columns each filled with noughts, there will automatically be 4 unconstrained cells, namely the 4 cells that are not in either of the two rows or two columns.

So the above expression indicates how many ways there are of choosing 2 rows to fill with noughts, simultaneously choosing 2 columns to fill with noughts, and allowing the remaining cells to be unconstrained.

In effect, the expression indicates that there are 36 distinct sets, each with 2 rows and 2 columns designated to be filled with noughts. Further, in each of the 36 sets, there are $$2^4 = 16$$ elements, corresponding to the possible cross/nought possibilities for the remaining (unconstrained) cells.

For $$k \in \{0,1,2,\cdots,8\},$$ the row labeled $$T_k$$ identifies all of the sets where the number of rows to be filled with noughts + the number of columns to be filled with noughts $$= k.$$

In each row, the intent is that the variable $$T_k =$$ a sum of terms, where each term has 3 factors.

The actual answer to the problem is $$T_0 - T_1 + T_2 - T_3 + T_4 - T_5 + T_6 - T_7 + T_8.$$

The fundamental idea in Inclusion-Exclusion, as I am using it, is that every unsatisfactory configuration (out of the $$2^{(16)}$$ possible configurations) will be subtracted, added back, subtracted, ... so that the net effect is that the unsatisfactory configuration is deducted once.

Consider the following example:
Rows $$1, 2,$$ and $$3$$ will be filled with noughts and columns $$1,2$$ will be filled with noughts. The 2 remaining cells will be filled with crosses. Of the $$2^{(16)}$$ possible configurations, this example, represents one of the unsatisfactory ones.

In order for the algorithm to function correctly, the net effect must be that this particular example is deducted one time from the $$2^{(16)}$$ possible configurations,

Examining the representation of this example with respect to $$T_1, T_2, \cdots, T_8$$:

• In the first term in $$T_1,$$ the example is represented 3 times, since there are three rows to be filled with noughts, Similarly, In the second term in $$T_1$$, the example is represented 2 times. Therefore, the example is represented (3 + 2 = 5) times in $$T_1$$.

• In the first term in $$T_2$$ this example is represented 3 times., This is because in this example, 3 rows are to be filled with noughts, and there are 3 different ways of selecting two out of the three rows.

Similarly, this example is represented 6 times in the second term in $$T_2$$. This is because there are 6 different ways ($$3 \times 2$$) of choosing 1 row and 1 column.

Simlarly, this example is represented once with respect to the third term in $$T_2$$.

Therefore, this example is represented (3 + 6 + 1 = 10) times in $$T_2.$$

• Using Similar analysis, this example is represented (1 + 6 + 3 + 0) = 10 times in row $$T_3$$.

• Using Similar analysis, this example is represented (0 + 2 + 3 + 0 + 0) = 5 times in row $$T_4$$.

• Using Similar analysis, this example is represented (0 + 1 + 0 + 0) = 1 time in row $$T_5$$.

• This example is not represented in any of rows $$T_6, T_7$$, or $$T_8$$. This is because those rows pertain to filling more than 5 "straight paths" with noughts, and this example represents filling only 3 rows + 2 columns with noughts.

Examining the representations for this example. the example is represented $$(5, 10, 10, 5, 1)$$ times in $$T_1, T_2, T_3, T_4,$$ and $$T_5$$ respectively. Notice that these 5 terms represent all but the first term in the 5th row of Pascal's triangle.

Although it is unclear to me exactly why this is happening, it is related to the fact that this example specifically pertains to (3 + 2 = 5) straight paths. It is easy to demonstrate that when you add - subtract - add - subtract... across any row in Pascal's triangle, where you start with the second term, the computation will equal 1. This relates to the binomial expansion of $$(1 + [-1])^k.$$

The net effect of the algorithm's computation of $$T_0 - T_1 + \cdots$$ is that this specific unsatisfactory configuration is deducted one time from the $$2^{(16)}$$ total possible configurations.

The backbone of the Inclusion-Exclusion principle, as documented in the Wikipedia article is that each region will end up being added, then subtracted, then added, ... so that the net effect is that the region is counted once.

• Hi, thank you for your answer. I have edited my question. Oct 28, 2020 at 21:37

I’m afraid that all of these are incorrect.

$$2^{16}$$ is the number of different ways to put either a nought or a cross in each of the $$16$$ positions without any restriction on the number of crosses. Here, however, we must have exactly $$4$$ crosses; there are $$\binom{16}4$$ ways to choose $$4$$ of the $$16$$ positions to get the $$4$$ crosses, and once we’ve done that, the other $$12$$ positions must be filled with noughts, so the correct answer to (a) is $$\binom{16}4=1820$$.

In (b) we must choose one position in each row. In any one row there are $$4$$ possible choices, so there are altogether $$4^4=256$$ ways to choose one position in each row to get the cross for that row.

In (c) there are $$4$$ ways to place a cross in the first row. Once that’s been done, there are only $$3$$ possible places for the cross in the second row, since it cannot lie in the same column as the cross in the first row. Similarly, once those two crosses have been placed, there are just $$2$$ possible positions for the cross in the third row, and after that there is just one possible position for the cross in the fourth row. Thus, there are $$4\cdot3\cdot2\cdot1=4!=24$$ possible arrangements of this type.

• Hi, thank you very much for the comment. I have misread the question. I have edited my original post as I would still like to know if the generalization is correct. Oct 28, 2020 at 21:40
• @MathsWizzard: Your answer to (a) is correct for that interpration. Your answer to (b) is the number of arrangements that have at least one cross and have the same number of crosses in each row. I’m not sure just what you’re counting in part (c). Oct 28, 2020 at 22:09

Put the rows in line: you get a line of $$16$$ places divided in $$4$$ sectors, then

a) $$\binom{16}{4}$$ : you can put the four $$\times$$ in every place;
b) $$4^4$$ : four choices for each sector;
c) $$4!$$ : you can chose any permutation of $$(1,2,3,4)$$ and assign as place in first, 2nd , .. sector

No.

Hints:

For the first one you are allowing more than $$4$$ crosses. So you have to choose where are the crosses out of $$16$$ possibilities.

For the second one, I am really confused in how you are arguing. Where does the power of the combinatorial comes from? Notice that you have $$4$$ choices per row. Multiplication principle gives you that...

For the third one you can not have two crosses in the same column. So here are $$4$$ choices for the first row but $$3$$ for the second one...So multiplication principle again gives you...

Edit: For the new problem, the first one is fine. The second one is not right. Notice that per row there are $$2^4-1$$ possibilities (this follows from your logic in problem 1). So you have $$(2^4-1)^4.$$
The third one is tricky cause you will have to do inclusion-exclusion. Try to do something like $$2^{16}-(4+4)*2^{16-4}+2\cdot \binom{4}{2}\cdot 2^{16-8}+4\cdot 4\cdot 2^{16-8+1}\cdots,$$ Essentially you are doing all of them and excluding when one row or one column has no crosses.

• Hi, thank you for your answer. I have edited my question. Oct 28, 2020 at 21:37
• @MathsWizzard I have edited. Oct 28, 2020 at 21:48
• @user2661923 Yes, that is why at the end I am adding two different values. First for non intersecting and then for intersecting. It becomes very tedious after that, better the OP can finish. Oct 28, 2020 at 23:42