. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Olympiad Training for Individual Study

Rigid
Based on “Understanding” at MOP 2016 IMO Team Training

EVAN CHEN《陳誼廷》
11 April 2026

》
BCX-RIGID

廷
誼 e
陳 Us
n 《 al
h e r n
C n t e
a n ,I
E v I S
y
B O T

OTIS, © Evan Chen, internal use only. Artwork contributed by Arul Kolla.

1
 Evan Chen《陳誼廷》 (OTIS, updated 2026-04-11) Rigid

§1 Lecture notes
§1.1 Discussion
By “rigid” problems, I mean a class of problems which focus on a specific concrete structure.
This can’t be defined formally, but here are some characteristics:

• Often the problem has few degrees of freedom.

• The structure is often pretty complex, and understanding it well is the entire point
of the problem.

• The particular task you’re asked to prove can feel very superficial, almost like an
answer extraction (like on the AIME). For example, you might be asked to count

》
the number of objects satisfying P , but in fact you simply characterize all the
objects satisfying P and then do the counting as a little step at the end.

廷
• One feels that one is discovering mathematics, rather than inventing it — the

誼 e
properties which you prove are forced upon you, rather than your design.

• Often there is only one solution to the problem, up to isomorphism.

陳 Us
These problems often rely on soft methods to solve, because most of the problem is

《
deciding what to prove about the given structure.

l
For some related discussion, you might see [Link]

e n a
the rigid philosophy is an example of a “soft” technique.

n
You can expect quite a few bijections on this unit, on paper.

C h
§1.2 Examples
e r
n ,I n t
a
Example 1.1 (TSTST 2016/4)

v
Prove that if n and k are positive integers satisfying ϕk (n) = 1, then n ≤ 3k . (Here

E S
ϕk denotes k applications of the Euler phi function.)

16TSTST4

y T I
Walkthrough. Let a, b, c, . . . , denote positive integers.

B O
(a) For positive integers a, b, show that n = 2a · 3b takes a + b steps.

(b) How many steps does each of n = 2a 5b , n = 2a 17b , 2a 3b 7c , 2a 11b take?

(c) Show that 2a 2017b takes a + 9b steps.

(d) Define the function w : N → Z≥0 by w(ab) = w(a) + w(b), w(2) = 1, and w(p) =
w(p − 1) for odd primes p. Figure out the connection between the values of w(p)
and your answer in (b).

(e) By looking at ν2 prove the conjecture in (d).

(f ) Show that w(n) is the number of steps required for n, if n is even. What if n is
odd?

(g) Show that w(n) ≥ log3 n by induction on n ≥ 1. (The case where n is composite is
immediate, so the only work is when n is prime.)

(h) In fact, prove that the stronger estimate n ≤ 2 · 3k−1 holds (and is best possible).

2
 Evan Chen《陳誼廷》 (OTIS, updated 2026-04-11) Rigid

As a rigid problem, this is a chief example: the point of the problem is to determine the
function w, and the “extraction” of comparing to log3 occurs at the end. It’s important
to realize that w is “God-given”; we were not permitted any decisions in deriving it.
It might be tempting to try and prove ϕ(n) ≥ n/3 or similar statements, but this is
false, and in any case not representative of small cases. However, I think trying the “small
cases”: which in this situation are those n with relatively few prime factors — suggests
that this is the wrong approach.

Example 1.2 (China TST 2018/2/3)

Two positive integers p and q are fixed. There is a blackboard with n positive integers
written on it. An operation is to choose two of the same number a, a written on the
blackboard, and replace them with a + p, a + q. Determine the smallest n (in terms

》
of p and q) for which such an operation could go on infinitely.

廷
18CHNTST23 Walkthrough.

誼 e
(a) Reduce the problem to the case where gcd(p, q) = 1. (Hint: if d := gcd(p, q) > 1,
then work modulo d.)

陳 Us
(b) Come up with a guess for the answer. It might be helpful to try (p, q) = (n, 1) and

《
(p, q) = (3, 2).

l
(c) It might seem right now the problem is not that rigid, because for example one

e n a
gets to make a choice at each step of the process what numbers are supposed to be

n
h
erased. But consider actually the smallest number on the board. What can you

