Pigeonhole, Extremal and Invariants

Problems

Solutions

Solution: IOQM 2021 Part A, Q2

Let $b$ be the number of blue entries and $r$ the number of red ones, so $b + r = 101$.

Read the first condition carefully. The largest blue number is $b$, so every blue number is at most $b$, and there are $b$ of them. But there are only $b$ numbers in the whole list that are at most $b$, namely $1, 2, \ldots, b$, so the blue numbers are precisely those and nothing is left over. That single observation removes all the freedom from the problem.

Everything else is therefore red, so the red numbers are $b+1, b+2, \ldots, 101$ and the smallest red number is $b + 1$. The second condition says this equals half the number of reds: $$b + 1 = \frac{r}{2} = \frac{101 - b}{2}.$$ Clearing the denominator gives $2b + 2 = 101 - b$, so $3b = 99$ and $b = 33$.

Hence $r = 101 - 33 = 68$, and as a check the smallest red number is $34$, which is indeed half of $68$.

Answer 68

Solution: PRMO 2015 Part A, Q17

The pairs $\{m, 125-m\}$ with both entries in $\{1, 2, \ldots, 100\}$ need $125 - m \le 100$, that is $m \ge 25$. So the pairs are $$\{25, 100\},\ \{26, 99\},\ \ldots,\ \{62, 63\},$$ of which there are $62 - 25 + 1 = 38$. Together they use up the numbers $25$ through $100$, and the remaining numbers $1$ through $24$ belong to no pair at all, because for those $m$ the partner $125 - m$ exceeds $100$.

Now the two halves of the argument. Any admissible $B$ contains at most one member of each pair, so $|B| \le 24 + 38 = 62$. And $62$ is attained: take all of $1$ through $24$ together with the larger member of each pair, that is $63$ through $100$. No two of the chosen numbers sum to $125$, since two numbers below $25$ sum to at most $48$, two numbers above $62$ sum to at least $127$, and a number below $25$ paired with one above $62$ sums to at most $24 + 100 = 124$.

Hence the maximum is $62$.

Answer 62

Solution: IOQM 2020, Q10

Order the five scores as $a \leq b \leq c \leq d \leq e$, so that the median is the middle one, $c$. Rather than reasoning about the median and the mean separately, it pays to write their difference as a single fraction and see which letters actually survive: $$c - \text{mean} = c - \frac{a+b+c+d+e}{5} = \frac{4c - a - b - d - e}{5}.$$

The expression is increasing in $c$ and decreasing in each of $a$, $b$, $d$ and $e$, so we would like $c$ large and the other four small. The ordering constraint is what stops us: $d$ and $e$ are not allowed to fall below $c$. The best available compromise is therefore to send $a$ and $b$ down to $0$, hold $d$ and $e$ at their lowest permitted value $c$, and then read off $$\frac{4c - 0 - 0 - c - c}{5} = \frac{2c}{5},$$ which is largest when $c$ takes its maximum value $100$, giving a difference of $40$.

It is worth checking the opposite direction, since the question asks only for the largest difference and does not say which way round it runs. There $$\text{mean} - c = \frac{a + b + d + e - 4c}{5},$$ and now $a$ and $b$ are at most $c$ while $d$ and $e$ are at most $100$, so $a + b + d + e - 4c \le 2c + 200 - 4c = 200 - 2c \le 200$. Taking $a = b = c = 0$ with $d = e = 100$ reaches $200/5 = 40$ once again. The two extremes happen to agree, so the answer is $40$ whichever way the gap opens.

Answer 40

Solution: IOQM 2024, Q20

Suppose the journey uses $d$ doublings and $s$ subtractions. Follow a single subtraction: if it is performed when $j$ doublings still lie ahead, then by the end it has reduced the final value by $3 \cdot 2^j$, because each later doubling doubles whatever was taken away along with everything else. Try it on a short journey. Starting from $11$, subtracting $3$ and then doubling twice gives $11 \to 8 \to 16 \to 32$, whereas doubling twice alone gives $44$; the $3$ removed at the start has cost $3 \cdot 2^2 = 12$ by the end. Hence $$121 = 11 \cdot 2^d - 3S, \qquad S = \sum_{i=1}^{s} 2^{j_i}, \quad 0 \le j_i \le d.$$

Now narrow $d$ down. Doublings are the only way to grow, and $11 \cdot 2^3 = 88 < 121$, so $d \ge 4$.

