Counting and Arrangements

Problems

Solutions

Solution: PRMO 2013, Q4

Put $X$ at the origin of a number line and $Y$ at $10$. The point $Z$ is at distance $3$ from $X$, so it is at $3$ or at $-3$, and correspondingly $$YZ = 10 - 3 = 7 \qquad \text{or} \qquad YZ = 10 + 3 = 13.$$ Both are genuinely possible, since nothing in the question orders the three points. The product is $$7 \times 13 = 91.$$

Answer 91

Solution: PRMO 2015 Part A, Q5

A cube has $8$ vertices, and a line segment with both endpoints at vertices is determined by which pair of vertices it joins. Different pairs give different segments, and every pair gives one. So the number of segments is $$\binom{8}{2} = \frac{8 \times 7}{2} = 28.$$

Students sometimes hesitate here, wondering whether the twelve edges, the face diagonals and the space diagonals should be counted separately and added. They can be, and it is a useful check: $12$ edges, $2$ diagonals on each of $6$ faces giving $12$, and $4$ space diagonals, for a total of $12 + 12 + 4 = 28$. The two routes agree, which is what one wants from a counting problem.

Answer 28

Solution: IOQM 2024, Q2

The number uses each of $1, 2, 3, 4$ exactly once, and it is odd precisely when its last digit is $1$ or $3$. That is $2$ choices. The other three digits then occupy the first three places in any order, which can be done in $3! = 6$ ways.

So the count is $2 \cdot 6 = 12$.

Answer 12

Solution: PRMO 2012, Q6

Choosing the two correctly delivered letters can be done in $\binom52 = 10$ ways. The remaining three letters must go to the remaining three houses with none of them correct, and there are exactly two ways to do that. Label those houses $A,B,C$, with each letter named for its proper house. If letter $A$ goes to $B$, letter $B$ must go to $C$ and letter $C$ to $A$. If letter $A$ goes to $C$, the other direction is forced: $$A\to B\to C\to A \qquad\text{or}\qquad A\to C\to B\to A.$$

So the number of ways is $$10 \times 2 = 20.$$

Note that “exactly two” is what makes this finite and small: had the question said “at least two”, the count would run over the other cases too.

Answer 20

Solution: PRMO 2013, Q5

A pair of different colours is one red and one green, or one green and one blue, or one blue and one red. With $n-1$ red, $n$ green and $n+1$ blue balls, $$(n-1)n + n(n+1) + (n+1)(n-1) = \left(n^2 - n\right) + \left(n^2 + n\right) + \left(n^2 - 1\right),$$ which is $3n^2 - 1$. The two linear terms cancel, which is the tidy part of the arrangement.

Setting $3n^2 - 1 = 299$ gives $n^2 = 100$ and $$n = 10.$$

Answer 10

Solution: PRMO 2017, Q21

Since $108 = 2^2 \cdot 3^3$, giving an ordered triple $(a,b,c)$ with $abc = 108$ means deciding how many of the two factors of $2$ go to each of $a$, $b$, $c$, and likewise for the three factors of $3$. The two decisions are independent.

For example, allocating the two factors of $2$ as one to $a$, one to $b$ and none to $c$ can be shown by two stars separated into three groups: $$\underbrace{\star}_{a}\mid\underbrace{\star}_{b}\mid\underbrace{\phantom{\star}}_{c}.$$ Placing the two bars among the four star-or-bar positions gives the six possible allocations, including empty groups. Distributing $2$ identical items into $3$ labelled boxes can be done in $\binom{2+2}{2} = 6$ ways, and $3$ identical items in $\binom{3+2}{2} = 10$ ways. Hence $$6 \times 10 = 60.$$

Answer 60

Solution: PRMO 2019, Q5

Think of the seating as a cycle on the five badges, where two badges are joined when they sit next to each other. The rule forbids joining $1$ to $2$, $2$ to $3$, $3$ to $4$ and $4$ to $5$, so the permitted neighbours are $$1: \{3,4,5\}, \quad 2: \{4,5\}, \quad 3: \{1,5\}, \quad 4: \{1,2\}, \quad 5: \{1,2,3\}.$$

Badges $2$, $3$ and $4$ have exactly two permitted neighbours each, and in the seating every person has exactly two neighbours. So all of those pairings are forced: $2$ must sit between $4$ and $5$, badge $3$ between $1$ and $5$, and badge $4$ between $1$ and $2$. Collecting them, the five adjacencies must be $$1\!-\!3, \quad 3\!-\!5, \quad 5\!-\!2, \quad 2\!-\!4, \quad 4\!-\!1,$$ which is precisely the single cycle $1, 3, 5, 2, 4$. There is exactly one admissible cyclic order.

Now count seatings. Rotations are counted as different, so the cycle can be placed on the five chairs in $5$ rotations, and it can be traversed in either of $2$ directions, giving $$5 \times 2 = 10$$ seatings in all.

Answer 10

Solution: IOQM 2021 Part A, Q7

The condition $f(i) \leq f(j)$ whenever $i < j$ says that $f(1) \leq f(2) \leq f(3)$. Once we know which three values are used, and with what multiplicity, the map is completely determined, because the values must be written in increasing order. So counting maps is the same as counting the ways of choosing three values from five with repeats allowed and order ignored.