r
say about it?

C t e
(d) Use your answer to (c) to eliminate the illusion of choice: prove that we can WLOG

n
n ,I
assume that we always operate on the smallest number. (You should assume n is

a
minimal for this part, meaning every entry is changed infinitely often.)

E v S
(e) Assume that the smallest number on the board initially is 0. Make sense of the

I following table, which is an example for (p, q) = (3, 5).

y
B O T
 
0 0
3 5 3 
 
6 5 8 5 
 
 6 10 8 8 6 
 
 9 10 8 8 11 
 
 9 10 13 11 11 9 
 
12 10 13 14 16 14
 

12 10 13 14 16 14 10
 
 
12 15 13 14 16 14 13 12
 
 
15 15 13 14 16 14 13 17
 
15 15 18 14 16 14 16 17
 
15 15 18 17 16 19 16 17
18 20 18 17 16 19 16 17

(f ) Come up with a construction with the minimal number of elements for which the
process goes on indefinitely. (For example, use engineer’s induction on the last rows
of the example above.)

3
 Evan Chen《陳誼廷》 (OTIS, updated 2026-04-11) Rigid

(g) Study the first nonzero numbers in each column of the above table, and come up
with a guess for what they are in terms of p and q in general. We’ll denote the set
of such numbers by S.
(h) Show that we set up the table above in such a way that the first two columns
contain every element of S.
(i) Prove that for every s ∈ S, there exists a column C (not including the first two)
such that max(S ∩ C) = s.
(j) Use this to show that the minimum you conjectured is correct.
This example is interesting because of part (c); it’s a surprising example of a problem
which does not look rigid at all when we first glance at it, but then turns out to lose most

》
of its degrees of freedom after a bit of thinking. In that way we get a problem which
really only has two parameters p and q and can make much progress by studying the

廷
resulting table.

誼 e
Example 1.3 (TSTST 2012/8)
Let n be a positive integer. Consider a triangular array of nonnegative integers as

陳 Us
follows:

《
Row 1: a0,1

l
Row 2: a0,2 a1,2

n
..

a
.. ..
.

e
..

. . .

n
Row n − 1: a0,n−1 a1,n−1 . . . an−2,n−1

h r
Row n: a0,n a1,n a2,n ... an−1,n

C t e
Call such a triangular array stable if for every 0 ≤ i < j < k ≤ n we have

n
a n ,I ai,j + aj,k ≤ ai,k ≤ ai,j + aj,k + 1.

E v S
For s1 , . . . , sn any nondecreasing sequence of nonnegative integers, prove that there

I
exists a unique stable triangular array such that the sum of all of the entries in row

y T
k is equal to sk .

B O
12TSTST8 Walkthrough. We’ll use induction on n, so essentially fixing the first n − 1 rows with
the values of s1 , . . . , sn−1 .
(a) Left-aligning the array, consider the example:
 
2
4 1 
 
5 3 1 
5 3 1 0
Verify that this is a stable array with (s1 , s2 , s3 , s4 ) = (2, 5, 9, 9).
(b) Write down the unique stable arrays for (s1 , s2 , s3 , s4 ) = (2, 5, 9, x) when x ∈
{10, 11, 12, 13, 14}. You should find that one entry changes at each step. The final
array should be:  
2
4 1 
 
5 3 1 
7 4 2 1

4
 Evan Chen《陳誼廷》 (OTIS, updated 2026-04-11) Rigid

(c) In part (b) you likely found that each of the entries in the bottom row interacts with
another entry, and there was always exactly one entry that could be incremented by
1. Find a natural way to construct a tournament on the bottom row such that an
entry can be incremented if and only if it is a source (all edges point away from it).

(d) What property does this tournament have that ensures exactly one vertex is a
source at each step? Verify your conjecture directly from the definition of a stable
array.

(e) Using what you have found, prove existence using induction on sn .

(f ) Prove uniqueness of sn . One way to do this is to again use induction, using again
the tournament property you found in (d) a couple times. There is also a direct
proof that is less motivated, by bounding.

》
This problem is especially amenable to “rigid”-type thinking due to the guarantee that