First, $d$ must be odd. Working modulo $3$, where $2 \equiv -1$, $$11 \cdot 2^d - 121 \equiv 2 \cdot (-1)^d - 1 \pmod 3,$$ which is $1$ for even $d$ and $0$ for odd $d$. Only the odd values leave $3S$ a whole multiple of $3$, so $d = 4$ and $d = 6$ are out, along with every other even value.

$d = 5$

Here $11 \cdot 32 - 121 = 231$, so $S = 77$ with every term at most $2^5 = 32$. Since $77$ is odd and $1$ is the only odd power of two, an odd number of the terms equal $1$. Three or more of them already mean six terms in all, since three ones leave $74$, and two terms of at most $32$ make at most $64$, so at least three more are needed. So take the case of exactly one $1$, where the rest total $76$. Two terms give at most $64$. Three cannot reach $76$ either: one of them must be $32$, because three terms of $16$ or less total at most $48$, and the remaining pair would then have to make $44$, which no two powers of two at most $32$ do. So $s \ge 5$, and $s = 5$ is achieved by $77 = 32+32+8+4+1$, giving $d + s = 10$.

$d \ge 7$

Here $S$ is large compared with the biggest term available. From $S = \left(11 \cdot 2^d - 121\right)/3$, $S > 3 \cdot 2^d$ exactly when $11 \cdot 2^d - 121 > 9 \cdot 2^d$, that is when $2^{d+1} > 121$, which holds for every $d \ge 6$. Since each term is at most $2^d$, three terms could never reach $S$, so $s \ge 4$ and $$d + s \ge 7 + 4 = 11,$$ worse than $10$.

So the least total is $d + s = 5 + 5 = 10$, and here is a route that achieves it: $$11 \to 8 \to 5 \to 10 \to 20 \to 17 \to 34 \to 31 \to 62 \to 124 \to 121.$$ Notice that it begins by going down, which is the step most people do not try. Subtracting early is cheap precisely because a later doubling magnifies whatever has been taken off.

Answer 10

Solution: IOQM 2025 Part SEP, Q28

The product is a multiple of $6$ exactly when the cards drawn include at least one even number and at least one multiple of $3$.

So consider what can go wrong. A draw avoiding every even number can be as large as the number of odd cards, which is $50$. A draw avoiding every multiple of $3$ can be as large as $100 - \lfloor 100/3 \rfloor = 100 - 33 = 67$. The second is the binding constraint, so drawing $67$ cards is not enough: the $67$ non-multiples of $3$ are a genuine bad draw.

With $68$ cards both risks vanish. Only $67$ cards are not multiples of $3$, so any $68$ must include one; and only $50$ cards are odd, so any $68$ must include an even one.

Hence $68$ cards are needed, and they suffice.

Answer 68

Solution: PRMO 2013, Q13

Work modulo $15$. The rule says that if $a + b \equiv 0$ then $a$ and $b$ share a colour.

First, the remainder $0$: any two multiples of $15$ sum to a multiple of $15$, so all of them share one colour.

Next, take $r$ between $1$ and $14$. Every element of remainder $r$ must share a colour with every element of remainder $15-r$, and both classes are non-empty, since $1000$ is far more than $15$. Two elements $a$ and $a'$ of the same remainder $r$ are therefore forced together as well, through any element of remainder $15 - r$. So each pair of classes $\{r, 15-r\}$ is a single colour.

That gives the groups $$\{0\}, \ \{1,14\}, \ \{2,13\}, \ \{3,12\}, \ \{4,11\}, \ \{5,10\}, \ \{6,9\}, \ \{7,8\},$$ eight of them, and nothing forces two different groups to share a colour: colouring by group satisfies the rule, since $a + b \equiv 0$ puts $a$ and $b$ in the same group by construction.

So the maximum number of colours is $8$.

Note that $15$ being odd is what makes every non-zero class pair with a different one. For an even modulus the class $r = m/2$ would pair with itself and behave like the zero class.

Answer 8

Solution: IOQM 2021 Part A, Q12

The question has two halves, and they need separate arguments: show that $72$ rooks can fail, and show that $73$ rooks never can.

For the first half, notice that mutually non-attacking rooks occupy distinct rows. So if every rook is confined to just six of the twelve rows, no seven of them can ever be pairwise non-attacking, because two of any seven would share a row. Six rows contain $6 \times 12 = 72$