The standard count for that is $\binom{n + k - 1}{k}$ with $n = 5$ and $k = 3$, which comes from the stars-and-bars correspondence: lay out three stars and four bars, and read off how many of each value to take. For example, $$\mid\star\star\mid\mid\star\mid \quad\longleftrightarrow\quad (f(1),f(2),f(3))=(2,2,4).$$ The five groups contain $0,2,0,1,0$ stars: those are the numbers of copies of the values $1,2,3,4,5$. Here $$\binom{5 + 3 - 1}{3} = \binom{7}{3} = 35.$$

Answer 35

Solution: IOQM 2025 Part SEP, Q7

Let the equal sides be $a$ and the third side $b$, so $2a + b = 23$ with $a, b$ positive integers. The only triangle inequality that can fail is $a + a > b$, that is $$2a > 23 - 2a, \qquad 4a > 23, \qquad a \ge 6.$$ At the other end, $b \ge 1$ forces $2a \le 22$, so $a \le 11$.

Every $a$ from $6$ to $11$ gives a genuine triangle, and different values of $a$ give non-congruent triangles, so there are $6$ of them. (No equilateral triangle appears, since $23$ is not divisible by $3$, so nothing is counted twice.)

Answer 6

Solution: PRMO 2012, Q15

Let $k$ be the common value of the two floors. Then $$5k \le x \le 5k + 4 \qquad \text{and} \qquad 7k \le x \le 7k + 6.$$ For an overlap we need $7k \le 5k + 4$, that is $k \le 2$, so only three values of $k$ are possible.

Taking them in turn:

• $k = 0$: $x \in \{0,1,2,3,4\}$, five values.

• $k = 1$: $[5,9] \cap [7,13] = \{7,8,9\}$, three values.

• $k = 2$: $[10,14] \cap [14,20] = \{14\}$, one value.

So there are $$5 + 3 + 1 = 9$$ non-negative integers in all.

Answer 9

Solution: PRMO 2017, Q9

A route leaves $A$, passes through some of the other four cities without repetition, and returns. Since every pair of cities is joined, the only decisions are which cities to use and in what order. A route through $k$ other cities is therefore determined by an ordered selection of $k$ cities out of four, and each such selection gives exactly one route.

How small can $k$ be? Not $0$, and not $1$: going $A \to B \to A$ would use the road $AB$ twice. So $k$ runs from $2$ to $4$, and $$\sum_{k=2}^{4}\binom{4}{k}k! = \binom42 2! + \binom43 3! + \binom44 4! = 12 + 24 + 24 = 60.$$

The problem’s remark that the two directions count separately is exactly what makes this an ordered count, and it is why each cycle contributes $k!$ rather than $k!/2$.

Answer 60

Solution: PRMO 2017, Q10

Number the rooms $1, 2, 3, 4$ on one side and $1', 2', 3', 4'$ on the other, with $i$ opposite $i'$. Forbidden pairs are $i$ with $i'$, and consecutive rooms on the same side.