廷
there exists a unique stable array for each (sn )n . Thus you are essentially guaranteed that
all the examples you come up with when playing with the problem are “the” examples.

誼 e
This allows you to verify from data for example that the stable arrays going from
sn → sn + 1 are indeed just increasing one entry by one. Part (b) of this walkthrough is

陳 Us
critical, because that is the data on which the later claims are based.

n 《 al
h e r n
C n t e
a n ,I
E v I S
y
B O T

5
 Evan Chen《陳誼廷》 (OTIS, updated 2026-04-11) Rigid

§2 Practice problems
Instructions: Solve [32♣]. If you have time, solve [40♣]. Problems with red weights are mandatory.

The only thing I’m really good at is. . . That’s it!

BARKING! There really isn’t much else in life!

Missile in Ghost Trick

95SLS3
[3♣] Problem 1 (Shortlist 1995). For an integer x ≥ 1, let p(x) be the least prime
that does not divide x, and define q(x) to be the product of all primes less than p(x).
In particular, p(1) = 2. For x having p(x) = 2, define q(x) = 1. Consider the sequence
x0 , x1 , x2 , . . . defined by x0 = 1 and

》
xn p(xn )
xn+1 =

廷
q(xn )

for n ≥ 0. Find all n such that xn = 1995.

誼 e
17IMO1
[3♣] Problem 2 (IMO 2017/1). For each integer a0 > 1, define the sequence a0 , a1 , a2 ,