unit squares, and filling all of them gives $72$ rooks with no seven mutually non-attacking. So $N$ must be at least $73$.

For the second half we need one fact, and it is not a school result, so here it is with a proof. It says that whenever the biggest non-attacking set is small, the rooks themselves must be crowded into a few lines, which is exactly the leverage we want.

The covering lemma

If the largest set of mutually non-attacking rooks has $t$ members, then every rook on the board can be covered by $t$ lines, each line a whole row or a whole column.

Fix a largest such set $M$, with $t$ rooks. Call a row or column used if it contains a rook of $M$; each rook of $M$ uses one row and one column, and all of these are distinct.

Now mark some rows and columns as reached. Every unused row is reached to begin with. From a reached row, follow any rook standing in it to that rook’s column and mark that column reached. From a reached column, follow the rook of $M$ in it, if there is one, back to that rook’s row and mark that row reached. Repeat until nothing new gets marked.

Every reached column is used. If some reached column were unused, the trail that reached it would run from an unused row to an unused column, alternating between rooks outside $M$ and rooks inside it. Exchanging along that trail, taking the outside rooks into $M$ and the inside ones out, would leave a set of mutually non-attacking rooks with one more member than $M$, which is impossible.

Take as the cover the reached columns together with the used rows that were not reached. This covers every rook: a rook standing in a reached row has its own column reached, by the marking rule, while a rook in a row that was not reached must be in a used row, since every unused row is reached at the start.

And the cover uses exactly $t$ lines. Each reached column is used, so it carries a rook of $M$, and each unreached row is used as well, since the unused rows are all reached at the start, so it too carries a rook of $M$. Every rook of $M$ is picked up by one of those lines and by only one. By one, because a rook standing in a reached row has its column reached, by the marking rule, so a rook whose column is unreached has its row unreached and is caught by its row. By only one, because a reached column marks its own rook’s row, so a rook whose column is reached has its row reached and is not caught again. Distinct rooks of $M$ stand in distinct rows and distinct columns, so they are caught by distinct lines, and every line of the cover catches one. The cover and the rooks of $M$ are therefore in one-to-one correspondence, and that is $t$ lines.

Stated about rows and columns of a rectangular array rather than a chessboard, that lemma is König’s theorem.

Finishing

Suppose $73$ rooks are placed and the largest mutually non-attacking set had only six members. The lemma would cover all $73$ rooks with six lines. But six lines of a $12 \times 12$ board cover $6 \times 12 = 72$ squares at most, holding at most $72$ rooks, one to a square. So seven mutually non-attacking rooks must exist.

Hence $N = 73$.

Answer 73

Solution: IOQM 2023, Q27

Read the ordering carefully, because it is not the obvious one: the condition is $a < b < d < c$. Given any four-element subset $\{w < x < y < z\}$ of $\{1, \ldots, 20\}$, there is exactly one way to name its elements so that this holds, namely $a = w$, $b = x$, $d = y$, $c = z$. So the quadruples correspond exactly to four-element subsets, and there are $$\binom{20}{4} = 4845$$ of them. (Had the ordering been $a<b<c<d$, the balanced condition $a + c = b + d$ would have been impossible, since then $a < b$ and $c < d$.)

Such a quadruple is balanced when $a + c = b + d$, that is $w + z = x + y$. So a balanced quadruple is a pair of disjoint pairs with the same sum, and conversely two distinct pairs with the same sum are automatically disjoint and automatically nest, the wider one giving $w$ and $z$. Counting them by the common sum $s$, if $k_s$ pairs $\{p < q\}$ from $\{1,\ldots,20\}$ have $p + q = s$, the number of balanced quadruples is $\sum_s \binom{k_s}{2}$.

There is a formula: a pair $\{p < q\}$ from $\{1, \ldots, 20\}$ with $p + q = s$ is fixed by its smaller member, which may be anything from $\max(1, s-20)$ up to $\lceil s/2 \rceil - 1$, so $$k_s = \left\lfloor \frac{s-1}{2} \right\rfloor \ \ (s \le 21), \qquad k_s = \left\lfloor \frac{41-s}{2} \right\rfloor \ \ (s \ge 21).$$ Written out, for $s = 3, 4, \ldots, 21$ they are $1,1,2,2,3,3,\ldots,9,9,10$, and for $s = 22, \ldots, 39$ they repeat in reverse, $9,9,8,8,\ldots,1,1$, by the symmetry $p \mapsto 21-p$. Hence $$\sum_s \binom{k_s}{2} = \underbrace{2\bigl(0+1+3+6+10+15+21+28+36\bigr) + 45}_{s \le 21}$$ $$\qquad\qquad + \; \underbrace{2\bigl(36+28+21+15+10+6+3+1\bigr)}_{s \ge 22},$$ which is $285 + 240 = 525$.

