Counting One Thing by Counting Another

Problems

Solutions

Solution: PRMO 2015 Part A, Q14

Call a pair consisting of a man and a woman who danced together a dancing pair, and let $W$ be the number of women. Counting these pairs from the men’s side, each of the $9$ men appears in exactly $4$ of them, so there are $9 \times 4 = 36$ pairs. Counting from the women’s side, each woman appears in exactly $3$, so there are $3W$ pairs.

The same collection has been counted both times, so $$3W = 36, \qquad W = 12.$$

This is double counting in its purest form, and the shape recurs constantly: whenever a problem gives you a fixed number of connections at each end of a two-sided relationship, count the connections themselves and set the two totals equal.

Answer 12

Solution: IOQM 2023, Q8

Let $f(k)$ be the number of ways to tile a $2 \times k$ rectangle with dominoes only. Looking at the leftmost column, either one vertical domino fills it, leaving $2 \times (k-1)$, or two horizontal dominoes fill the first two columns, leaving $2 \times (k-2)$. So $$f(k) = f(k-1) + f(k-2), \qquad f(0) = 1,\ f(1) = 1,$$ giving $1, 1, 2, 3, 5, 8, 13, 21$ for $k = 0$ through $7$. In particular there are $f(7) = 21$ tilings that use dominoes alone, and they use exactly seven dominoes, which is what we have.

Now suppose the $2 \times 2$ tile is used. Only one such tile is available, so it is used at most once. It covers two adjacent columns, say columns $i$ and $i+1$ with $1 \le i \le 6$, and it splits the strip into a $2 \times (i-1)$ piece on the left and a $2 \times (6-i)$ piece on the right, each tiled by dominoes alone. The number of tilings using the square is therefore $$\sum_{i=1}^{6} f(i-1)\,f(6-i) = 1\cdot 8 + 1 \cdot 5 + 2 \cdot 3 + 3 \cdot 2 + 5 \cdot 1 + 8 \cdot 1 = 38.$$ Each of these uses five dominoes, comfortably within the seven available.

The two cases are disjoint and cover everything, so the answer is $21 + 38 = 59$.

Answer 59

Solution: IOQM 2025 Part SEP, Q28

The exponents on opposite faces add to $5$, so opposite faces carry $\{1,32\}$, $\{2,16\}$ or $\{4,8\}$. Each die carries all six numbers, with total $$1+2+4+8+16+32 = 63,$$ so the two dice together carry $126$.

Stacking hides exactly three faces: the bottom face of the lower die, the top face of the lower die and the bottom face of the upper die. The first two are opposite faces of the same die, so their sum is one of $$1 + 32 = 33, \qquad 2 + 16 = 18, \qquad 4 + 8 = 12,$$ and the smallest is $12$. The third hidden face is any face of the upper die and can be as small as $1$.

So the least possible hidden total is $12 + 1 = 13$ and $$N = 126 - 13 = 113.$$ The sum of the squares of the digits is $1 + 1 + 9 = 11$.

Answer 11

Solution: PRMO 2014, Q20

Build a pair $(A,B)$ element by element. Each of the five elements is in $A$ only, in $B$ only, in both, or in neither, four independent choices, so there are $$4^5 = 1024$$ ordered pairs altogether.

Now count the bad ones. For $A \subseteq B$, each element must avoid the state “in $A$ only”, leaving three choices, so there are $3^5 = 243$ such pairs, and likewise $243$ with $B \subseteq A$. Pairs counted twice are those with both inclusions, that is $A = B$, of which there are $2^5 = 32$. By inclusion-exclusion the bad pairs number $$243 + 243 - 32 = 454.$$

Hence the answer is $$1024 - 454 = 570.$$

Answer 570

Solution: PRMO 2019, Q24