Each of the four opposite pairs $\{i, i'\}$ can hold at most one guest, and there are four guests, so every pair holds exactly one. Reading along the corridor, that means a choice for each $i$ of which side its guest is on.

Now the adjacency rule bites. If the guests in positions $i$ and $i+1$ were on the same side they would be in adjacent rooms, so consecutive choices must alternate. There are exactly two alternating patterns for four positions, namely $$1, 2', 3, 4' \qquad\text{and}\qquad 1', 2, 3', 4.$$

Finally the guests are four different people, so each set of rooms can be filled in $4!$ ways: $$2 \times 24 = 48.$$

Answer 48

Solution: PRMO 2017, Q20

Four positive lengths are the sides of a quadrilateral exactly when each is less than the sum of the other three. Here is the needed converse in this case. Draw a diagonal of length $t$, and build triangles with sides $(a,b,t)$ and $(c,10,t)$ on its opposite sides. Both are non-degenerate precisely when $$b-a<t<a+b \qquad\text{and}\qquad 10-c<t<10+c.$$ These intervals overlap exactly when $10-c<a+b$: the other lower bound $b-a$ is already below $a+b$, and $10+c$ exceeds both lower bounds and $a+b$. Joining the two triangles then gives a quadrilateral with the required sides. Since $a < b < c < 10$, the side of length $10$ is the longest, so the only condition that can fail is $$a + b + c > 10.$$

There are $\binom93 = 84$ triples with $1 \le a < b < c \le 9$, so count instead the failures, those with $a + b + c \le 10$: $$\begin{array}{ll} a = 1, b = 2: & c = 3,4,5,6,7 \quad (5) \\ a = 1, b = 3: & c = 4,5,6 \quad (3) \\ a = 1, b = 4: & c = 5 \quad (1) \\ a = 2, b = 3: & c = 4,5 \quad (2) \end{array}$$ and nothing else, since $a = 2, b = 4$ already needs $c \ge 5$ and gives $11$. That is $11$ failures, so the count is $$84 - 11 = 73.$$

Answer 73

Solution: PRMO 2018, Q11

Let $n$ be the number of cups without handles and $h$ the number with. The selections are independent, so $$\binom{n}{2}\binom{h}{3} = 1200.$$

Go through the values of $\binom{h}{3}$ in turn, keeping only those that divide $1200$ and leave a quotient of the form $\binom{n}{2} = \tfrac12 n(n-1)$: $$\begin{array}{r|r|l} h & \binom{h}{3} & \text{quotient } \binom{n}{2} \\ \hline 3 & 1 & 1200 \text{, needs } n(n-1) = 2400 \text{: no} \\ 4 & 4 & 300 \text{, so } n(n-1) = 600 = 25 \times 24, \ n = 25 \\ 5 & 10 & 120 \text{, so } n(n-1) = 240 = 16 \times 15, \ n = 16 \\ 6 & 20 & 60 \text{, needs } n(n-1) = 120 \text{: no} \\ 10 & 120 & 10 \text{, so } n(n-1) = 20 = 5 \times 4, \ n = 5 \end{array}$$ The values $\binom{h}{3}$ for $h = 7, 8, 9$ are $35$, $56$ and $84$, none of which divides $1200$; and for $h \ge 11$ we have $\binom{h}{3} \ge 165$, which would force $\binom{n}{2} \le 7$, that is $\binom{n}{2} \in \{1, 3, 6\}$, which would need $\binom{h}{3}$ to be $1200$, $400$ or $200$. None of the three is a binomial coefficient of that shape, as the neighbouring values show: $$\binom{20}{3} = 1140 < 1200 < 1330 = \binom{21}{3},$$ $$\binom{14}{3} = 364 < 400 < 455 = \binom{15}{3},$$ $$\binom{11}{3} = 165 < 200 < 220 = \binom{12}{3}.$$

So the kitchen holds $25 + 4 = 29$, or $16 + 5 = 21$, or $5 + 10 = 15$ cups, and the maximum is $$29.$$

A word about the key. The official answer cell for this question reads “$15, 21, 29$”, because the phrase maximum possible was dropped in translation and all three totals were given full credit. The English paper does ask for the maximum, and its answer is $29$.

Answer 29

Solution: PRMO 2018, Q12

Reduce the coefficients modulo $3$. The terms with $k = 3$ and $k = 6$ vanish, whatever their signs, so $\epsilon_3$ and $\epsilon_6$ are free: $4$ choices. What is left is $$\epsilon_1 + 4\epsilon_4 + 7\epsilon_7 + 2\epsilon_2 + 5\epsilon_5 + 8\epsilon_8 \equiv (\epsilon_1 + \epsilon_4 + \epsilon_7) - (\epsilon_2 + \epsilon_5 + \epsilon_8),$$ all of it modulo $3$, since $1, 4, 7 \equiv 1$ and $2, 5, 8 \equiv -1$.

Write $A$ for the first bracket and $B$ for the second. Each is a sum of three signs, so it takes the values $3, 1, -1, -3$ in $1, 3, 3, 1$ ways respectively. Modulo $3$ those values are $0, 1, 2, 0$, so $$A \equiv 0 \ (2 \text{ ways}), \qquad A \equiv 1 \ (3 \text{ ways}), \qquad A \equiv 2 \ (3 \text{ ways}),$$ and the same for $B$. The condition is $A \equiv B$, so the number of choices for the six constrained signs is $$2^2 + 3^2 + 3^2 = 4 + 9 + 9 = 22.$$

Multiplying by the $4$ free choices, $$22 \times 4 = 88.$$

Answer 88

Solution: PRMO 2019, Q15

Label the vertices $P_0, P_1, \ldots, P_9$ around the circle, with $P_k$ at angle $36k^{\circ}$. The chord $P_iP_j$ is perpendicular to the radius bisecting its arc, so its direction, taken modulo $180^{\circ}$, is $$\frac{36i + 36j}{2} + 90^{\circ} = 18(i+j) + 90^{\circ} \pmod{180^{\circ}}.$$ Two chords are therefore parallel exactly when $18(i+j) \equiv 18(i'+j') \pmod{180}$, that is when $$i + j \equiv i' + j' \pmod{10}.$$

So sort the $\binom{10}{2} = 45$ chords by the value of $i + j$ modulo $10$, giving ten families of mutually parallel chords. How big is each family? Fix a remainder $c$ and count the pairs $\{i,j\}$ with $i \ne j$ and $i + j \equiv c$. There are ten ordered pairs $(i,j)$ with $i + j \equiv c$, one for each $i$. If $c$ is even, two of them have $i = j$, namely $i \equiv c/2$ and $i \equiv c/2 + 5$, leaving $8$ ordered pairs and hence $4$ chords. If $c$ is odd, none has $i = j$, leaving $5$ chords. The tally checks out: $5 \times 4 + 5 \times 5 = 45$.

Sides must now be removed, since the question asks about diagonals. The side $P_iP_{i+1}$ has $i + j = 2i + 1$, always odd, so every side lies in an odd family. How many in each? Fixing an odd $c$ and asking for $2i + 1 \equiv c$ means $2i \equiv c - 1$, and since $c-1$ is even this has exactly two solutions modulo $10$, namely $i \equiv \tfrac{c-1}{2}$ and $i \equiv \tfrac{c-1}{2} + 5$. So each odd family contains exactly two sides, accounting for all ten, and the even families contain none. Hence

• each of the five odd families has $5 - 2 = 3$ diagonals,

• each of the five even families has $4$ diagonals,

for a total of $15 + 20 = 35$ diagonals, as it should be.

A pair of parallel diagonals is a pair chosen from one family, so the answer is $$5\binom{3}{2} + 5\binom{4}{2} = 5 \times 3 + 5 \times 6 = 15 + 30 = 45.$$

The even families are the larger ones because a chord in an even family never touches the two vertices $P_{c/2}$ and $P_{c/2+5}$ that anchor it, while an odd family gets to use all ten vertices. It is the same parity distinction that makes a regular polygon with an even number of sides have diameters at all.

Answer 45

Solution: PRMO 2019, Q17

Every term on the left of $30a + 50b + 70c \le 343$ is a multiple of $10$, so the left-hand side is a multiple of $10$ and the bound may be sharpened to $30a + 50b + 70c \le 340$, that is $$3a + 5b + 7c \le 34.$$ Since $a, b, c \ge 1$, write $a = 1 + \alpha$, $b = 1 + \beta$, $c = 1 + \gamma$ with $\alpha, \beta, \gamma \ge 0$. The condition becomes $$3\alpha + 5\beta + 7\gamma \le 34 - 15 = 19.$$

Now count, splitting on $\gamma$, which can only be $0$, $1$ or $2$ since $3 \times 7 = 21 > 19$.

• $\gamma = 0$ leaves $3\alpha + 5\beta \le 19$, and $\beta = 0, 1, 2, 3$ allow $\alpha \le 6, 4, 3, 1$ respectively: $7 + 5 + 4 + 2 = 18$.

• $\gamma = 1$ leaves $3\alpha + 5\beta \le 12$, and $\beta = 0, 1, 2$ allow $\alpha \le 4, 2, 0$: $5 + 3 + 1 = 9$.

• $\gamma = 2$ leaves $3\alpha + 5\beta \le 5$, and $\beta = 0, 1$ allow $\alpha \le 1, 0$: $2 + 1 = 3$.

Adding, $18 + 9 + 3 = 30$ ordered triples.

Answer 30

Solution: IOQM 2023, Q17

An element of $\mathcal S$ is just a choice of five numbers from $\{1, 2, \ldots, 99\}$, written in increasing order. For a smaller example, choose $1,4,6,9,12$ from $1$ through $13$. The unchosen numbers before, between and after the chosen ones form six gaps of sizes $0,2,1,2,2,1$:

Record the actual choice from $1$ through $99$ by its gaps: $$g_0 = a - 1, \quad g_1 = b-a-1, \quad g_2 = c-b-1,$$ $$g_3 = d-c-1, \quad g_4 = e-d-1, \quad g_5 = 99 - e.$$ These six numbers are non-negative and $$g_0 + g_1 + g_2 + g_3 + g_4 + g_5 = 99 - 5 = 94.$$ Conversely every such six-tuple of non-negative integers summing to $94$ comes from exactly one element of $\mathcal S$, so the correspondence pairs the two collections off exactly.

Here is the point of setting it up this way. The description is completely symmetric in the six gaps: permuting them gives another valid six-tuple. So when we average over all of $\mathcal S$, the six gaps have the same average value, and since they sum to $94$ that common average is $\tfrac{94}{6}$.

Now express the fourth element in terms of gaps. Unwinding the definitions, $$d = g_0 + g_1 + g_2 + g_3 + 4.$$ Taking averages and using the common value, $$D = 4 \cdot \frac{94}{6} + 4 = \frac{188}{3} + 4 = \frac{200}{3} = 66.66\ldots$$ The largest integer not exceeding $D$ is therefore $66$.

Nothing in the argument used the number $4$ except at the last step, so the same reasoning gives the average of the $j$th element as $j \cdot \tfrac{100}{6}$, which is the familiar rule that the chosen points sit, on average, evenly spread.

Answer 66

Solution: IOQM 2024, Q14

At every step a particle moves one unit up, and its $x$-coordinate changes by $+1$, $0$ or $-1$. Suppose a particle takes $u$ steps to the right, $v$ straight up and $w$ to the left. After $80$ steps at the point $(79, 80)$, $$u + v + w = 80, \qquad u - w = 79.$$ Subtracting the second equation from the first leaves $$(u+v+w) - (u-w) = v + 2w = 1,$$ and since $v$ and $w$ are non-negative integers the only possibility is $w = 0$ and $v = 1$, so $u = 79$. Exactly one of the eighty steps is a straight-up step and the rest go right, and there are $80$ ways to choose which step that is.

Now count particles rather than paths. The claim is that after $k$ steps the pile at any point holds exactly $3^{80-k}$ particles for each path of length $k$ reaching that point, and it follows by induction on $k$.

At $k = 0$ there is one path, the empty one, and $3^{80}$ particles. Suppose the claim holds at step $k < 80$. Every pile then has size $3^{80-k}$ times a whole number, so it is divisible by $3$, and the rule splits it into three exactly equal parts with the floors rounding nothing away. Each part is $3^{79-k}$ times the number of paths that reached the old point, and a point at step $k+1$ collects one such part from each of its predecessors. Adding them gives $3^{79-k}$ times the total number of paths reaching it, which is the claim at $k+1$.

After $80$ steps a pile is therefore $3^0 = 1$ particle per path, and there are $80$ paths to $(79,80)$. The answer is $80$.

Answer 80

Solution: IOQM 2026, Q23

Colour from left to right: the leftmost vertical segment first, then for each square in turn its right side, its top and its bottom. When a square is reached its left side is already coloured, say $L$.

• Right side also $L$: the top and bottom must be the other two colours, in either order, which is $2$ ways.

• Right side one of the $2$ other colours: the third colour must appear on the top or the bottom. Of the $9$ choices for that pair, $4$ avoid it, so $5$ do not, giving $2 \times 5 = 10$ ways.

That is $12$ ways whatever $L$ is, so $$N = 3 \times 12^5 = 3 \times 248832 = 746496,$$ and the remainder on division by $100$ is $96$.

Answer 96

Solution: PRMO 2018, Q24

A triangle up to similarity is an unordered triple of positive integers $\{A, B, C\}$ with $A + B + C = 180$.

Count the ordered triples first. A smaller example is $8=2+3+3$, drawn as a row of units with its two dividers: $$\star\star\mid\star\star\star\mid\star\star\star.$$ The dividers occupy two of the seven gaps between units, ensuring that every part is positive. Writing $180$ as an ordered sum of three positive integers is a choice of two dividers among the $179$ gaps in a row of $180$ units, so there are $$\binom{179}{2} = \frac{179 \times 178}{2} = 15931$$ of them.

Now pass to unordered triples. An ordered triple has $6$ arrangements if its three entries are distinct, $3$ if exactly two agree and $1$ if all three do, so the triples with a repeat have to be removed before dividing.

All three equal means $A = B = C = 60$: one shape, one ordered triple.

Exactly two equal means $A = A$ and $C = 180 - 2A$ with $A$ running from $1$ to $89$, which keeps $C$ positive, and excluding $A = 60$, which is the all-equal case. That is $88$ shapes, each appearing as $3$ ordered triples, so $264$ ordered triples.

The rest have three distinct entries: $$15931 - 264 - 1 = 15666$$ ordered triples, which is $15666 / 6 = 2611$ shapes. Altogether $$N = 2611 + 88 + 1 = 2700,$$ and $N/100 = 27$.

Answer 27

Solution: PRMO 2018, Q27

Record each row by the pair of columns it colours red. The column condition says the four pairs, counted with multiplicity, cover each of the four columns exactly twice.

For example, these two boards satisfy the conditions; $R$ marks a red square and $B$ a blue one: $$\begin{array}{cccc} R&R&B&B\\R&R&B&B\\B&B&R&R\\B&B&R&R \end{array}\qquad \begin{array}{cccc} R&R&B&B\\R&B&R&B\\B&R&B&R\\B&B&R&R \end{array}$$ The first uses row-pairs $12,12,34,34$ and the second uses $12,13,24,34$. There are six pairs in all, and they fall into three complementary couples: $\{12, 34\}$, $\{13, 24\}$, $\{14, 23\}$, where the two pairs of a couple are disjoint.

Case 1: a repeated pair

Suppose some pair $A$ is used twice. It covers its two columns twice already, so the other two rows must cover only the complementary pair $B$, hence both are $B$. The four pairs are $A, A, B, B$ for one of the three couples, and the four rows can be arranged in $\tfrac{4!}{2!\,2!} = 6$ orders. That is $3 \times 6 = 18$ colourings.

Case 2: four distinct pairs

Now the four pairs are distinct, so exactly two of the six are unused. Each column lies in three of the six pairs and must be covered twice, so each column lies in exactly one unused pair. That makes the two unused pairs disjoint, that is a complementary couple: $3$ choices. The four remaining pairs can be assigned to rows in $4! = 24$ ways, giving $3 \times 24 = 72$ colourings.

Total

No other shape is possible: three copies of one pair would cover its columns three times. So $$18 + 72 = 90.$$

Answer 90

Solution: PRMO 2018, Q28

The three children get distinct positive numbers of chocolates summing to $8$. Listing the ways of writing $8$ as a sum of three different positive numbers: $$8 = 1 + 2 + 5 = 1 + 3 + 4,$$ and nothing else. If the smallest share were $2$ or more, the three shares would total at least $2 + 3 + 4 = 9$; so the smallest is $1$, and the other two are different numbers above $1$ adding to $7$, which leaves only $2 + 5$ and $3 + 4$.

For each such split, the chocolates are distinguishable, so the number of ways to put them into labelled groups of sizes $a$, $b$ and $c$ is $8!/(a!\,b!\,c!)$, and the three sizes can be attached to the three children in $3! = 6$ ways because they are all different: $$\frac{8!}{1!\,2!\,5!} \times 6 = 168 \times 6 = 1008, \qquad \frac{8!}{1!\,3!\,4!} \times 6 = 280 \times 6 = 1680.$$

Hence $N = 1008 + 1680 = 2688$, and its digits sum to $$2 + 6 + 8 + 8 = 24.$$

Answer 24

Solution: IOQM 2023, Q20

Since $11$ is prime and $|A|$, $\max(B)$ are positive integers, either $|A| = 1$ and $\max(B) = 11$, or $|A| = 11$ and $\max(B) = 1$. Take them in turn.

Case $|A| = 1$, $\max(B) = 11$. Write $A = \{m\}$, so $\max(A) = m$ and the first equation reads $m \cdot |B| = 12$. Thus $m$ is a divisor of $12$ and $|B| = 12/m$. The set $B$ consists of positive integers with largest element $11$, so $B$ contains $11$ together with $|B| - 1$ of the ten numbers $1, \ldots, 10$, which can be done in $\binom{10}{|B|-1}$ ways. Running through the divisors: $$\begin{array}{c|c|c} m & |B| & \text{count} \\ \hline 1 & 12 & \binom{10}{11} = 0 \\ 2 & 6 & \binom{10}{5} = 252 \\ 3 & 4 & \binom{10}{3} = 120 \\ 4 & 3 & \binom{10}{2} = 45 \\ 6 & 2 & \binom{10}{1} = 10 \\ 12 & 1 & \binom{10}{0} = 1 \end{array}$$ The case $m=1$ contributes nothing, since $B$ would need twelve elements from a pool of eleven. The total here is $252 + 120 + 45 + 10 + 1 = 428$.

Case $|A| = 11$, $\max(B) = 1$. Then $B = \{1\}$ and $|B| = 1$, so the first equation gives $\max(A) = 12$. So $A$ contains $12$ together with ten of the eleven numbers $1, \ldots, 11$, which can be done in $\binom{11}{10} = 11$ ways.

Hence $N = 428 + 11 = 439$. Writing $N = 100a + b$ with $a, b$ below $100$ gives $a = 4$ and $b = 39$, so $a + b = 43$.

Answer 43

Solution: IOQM 2023, Q21

The condition $f(i) \ge f(j)$ for $i > j$ says that $f$ is non-decreasing. Summing the given equation, $$\sum_{i=1}^{n} f(i) = 2023 - \sum_{i=1}^n i = 2023 - \frac{n(n+1)}{2},$$ which must be non-negative since the values of $f$ are non-negative. So the sum to be minimised decreases as $n$ grows, and we want the largest $n$ with $\tfrac{n(n+1)}2 \le 2023$. Since $$\frac{63 \cdot 64}{2} = 2016 \le 2023 < 2080 = \frac{64 \cdot 65}{2},$$ the choice is $n = 63$, and then $\sum f(i) = 2023 - 2016 = 7$.

What remains is to count the non-decreasing sequences $$0 \le f(1) \le f(2) \le \cdots \le f(63)$$ of integers with total $7$. Reading such a sequence from the right and discarding the zeros gives a way of writing $7$ as a sum of at most $63$ positive integers in non-increasing order, and the correspondence goes both ways because $63$ is more than $7$, so no such sum is too long to fit. Those sums are $$7,\ 6{+}1,\ 5{+}2,\ 5{+}1{+}1,\ 4{+}3,\ 4{+}2{+}1,\ 4{+}1{+}1{+}1,\ 3{+}3{+}1,\ 3{+}2{+}2,$$ $$3{+}2{+}1{+}1,\ 3{+}1^4,\ 2{+}2{+}2{+}1,\ 2{+}2{+}1{+}1{+}1,\ 2{+}1^5,\ 1^7,$$ fifteen in all. So there are $15$ such functions.

Answer 15

Solution: IOQM 2023, Q24

Slide one leg along the parallel sides: cutting off a parallelogram from the trapezium leaves a triangle with sides $p - q$, $m$ and $n$. So a non-degenerate trapezium with parallel sides $p > q$ and legs $m, n$ exists precisely when $$|m - n| < p - q < m + n,$$ and it is then determined up to congruence. The reason is that the construction reverses: the triangle on sides $p-q$, $m$, $n$ is fixed up to congruence by its three sides, and gluing a parallelogram with sides $q$ and $m$ onto it along the side of length $m$ rebuilds the trapezium, with no freedom left. Swapping the two legs merely produces the mirror image.

The right-hand inequality never fails here. All four lengths lie in $\{5, \ldots, 10\}$, so $p - q \le 5$ while $m + n \ge 11$. The condition is therefore just $$|p - q| > |m - n|.$$

Now count. Choose four distinct lengths from the six available, in $\binom64 = 15$ ways, and split them into two pairs, which can be done in $3$ ways. For each such split, one pair must be the parallel sides and the other the legs, and the condition says the parallel pair is the one with the larger difference. So each split contributes exactly one trapezium, unless the two pairs have equal differences, in which case it contributes none.

That leaves us counting the splits with equal differences. A split into two disjoint pairs with a common difference $d$ is a choice of two disjoint pairs from $\{5,\ldots,10\}$ each with difference $d$: $$\begin{array}{c|c|c} d & \text{pairs available} & \text{disjoint choices} \\ \hline 1 & (5,6),(6,7),(7,8),(8,9),(9,10) & \binom52 - 4 = 6 \\ 2 & (5,7),(6,8),(7,9),(8,10) & \binom42 - 2 = 4 \\ 3 & (5,8),(6,9),(7,10) & \binom32 = 3 \\ 4 & (5,9),(6,10) & 1 \\ 5 & (5,10) & 0 \end{array}$$ In the first two rows the subtracted terms are the choices sharing an endpoint. The total is $6 + 4 + 3 + 1 = 14$.

Hence the number of trapeziums is $$15 \cdot 3 - 14 = 45 - 14 = 31.$$

Answer 31

Solution: IOQM 2026, Q22

One string can come from different block orders. For example, all four rows below produce $10102323$, with brackets showing the original six blocks: $$\begin{array}{llllll} {}[10]&[1]&[0]&[23]&[2]&[3]\\ {}[1]&[0]&[10]&[23]&[2]&[3]\\ {}[10]&[1]&[0]&[2]&[3]&[23]\\ {}[1]&[0]&[10]&[2]&[3]&[23] \end{array}$$ The six blocks can be arranged in $6! = 720$ ways, each giving an eight-digit string. Two arrangements give the same string only through a repeated pattern. A $0$ directly after a $1$ is either the second digit of the block $10$ or the single $0$ placed right after the single $1$, and in the second case the glued pair and the block can exchange roles without changing the string. The same is true of $23$. So a string is made by one arrangement, or two, or four when both repeats happen.

Gluing the single $1$ to a single $0$ after it leaves five units, $5! = 120$ arrangements, and the same for $2$ before $3$; both at once is $4! = 24$. Sorting the $720$ arrangements:

• neither repeat: $720 - 120 - 120 + 24 = 504$ arrangements, $504$ strings;

• only the $10$ repeat: $120 - 24 = 96$ arrangements, each string twice, $48$ strings;

• only the $23$ repeat: likewise $48$ strings;

• both: $24$ arrangements, each string four times, $6$ strings.

That is $504 + 48 + 48 + 6 = 606$ different strings.

A string starts with $0$ exactly when the single $0$ comes first. The other five blocks then follow in $5! = 120$ orders, and only the $23$ repeat can occur: $24$ arrangements give $12$ strings and the other $96$ give $96$, so $108$ strings start with $0$. Hence $$N = 606 - 108 = 498,$$ and the sum of its digits is $4 + 9 + 8 = 21$.

Answer 21

Solution: IOQM 2022, Q24

Two counts differ by a multiple of $6$ precisely when they agree modulo $6$, so the condition says the four box-counts lie in four distinct remainder classes modulo $6$. Since there are six classes, exactly two are unused, and the sum decides which.

All six remainders together sum to $0+1+2+3+4+5 = 15 \equiv 3 \pmod 6$, while our four counts must total $52 \equiv 4 \pmod 6$. So the two omitted remainders sum to $3 - 4 \equiv 5 \pmod 6$, and the unordered pairs of distinct remainders summing to $5$ are $$\{0,5\}, \qquad \{1,4\}, \qquad \{2,3\}.$$ Three cases, and in each the set of four remainders is determined.

Within a case, assign the four remainders to the four distinguishable boxes in $4! = 24$ ways, then count the balls. If a box must hold a count congruent to $r$ modulo $6$ and at least $1$, write that count as $r' + 6k$ where $r'$ is the least positive representative, so $r' = 6$ when $r = 0$ and $r' = r$ otherwise, and $k \geq 0$. Summing, $\sum r' + 6\sum k = 52$.

For the omitted pair $\{0,5\}$ the remainders are $\{1,2,3,4\}$ with $\sum r' = 10$, so $\sum k = 7$ and the number of non-negative solutions is $\binom{10}{3} = 120$. For $\{1,4\}$ the remainders are $\{0,2,3,5\}$ with $\sum r' = 6+2+3+5 = 16$, so $\sum k = 6$ and the count is $\binom{9}{3} = 84$. For $\{2,3\}$ the remainders are $\{0,1,4,5\}$, again with $\sum r' = 16$ and count $84$.

Multiplying by the $24$ assignments, $$N = 24\,(120 + 84 + 84) = 24 \cdot 288 = 6912.$$ Writing $6912 = 100 \cdot 69 + 12$ gives $a = 69$ and $b = 12$, both below $100$, so $a + b = 81$.

Answer 81

Solution: IOQM 2023, Q22

Cevians from the same vertex meet only at that vertex, which is on the boundary; cevians from different vertices always cross inside. A family of chords cuts a convex region into $$1 + (\text{number of chords}) + \sum_{p} \bigl(m_p - 1\bigr)$$ pieces, the sum being over interior intersection points and $m_p$ being the number of chords through $p$. To see why, draw the chords one at a time: a new chord is cut by the points where it meets earlier chords into pieces, and each piece splits one region in two, so it adds one region more than the number of new crossing points on it. A point where $m_p$ chords meet is met $m_p - 1$ times in this way, by every chord through it except the first. With four cevians this reads $5 + \sum_p (m_p - 1)$, so nine regions means $$\sum_p (m_p - 1) = 4.$$ A simple crossing contributes $1$ and a point where three cevians meet contributes $2$.

Suppose the four chosen pegs lie $n_A$, $n_B$, $n_C$ to a side, with $n_A + n_B + n_C = 4$. The number of crossing pairs, before worrying about concurrency, is $$\binom42 - \binom{n_A}2 - \binom{n_B}2 - \binom{n_C}2 = 6 - \binom{n_A}2 - \binom{n_B}2 - \binom{n_C}2.$$

Distribution $(2,2,0)$. The subtracted terms give $1 + 1 = 2$, leaving $4$ crossing pairs. Three concurrent cevians would have to come from three different vertices, which is impossible here, so the count of $4$ is exact and every such choice gives nine regions. There are $\binom32 = 3$ ways to choose the two sides and $\binom52 = 10$ ways to choose two pegs on each, so this contributes $3 \cdot 10 \cdot 10 = 300$.

Distribution $(2,1,1)$. The subtracted term is $1$, leaving $5$ crossing pairs, which gives ten regions unless three cevians are concurrent. Concurrency makes three of those pairs meet at a single point, which contributes $2$ to the sum in place of $3$, so the sum drops from $5$ to $4$, and that is exactly what we want. So we need choices in which three cevians, one from each vertex, are concurrent.

When three cevians pass through one point

What decides concurrency is the three ratios in which the cevians cut the opposite sides, and the relation between them can be got with nothing but areas. Suppose cevians $AD$, $BE$, $CF$ meet at an interior point $P$. Triangles $ABD$ and $ACD$ share the apex $A$ and have bases $BD$ and $DC$ on one line, so their areas are in the ratio $BD : DC$; the same is true of $PBD$ and $PCD$. Subtracting, $$\frac{BD}{DC} = \frac{[ABD] - [PBD]}{[ACD] - [PCD]} = \frac{[ABP]}{[ACP]},$$ and the two companion statements are obtained by relabelling. Multiplying all three, every area appears once above and once below, so $$\frac{BD}{DC} \cdot \frac{CE}{EA} \cdot \frac{AF}{FB} = 1.$$ The converse follows at once: if the product is $1$ and the first two cevians meet at $P$, then the line from the third vertex through $P$ cuts its side in a ratio forced to equal the third factor, so it is the third cevian. This relation, in both directions, is Ceva’s theorem.

Counting the concurrent triples

Let the cevian from $A$ meet $BC$ at distance $x$ from $B$, the cevian from $B$ meet $CA$ at distance $y$ from $C$, and the cevian from $C$ meet $AB$ at distance $z$ from $A$, with $x, y, z \in \{1,2,3,4,5\}$. They are concurrent exactly when $$\frac{x}{6-x} \cdot \frac{y}{6-y} \cdot \frac{z}{6-z} = 1.$$ The five available ratios are $\tfrac15, \tfrac12, 1, 2, 5$ for $x = 1,2,3,4,5$. A product of three of them, with repetition allowed, equals $1$ only as $$1 \cdot 1 \cdot 1, \qquad \tfrac15 \cdot 5 \cdot 1, \qquad \tfrac12 \cdot 2 \cdot 1,$$ giving $1 + 3! + 3! = 13$ concurrent triples.

Each such triple is completed to a set of four pegs by adding one more peg, which may be any of the four unused pegs on any of the three sides, so $12$ ways. No set of four is counted twice, because two concurrent triples inside one such set would share the two single cevians and use the two cevians from the doubled vertex, forcing those two to meet at an interior point, which they do not. This contributes $13 \cdot 12 = 156$.

The other distributions. $(3,1,0)$ leaves $3$ crossings and $(4,0,0)$ leaves none, and in neither can three cevians be concurrent, so both give fewer than nine regions.

Hence $N = 300 + 156 = 456$, and the sum of the squares of the digits is $16 + 25 + 36 = 77$.

Answer 77

Solution: IOQM 2025 Part SEP, Q28

Number the heights $1$ through $10$, so the line begins with $1$ and ends with $10$. Between consecutive people the height either rises or falls, and the first and last comparisons are both rises. Along such a word, peaks and valleys alternate and there are as many of each, so exactly one valley means exactly one peak. The line therefore rises to a peak, falls to a valley, and rises to the end.

Here is one such line, with the three runs marked: $$\underbrace{1,\ 3,\ 7,\ 9}_{\text{up to the peak}}\ \big|\ \underbrace{9,\ 2}_{\text{down to the valley}}\ \big|\ \underbrace{2,\ 4,\ 5,\ 6,\ 8,\ 10}_{\text{up to the end}}$$ The peak is $9$, the valley is $2$, and every line being counted has this shape. Keep it in view while the general count is set up.

Now count. Let $v$ be the height at the valley. It cannot be $1$ or $10$, since those two stand at the ends, so $$v \in \{2, 3, \ldots, 9\}.$$ Everyone shorter than $v$ must stand in the first rising run, since the falling run bottoms out at $v$ and the final run starts at $v$. Everyone taller than $v$ is in one of three places, and the tallest person is fixed at the very end, so the free ones are the heights $v+1, \ldots, 9$, of which there are $9-v$.

Let $U$ be the set of those free heights that go into the first two runs, so the rest join the final run. The set $U$ cannot be empty, since the peak lies in it, and the peak is forced to be $\max U$. Every other member of $U$ may be placed either in the rising run or in the falling run, freely, and once the sets are known the order within each run is forced. So a set $U$ of size $u$ contributes $2^{u-1}$ lines, and $$N = \sum_{v=2}^{9}\ \sum_{u \ge 1} \binom{9-v}{u} 2^{u-1} = \sum_{v=2}^{9} \frac{3^{9-v} - 1}{2},$$ using $\sum_u \binom mu 2^u = 3^m$ with the $u = 0$ term removed. Writing $k = 9-v$, which runs from $0$ to $7$, $$N = \frac12\left(\sum_{k=0}^{7}3^k - 8\right) = \frac12\left(\frac{3^8-1}{2} - 8\right) = \frac{3280 - 8}{2} = 1636.$$

So $N = 1636 = 100 \cdot 16 + 36$, giving $a = 16$, $b = 36$ and $a + b = 52$.

Answer 52