So $4845 - 525 = 4320$ quadruples are unbalanced. A set $\mathcal S$ of size $4411$ can contain at most all of them, and the remaining $4411 - 4320 = 91$ members must be balanced. That many is also achieved, by taking every unbalanced quadruple together with any $91$ balanced ones. The least possible number of balanced quadruples is therefore $$4411 - 4320 = 91.$$

Answer 91

Solution: IOQM 2023, Q28

Start with two small nets. For $n=1$, the one triangle move flips all three coins. For $n=2$, performing all four unit-triangle moves flips each corner once and each side-midpoint three times, so again every coin turns over. Yet $n=3$ will fail: a three-colouring splits its ten coins into classes of sizes $4,3,3$, and every move flips one coin of each class. These examples suggest looking at the colour classes rather than individual coins. Describe a vertex of the net by the triple $(x, y, z)$ of non-negative integers with $x + y + z = n$, the three coordinates being the distances to the three sides in lattice steps. The vertices of an upward unit triangle are $$(x+1, y, z), \quad (x, y+1, z), \quad (x, y, z+1), \qquad x+y+z = n-1,$$ and those of a downward one are obtained similarly.

The colouring

Put a vertex in class $C_r$ when $y - x \equiv r \pmod 3$. Reading off the three vertices of the upward triangle above, their values of $y - x$ are $$(y - x) - 1, \qquad (y-x)+1, \qquad (y-x),$$ which are three consecutive remainders, so they are one of each class. The same holds for a downward triangle. Therefore every move flips exactly one coin in each of the three classes.

The obstruction

Suppose all coins can be turned over in $k$ moves. Within class $C_r$, the total number of flips is exactly $k$, since each move contributes one. On the other hand every one of the $|C_r|$ coins in that class must be flipped an odd number of times, so the total number of flips in $C_r$ has the same parity as $|C_r|$. Hence $$k \equiv |C_0| \equiv |C_1| \equiv |C_2| \pmod 2.$$

Counting the classes

Fix $z$ and let $s = n - z$, so the row consists of the $s+1$ vertices with $x$ running from $0$ to $s$ and $y = s - x$. Along the row, $y - x = s - 2x$ takes the values $s, s-2, s-4, \ldots$, which modulo $3$ cycle through all three remainders in order. So a row of length divisible by $3$ contributes equally to the three classes; a row with $s \equiv 0 \pmod 3$, whose length is $s+1 \equiv 1$, contributes one extra to $C_0$; and a row with $s \equiv 1 \pmod 3$ contributes one extra to each of $C_1$ and $C_2$.

Now suppose $3 \mid n$. As $z$ runs from $0$ to $n$, the value $s = n-z$ runs over $0, 1, \ldots, n$, and among these there are $\tfrac n3 + 1$ multiples of $3$ but only $\tfrac n3$ values congruent to $1$. Hence $$|C_0| = |C_1| + 1 = |C_2| + 1,$$ the parities disagree, and turning every coin over is impossible.

If $3 \nmid n$ the three classes have equal size, because rotating the triangle through $120^{\circ}$, which sends $(x,y,z)$ to $(z,x,y)$, changes $y-x$ by $-n$ modulo $3$ and therefore permutes the three classes cyclically.

When it can be done

Take two unit triangles sharing an edge. Performing both moves flips the two shared coins twice, so the net effect is to flip just the two opposite coins of the rhombus. Reading off coordinates, those two differ by one of $$(1, 1, -2), \qquad (1, -2, 1), \qquad (-2, 1, 1),$$ and each of these leaves $y - x$ unchanged modulo $3$, so a rhombus move flips two coins of the same class and nothing else.