陳 Us
. . . , by (√ √
if an is an integer,

《
an
an+1 =
an + 3 otherwise

n al
for each n ≥ 0. Determine all values of a0 for which there is a number A such that

e n
an = A for infinitely many values of n.

h r
21NICE1

C e
[2♣] Problem 3 (NICE 2021/1). The fibboican sequence a1 , a2 , . . . is defined by

t
a1 = a2 = 1, and for integers k ≥ 3,

a n ,I n
• ak = ak−1 + ak−2 if k is odd

•
v S
if k is even.
1 1 1
= +

E I
ak ak−1 ak−2

Prove that, for each integer m ≥ 1, the numerator of am (when written in simplest form)

11MOPR32
y
B O T
is a power of 2.

[2♣] Problem 4 (MOP 2011). Let S be a finite set with |S| > 1 and let P(S) denote
the set of all subsets of S. A function f : P(S) → P(S) is called united if f (∅) = ∅ and
f (A) ∪ f (B) = f (A ∪ B) for any A, B ∈ P(S). Show that the number of united functions
is a perfect power.
20SLC1
[3♣] Problem 5 (Shortlist 2020 C1). Let n be a positive integer. Find the number of
permutations a1 , . . . , an of 1, . . . , n satisfying

a1 ≤ 2a2 ≤ · · · ≤ nan .
06SLA1
[3♣] Problem 6 (Shortlist 2006 A1). A sequence of real numbers a0 , a1 , . . . is defined
recursively by
ai+1 = bai c · {ai }
for i ≥ 0, where {x} = x − bxc is the fractional part. Prove that ai+2 = ai for sufficiently
large indices i.

6
 Evan Chen《陳誼廷》 (OTIS, updated 2026-04-11) Rigid

19IMO5
[5♣] Required Problem 7 (IMO 2019/5). Let n be a positive integer. Harry has n
coins lined up on his desk, which can show either heads or tails. He does the following
operation: if there are k coins which show heads and k > 0, then he flips the kth coin
over; otherwise he stops the process. (For example, the process starting with T HT would
be T HT → HHT → HT T → T T T , which takes three steps.)
Prove the process will always terminate, and determine the average number of steps
this takes over all 2n configurations.
07SLC1
[5♣] Problem 8 (Shortlist 2007 C1). Let n ≥ 1 be an integer. Find all sequences a1 ,
a2 , . . . , an2 +n consisting of 0 and 1 such that
ai+1 + ai+2 + · · · + ai+n < ai+n+1 + ai+n+2 + · · · + ai+2n

》
for all 0 ≤ i ≤ n2 − n.
19SLC1
[5♣] Required Problem 9 (Shortlist 2019 C1). The infinite sequence a0 , a1 , . . .of

廷
integers satisfies the relations 0 ≤ an ≤ n and

誼 e
     
n n n
+ + ··· + = 2n
a0 a1 an

陳 Us
for every nonnegative integer n. Show that every nonnegative integer appears in the

《
sequence.
13JMO4

l
[3♣] Problem 10 (JMO 2013/4). Let f (n) be the number of ways to write n as a sum

e n n a
of powers of 2, where we keep track of the order of the summation. For example, f (4) = 6
because 4 can be written as 4, 2 + 2, 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2, and 1 + 1 + 1 + 1.

h r
Find the smallest n greater than 2013 for which f (n) is odd.

C e
t
98SLN8
[3♣] Problem 11 (Shortlist 1998 N8). Let a0 , a1 , a2 , . . . be an increasing sequence of

n ,I n
nonnegative integers such that every nonnegative integer can be expressed uniquely in

a
the form ai + 2aj + 4ak , where i, j and k are not necessarily distinct. Determine a1998 .

v
05IMO2

S
[3♣] Problem 12 (IMO 2005/2). Let a1 , a2 , . . . be a sequence of integers with infinitely

E I
many positive and negative terms. Suppose that for every positive integer n the numbers

y T
a1 , a2 , . . . , an leave n different remainders upon division by n. Prove that every integer
occurs exactly once in the sequence.

B O
18APMO4
[3♣] Problem 13 (APMO 2018/4). Let ABC be an equilateral triangle. From the
vertex of A we draw a ray towards the interior of the triangle such that the ray reaches
one of the sides of the triangle. When the ray reaches a side, it then bounces off following
the law of reflection. After n bounces the ray returns to A for the first time without ever
landing on any of the other two vertices. Find all possible values of n.
15EGMO2
[5♣] Problem 14 (EGMO 2015/2). A domino is a 2 × 1 or 1 × 2 tile. Determine in
how many ways exactly n2 dominoes can be placed without overlapping on a 2n × 2n
chessboard so that every 2 × 2 square contains at least two uncovered unit squares which
lie in the same row or column.
15AMO3
[9♣] Required Problem 15 (USAMO 2015/3). Let S = {1, 2, . . . , n}, where n ≥ 1.
Each of the 2n subsets of S is to be colored red or blue. (The subset itself is assigned a
color and not its individual elements.) For any set T ⊆ S, we then write f (T ) for the
number of subsets of T that are blue.
Determine the number of colorings that satisfy the following condition: for any subsets
T1 and T2 of S,
f (T1 )f (T2 ) = f (T1 ∪ T2 )f (T1 ∩ T2 ).

7
 Evan Chen《陳誼廷》 (OTIS, updated 2026-04-11) Rigid

15APMO3
[5♣] Problem 16 (APMO 2015/3, added by Haozhe Yang). Find the smallest positive
integer n such that there exists a sequence a0 , a1 , . . .of real numbers such that:

(i) a0 is a positive integer;

(ii) for each nonnegative integer i we have either ai+1 = 2ai + 1 or ai+1 = ai +2 .
ai

(iii) an = 2014.
25IMO1
[3♣] Problem 17 (IMO 2025/1). A line in the plane is called sunny if it is not parallel
to any of the x-axis, the y-axis, or the line x + y = 0.
Let n ≥ 3 be a given integer. Determine all nonnegative integers k such that there
exist n distinct lines in the plane satisfying both of the following:

》
• for all positive integers a and b with a + b ≤ n + 1, the point (a, b) lies on at least

廷
one of the lines; and

• exactly k of the n lines are sunny.

誼 e
11SLN1
[3♣] Problem 18 (Shortlist 2011 N1). For any integer d > 0, let f (d) be the smallest

陳 Us
positive integer that has exactly d positive divisors (for example, f (1) = 1, f (5) = 16,
and f (6) = 12). Prove that for every integer k ≥ 0, f (2k ) divides f (2k+1 ).

《
24SLA2

l
[3♣] Problem 19 (Shortlist 2024 A2). Let n be a fixed positive integer. Find the

n a
minimum possible value of

h e r n S = 20 x20 + 21 x21 + · · · + 2n x2n ,

C t e
where x0 , . . . , xn are nonnegative integers such that x0 + · · · + xn = n.

n
a n ,I
[2♣] Problem 20. What do the previous two problems have in common? (See https:

v
//[Link]/write-well/ for a nudge. This assumes you found the nice solution

S
to 2024 A2, rather than the induction-calculation one.)

y E T I
[1♣] Mini Survey. Fill out feedback on the OTIS-WEB portal when submitting this
problem set. Any thoughts on problems (e.g. especially nice, instructive, easy, etc.) or

B O
overall comments on the unit are welcome.
In addition, if you have any suggestions for problems to add, or want to write hints for
one problem you really liked, please do so in the ARCH system!

The maximum number of [♣] for this unit is [72♣], including the mini-survey.

8
 Evan Chen《陳誼廷》 (OTIS, updated 2026-04-11) Rigid

§3 Solutions to the walkthroughs

§3.1 Solution 1.1, TSTST 2016/4
The main observation is that the exponent of 2 decreases by at most 1 with each
application of ϕ. This will give us the desired estimate.
Define the weight function w on positive integers as follows: it satisfies
w(ab) = w(a) + w(b);
w(2) = 1; and
w(p) = w(p − 1) for any prime p > 2.
By induction, we see that w(n) counts the powers of 2 that are produced as ϕ is repeatedly
applied to n. In particular, k ≥ w(n).

》
From w(2) = 1, it suffices to prove that w(p) ≥ log3 p for every p > 2. We use strong
induction and note that

廷
 
p−1
w(p) = w(2) + w ≥ 1 + log3 (p − 1) − log3 2 ≥ log3 p

誼 e
2
for any p > 2. This solves the problem.

陳 Us
Remark. One can motivate this solution through small cases 2x 3y like 2x 17w , 2x 3y 7z ,

《
2x 11t .
Moreover, the stronger bound

n l
n ≤ 2 · 3k−1

e a
is true and best possible.

h n
C t e r
§3.2 Solution 1.2, China TST 2018/2/3

n ,I n
p+q
The answer is gcd(p,q) . Obviously we may assume that gcd(p, q) = 1 (if d := gcd(p, q) > 1,

va
then numbers on the blackboard which are different modulo d never interact, so we have

S
d independent blackboards); we prove in that case n ≥ p + q is optimal.

y E T I
To see n = p + q is sufficient, consider a board with {1, . . . , p} t {1, . . . , q}; this clearly
can last forever. We now show n ≥ p + q is necessary.
Assume n minimal, which implies that every entry is changed infinitely many times.

B O
We’ll consider the entire blackboard as generating an infinite table with n columns, such
that each row is obtained from the previous one by replacing a, a with a + p, a + q (for
some a), and each column is unbounded.
An example of such a table is below for p = 3, q = 5.
 
0 0
3 5 3 
 
6 5 8 5 
 
 6 10 8 8 6 
 
 9 10 8 8 11 
 
 9 10 13 11 11 9 
 
12 10 13 14 16 14
 

12 10 13 14 16 14 10
 

12 15 13 14 16 14 13 12
 
 
15 15 13 14 16 14 13 17
 
15 15 18 14 16 14 16 17
 
15 15 18 17 16 19 16 17
18 20 18 17 16 19 16 17

9
 Evan Chen《陳誼廷》 (OTIS, updated 2026-04-11) Rigid

Now, WLOG (by shifting and rearranging) and first two entries of first row are 0,
and all others are nonnegative. We then add the additional condition (as we may) that
whenever the first column is erased we increment that entry by p, and whenever the
second column is erased we increment that entry by q. Thus the first column will contain
all positive multiples of p and the second column will contain all positive multiples of q.

Claim — Let S = {p, 2p, . . . , (q − 1)p} ∪ {q, 2q, . . . , (p − 1)q}. Then for every
s ∈ S, there exists a column C other than the first or second column such that
max(S ∩ C) = s.

Proof. Let t ∈ S and assume p | t (other case similar). Since it is incremented by p in

the first column, there must be some column containing t followed immediately by t + q.
That column then cannot contain any larger elements of S. Indeed, the next smallest

》
multiples of p and q exceeding t + q are t + pq and pq + q, respectively.

廷
Hence the number of columns is at least 2 + #S = p + q, as needed.

誼 e
Remark. After making the assumption that n is minimal, the main way to motivate is
that at any point the smallest number must have a partner (for it to change infinitely often)

陳 Us
and we may as well operate on that smallest number now, rather than later (that operation
commutes earlier).

《
In this way, once we set the starting numbers to be 0 and 0, say, then the rest of the
process is essentially fixed by the following algorithm:

e n al
• Look at the smallest number, operate it if possible,

h n
• Otherwise, add a new column with that smallest number and operate.

C e r
So the problem becomes rigid, as p and q are the only parameters, after which the blackboard

t
is essentially autonomous in determining the optimal value of n. The example above

n ,I n
illustrates this.

va
S
Remark. Ankan Bhattacharya points out an alternative approach to showing n ≥ p + q by

E I
chip-firing. It suffices to work modulo p + q for this bound.
Consider the residues of V = Z/(p + q) and the graph G on V with adjacency relations

y
B O T
x ∼ x + p, (equivalently x ∼ x + q; hence G is a cycle). Then an operation corresponds to
chip-firing on this graph. The theory of chip-firing then says that this can go on indefinitely
only if n ≥ #E(G) = p + q.

§3.3 Solution 1.3, TSTST 2012/8

Firstly, here are illustrative examples showing the arrays for (s1 , s2 , s3 , s4 ) = (2, 5, 9, x)
where 9 ≤ x ≤ 14. (The array has been left justified.)
   
2 . 2 . 2 .
4 1 .  4 1 .  4 1 . 
   
5 3 1 .  5 3 1 . 5 3 1 .
5 3 1 0 6 3 1 0 6 3 2 0
   
2 . 2 . 2 .
4 1 .  4 1 .  4 1 . 
   
5 3 1 . 5 3 1 .  5 3 1 .
6 4 2 0 6 4 2 1 7 4 2 1

10
 Evan Chen《陳誼廷》 (OTIS, updated 2026-04-11) Rigid

Now we outline the proof. By induction on n, we may assume the first n − 1 rows
are fixed. Now, let N = sn vary. Now, we prove our result by (another) induction on
N ≥ sn−1 .
The base case N = sn−1 is done by copying the n − 1st row and adding a zero at the
end.
P This is also unique, since ai,n ≥ ai−1,n + an−1,n for all i = 0, . . . , n − 2, whence
ai,n ≥ sn−1 follows.
Now the inductive step is based on the following lemma, which illustrates the idea of a
“unique increasable entry”.

Lemma
Fix a stable array Construct a tournament on the n entries of the last row as follows:
for i < j,

》
• ai,n → aj,n if ai,n = ai,j + aj,n , and

廷
• aj,n → ai,n if ai,n = ai,j + aj,n + 1.

誼 e
Then this tournament is transitive. Also, except for N = sn−1 , a 0 entry is never a
source.

陳 Us
Intuitively, ai,n → aj,n if ai,n blocks aj,n from increasing. For instance, in the example

《 l
 
2 .

e n a
4 1 . 

n
 

h
 5 3 1 .

r
6 3 1 0

C t e
the tournament is 1 → 3 → 0 → 6.

n
a n ,I
Proof of lemma. Let 0 ≤ i < j < k < n be indices. Let x = ai,n , y = aj,n , z = ak,n ,

v
p = ai,j , s = ai,k , q = aj,k . Picture:

E I S
 
p .

y T
 s q .

B O
x y z

If x → y → z → x happens, that means x = y + p, y = q + z, x = s + z + 1, which gives

s = p + q − 1, contradiction. Similarly if x ← y ← z ← x then x = y + p + 1, y = q + z + 1,
x = s + z, which gives s = p + q + 2, also contradiction.

Now this allows us to perform our induction. Indeed, to show existence from N to N +1
we take a source of the tournament above and increase it. Conversely, to show uniqueness
for N , note that we can take the (nonzero) sink of the tournament and decrement it,
which gives N − 1; our uniqueness inductive hypothesis now finishes.

Remark. Colin Tang found a nice proof of uniqueness:

k−1
X X
sk + a0,i ≤ ka0,k ≤ sk + (a0,i + 1)
i=1 i=1

and similarly for other entries.

11