For one square, blue and green contribute $+1$ each and red contributes $-1$, so the signed total is $1+1-1=1$, while the ordinary total is $3$. Adding gives $4$, twice the number of choices with an even number of reds. The same separation can work with any number of squares. The ordinary total number of colourings is $3^n$. Now attach to each colouring the sign $(-1)^{\#\text{red}}$ and add: $$\sum_{\text{colourings}} (-1)^{\#\text{red}} = (1 + 1 - 1)^n = 1,$$ because each square independently contributes $+1$ for either of the two non-red colours and $-1$ for red. The left-hand side is (even-red count) minus (odd-red count), while the total is their sum, so $$f(n) = \frac{3^n + 1}{2}.$$

Therefore $$\frac{f(9)}{f(3)} = \frac{3^9 + 1}{3^3 + 1} = \frac{27^3 + 1}{27 + 1} = 27^2 - 27 + 1 = 703,$$ using $a^3 + 1 = (a+1)(a^2 - a + 1)$ with $a = 27$, which spares the division of $9842$ by $14$. Finally $703 = 19 \times 37$, so the largest prime factor is $37$.

Answer 37

Solution: IOQM 2022, Q10

The ten digits of $M$ are all different, so two different choices of swaps always produce two different numbers, and we may count the choices directly.

For three positions, there are just three disjoint-swap choices: no swap, swap positions $1,2$, or swap positions $2,3$. Both swaps together are forbidden because they share position $2$. Think of the ten digit positions as vertices of a path, with an edge joining each adjacent pair. Choosing disjoint adjacent pairs to swap is exactly choosing a set of edges no two of which share a vertex, that is a matching. Let $f_n$ be the number of matchings on a path of $n$ vertices. Looking at the last vertex, either it is unmatched, leaving $f_{n-1}$, or it is matched to its neighbour, leaving $f_{n-2}$. So $$f_n = f_{n-1} + f_{n-2}, \qquad f_1 = 1, \quad f_2 = 2,$$ which is the Fibonacci sequence shifted along. Running it out, $f_3 = 3$, $f_4 = 5$, and onwards to $f_{10} = 89$.

One of those $89$ choices is the empty one, which leaves $M$ unchanged and so produces no new number. The count of new numbers is $89 - 1 = 88$.

Answer 88

Solution: IOQM 2022, Q21

An hour is six moves of ten minutes each, so we want the number of closed walks of length six from a fixed vertex of a cube.

Classify each vertex by its distance from the start: there is $1$ vertex at distance $0$, three at distance $1$, three at distance $2$, and one at distance $3$. Because every vertex of the cube looks the same as every other, with three neighbours apiece, the count of walks depends only on this class, so let $(a_t, b_t, c_t, d_t)$ record how many length-$t$ walks end in each class. From the adjacency, a vertex at distance $0$ has all three neighbours at distance $1$, a vertex at distance $1$ has one neighbour at distance $0$ and two at distance $2$, a vertex at distance $2$ has two neighbours at distance $1$ and one at distance $3$, and the vertex at distance $3$ has all three neighbours at distance $2$. A walk arriving in a class came from a neighbouring class, so $$a_{t+1} = b_t, \quad b_{t+1} = 3a_t + 2c_t, \quad c_{t+1} = 2b_t + 3d_t, \quad d_{t+1} = c_t.$$

Starting from $(1,0,0,0)$ and stepping six times: $$\begin{array}{c|cccc} t & a_t & b_t & c_t & d_t \\ \hline 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 3 & 0 & 0 \\ 2 & 3 & 0 & 6 & 0 \\ 3 & 0 & 21 & 0 & 6 \\ 4 & 21 & 0 & 60 & 0 \\ 5 & 0 & 183 & 0 & 60 \\ 6 & 183 & 0 & 546 & 0 \end{array}$$ Half the entries are zero because every move changes the distance by one, so after an even number of moves the ant is at distance $0$ or $2$. The number of walks that finish where they started is $N = a_6 = 183$.

The question asks for the sum of the squares of the digits of $N$, which is $1^2 + 8^2 + 3^2 = 1 + 64 + 9 = 74$.

Answer 74

Solution: IOQM 2023, Q7

First count dice with the faces labelled and coloured in space, ignoring the identification by rotation. The face carrying $1$ can be any of the $6$, its opposite face must carry $2$, and the remaining four numbers can be placed on the remaining four faces in $4! = 24$ ways. That gives $6 \cdot 24 = 144$ numberings. Colouring is independent: the three pairs of opposite faces each take one of two colours, so $2^3 = 8$ colourings. In total there are $144 \cdot 8 = 1152$ labelled coloured dice sitting in space.

Now bring in the rotations. A rotation of the cube is fixed by saying where one chosen face goes, which is any of the $6$ faces, and then how that face is turned, which is any of $4$ quarter turns; so there are $6 \cdot 4 = 24$ of them. Two of our dice have the same design exactly when a rotation carries one to the other. The count of designs would be $1152/24$ provided no rotation other than the identity leaves a die unchanged, and that is where the distinct numbers help: a non-identity rotation moves some face to a different face, and those two faces carry different numbers, so the die is changed. Every family of dice that count as the same therefore has exactly $24$ members and $$\text{number of designs} = \frac{1152}{24} = 48.$$

If it helps to see the same answer built up rather than divided down, fix $1$ on top and $2$ below, which uses up the freedom to rotate the die as a whole except for the four turns about the vertical axis. The four side faces can be filled with $3, 4, 5, 6$ in $4! = 24$ ways, and those four turns identify them in groups of four, leaving $6$ numberings. Multiply by the $8$ colourings to get $48$.

Answer 48

Solution: IOQM 2026, Q7

Condition (c) says every $1$ sits immediately after an $8$. Glue each such $1$ to its $8$, and the number becomes a row of blocks $2$, $4$, $8$ and $81$, whose digit sums are $2$, $4$, $8$ and $9$. All but the last are even, and the total is the even number $14$, so the number of $81$ blocks is even. Two of them already add up to $18$, which is too much, so there are none, and $n$ uses only the digits $2$, $4$ and $8$.

Halve everything: we want the number of ordered ways to write $7$ as a sum of $1$s, $2$s and $4$s. Write $f(m)$ for the number of ways to make a total of $m$. The first part is $1$, $2$ or $4$, and what follows is any arrangement of the remainder, so $$f(m) = f(m-1) + f(m-2) + f(m-4),$$ where $f(0) = 1$ (the empty sum) and $f$ of a negative number is $0$. Each entry of the table after the first is the sum of the entries one, two and four places to its left: $$\begin{array}{c|cccccccc} m & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline f(m) & 1 & 1 & 2 & 3 & 6 & 10 & 18 & 31 \end{array}$$ and in particular $f(7) = 18 + 10 + 3 = 31$.

Each way of making $7$, read left to right and doubled, is the list of digits of exactly one $n$, so there are $31$ numbers.

Answer 31

Solution: IOQM 2020, Q26

The six discs sit in a triangular array, three at the corners and three at the midpoints of the sides, and the symmetries of that array are the six symmetries of an equilateral triangle: the identity, two rotations, and three reflections. Two colourings count as the same exactly when one symmetry carries one to the other, so what we are counting is families of colourings, each family holding the ones the symmetries carry into each other.

The obvious move is to count the $90$ labelled colourings and divide by $6$, and it fails, because $90/6 = 15$ is not the answer. It fails because the six symmetries do not always give six different labelled colourings: a colouring that a reflection leaves alone is reached in fewer than six ways, so dividing by six undercounts it. What is needed is a division that adjusts for exactly that.

The tool is to average, over the six symmetries, the number of colourings each one leaves unchanged, and since that is not a school result, here is why it works. Count the pairs $(g, C)$ in which the symmetry $g$ leaves the colouring $C$ unchanged, in two ways. Summing over $g$ gives the total of the fixed-colouring counts. Summing instead over $C$: fix a colouring $C$ and let $S$ be the set of symmetries leaving it unchanged. Two symmetries $g$ and $h$ send $C$ to the same colouring exactly when applying $h$ and then undoing $g$ leaves $C$ unchanged, so the six symmetries fall into groups of size $|S|$, one group for each colouring in the family of $C$. The order matters: doing it the other way round tests a different symmetry, and for the reflections that test gives the wrong answer. Hence $|S|$ times the size of that family is $6$, so each colouring in a family contributes $6 / (\text{family size})$, and the whole family contributes $6$. Adding over families, the two counts give $$\text{number of families} \times 6 = \sum_g \bigl(\text{colourings } g \text{ fixes}\bigr),$$ which is the averaging rule.

Take the symmetries in turn. The identity leaves every colouring unchanged, and the number of ways to give two discs each of three colours to six labelled positions is $\tfrac{6!}{2!\,2!\,2!} = 90$.

The two rotations fix nothing. A rotation through $120^\circ$ permutes the three corners in a single cycle and the three midpoints in another, so any colouring it leaves unchanged must give all three corners one colour and all three midpoints another. That would need three discs of some colour, and we have only two of each, so the count is $0$ for each rotation.

Each reflection fixes one corner and the midpoint of the opposite side, while swapping the other two corners with each other and the other two midpoints with each other. A colouring unchanged by it must give the swapped corner pair a single colour and the swapped midpoint pair a single colour, and those two colours must differ, since otherwise that colour would appear four times. The remaining colour then goes to the two fixed discs, which is exactly the two we have left. So there are $3 \times 2 = 6$ such colourings for each of the three reflections.

Averaging over the six symmetries, $$\frac{90 + 0 + 0 + 6 + 6 + 6}{6} = \frac{108}{6} = 18.$$

Answer 18

Solution: IOQM 2022, Q22

Read the condition position by position. The first term needs $b_2 = 1$ and the last needs $b_{n-1} = 1$, those being their only neighbours. For an interior position $i$, the requirement is that $b_{i-1}$ and $b_{i+1}$ are not both $0$.

That last condition is the useful one, because $i-1$ and $i+1$ have the same parity and are consecutive within their parity. As $i$ runs over $2, \ldots, n-1$, the pairs $(i-1, i+1)$ run over every consecutive pair of the odd-indexed terms and every consecutive pair of the even-indexed terms. So a sequence is friendly exactly when $$b_2 = 1, \qquad b_{n-1} = 1,$$ and neither the odd-indexed subsequence nor the even-indexed subsequence contains two consecutive zeros. The two subsequences are otherwise independent, so the count is a product.

It is worth splitting one sequence by hand before going on. For $n = 8$ take $$\begin{array}{r|cccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline b_i & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \end{array}$$ The odd positions carry $1, 0, 1, 1$ and the even positions carry $1, 1, 0, 1$. Neither has two zeros in a row, the required $b_2$ and $b_7$ are both $1$, and one may check position by position that the sequence really is friendly. Notice that the two rows never look at each other.

The building block is the number of binary strings of length $L$ with no two consecutive zeros, which is $\operatorname{Fib}_{L+2}$ with $\operatorname{Fib}_1 = \operatorname{Fib}_2 = 1$: the first term is $0$ or $1$, and the two cases leave strings of length $L-2$ and $L-1$ with the same property. Fixing one end to be a $1$ costs one step of the recursion, giving $\operatorname{Fib}_{L+1}$; fixing both ends gives $\operatorname{Fib}_L$.

$n = 2m$

The odd positions are $1, 3, \ldots, 2m-1$ and the even ones $2, 4, \ldots, 2m$, both of length $m$. The condition $b_{n-1} = 1$ fixes the last odd term and $b_2 = 1$ fixes the first even term, so each subsequence contributes $\operatorname{Fib}_{m+1}$ and $$F_{2m} = \operatorname{Fib}_{m+1}^{\,2}.$$

$n = 2m+1$

Now the odd positions number $m+1$ and carry no fixed term, contributing $\operatorname{Fib}_{m+3}$; the even positions number $m$ and have both ends fixed, since $b_2$ is the first and $b_{n-1} = b_{2m}$ the last, contributing $\operatorname{Fib}_m$. So $$F_{2m+1} = \operatorname{Fib}_{m+3}\operatorname{Fib}_m.$$

Now evaluate. With $m = 5$ the even case gives $F_{10} = \operatorname{Fib}_6^{\,2} = 8^2 = 64$, still below $100$, and the odd case gives $$F_{11} = \operatorname{Fib}_8 \operatorname{Fib}_5 = 21 \cdot 5 = 105 > 100.$$ Both $F_n$ formulas increase with $n$, so the smallest such $n$ is $n = 11$.

Answer 11

Solution: IOQM 2025 Part SEP, Q7

The digits are two $2$s, three $3$s and four $4$s, so the total number of arrangements is $$\frac{9!}{2!\,3!\,4!} = \frac{362880}{288} = 1260.$$

Now count the arrangements in which no $3$ lies to the right of the last $4$. Everything after the last $4$ is then a $2$, say $k$ of them with $k \in \{0,1,2\}$. Such an arrangement is completely described by choosing $k$, placing a $4$ in position $9-k$, filling the last $k$ places with twos, and arranging the remaining digits, which are three $3$s, three $4$s and $2-k$ twos, in the first $8-k$ places. So the count is $$\sum_{k=0}^{2} \frac{(8-k)!}{(2-k)!\,3!\,3!} = \frac{8!}{2!\,3!\,3!} + \frac{7!}{1!\,3!\,3!} + \frac{6!}{0!\,3!\,3!},$$ which is $560 + 140 + 20 = 720$.

Hence $N = 1260 - 720 = 540$, and the remainder on division by $100$ is $40$.

Answer 40

Solution: IOQM 2025 Part SEP, Q28

The forbidden points are those with both coordinates odd. Look at where you can be.

• At $(\text{even}, \text{even})$ either step is legal.

• At $(\text{odd}, \text{even})$ a step North would land on two odd coordinates, so you must go East, arriving at $(\text{even}, \text{even})$.

• At $(\text{even}, \text{odd})$ you must likewise go North.

So from an even-even point every choice commits you to two steps, taking you either two East or two North, and back to an even-even point.

The journey therefore consists of double steps from $(0,0)$ to the last even-even point, and since the destination is $(7,12)$, with $7$ odd and $12$ even, that last point is $(6,12)$ and the journey finishes with a single step East. The double steps take you from $(0,0)$ to $(6,12)$, which needs $3$ double steps East and $6$ double steps North in some order: $$\binom{9}{3} = 84.$$

Answer 84

Solution: IOQM 2026, Q18

A labelling is a path through all eight vertices, visited in the order $1, 2, \ldots, 8$. The claim is that in a good labelling, at every stage, the vertices visited so far are consecutive around the octagon and the current vertex is at one end of that run.

At the start the run is one vertex. Suppose the claim holds, the current vertex is $c$, and the unvisited vertices form the complementary run $U$. Suppose the path next goes to a vertex $w$ of $U$ that is not one of its two ends. The segment $cw$ is a chord with unvisited vertices on both sides of it: those of $U$ between $c$ and $w$, and those beyond $w$. The rest of the path starts at $w$ and has to visit both sides, so at some moment it steps along a segment whose ends lie strictly on opposite sides of the chord $cw$. In a convex polygon such a segment crosses $cw$, and the labelling is not good. So the path moves to an end of $U$, and the claim holds one step later.

Conversely, a step to an end of $U$ crosses nothing already drawn. If the end is next to $c$ the step is a side of the octagon. If it is the other end, every visited vertex other than $c$ lies on one side of the new chord, so every earlier segment does too, and none can cross it.

So the good labellings are counted by their choices. There are $8$ places for vertex $1$. Each of vertices $2$ to $7$ has two choices, the two ends of $U$, which are different while $U$ has at least two vertices. Vertex $8$ is forced. Hence $$N = 8 \times 2^6 = 512,$$ and the remainder on division by $100$ is $12$.

Answer 12

Solution: IOQM 2021 Part B, Q3

What the condition means

Place $a_1, a_2, \ldots, a_N$ at the nodes of a binary tree, with $a_i$ the parent of $a_{2i}$ and $a_{2i+1}$. The two conditions say precisely that every number is larger than the two hanging beneath it. So $a_1$, at the top, is the largest of all, and once it is placed the two branches have nothing to do with each other: each is the same problem on fewer nodes.

That picture is the whole method. Choosing which numbers go left and which go right is free, and then each branch is counted the same way, so every count below will be a binomial coefficient times two smaller counts. An arrangement of this kind is called a heap, and the name will not be asked to do any work beyond that.

(a) $T(7)$

For $N = 7$ the tree is the full tree of three levels: a root with two subtrees of three nodes each. The root must hold $7$. Of the remaining six numbers, choose three for the left subtree in $\binom63$ ways, and arrange each subtree in $T(3) = 2$ ways. Hence $$T(7) = \binom63 \cdot T(3)^2 = 20 \cdot 4 = 80.$$

A lemma on powers of two

For example, $6!=720=2^4\cdot45$ contains four factors of $2$. The number $6$ is $110$ in binary, so it has two ones, and $4=6-2$. This is the pattern we will prove. Write $v(m)$ for the exponent of $2$ in $m$, and $s(m)$ for the number of ones when $m$ is written in binary. The claim is $$v(m!) = m - s(m).$$

The proof is an induction that splits on whether $m$ is even or odd, and it needs only two observations of each kind. Among $1, 2, \ldots, 2k$ the odd numbers carry no factor of $2$ at all, while the even ones are $2, 4, \ldots, 2k$, whose product is $2^k \cdot k!$. So $$v\bigl((2k)!\bigr) = k + v(k!), \qquad v\bigl((2k+1)!\bigr) = v\bigl((2k)!\bigr),$$ the second because the extra factor $2k+1$ is odd. On the other side, doubling a number in binary just appends a zero and adding one after that turns it into a one, so $$s(2k) = s(k), \qquad s(2k+1) = s(k) + 1.$$

Now induct. The claim holds at $m = 1$, where both sides are $0$. Suppose it holds below $m$. If $m = 2k$ then $$v(m!) = k + \bigl(k - s(k)\bigr) = 2k - s(2k) = m - s(m),$$ and if $m = 2k+1$ then $$v(m!) = v\bigl((2k)!\bigr) = 2k - s(k) = (2k+1) - \bigl(s(k)+1\bigr) = m - s(m).$$ That is the lemma, and nothing outside it is used below.

One consequence is worth recording now, for $n\ge2$. Since $s(2^{n-1}+1) = 2$ and $s(2^{n-1}-1) = n-1$, $$v\binom{2^n}{2^{n-1}+1} = \left(2^n - 1\right) - \left(2^{n-1} - 1\right) - \left(2^{n-1} - n\right) = n.$$

(b) Full trees

For $N = 2^n - 1$ the tree is full, and the same argument as in part (a) gives $$T\left(2^n - 1\right) = \binom{2^n - 2}{2^{n-1} - 1}\,T\left(2^{n-1} - 1\right)^2.$$ The exponent of $2$ in that binomial coefficient is $n - 1$: by the lemma it is $\left(2^n - 2 - s(2^n-2)\right) - 2\left(2^{n-1} - 1 - s(2^{n-1}-1)\right)$, and $s(2^n - 2) = n - 1 = s(2^{n-1}-1)$, so the whole thing is $n-1$.

Writing $t_n$ for the exponent of $2$ in $T(2^n - 1)$, the recurrence reads $$t_n = 2t_{n-1} + (n-1), \qquad t_1 = 0.$$ And $t_n = 2^n - n - 1$ satisfies it, since $$2\left(2^{n-1} - (n-1) - 1\right) + (n-1) = 2^n - n - 1,$$ with $t_1 = 2 - 1 - 1 = 0$ correct. So $K = 2^n - n - 1$, as required.

(c) One node more than a power of two

For $n\ge2$ and $N = 2^n + 1$, the tree has its root, a left subtree of $2^{n-1}+1$ nodes and a right subtree of $2^{n-1}-1$ nodes. The same splitting gives $$T\left(2^n + 1\right) = \binom{2^n}{2^{n-1}+1}\,T\left(2^{n-1}+1\right)T\left(2^{n-1}-1\right),$$ which one may check at $n = 2$: $T(5) = \binom43 T(3)T(1) = 4 \cdot 2 \cdot 1 = 8$.

Let $s_n$ be the exponent of $2$ in $T(2^n+1)$. Using the consequence of the lemma recorded above and part (b), $$s_n = n + s_{n-1} + t_{n-1} = n + s_{n-1} + 2^{n-1} - n = s_{n-1} + 2^{n-1}.$$ Since $T(3) = 2$ gives $s_1 = 1$, summing the geometric series leaves $$s_n = 1 + \left(2 + 4 + \cdots + 2^{n-1}\right) = 2^n - 1.$$

So the largest $K$ with $2^K$ dividing $T(2^n+1)$ is $2^n - 1$.

Answer proof

Solution: IOQM 2022, Q20

First identify what a landmark is. The condition $(p_{l-1}-p_l)(p_{l+1}-p_l) > 0$ says the two neighbours lie on the same side of $p_l$, so $p_l$ is either larger than both, a peak, or smaller than both, a valley. Exactly one landmark therefore means the permutation rises to a single peak and then falls, or falls to a single valley and then rises.

A small peak example is $2,4,3,1$: after choosing $\{2\}$ to lie left of the maximum $4$, the increasing left part and decreasing right part are forced. A valley example is $3,1,2,4$. $$\underbrace{2,4}_{\text{rising}}\mid\underbrace{4,3,1}_{\text{falling}} \qquad\underbrace{3,1}_{\text{falling}}\mid\underbrace{1,2,4}_{\text{rising}}.$$ The shared peak or valley is repeated in the display only to mark the two runs. Count the peak case. The peak is larger than everything around it and the sequence is increasing up to it and decreasing after, so the peak is the largest value, $n$. The elements to its left are then determined as a set, since they must appear in increasing order, and likewise those to its right. So a permutation of this kind is exactly a choice of which elements of $\{1, \ldots, n-1\}$ go to the left. That choice may not be empty, which would put $n$ first and leave no interior landmark, nor everything, which would put $n$ last. Hence $$2^{n-1} - 2$$ permutations with one peak, and by the same argument with the smallest value, $$2^{n-1} - 2$$ with one valley. The two families do not overlap, so $$L(n) = 2\left(2^{n-1} - 2\right) = 2^n - 4.$$

Now ask when $2^n - 4 = 4\left(2^{n-2} - 1\right)$ is a perfect square. Since $4$ is already a square, the question is exactly whether $2^{n-2} - 1$ is one. For $n = 3$ it equals $1 = 1^2$, so $L(3) = 4 = 2^2$ and $n = 3$ works. For $n = 4$ it equals $3$, which is not a square.

For $n \geq 5$, so that $k = n - 2 \geq 3$, look modulo $8$. Since $8 \mid 2^k$, $$2^k - 1 \equiv -1 \equiv 7 \pmod 8.$$ But the squares modulo $8$ are only $0$, $1$ and $4$, since an even number squares to $0$ or $4$ and an odd number squares to $1$. So $2^k - 1$ is never a square once $k \geq 3$, and no $n \geq 5$ can work.

The largest, and in fact the only, value is $n = 3$.

Answer 3

Solution: IOQM 2024, Q24

Write $p(x) = \sum_{i=0}^{14} c_i x^i$ with each $c_i \in \{0,1\}$ and $c_{14} = 1$, since the degree is exactly $14$. Because $q(x) = 1 + x + x^3$, $$[x^k]\,p(x)q(x) = c_k + c_{k-1} + c_{k-3},$$ with the convention that $c_j = 0$ outside the range. There is no carrying anywhere: these are integer coefficients, not binary digits. So the requirement is that for every $k$, $$c_k + c_{k-1} + c_{k-3} \le 1.$$

Read off what that forbids. Taking $k$ and $k-1$ together says no two chosen exponents differ by $1$; taking $k$ and $k-3$ says none differ by $3$; and taking $k-1$ and $k-3$, which appear in the same sum, says none differ by $2$. Conversely, if no two chosen exponents differ by $1$, $2$ or $3$, then in each sum at most one term is $1$. So the condition is exactly $$\text{any two exponents used by } p \text{ differ by at least } 4.$$

Now count. The set of exponents is a subset $S \subseteq \{0, 1, \ldots, 14\}$ containing $14$, with all gaps at least $4$. Removing $14$ leaves a subset of $\{0, 1, \ldots, 10\}$ with gaps at least $4$, of some size $j$. For example, three of the remaining exponents might be $0,4,10$. Compressing the compulsory gaps moves them to $0,1,4$: $$\begin{array}{c|ccc} \text{original exponents}&0&4&10\\ \text{subtracted spaces}&0&3&6\\ \hline \text{compressed exponents}&0&1&4 \end{array}$$ The compressed entries are still distinct, and adding back $0,3,6$ recovers the original choice. In general such subsets are counted by subtracting $3$ from the second element, $6$ from the third and so on, which turns them into arbitrary $j$-element subsets of a set of $11 - 3(j-1)$ numbers. So there are $\binom{14-3j}{j}$ of them, and $$\binom{14}{0} + \binom{11}{1} + \binom{8}{2} + \binom{5}{3} + \binom{2}{4} = 1 + 11 + 28 + 10 + 0 = 50.$$

Answer 50

Solution: IOQM 2025 Part SEP, Q7

Let the sequence be $x_1, \ldots, x_L$. Two consecutive four-term averages differ by $$\frac{x_i+\cdots+x_{i+3}}{4} < \frac{x_{i+1}+\cdots+x_{i+4}}{4},$$ and all but the end terms cancel, so the condition is $$x_i < x_{i+4} \quad \text{for } i = 1, \ldots, L-4.$$ The same cancellation on the seven-term averages, now decreasing, gives $$x_i > x_{i+7} \quad \text{for } i = 1, \ldots, L-7.$$

Draw the indices $1, \ldots, L$ as dots and put an arrow from $i$ to $j$ whenever one of those requirements says $x_i < x_j$. There are two kinds of arrow: from $i$ to $i+4$, and from $j$ to $j-7$, the second because $x_{j-7} > x_j$ reads as an arrow pointing backwards from $j$ to $j-7$. Every arrow means the same thing, that the value at its head is the larger.

Now the question is whether such a picture can be filled in with real numbers, and the answer is that it can exactly when the arrows cannot be followed round into a loop. One direction is clear: following a loop all the way round would give $x_i < x_i$.

For the other, suppose there is no loop. Repeatedly pick a dot that no remaining arrow points to, which is always possible when there is no loop, since otherwise one could keep walking backwards along arrows for ever and would have to revisit a dot. Rub it out and carry on, listing the dots in the order chosen, then hand out the values $1, 2, 3, \ldots$ along that list. Every arrow then runs from a smaller value to a larger one: if an arrow goes from $i$ to $j$ and $i$ were still on the board when $j$ was chosen, that arrow would be pointing at $j$ and $j$ could not have been chosen. So $i$ is always rubbed out first and always gets the smaller value. Hence the sequence exists.

The direction of that sweep matters. Picking a dot with no arrow leaving it and then counting upwards would put the large values at the wrong end and reverse every inequality.

Here is the observation that settles both directions at once: modulo $11$ the two moves are the same, since $-7 \equiv 4 \pmod{11}$. So every move advances the index by $4$ modulo $11$, and a loop of $k$ moves needs $4k \equiv 0 \pmod{11}$, hence $11 \mid k$. Moreover the positions along $k = 11$ consecutive moves occupy eleven different remainders modulo $11$, because $4$ is coprime to $11$, so they are eleven different indices.

Therefore no loop can fit inside $\{1, \ldots, 10\}$, and for $L = 10$ the inequalities are consistent: list the indices in an order compatible with every required comparison, which is possible precisely because there is no loop, and assign increasing values along that list.

For $L = 11$ a loop does fit, and here it is: $$1 \to 5 \to 9 \to 2 \to 6 \to 10 \to 3 \to 7 \to 11 \to 4 \to 8 \to 1,$$ seven steps of $+4$ and four of $-7$, every index between $1$ and $11$. Going once round would give $x_1 < x_1$. Any longer sequence contains this loop as well.

Hence the greatest possible length is $10$.

Answer 10