Next, the rhombus moves reach every vertex of a class from every other. Take any vertex with $z \ge 2$: the move $(1,1,-2)$ is available, since the rhombus it uses has its other two corners at $(x+1, y, z-1)$ and $(x, y+1, z-1)$, both inside the triangle. Repeating it brings $z$ down to $0$ or $1$. From $z = 1$, if $x \ge 2$ apply $(-2,1,1)$ and then $(1,1,-2)$, which takes $z$ from $1$ up to $2$ and back down to $0$; if instead $y \ge 2$ use $(1,-2,1)$ followed by $(1,1,-2)$. One of the two is available unless $x$ and $y$ are both at most $1$, which forces $n \le 3$, and those cases are small enough to see directly. So every vertex is joined to one on the side $z = 0$.

Along that side the vertices are $(x, n-x, 0)$. A rhombus joins its two opposite corners either way round, so each move may be read as $+d$ or as $-d$. Applying $(1,-2,1)$ and then $(-2,1,1)$ backwards therefore steps by $$(1,-2,1) + (2,-1,-1) = (3, -3, 0),$$ which lands back on the side and moves $x$ along in threes. Two vertices of the side lie in the same class exactly when their values of $x$ agree modulo $3$, so those steps join all of them. Each class is therefore connected.

The rest is a standard fact about a connected collection: since each rhombus move flips two of its coins, any pair of coins in one class can be flipped and nothing else, by running along a chain of moves from one to the other and letting the intermediate flips cancel in pairs. So exactly the even-sized subsets of a class can be flipped on their own.

Now finish. When $3 \nmid n$ the three classes have the same size $m$. If $m$ is even, flip each class entirely, taking the coins in pairs. If $m$ is odd, first make one triangle move, which flips one coin in each class and leaves an even number still to flip in each, then finish as before. Either way every coin ends tail up. For instance $n = 1$ needs one move and $n = 2$ needs all four unit triangles.

So the flipping is possible exactly when $n$ is not a multiple of $3$. Among $1 \le n \le 100$ there are $33$ multiples of $3$, leaving $$100 - 33 = 67$$ values of $n$.

Answer 67

Solution: IOQM 2025 Part SEP, Q7

Call a position $(m,n)$ with $n \ge 1$ reds remaining a win if the player about to move can force a victory. Two facts settle everything.

If $n = 1$ the mover takes the last red and wins, so every position with one red is a win.

With two reds and no blues, the mover must leave one red to the opponent and loses. With two reds and one blue, taking the blue hands back that losing position. With three reds and no blues, taking one red also hands back the losing two-red position. The total parity has begun to separate these examples, while the one-red case remains exceptional. Now suppose $n \ge 2$. We claim the position is a win exactly when $m + n$ is odd, and we check both directions at once by induction on $m+n$. Note that $m$ may be $0$, in which case the only legal move is to take a red; the argument below covers that case, since the blue move is used only to establish a win, never to rule one out.

Suppose $m+n$ is odd, with $n \ge 2$. If $n \ge 3$, take a red: the new position is $(m, n-1)$ with $n - 1 \ge 2$ and $m + n - 1$ even, which by induction is a loss for the opponent. If $n = 2$, then $m$ is odd, so $m \ge 1$; take a blue instead, reaching $(m-1, 2)$ with $m - 1 + 2$ even and two reds still on the table, again a loss for the opponent. Either way the mover wins.

Suppose instead $m+n$ is even, with $n \ge 2$. Taking a blue reaches $(m-1, n)$, where $n \ge 2$ and the total is odd, a win for the opponent. Taking a red reaches $(m, n-1)$: if $n - 1 \ge 2$ the total is again odd and the opponent wins, and if $n-1 = 1$ the opponent takes the last red and wins. So every move loses.

Count the pairs with $1 \le m, n \le 11$ that Alex wins:

• $n = 1$: all $11$ values of $m$.

• $n$ even, so $n \in \{2,4,6,8,10\}$: need $m$ odd, which is $6$ values, giving $5 \cdot 6 = 30$.

• $n$ odd and at least $3$, so $n \in \{3,5,7,9,11\}$: need $m$ even, which is $5$ values, giving $25$.

The total is $11 + 30 + 25 = 66$.

Answer 66

Solution: IOQM 2025 Part SEP, Q7

The condition is that any two vertices within four steps of each other, going around the polygon, receive different colours.

Why $n = 19$ fails. Fix a colour and look at the vertices carrying it. Any two of them are at least $5$ apart around the cycle, so if a colour is used $k$ times then going once around covers at least $5k$ steps, giving $5k \le n$. For $n = 19$ this means $k \le 3$. Six colours can therefore account for at most $6 \cdot 3 = 18$ vertices, one short of $19$. So no colouring exists.

Why every $n \ge 20$ succeeds. For instance, $21=5+5+5+6$. Put the colour strips around the polygon in that order: $$12345\mid12345\mid12345\mid123456.$$ Across a seam, five consecutive colours might look like $45\mid123$ or $56\mid123$; they remain different, including at the seam back to the first strip. For the general construction, cut the cycle into consecutive blocks, some of length $5$ and some of length $6$, colouring a block of length $5$ with the colours $1,2,3,4,5$ in order and a block of length $6$ with $1,2,3,4,5,6$ in order. Any five consecutive vertices either lie inside one block, where the colours are distinct by construction, or straddle two blocks, taking the last $j$ colours of one and the first $5-j$ of the next. The tail of a block of length $5$ is $\{6-j, \ldots, 5\}$ and of a block of length $6$ is $\{7-j, \ldots, 6\}$, while the head of the next block is $\{1, \ldots, 5-j\}$; in both cases the smallest entry of the tail exceeds the largest entry of the head, so the five colours are distinct. The same check covers the seam where the last block runs back into the first, since the argument used nothing about which blocks they were, only that a tail is followed by a head.

Such a decomposition exists exactly when $n$ can be written as $5s + 6t$ with $s, t \ge 0$, and every integer $n \ge 20$ can: writing $n = 5q + r$ with $r \in \{0,1,2,3,4\}$ and $q \ge 4$, take $t = r$ blocks of length six and $s = q - r$ blocks of length five, which is legitimate because $q \ge 4 \ge r$.

So $19$ is the largest polygon that is not colourful. (It is the last integer not of the form $5s+6t$, which is the reason the numbers five and six appear at all.)

Answer 19

Solution: IOQM 2025 Part SEP, Q28

In a regular dodecagon the equilateral triangles are $\{i, i+4, i+8\}$, four of them, and the squares are $\{i, i+3, i+6, i+9\}$, three of them. A vertex $i$ belongs to the triangle determined by $i \bmod 4$ and the square determined by $i \bmod 3$, and since $4$ and $3$ are coprime the pair $(i \bmod 4,\ i \bmod 3)$ determines $i$. So label the vertices by a $4 \times 3$ grid: the four triangles are the rows and the three squares are the columns.

Every vertex of the dodecagon appears exactly once in that grid, each row is one of the equilateral triangles and each column is one of the squares. Nothing about the dodecagon is needed from here on.

The condition is that no row and no column is monochromatic. Count by inclusion and exclusion over the set of rows and columns declared monochromatic. Fix $r$ rows and $c$ columns.

• If $r \ge 1$ and $c \ge 1$, a chosen row meets a chosen column, so all of them share one colour: $2$ choices, and the $(4-r)(3-c)$ untouched cells are free.

• If only rows are chosen, each takes its own colour: $2^r$, with $3(4-r)$ free cells.

• Similarly for columns alone.

So $$N = \sum_{r,c} (-1)^{r+c}\binom4r\binom3c \cdot \begin{cases} 2^{12} & r = c = 0,\\ 2^{r}\,2^{3(4-r)} & c = 0,\ r \ge 1,\\ 2^{c}\,2^{4(3-c)} & r = 0,\ c \ge 1,\\ 2 \cdot 2^{(4-r)(3-c)} & r,c \ge 1. \end{cases}$$ The rows-only terms give $4096 - 4096 + 1536 - 256 + 16 = 1296$ and the columns-only terms subtract $1536 - 192 + 8 = 1352$. The mixed terms, one for each $r$ from $1$ to $4$ and each $c$ from $1$ to $3$, are worth setting out rather than running together: $$\begin{array}{c|rrr} & c = 1 & c = 2 & c = 3 \\ \hline r = 1 & 1536 & -192 & 8 \\ r = 2 & -576 & 144 & -12 \\ r = 3 & 96 & -48 & 8 \\ r = 4 & -6 & 6 & -2 \end{array}$$ Their total is $962$. Adding the three parts, $N = 1296 - 1352 + 962 = 906$.

Writing $N = 100p + q$ gives $p = 9$ and $q = 6$, so $p + q = 15$.

Answer 15