NICE Journal

NICE Committee

April 2, 2021
Mock SAT Prompt
Some Background
Reading this journal requires a high level of experience with skills of all natures, includ-
ing essay writing. Please complete the following to see if you are capable of understand-
ing the journal entries.

Prompt
V ENHANCE’S MOCK SAT1EVAN CHEN AND V ENHANCE AND JAMES4L

Essay Prompt. Think carefully about the issue presented in the following excerpt
and the assignment below.
It is impossible for a cube to be written as a sum of two cubes or a
fourth power to be written as the sum of two fourth powers or, in
general, for any number which is a power greater than the second
to be written as a sum of two like powers. I have a truly marvelous
demonstration of this proposition which this margin is too small to
contain.
– Pierre De Fermat
Assignment: Do there exist nonzero integers x, y, z, and n > 2 such that
xn + y n = z n ?
Plan and write an essay in which you prove or disprove Fermat’s conjecture. Sup-
plement your proof with reasoning and examples taken from your reading, studies,
experience, or observations.

Work Space
Use the space below to write your answer. Your answer must consist of 3 syllable words,
each rhyming with “cucumber”.

Do not turn the page over until you are finished with this prompt. Failure to follow
" this rule will result in immediate disqualification from reading this journal. Please
alert the supervising teacher know when you have completed this assignment.

2
NICE Committee (April 2, 2021) NICE Journal

APRIL FOOLS!
Obviously this is not a legitimate test. The essay prompt was made by Evan Chen several
years ago, and we thought it would be interesting for an April Fools joke. If you’re
interested in some other math-themed April Fools jokes, take a look at
• this mock AIME (see problem 15 in particular),
• this fake AIME,

• the NIMO April rounds (specifically, take a look at the USAYNO contest; the same
idea appears in problems 33-36 on HMMT February Guts 2017),
• this math professor’s prank, and
• another one of the professor’s pranks.

Okay, now onwards with the real material!

3
NICE Journal NICE Committee (April 2, 2021)

4
NICE Committee (April 2, 2021) NICE Journal

Oops.

5
Preface
Hello everyone!

This is the first ever NICE Journal, and we’re glad that you’ve decided to read us. Below
is a short list of notes and questions that may enhance your reading experience.

What is this journal?

This is a journal of selected articles we thought the math community might enjoy.

What this journal is not

This journal is not:

• a list of everything you’ll need for contests,

• limited to math contest articles (but this is our main focus for the time being),

• for the weak, or

• a shoe.

Some humorous notes

• The chapter on Complex Numbers was written by David in 2014. It was intended
for AoPS, but it was never published. We included it in our journal because it is (a)
a good and informative read and (b) for the memes.

• I (Dylan) will try to clarify who is talking when we use first person, but you can
assume it is the person who wrote the text. If you want, you can just pretend we are
one person like in those combinatorics problems that require you to treat people
who want to sit together as a single being.

• There are no more April Fools pranks after this page. I promise.

Chapter Authors and Descriptions

You may be interested in knowing the authors of the journal entries or some information
about them. Here they are:
6
NICE Committee (April 2, 2021) NICE Journal

Entry Name Author Description

Some strategies for eval-
uating sums, e.g. sym-
Summations Eric Shen metry, partial fraction de-
composition, and tele-
scoping.
Some combinatorial ar-
guments, including bijec-
Combinatorial Arguments Neil Shah
tions, identities, and the
use of Catalan numbers.
Basic properties of com-
Complex Numbers David Altizio plex numbers and their re-
lation to geometry.
The method of bounding
two sides (with squares)
Bounding between Squares Valentio Iverson
to reduce the problem to
finite cases.
Solving problems with
specific focus on general
Soft Techniques Abhay Bestrapalli
heuristics, e.g. symmetry
and visualization.

Acknowledgements
We would like to thank everyone involved in this journal:

• David Altizio • Neil Shah • Dylan Yu

• Sanjana Das • Eric Shen
• Valentio Iverson • Yuchan Yang • Alex Zhao

The author of Combinatorial Arguments would like to thank Kevin Wu.

Final words before you start reading

Again, we’re very excited that you’re taking your time to read this body of work. Let us
know if you have any suggestions, and have fun learning math!

Sincerely,
Dylan Yu

7
Contents
1 Summations 10
1.1 A Few Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 Fundamental Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Partial Fraction Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Telescoping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 Combinatorial Arguments 18
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 The Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.1 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2 Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.3 Relations to the Binomial Theorem . . . . . . . . . . . . . . . . . . . 21
2.3 Bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.1 Putting People in Committees . . . . . . . . . . . . . . . . . . . . . 22
2.3.2 Walking on a Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.3 Grid-Walking on Pascal’s Triangle . . . . . . . . . . . . . . . . . . . 25
2.3.4 Other Assorted Bijections . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4 Common Combinatorial Identities . . . . . . . . . . . . . . . . . . . . . . . 29
2.4.1 Stars and Bars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4.2 Hockey-Stick Identity . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.3 Vandermonde’s Identity . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5 Catalan Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5.1 Bijecting Them . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5.2 Finding Them in Problems . . . . . . . . . . . . . . . . . . . . . . . 34
2.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3 Complex Numbers 37
3.1 Introduction and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Complex Numbers through an Algebraic Lens . . . . . . . . . . . . . . . . 37
3.2.1 The Substitution z = a + bi . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.2 Working with Magnitudes and Conjugates . . . . . . . . . . . . . . 40
3.3 Basic Geometric Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.1 Triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.2 Analysis of Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4 Rotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4 Bounding between Squares 47

4.1 Before Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
8
NICE Committee (April 2, 2021) NICE Journal

4.2 Lecture Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2.2 A Nontrivial Example . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 Useful Theorems and Strategies . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3.1 Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3.2 Grand Finale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3.3 Summary of Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4.1 Easier Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4.2 Challenging Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5 Soft Techniques 55
5.1 Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2 Visualisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

A Key Parts 65
A.1 List of Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
A.2 List of Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
A.3 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

B Selected Solutions 70

9
1 Summations
â1.1 A Few Tips
Here are a few general things that work:

1. Just know your basic sums. This includes arithmetic/geometric series, consecutive
squares, consecutive cubes, and the like. Remember also your usual trig and/or
complex number stuff – for example for the kth root of unity 1 + w + . . . + wk−1 =
0.1

2. Exploit symmetry when you see it. We’ll have a cool example on this later.

3. A lot of people forget to do this – if you’re stuck, try small cases! This often helps
you understand what’s going on and what cancellations need to occur.

4. Don’t hesitate to substitute stuff to make your life easier – this goes along pretty
well with the next point.

5. Finally, telescoping. We’ll look more into this later, but basically the idea behind
telescoping is that when summing a series we make each term into a difference of
two terms, allowing us to basically have everything cancel except for a few edge
terms.
Something that works well with this is partial fraction decomposition – a technique
that allows you to separate one fraction with linear terms in the bottom into a bunch
of different fractions.

â1.2 Fundamental Examples

Here are some non-telescoping token examples:

Example 1 (Putnam 2015/B4)

Let T be the set of all triples ( a, b, c) of positive integers for which there exist triangles
with side lengths a, b, c. Express
2a
∑ 3b 5c
( a,b,c)∈ T

as a rational number in lowest terms. Solution: 2

1 Remember to factor stuff when necessary to make sums easier to handle.
10
NICE Committee (April 2, 2021) NICE Journal

Walkthrough. If you’ve ever done inequalities before you know exactly what to do. If not,
this won’t be so much of a walkthrough as just me introducing something cool that deals
with the condition.

1. Derive an inequality between a, b, and c.

What we do now is called the Ravi Substitution which replaces the numbers with
x + y, y + z, z + x in some order.

2. Perform this substitution and repeat the inequality on x, y, and z. What do we get,
and why is this useful?
At this point we’re a lot closer.

3. Factor the expression into a product of a few independent geometric series, multi-
plied by a constant.

4. Finish.

Now here’s a token symmetry example:

Example 2 (HMMT February Algebra 2019/7)

Find the value of
∞ ∞ ∞
ab(3a + c)
∑ ∑ ∑ 4a+b+c (a + b)(b + c)(c + a) .
a =1 b =1 c =1
Solution: 15

Walkthrough. The symmetry step comes right off the bat:

1. Prove that the expression is equal to

∞ ∞ ∞
ab(3b + c)
∑∑∑ 4 a+b+c ( a + b )( b + c )( c + a )
.
a =1 b =1 c =1

2. Sum cyclically to get a symmetric expression. You should be summing 6 terms here.

3. Factor the top. Note that since the expression is probably going to cancel pretty
well (it’s short answer!) you can probably use the denominator as a hint for this
part.

4. Cancel stuff to make this into a geometric series question.

5. Solve the geometric series question and win.

11
NICE Journal NICE Committee (April 2, 2021)

â1.3 Partial Fraction Decomposition

The idea behind PFD is that we are given something like this:
3x + 9
(2x + 1)(7x − 4)
and we want to separate it into something like this:
A B
+ .
2x + 1 7x − 4
To do this we just cross multiply to get:

A(7x − 4) + B(2x + 1) = 3x + 9.

Now we compare coefficients:

7Ax + 2Bx = 3x
7A + 2B = 3
−4A + B = 9.
Solving this gives ( A, B) = (−1, 5), or in other words:
3x + 9 1 5
=− + .
(2x + 1)(7x − 4) 2x + 1 7x − 4
As we’ll see later, separating fractions into this form is quite useful because it allows for
telescoping and in general just individual manipulation of the sum components.

â1.4 Telescoping
The main idea of telescoping as some of you may know is to just separate one term into
two terms. This is probably best explained through example, so here’s a classic one:

Example 3 (Folklore)
Compute the value of

1 1 1
+ +...+
1·2 2·3 99 · 100
Solution: 16

Walkthrough.
1
1. Note that we’re just summing . PFD this.
n ( n + 1)
12
NICE Committee (April 2, 2021) NICE Journal

2. Watch terms cancel.

Here’s my (Eric Shen’s) favorite PFD example:

Example 4 (COMC 2014/4)

1
Let f ( x ) = 3 . Determine the smallest positive integer n such that
x + 3x2 + 2x
503
f (1) + f (2) + f (3) + . . . + f ( n ) > .
2014
Solution: 9

Walkthrough.

1. Factor the denominator.

2. Note that we have three linear terms instead of two. However, we can still do this!
Put A, B, and C as your coefficients, and solve for the triple. Note that this step
might take more time than most other steps.

3. Now that that’s out of the way, sum it all up and see what you get.

4. Cancel stuff to get a bound. It should be quadratic.

5. Finish (be careful here).

Example 5 (IMO 2002/4)

Let n ≥ 2 be a positive integer, with divisors 1 = d1 < d2 < . . . < dk = n. Prove that
d1 d2 + d2 d3 + . . . + dk−1 dk is always less than n2 , and determine when it is a divisor of
n2 . Solution: 35

Walkthrough. Given this, it looks kind of hard to approach this naturally. We could
bound, but that would probably get pretty messy. Thus we start off with a few examples:

1. Compute the case n = 6.

2. Compute the case n = 12, if you’re willing to.

3. Now in the cases above, divide everything by n2 . We do this because that leaves 1
on one side all the time and that might be nice.

4. Do you see what’s going? In particular, look closely at the smaller terms.
Hopefully this gives you an idea of what to do. In particular, if you see something
that might telescope you’re super set for this.

5. Compute i such that d1 di−1 = n2 .

13
NICE Journal NICE Committee (April 2, 2021)

6. Reciprocate everything.
At this point we almost have the first telescoping example.

7. Use an inequality to basically get the telescoping expression of this well-known

example.
8. Telescope to show that the expression is always less than n2 .
9. Prove that when the expression is a divisor of n2 when n is prime.
n2
10. Prove that the expression exceeds p when n is not prime and p is the smallest
prime dividing n.

11. Finish by using the above step to show the desired result.

When dealing with values of the form x−1 A , we can get around x 6= A by multiplying the
whole equation by ( x − A), then plugging it in. Here is an example to illustrate this.

Example 6 (AMC 10A 2019/24)

Let p, q, and r be the distinct roots of the polynomial x3 − 22x2 + 80x − 67. It is given
that there exist real numbers A, B, and C such that
1 A B C
= + +
s3 − 22s2 + 80s − 67 s − p s − q s − r
1 1
for all s 6∈ { p, q, r }. What is A + B + C1 ? Solution: 42

Walkthrough.

1. Let f ( x ) = x3 − 22x2 + 80x − 67. Multiply the equation given in the problem by
f ( x ) (in its factored form) on both sides.
2. Substitute in s = p. Yes, I know it says don’t do this – do it anyways.
3. Redo with s = q, r and sum your three equations. Vieta’s to finish.

â1.5 Problems
1 1 1
Problem 1. Evaluate √ √ +√ √ +···+ √ √ .
1+ 2 2+ 3 1368 + 1369

14
NICE Committee (April 2, 2021) NICE Journal

Problem 2 (AMC 12B 2018/7). What is the value of

log3 7 · log5 9 · log7 11 · log9 13 · · · log21 25 · log23 27?

Problem 3 (AMC 12B 2018/9). What is

100 100
∑ ∑ (i + j ) ?
i =1 j =1

Problem 4 (AIME I 2016/1). For −1 < r < 1, let S(r ) denote the sum of the geometric
series
12 + 12r + 12r2 + 12r3 + . . . .
Let a between −1 and 1 satisfy S( a)S(− a) = 2016. Find S( a) + S(− a).

Problem 5 (AIME II 2005/3). An infinite geometric series has sum 2005. A new series,
obtained by squaring each term of the original series, has 10 times the sum of the original
series. The common ratio of the original series is m
n where m and n are relatively prime
integers. Find m + n.

Problem 6 (HMMT February Algebra 2017/2). Find the value of

1
∑ 2 a 3b 5c
1≤ a < b < c

1
(i.e. the sum of 2 a 3b 5c
over all triples of positive integers ( a, b, c) satisfying a < b < c).

Problem 7. Find
22 32 20062
· · . . . ·
22 − 1 32 − 1 20062 − 1

Problem 8 (AMC 12A 2018/19). Let A be the set of positive integers that have no prime
factors other than 2, 3, or 5. The infinite sum
1 1 1 1 1 1 1 1 1 1 1 1 1 1
+ + + + + + + + + + + + + +···
1 2 3 4 5 6 8 9 10 12 15 16 18 20
m
of the reciprocals of the elements of A can be expressed as n, where m and n are relatively

15
NICE Journal NICE Committee (April 2, 2021)

prime positive integers. What is m + n?

Problem 9 (AMC 12B 2019/8). Let f ( x ) = x2 (1 − x )2 . What is the value of the sum
       
1 2 3 4
f −f +f −f +···
2019 2019 2019 2019
   
2017 2018
+f −f ?
2019 2019

Problem 10 (AIME I 2019/1). Consider the integer

N = 9 + 99 + 999 + 9999 + · · · + 99
| .{z
. . 99} .
321 digits

Find the sum of the digits of N.

Problem 11 (AIME I 2017/3). For a positive integer n, let dn be the units digit of 1 + 2 +
· · · + n. Find the remainder when
2017
∑ dn
n =1

is divided by 1000.

√ 12 (AMC 12B 2016/25). The sequence ( an ) is defined recursively by a0 = 1,

Problem
a1 = 19 2, and an = an−1 a2n−2 for n ≥ 2. What is the smallest positive integer k such that
the product a1 a2 · · · ak is an integer?

Problem 13 (AMC 12B 2016/21). Let ABCD be a unit square. Let Q1 be the midpoint
of CD. For i = 1, 2, . . . , let Pi be the intersection of AQi and BD, and let Qi+1 be the foot
of the perpendicular from Pi to CD. What is
∞
∑ Area of 4 DQi Pi ?
i =1

Problem 14. Determine the value of the sum

1 2 n−1
+ +...+
2! 3! n!

16
NICE Committee (April 2, 2021) NICE Journal

Problem 15. Determine the value of the sum

3 5 29
+ 2 2 +...+ 2
12 · 22 2 ·3 14 · 152

Problem 16. Compute

∞
n3 + 1
∏ n3 − 1
n =2

Problem 17 (SMT Advanced Topics 2011/2). Compute

(7n + 32) · 3n
∑ n · ( n + 2 ) · 4n
n ≥1

1 √
Problem 18 (ARML Local Team 2019/15). Given that ∑∞ 2k
k =0 ( k ) k
= 5, compute the
5
value of the sum
∞
2k + 1 1
 
∑ k 5k
k =0

Problem 19 (USAMTS 3/4/11). Determine the value of

r r r
1 1 1 1 1 1
1+ 2 + 2 + 1+ 2 + 2 +... 1+ 2
+
1 2 2 3 1999 20002

Problem 20. Evaluate ∑nk=2 k!(k2 + k + 1).

Problem 21 (AIME II 2000/15). Find the least positive integer n such that

1 1 1 1
+ +···+ = .
sin 45◦ sin 46◦ sin 47◦ sin 48◦ sin 133◦ sin 134◦ sin n◦

17
2 Combinatorial Arguments
â2.1 Introduction
If you’re reading this, there’s a high likelihood that you’ve already dealt with combina-
torial arguments in some capacity. However, for those of you who haven’t, this article
begins by starting with the basics and building up from there. The natural starting point
is to address the sub-field of mathematics into which combinatorial arguments fall.

Combinatorics
Combinatorics is the study of selection, arrangement and operation within a finite or
discrete system.

If you put this into simple English, combinatorics is basically the study of counting. As
you may have guessed, a combinatorial argument is an argument that applies combina-
torics, which means that a combinatorial argument is essentially a “way of counting.”
Note that this article aims to tackle combinatorial arguments primarily in the context
of computational problems. Hence, it’s not a surprise that many problems in this article
and in related contexts often deal with counting the number of ways that something can
be done.

â2.2 The Basics

It’s impossible to have a proper discussion of combinatorial arguments without mention-
ing permutations and combinations. Let’s start with the first.

â2.2.1 Permutations
Theorem 7 (Permutations of Items)
Given n items, there are n! ways to rearrange (permute) them.

Proof. The idea behind this is quite intuitive if we take a “left to right” approach. We
have n items and we have n spots to place them in. If we start at the left and move to the
right, there are n possible items that could go in the first spot, n − 1 that could go in the
second spot after that, and we see that this pattern continues onward. The number of
items that could possibly go in each slot decreases by 1 each time, as 1 item is used up by
being placed each time. If we multiply out all of these numbers of ways, we have a total
of n! permutations!
18
NICE Committee (April 2, 2021) NICE Journal

Computing permutations can be done using factorials for some slightly more complex
situations as well. For example, we can tackle this:

Example 8
How many ways can you permute the letters in the word WADDLE? Solution: 37

Walkthrough.
1. How many ways are there to choose a possible letter for the first letter? Ignore the
duplicate letters and repeat this process for each letter.
2. How many times is each permutation overcounted?
3. Divide and get your answer!
It’s the same for all situations where we have duplicates. For example, if we have
MISSISSIPPI and we want to find the number of permutations, we have to divide by 4!,
4! again, and 2! to account for all of the duplicates from the original n! where n is the
number of letters. In general, we have:

Theorem 9 (Permuting with Duplicates)

If we have n total items and there are distinct groups of duplicates of sizes d1 , . . . , dk
(not necessarily distinct), the total number of permutations is

n!
.
d1 ! . . . d k !

Exercise 10. Convince yourself that the above is always true.

â2.2.2 Combinations
Using the idea of computing the number of permutations, we can tackle the other building
block of computational combinatorial arguments. This is the idea of “combinations.”
Combination
The function (nk), named the combination function, denotes the number of ways that k
objects can be chosen from n distinct objects. This is why the function is often referred
to as “n choose k.”

Theorem 11 (Combination Closed Form)

The expression (nk) can be expanded out as:
 
n n!
= .
k k!(n − k)!

19
NICE Journal NICE Committee (April 2, 2021)

The motivation to use counting techniques in this situation comes from the presence of
factorials in the statement. Generally, factorials are an indicators of permutations and/or
counting the number of ways to do something. Now that we’re thinking of the theorem
statement in terms of permutations, we can continue with proving this statement as
follows:
Proof. If we look at just the numerator alone, we’re looking at the number of ways to
permute the n items we are dealing with. Dividing by k! and (n − k)!, by the Permuting
with Duplicates formula, can be thought of as accounting for groups of duplicates where
one of the items has k total occurrences and the other has n − k total occurrences. As
we’re trying to count the number of ways to choose k objects from n objects, we can
think of the k duplicated items as k items that are all “chosen” and the n − k duplicated
items as n − k items that are all “not chosen.” Thus, this truly is the closed form for the
combination function “n choose k.”
There’s a key strategy in this proof that is very common in computational combinatorics
problems. The idea is to count some quantity in two different ways (generally one
algebraic and one combinatorial) and then use this equality to solve the problem. In
the case of proving the closed form of the combination function, we thought of the
situation combinatorially using permutations and used this to come up with an algebraic
expression which we knew was equivalent to our combinatorial situation. This is an
example of a combinatorial argument.

Exercise 12. Use a combinatorial argument to prove the equality

   
n n
= .
k n−k

The above is a well-known equality and it can actually be used to make very useful
simplifications in combinatorics problems.
There is one last technique I want to mention that is very common in problems. We
have:
Fact 13. If we have n items and we want to find the number of permutations such that
a specific pair of them are not adjacent, this number of permutations comes out to be

n! − 2(n − 1)!.

Proof. We can actually attack this problem using complementary counting. First, note
that the total number of ways to permute the n items without considering the pair in
question is n!. Now, let’s say that we want to find the number of ways that the pair is
adjacent. Let’s fix that one pair as a single element and when we permute, keep it together.
Now, we have “n − 1” items and we can permute them in (n − 1)! ways. However, we
multiply this by 2 because we can have the first element in the pair then the second, or
in the reverse order. When we subtract this from the total, we get the expression in the
theorem statement.
20
NICE Committee (April 2, 2021) NICE Journal

The idea here can be generalized. When we want to find the number of ways to do
something such that some group is next to each other or is not next to each other, the key
idea is to fix that group like a singular unit and then permute that group separately from
the rest.

â2.2.3 Relations to the Binomial Theorem

Before discussing how the combination function relates to the binomial theorem, let’s
start by defining the binomial theorem.

Theorem 14 (Binomial Theorem)

For some positive integer n:
       
n n n n n −1 n n −1 n n
( a + b) = a + a b+...+ ab + b .
0 1 n−1 n

As is common with many of these combinatorial arguments, the idea is fairly intuitive.
For those of you who have expanded out products of polynomials many times, you may
have realized that the key idea is to address each degree product at a time. For example,
if I’m multiplying ( x + y)( x + 2y), I’m going to first consider all of the possible products
that multiply to a term of x2 , then xy and then y2 separately. This is the idea that we can
use to prove that the combination function is the coefficient in the binomial theorem.

Proof. Now that we’re thinking of each “degree product” at a time, we proceed like this.
If we want to create an an−r br term, we get this by taking the a from n − r of the ( a + b)
terms and the b from the remaining r. So, we want to choose the n − r of the n a + b terms
n
in order to create an an−r br term, meaning that there will be a total of (n− r) a
n−r br terms.

Note that this is equivalent to the above statement of the binomial theorem, so therefore
it must be true.

Remark 15. Due to the fact that the combination function is the coefficient in the binomial
theorem, the function is more commonly referred to as the binomial coefficient. Henceforth, in
this article, we will refer to the combination function as the binomial coefficient.

It’s fairly straightforward to see how this idea generalizes to higher degrees as well.

Remark 16. Binomials, trinomials, etc., which are expressions of two, three, etc. variables
respectively are generally referred to as multinomials.

21
NICE Journal NICE Committee (April 2, 2021)

Theorem 17 (Multinomial Coefficient)

Just like we have the binomial coefficient, we have the multinomial coefficient. The
multinomial coefficient for m variables (a1 to am ) is equal to:

( a1 + . . . + a m ) !
.
( a1 ) ! . . . ( a m ) !

Exercise 18. Convince yourself of the above theorem by proving the statement.

â2.3 Bijections
Now that we’ve addressed the basic tools used in combinatorial arguments, we can move
on to actually using them. When a bijection is used, the problem solver is exploiting a
one-to-one correspondence between two things. The idea of a bijection is that you can
use a one-to-one correspondence between some quantity that you do not know how to
easily count and some quantity you do know how to easily count, in order to easily count
the former.
There are a few common bijections that make it easily to solve computational combina-
torics problems. Before going through examples of bijections, we’re going to go through
these specific types that show up often.

â2.3.1 Putting People in Committees

Think of it like this: if we have n people and we want to make a committee of k people,
the number of possible committees that could be formed is (nk). This might not seem like
an important observation, but this might become more clear with an example.

Example 19
Prove that for positive integers n,
       
n n n n
+ +...+ + = 2n .
0 1 n−1 n
Solution: 5

Walkthrough.
1. Think of each binomial one at a time. How many people are being chosen for a
specific committee?
2. If you combine all of these situations, what do you have?
3. Is there a way that you can consider each of the “n people” independently and
biject to such a situation?

22
NICE Committee (April 2, 2021) NICE Journal

Remark 20. There is also a proof using algebra and induction, as well as one using the binomial
theorem. The binomial theorem proof is particularly interesting – it involves considering
( x + y)n in the x = y = 1 case. In particular, 1 + 1 comes from one choice to include the person
in the commitee and one choice not to. Our proof here is global (as Evan calls it) because it
deals with everything at once, whereas the walkthrough above is local because we consider
each part at a time.

The benefits of this “bijective” approach using committee forming are clear. The idea
of translating the problem to a committee forming situation allows us to finish up the
problem.

Example 21 (AIME I 2017/7)

For nonnegative integers a and b with a + b ≤ 6, let T ( a, b) = (6a)(6b)( a+6 b). Let S denote
the sum of all T ( a, b), where a and b are nonnegative integers with a + b ≤ 6. Find the
remainder when S is divided by 1000. Solution: 26

Walkthrough.

1. Let’s say I have a group of people from which I need to choose a committee. Can I
choose this committee by partitioning the larger group into multiple smaller groups
and choosing a smaller amount of people from each group that total to the size of
the needed committee?

2. Find the answer.

This problem demonstrates a situation in which committee forming arguments are

useful. Generally, seeing either a summation, product or both of binomial coefficients is a
good sign that committee forming arguments would be effective. A very useful technique
is that when you get a summation of products of binomial coefficients, by rearranging to
ensure that the sum of the amounts being chosen is a constant, you make the quantity
much simpler to extract.

â2.3.2 Walking on a Grid

Before we get into the main ideas of “grid-walking” arguments, let’s start with a generic
grid-walking example to make it clear which types of problems this refers to.

Example 22
John is attempting to travel on the Cartesian plane. He is in a square grid with vertices
(0, 0), (0, 5), (5, 0), (5, 5). If he starts at (0, 0) and can only move in the positive x or y
directions to reach his destination of (5, 5), how many successful paths exist? Solution:
28

Walkthrough. A direct application of Number of Paths.

23
NICE Journal NICE Committee (April 2, 2021)

The types of problems we are referring to are the problems where we are given point
A and point B and we are asked how many ways we can go from point A to point B.

Theorem 23 (Number of Paths)

The number of ways to go from point A to point B on a grid, with coordinates (0, 0)
and ( a, b) for a, b > 0, if you can only go in the positive x and y directions is equal to
( a+a b).

Proof. Note that since each movement increases the x or y coordinate by 1 and the total
different in the x and y coordinates between (0, 0) and ( a, b) is a + b, there will be exactly
a + b moves. a of these moves will be in the positive x direction and b will be in the
positive y direction.
Once again, we are going to make a combinatorial argument. Finding the number
of these paths on a grid is equivalent to permuting U. . . UR . . . R, where U represents a
positive y movement and R represents a positive x movement such that there are a R’s
and b U’s. This is equivalent to choosing a of the a + b places to place an R in, which is
a+b
 
written as .
a

Unfortunately, grid-walking is not normally this simple. Let’s try an example that
practices a similar idea but there’s now a twist: there are restricted areas and whatever is
walking along the grid has to avoid them:

Example 24
John has to go from the same starting point, (0, 0), to the same ending point, (5, 5), by
moving only in the positive x, y directions but this time he is unable to pass through
the construction zone at (3, 3). How many successful paths exist for John? Solution: 36

Walkthrough.
1. If you tackle this with complementary counting, what needs to be subtracted from
what?
2. Can you break the “restricted paths” into two parts and compute out each part
individually?
3. Combine these two parts, compute the larger number and extract the answer!
Once again, there is a rather well-known way to approach these grid-walking problems
with the twist of a “restricted” zone.
Remark 25. When you see that a point or a path has to be avoided, this is screaming for an
application of complementary counting.

Note that we can generalize this:

24
NICE Committee (April 2, 2021) NICE Journal

Theorem 26 (Number of Paths Excluding One Point)

If we have a rectangular grid and we would like to go from (0, 0) to ( a, b) by only
moving one unit up or right at a time without passing through some point (m, n), the
number of successful paths is equal to:

a+b m+n a+b−m−n

     
N= − · .
a m m−a

Exercise 27. Prove the Number of Paths Excluding One Point formula.

The last grid-walking situation is when some path is blocked. Luckily, it’s a similar
combination of the Number of Paths formula and complementary counting.

Exercise 28. Derive a formula for the number of paths if a specific path is blocked. For example,
what if you are on the coordinate plane and would like to go from (0, 0) to (5, 5) going only in
the positive x and y directions, but you are not allowed on the path from (2, 3) to (3, 3)?

Grid-walking arguments are quite useful in mathematics, and there are many bijections
that biject some quantity to paths on a grid. In this next section, we give an example. This
is one of the most famous applications of grid-walking ideas, and you may have even
seen it in school, although the relation to grid-walking may not have been mentioned.

â2.3.3 Grid-Walking on Pascal’s Triangle

Pascal’s Triangle
Pascal’s triangle is the triangle where the top row has 1 number and each successive
row has 1 more number than the last. All numbers on the left and right edges are 1
and all other numbers are the sum of the two numbers above them. Note that the
triangle expands downward infinitely.

See the below picture for a diagram of the first few rows of Pascal’s Triangle:

1 1

1 2 1

1 3 3 1

1 4 6 4 1
25
NICE Journal NICE Committee (April 2, 2021)

When dealing with Pascal’s Triangle, there are a few conventions that you will want to
remember:

1. The topmost row that contains only the single 1 is referred to as the row with index
0. So, the rows from top to bottom go 0, 1, 2, . . ..

2. The leftmost 1 in each row has index 0, so the numbers in each row are also counted
as 0, 1, 2, . . ..

Theorem 29 (Terms in Pascal’s Triangle)

The kth number in the nth row of Pascal’s triangle is equal to (nk).

(00)

(10) (11)

(20) (21) (22)

(30) (31) (32) (33)

(40) (41) (42) (43) (44)

Proof. Take a close look at Pascal’s triangle. If you think about it, if each number repre-
sented a point on a grid, each number actually represents the number of ways to go from
the top 1 to that number while only moving downward diagonally. So, this all comes
down to a grid-walking argument!
If you turn your head a little, note that you can create a “rectangular grid” placing the
topmost 1 in Pascal’s triangle at (0, 0) and the kth number in the nth row at (n, n − k)
because there need to be k “down and right” movements and n − k “down and left
movements.” So, the number of paths by the earlier theorem is just (nk).

Also, if you take a look at Pascal’s Triangle, there is also an instance of a rather cool
property that we already proved:

Fact 30. The sum of the kth row of Pascal’s Triangle is 2k .

Note that we already proved this in in the earlier section on committee forming.
Furthermore, Pascal’s Identity is just an extension of these ideas.
26
NICE Committee (April 2, 2021) NICE Journal

Theorem 31 (Pascal’s Identity)

For positive integers n, k > 1,

n−1 n−1
     
n
+ = .
k−1 k k

Note that although this is obvious from the facts we have already proved about
Pascal’s Triangle, we will still go over two different proofs of this identity. One will be a
combinatorial proof (making use of a committee forming argument) whereas the other
will be an algebraic proof. First up, we have the combinatorial argument:
Committee-Forming Proof. Assume we have n people and we want to form a committee
with k people in it. It is clear that the right hand side refers to the number of ways we can
form such a committee.
Let’s pick an arbitrary person of the n people, and assume they are named person A.
−1
Note that there are (nk− 1 ) ways to choose a committee with person A in it because then
you have to choose k − 1 people from the remaining n − 1. Similarly, there are (n− 1
k )
ways to choose a committee that does not have person A in it because then you have to
choose k people from the remaining n − 1. So, together these make up the two cases and
it follows that:
n−1 n−1
     
n
+ = .
k−1 k k

Remark 32. Above, we used a bijection which took advantage of the fact of the fact that there is
a one-to-one correspondence between the left and right hand sides.

We can also prove the same identity through an algebraic proof, as seen here:
Algebraic Proof. Let LHS denote the left hand side:

n−1 n−1 ( n − 1) ! ( n − 1) !
   
LHS = + = + .
k−1 k (k − 1)!(n − k)! k!(n − k − 1)!

This simplifies to:

k(n − 1)! + (n − k)(n − 1)!

 
n! n
LHS = = = .
k!(n − k)! k!(n − k)! k

27
NICE Journal NICE Committee (April 2, 2021)

Example 33
Simplify (37 37 37
7 ) + 2( 8 ) + ( 9 ) into only a single binomial coefficient. Solution: 40

Walkthrough.
1. Split into two parts.
2. Apply Pascal’s to each part, then one more time to the overall sum.
As seen above, Pascal’s Identity comes in hand when it comes to simplifying expres-
sions to make them more usable. It’s a lot easier to deal with just one binomial coefficient
than it is to deal with multiple.

â2.3.4 Other Assorted Bijections

Although we’ve given committee forming bijections and grid-walking bijections as two
examples, bijections aren’t limited to only these two situations. The idea of a bijection
is just finding a one-to-one correspondence, and the actual thing being corresponded
to doesn’t need to be the same each time. For example, one common type of bijection
involves bijecting sequences. Here’s a classic example:

Example 34 (Folklore)
How many strictly increasing sequences of five positive integers can be made if all of
the positive integers are chosen from the numbers 1 to 50? Solution: 24

Walkthrough.
1. As the name of the section implies, you want to find a bijection. How many
increasing sequences exist per group of five distinct numbers?
2. Use the bijection to finish off the problem.
Normally, bijections in problems are not this simple but this is a very well-known
example that is worth knowing as variants of this idea are quite common.
Here’s another (fairly easy) example of similar ideas:

Example 35 (AIME II 2006/4)

Let ( a1 , a2 , a3 , . . . , a12 ) be a permutation of (1, 2, 3, . . . , 12) for which

a1 > a2 > a3 > a4 > a5 > a6 and a6 < a7 < a8 < a9 < a10 < a11 < a12 .

An example of such a permutation is (6, 5, 4, 3, 2, 1, 7, 8, 9, 10, 11, 12). Find the number
of such permutations. Solution: 4

Walkthrough.
28
NICE Committee (April 2, 2021) NICE Journal

1. Is there a value that you can reason out?

2. Can you come up with a bijection that finishes the problem by corresponding these
groups of 12 to choosing a group of numbers from a larger group of numbers?

The key idea of these bijections is that it doesn’t matter what you biject to. You
can biject to literally anything as long as it’s useful and simplifies the daunting task
of computing a quantity, whether it be paths on a grid, number of possible formed
committees or even just bijecting to another sequence or group of numbers.

â2.4 Common Combinatorial Identities

When it comes to combinatorics problems, there are a number of so-called “combinatorial
identities” that can make things significantly easier for us when we’re either directly
counting some quantity or using a bijection to count it.
In fact, we’ve already seen an example of one of these identities earlier in the text,
except it wasn’t cited directly. See if you can figure it out after reading through this
section!

â2.4.1 Stars and Bars

Theorem 36 (Stars and Bars)
The number of ways to put n indistinguishable objects into k distinguishable categories
is:
n+k−1
 
N= .
k−1

There is a clever combinatorial argument to prove this:

Proof. Now, essentially the problem is the same as putting the n indistinguishable objects
in a line and putting k − 1 dividers at spots in the line. It’s just like you’re drawing a table.
If you want to make the table have 6 columns, you only draw 5 vertical lines because that
creates 5 to the left and the last one to the right.
So, the numbers of ways to put n indistinguishable objects into k distinct categories is
equivalent to the number of ways to rearrange a sequence containing n identical objects
and k − 1 identical dividers.
As there are a total of n + k − 1 places in the line and k − 1 of those must be chosen to
place dividers in, there are (n+ k −1
k −1 ) ways to do this.

Often times when you are solving a problem, you might see a twist that makes it
difficult to just directly cite Stars and Bars. In those situations, it is very helpful to
understand the “dividers” logic behind the theorem so that you can tweak it to fit the
situation at hand. Here’s an example of a said twist:
29
NICE Journal NICE Committee (April 2, 2021)

Example 37
What is the number of ways to put n indistinguishable objects into k distinguishable
categories such that each category is non-empty? Solution: 21

Walkthrough.

1. If you want to ensure that everything is nonempty, can you just start by ensuring
this by placing an object in each category?

2. Use Stars and Bars to finish from here.

Here’s an example of applying Stars and Bars to one of the later problems on the AMC
10.

Example 38 (AMC 10B 2020/25)

Let D (n) denote the number of ways of writing the positive integer n as a product

n = f1 · f2 · · · fk ,

where k ≥ 1, the f i are integers strictly greater than 1, and the order in which the
factors are listed matters (that is, two representations that differ only in the order of
the factors are counted as distinct). For example, the number 6 can be written as 6,
2 · 3, and 3 · 2, so D (6) = 3. What is D (96)? Solution: 27

Walkthrough.

1. Prime factorize it. Try and consider the problem in terms of the different prime
factors (e.g. treat 2 separate from 3).

2. What considerations do you have to make to ensure that all of the factors are strictly
greater than 1?

3. Taking these considerations into account, do casework on the number of factors.

Hint: Stars and Bars might be needed.

4. Finish up by adding the totals for each case!

â2.4.2 Hockey-Stick Identity

Theorem 39 (Hockey-Stick Identity)
For integer k and n ≥ k,
n
n+1
   
i
∑ k =
k+1
.
i=k

30
NICE Committee (April 2, 2021) NICE Journal

Below is an algebraic proof of the identity:

Proof. Let n = k + x. Let’s just expand everything out:

n
k+1 k+x k+1 k+1 k+x
             
i k
∑ k = k + k +...+ x = k+1 + k +...+ x .
i =k

This looks suspiciously like Pascal’s Identity. Let’s apply Pascal’s Identity repeatedly
going from the left to the right:

k+1 k+1 k+x k+x+1 n+1

         
+ +...+ = = .
k+1 k x k+1 k+1

As the left hand side is equal to the right hand side now, we are done.

Remark 40. The combinatorial interpretation: imagine we are giving n candies to k children.
Alternatively, we could give i candies to the youngest child, and n − i candies to the other k − 1
kids, for all 0 ≤ i ≤ n. We then sum these n cases and we’re done.

Exercise 41. Find the relationship between Hockey-Stick and Pascal’s triangle.

Exercise 42. Use this relationship to come up with a combinatorial proof of the Hockey-Stick
Identity. Remember that Pascal’s Triangle can be related to grid-walking.

Here’s an example using the Hockey-Stick Identity:

Example 43 (AIME 1986/11)

The polynomial 1 − x + x2 − x3 + · · · + x16 − x17 may be written in the form a0 + a1 y +
a2 y2 + · · · + a16 y16 + a17 y17 , where y = x + 1 and that ai ’s are constants. Find the
value of a2 . Solution: 39

Walkthrough.

1. Make the substitution x = y − 1. Where does this get you?

2. Use the binomial theorem on the multiple expressions that result.

3. Finish with Hockey-Stick Identity.

â2.4.3 Vandermonde’s Identity

31
NICE Journal NICE Committee (April 2, 2021)

Theorem 44 (Vandermonde’s Identity)

For integers m, n, k, r:
r  
m+n
  
m n
∑ k r−k =
r
.
k =0

This identity is quite easy to prove using a combinatorial argument:

Proof. Looking at the statement, it appears that we are choosing r total out of a pool of
m + n things with k of those r coming from one section and the rest coming from the
other. So, let’s set it up so that our total pool of people is split into groups of m and n
with some being chosen from one group and the rest from the other.
Let’s say that I want to choose a committee of r people out of m + n people such that
this group of people includes m girls and n boys. Note that if I wanted the committee to
have x girls and r − x boys, the ways to create the committee would be:
  
m n
N= .
x r−x

So, this means that the summation in the left hand side of Vandermonde’s Identity cycles
over the ways to choose k girls and r − k boys for each possible value of k. In total, this is
just the total number of ways to make the committee while disregarding the number by
gender, which is just (m+ n
r ).

Remark 45. If you think about it, the earlier example (AIME I 2017/7) was essentially Vander-
monde’s Identity. In fact, we used the same combinatorial argument to figure that out as we
did to prove Vandermonde’s Identity.

2
Exercise 46. Prove ∑ik=0 (ki) = (2k
k ) using Vandermonde’s Identity.

Example 47 (AIME I 2020/7)

A club consisting of 11 men and 12 women needs to choose a committee from among
its members so that the number of women on the committee is one more than the
number of men on the committee. The committee could have as few as 1 member or
as many as 23 members. Let N be the number of such committees that can be formed.
Find the sum of the prime numbers that divide N. Solution: 12

Walkthrough.

1. Start off with the first steps of the previous walkthrough for this problem in the
committee-forming section.
32
NICE Committee (April 2, 2021) NICE Journal

2. Rather than coming up with your own custom combinatorial argument, finish off
the problem using Vandermonde’s Identity!

In general, a good time to use Vandermonde’s Identity is when you have a summation
of products of binomial coefficients where the sum of the amounts being chosen remains
constant.

â2.5 Catalan Numbers

The Catalan numbers are a rather interesting sequence of numbers that (not so coinciden-
tally) appear in many computational combinatorial problems. The below definition is a
basic starting point.

Catalan Numbers
The nth Catalan number Cn satisfies
 
1 2n
Cn = .
n+1 n

â2.5.1 Bijecting Them

If you just know how to compute the Catalan numbers, that won’t get you too far unless
you know where they actually show up. The Catalan numbers appear in many different
setups, so let’s just go through a few of them:

Theorem 48 (Catalan Grid-Walking)

The nth Catalan number is the number of paths from (0, 0) to (n, n) that don’t go
above the line y = x.

Proof. We can tackle proving this with complementary counting. As mentioned in the
earlier section, grid-walking with restrictions placed on where the path can and cannot
go SCREAMS complementary counting. From the Number of Paths Theorem, we know
that there are (2n
n ) ways to go from (0, 0) to ( n, n ) in total. Now, we have to count the
number of paths from (0, 0) to (n, n) that go above y = x and subtract them out.
This condition seems difficult to count, so we can use a one-to-one correspondence.
Specifically, consider the transformation where we take a path going above y = x and
reflect the entire part of the path after the first point where the path goes above y = x
over the line y = x + 1. For example, the path formed by the green and red parts will be
sent to the path formed by the green and blue parts in this image. We can always have
this transformation because the condition guarantees the path goes over the line.
33
NICE Journal NICE Committee (April 2, 2021)

We see that each path is sent to a path from (0, 0) to (n − 1, n + 1), but we also know that
each path from (0, 0) must go over the line y = x to get to (n − 1, n + 1), so we are able to
reverse this transformation. Since the transformation is reversible, it is a bijection, which
guarantees that the number of paths stays the same after the transformation. However,
we now know how to count these paths: this is just (n2n −1) from the Number of Paths
formula! Thus, since we were doing complementary counting, we get (2n 2n
n ) − (n−1), which
we can manipulate to get

(2n
n)
     
2n 2n 2n! 2n! 2n! n
− = − = 1− = .
n n−1 n! · n! (n − 1)!(n + 1)! n! · n! n+1 n+1
These are the Catalan numbers, so we are done.
There’s another cool bijection, the proof of which is left to the reader as it is very similar
to the proof for the preivous bijection.

Theorem 49 (Parentheses Orderings)

The number of valid expressions of n sets of parentheses (each one is opened and
closed) is equivalent to the nth Catalan number.

Exercise 50. Adapt the proof for the Catalan grid-walking bijection to the parentheses orderings
bijection.

â2.5.2 Finding Them in Problems

Here are some example problems related to finding the Catalan numbers secretly lying
around in combinatorics problems.

Example 51 (AIME 1993/7)

Three numbers, a1 , a2 , a3 , are drawn randomly and without replacement from the
set {1, 2, 3, . . . , 1000}. Three other numbers, b1 , b2 , b3 , are then drawn randomly and
without replacement from the remaining set of 997 numbers. Let p be the probability
that, after a suitable rotation, a brick of dimensions a1 × a2 × a3 can be enclosed in a
box of dimensions b1 × b2 × b3 , with the sides of the brick parallel to the sides of the

34
NICE Committee (April 2, 2021) NICE Journal

box. If p is written as a fraction in lowest terms, what is the sum of the numerator and
denominator? Solution: 14

Walkthrough.
1. Computing the numerator can be done using the Catalan number. Can you come
up with a combinatorial argument that bijects the situation to the Catalan numbers?
2. Find the denominator and simplify everything to finish.

â2.6 Problems
Here are some practice problems:

Problem 22 (A(N)IME 2020/6). The garden of Gardenia has 15 identical tulips, 16 iden-
tical roses, and 23 identical sunflowers. David wants to use the flowers in the garden
to make a bouquet. However, the Council of Elders has a law that any bouquet using
Gardenia’s flowers must have more roses than tulips and more sunflowers than roses.
For example, one possible bouquet could have 0 tulips, 3 roses, and 8 sunflowers. If N
is the number of ways David can make his bouquet, what is the remainder when N is
divided by 1000?

Problem 23 (AIME II 2008/12). There are two distinguishable flagpoles, and there are
19 flags, of which 10 are identical blue flags, and 9 are identical green flags. Let N be the
number of distinguishable arrangements using all of the flags in which each flagpole has
at least one flag and no two green flags on either pole are adjacent. Find the remainder
when N is divided by 1000.

Problem 24 (HMMT February Combinatorics 2007/6). Kevin has four red marbles
and eight blue marbles. He arranges these twelve marbles randomly, in a ring. Determine
the probability that no two red marbles are adjacent.

Problem 25 (HMMT February Combinatorics 2015/7). 2015 people sit down at a

restaurant. Each person orders a soup with probability 12 . Independently, each person
orders a salad with probability 12 . What is the probability that the number of people who
ordered a soup is exactly one more than the number of people who ordered a salad?

Problem 26 (AMC 12B 2019/23). How many sequences of 0s and 1s of length 19 are
there that begin with a 0, end with a 0, contain no two consecutive 0s, and contain no
three consecutive 1s?

35
NICE Journal NICE Committee (April 2, 2021)

Problem 27 (AIME II 2006/10). Seven teams play a soccer tournament in which each
team plays every other team exactly once. No ties occur, each team has a 50% chance of
winning each game it plays, and the outcomes of the games are independent. In each
game, the winner is awarded a point and the loser gets 0 points. The total points are
accumilated to decide the ranks of the teams. In the first game of the tournament, team A
beats team B. The probability that team A finishes with more points than team B is m n,
where m and n are relatively prime positive integers. Find m + n.

Problem 28 (AIME I 2015/12). Consider all 1000-element subsets of the set {1, 2, 3, . . . , 2015}.
From each such subset choose the least element. The arithmetic mean of all of these least
p
elements is q , where p and q are relatively prime positive integers. Find p + q.

√ 29 (AMC 12B 2016/25). The sequence ( an ) is defined recursively by a0 = 1,

Problem
a1 = 19 2, and an = an−1 a2n−2 for n ≥ 2. What is the smallest positive integer k such that
the product a1 a2 · · · ak is an integer?

Problem 30 (CMIMC Combinatorics 2016/9). 1007 distinct potatoes are chosen in-
dependently and randomly from a box of 2016 potatoes numbered 1, 2, . . . , 2016, with
p being the smallest chosen potato. Then, potatoes are drawn one at a time from the
remaining 1009 until the first one with value q < p is drawn. If no such q exists, let
S = 1. Otherwise, let S = pq. Then given that the expected value of S can be expressed
as simplified fraction m
n , find m + n.

Problem 31 (HMMT February Combinatorics 2014/10). An up-right path from ( a, b) ∈

R2 to (c, d) ∈ R2 is a finite sequence ( x1 , yz ), . . . , ( xk , yk ) of points in R2 such that ( a, b) =
( x1 , y1 ), (c, d) = ( xk , yk ), and for each 1 ≤ i < k we have that either ( xi+1 , yy+1 ) =
( xi + 1, yi ) or ( xi+1 , yi+1 ) = ( xi , yi + 1). Two up-right paths are said to intersect if they
share any point. Find the number of pairs ( A, B) where A is an up-right path from (0, 0)
to (4, 4), B is an up-right path from (2, 0) to (6, 4), and A and B do not intersect.

Problem 32 (HMMT February Combinatorics 2007/10). A subset S of the nonnega-

tive integers is called supported if it contains 0, and k + 8, k + 9 ∈ S for all k ∈ S. How
many supported sets are there?

36
3 Complex Numbers
â3.1 Introduction and Definitions
Chances are, many of you have heard what complex numbers are.
Complex Number
A complex number is a number of the form a + bi, where a and b are real numbers. In
this definition, we assume that i2 = −1. Complex numbers are often defined by their
real parts and their imaginary parts; in a complex number of the form a + bi, the real
part is a and the imaginary part is b. (Be careful, the imaginary part is not bi!)

It is possible to graph complex numbers in the same way it is possible to graph real
numbers on the number line. They are usually graphed on the Argand plane. This plane
has two axes, the real axis and the imaginary axis (to handle real and imaginary parts,
respectively). Graphically, the imaginary axis is perpendicular to the real axis, and they
both meet at the point 0 + 0i.
Complex Conjugate
The complex conjugate of a complex number of the form a + bi is the number a − bi.
Complex conjugates are usually denoted by a bar on the top of the number (so
a + bi = a − bi).

Magnitude
The magnitude of a complex number is its distance from the point 0 + 0i. Magnitude
is often denoted by √ vertical bars to the left and right of the number, and has the
definition | a + bi | = a2 + b2 . (Notice that this definition is consistent with the idea
of absolute value on the real numbers as well.)

Argument
The argument of a complex number arg(z) is defined as the angle θ that the line
connecting 0 + 0i and a + bi makes with the real axis. (For example, arg(1 + i ) = π4 .)

â3.2 Complex Numbers through an Algebraic Lens

In order to start looking at complex numbers through a geometric perspective, we must
first be fluent with how to manipulate them algebraically. This section will cover two
different methods of solving complex numbers using algebra.
37
NICE Journal NICE Committee (April 2, 2021)

â3.2.1 The Substitution z = a + bi

One common method for working with complex numbers is to rewrite the complex
number in terms of its real and imaginary components. While this does produce some
somewhat-ugly bashes, it is essential for some basic problems, as well as proving some
very useful theorems.

Theorem 52 (Spliting Conjugates)

z z
For any complex numbers z and w, we have zw = z · w and = .
w w

Proof. We tackle the former identity first. Let z = a + bi and w = c + di. Then zw =
( a + bi )(c + di ) = ac + adi + bci + bdi2 = ( ac − bd) + ( ad + bc)i. Therefore, zw = ( ac −
bd) − ( ad + bc)i. Next, remark that

( ac − bd) − ( ad − bc)i = ac − adi − bci + bdi2 = ( a − bi )(c − di ).

Therefore zw = z · w.
We now tackle the latter case. Once again, let z = a + bi and w = c + di. Then

a + bi c − di
 
z
=
w c + di c − di
( a + bi )(c − di )
=
(c + di )(c − di )
ac − adi + bci − bdi2
=
c2 + d2
( ac + bd) + (bc − ad)i
= .
c2 + d2
z ( ac+bd)−(bc− ad)i
This means that w = c2 + d2
. This can be rewritten as

ac + adi − bci − bdi2 ( a − bi )(c + di ) a − bi

= = .
c2 − d2 i 2 (c − di )(c + di ) c − di

z z
This means that = , which is what we wanted.
w w

Theorem 53 (Splitting Magnitudes)

For any complex numbers z and w, we have |zw| = |z||w|.

Proof. Let z = a + bi and w = c + di.pRemark that zw = ( a + bi )(c + di ) = ( ac − bd) +

( ad + bc)i. This means that |zw| = ( ac − bd)2 + ( ad + bc)2 . Next, remark that since
38
NICE Committee (April 2, 2021) NICE Journal
√ √
|z| = a2 + b2 and |w| = c2 + d2 , we have
q
|z||w| = ( a2 + b2 )(c2 + d2 )
q
= ( ac)2 + ( ad)2 + (bc)2 + (bd)2
q
= [( ac)2 − 2abcd + (bd)2 ] + [( ad)2 + 2abcd + (bc)2 ]
q
= ( ac − bd)2 + ( ad + bc)2 .

Therefore the two quantities are equal, as desired.

As you may have noticed, many of these proofs consist of lots of bashy and annoying
algebra. What is the advantage of working with such substitutions then? While I would
not recommend using this too often in problems like these, sometimes it is necessary
to make such substitutions. They are most useful when you know the exact values of
either the real or the complex components of any or all complex numbers. These are often
denoted <(z) and =(z), respectively.

Example 54 (AoPS)
Solve z + 2z = 6 − 4i for z. Solution: 18

Walkthrough.

1. Substitute z = a + bi.

2. Solve the system of equations by splitting into real and imaginary components.

Example 55
Suppose z and w are Gaussian integersa located in the first quadrant of the Argand
plane such that <(z) = 4, =(w) = 13, and |z + w| = 25. How many possible ordered
pairs (z, w) are there? Solution: 34
aA complex number z is said to be a Gaussian integer if <(z), =(z) ∈ Z.

Walkthrough.

1. Rewrite z and w in the form x + yi.

2. Substitute the above into |z + w| = 25.

3. Since z and w are Gaussian integers, our expression from the step above is actually
a Diophantine equation; solve this equation.

4. From the cases, extract the answer.

39
NICE Journal NICE Committee (April 2, 2021)

We conclude this section with a problem that, like the others in this section, deals with
real and imaginary components of a complex number. However, while it is tempting to
apply the z = a + bi substitution here, it is arguably simpler to work the problem without
this substitution. This problem shows that not all problems should be tackled by the
above methods (although they are very helpful), a theme that will reverberate in the next
section.

Example 56 (AIME I 2009/2)

There is a complex number z with imaginary part 164 and a positive integer n such
that
z
= 4i.
z+n
Find n. Solution: 20

Walkthrough.

1. Solve for z in terms of n.

2. Rewrite the equation in the form z = a + bi.

3. Since b = 164, we can extract n.

â3.2.2 Working with Magnitudes and Conjugates

Sometimes, when working with complex numbers, it is necessary to deal with magni-
tudes. This is often the case, as many problems will specify that certain complex numbers
are of a certain distance to the origin of the Argand plane. With the z = a + bi substitution,
these conditions are cumbersome to deal with, as they involve square roots and, as a
result, lots of algebraic manipulation. However, it is possible to convert magnitudes into
products, as shown by the theorem below.

Theorem 57 (Complex Times Conjugate)

For any complex number z, we have zz = |z|2 .
√
Proof. Let z = a + bi. Then z = a − bi and |z| = a2 + b2 . Thus

zz = ( a + bi )( a − bi ) = a2 − b2 i2 = a2 + b2 = |z|2 .

To start, we’ll revisit a problem that we did before. Notice the difference between this
solution and the one above.

Example 58
Show that |zw| = |z||w| for all complex numbers z and w. Solution: 6

40
NICE Committee (April 2, 2021) NICE Journal

Walkthrough.

1. Use the Complex Times Conjugate formula.

2. Everything else is obvious – recall that we can split conjugates.

Example 59 (AoPS)
Show that |z − 1|2 + |z + 1|2 = 4 for all complex numbers z such that |z| = 1. Solution:
38

Walkthrough.

1. Use the Complex Times Conjugate formula for |z − 1|2 .

2. Split conjugates and apply the Complex Times Conjugate formula in the opposite
direction.

3. Do the two steps above for |z + 1|2 as well.

4. Add |z − 1|2 and |z + 1|2 ; watch terms cancel.

Example 60 (AoPS)
Show that if w1 + w2 + w3 = 0 and |w1 | = |w2 | = |w3 | = 1, then w12 + w22 + w32 = 0.
Solution: 1

Walkthrough.

1. Show that w1 w2 + w1 w2 = −1.

2. Show that w12 + w22 + w32 = 2(w12 + w1 w2 + w22 ).

3. Now show that these two quantities are equal to 0.

â3.3 Basic Geometric Properties

Sometimes, when dealing with complex numbers, it is often advantageous to keep a
geometric mindset. As stated in the beginning of the article, complex numbers can be
graphed on a “coordinate system”, and this can be advantageous for simplifying some
problems.
41
NICE Journal NICE Committee (April 2, 2021)

â3.3.1 Triangles
Often times, when working with complex numbers, it is advantageous to step away from
the mathematics and look at the big picture. Below, you will see theorems and problems
that either rely or are related to concepts in Euclidean Geoemtry.

Theorem 61 (Triangle Inequality)

For any complex numbers z and w, we have |z| + |w| ≥ |z + w|.

Proof. Note that the origin, z, and z + w form a triangle on the complex plane. The side
lengths of this triangle are |z|, |(z + w) − z| = |w|, and |z + w|. It is well known that for
any triangle, the sum of the lengths of two of its sides is greater than or equal to the
length of the third side. Therefore, |z| + |w| ≥ |z + w| as desired.

The Triangle Inequality is most useful when one wishes to find the maximum or
minimum of a sum or difference of magnitudes in terms of z, as can be seen below.

Example 62
Find the minimum value of |2 + z| + |1 + 4i − z|. Solution: 30

Walkthrough.

1. Use Triangle Inequality.

2. Find when equality holds, i.e. find the z that gives us the desired minimum value.

Now, we’ll revisit a problem that was done in the previous section, where we attempted
it algebraically. While the algebra was not too messy, taking a stand from a geometric
approach leads to a very clean and beautiful solution.

Example 63 (AoPS)
Show that |z − 1|2 + |z + 1|2 = 4 for all complex numbers z such that |z| = 1. Solution:
19

Walkthrough.

1. Let a = z − 1, b = z + 1. Find |z − a| and |b − z|.

2. Show that the above step implies z is the midpoint of the line segment between a
and b.

3. Show that the line through a and 0 is perpendicular to the line through b and 0.

4. Finish with Pythagorean Theorem.

42
NICE Committee (April 2, 2021) NICE Journal

â3.3.2 Analysis of Arguments

In addition to the Triangle Inequality, we can analyze complex numbers by examining
their arguments as well.

Fact 64 (Complex Multiplication). In order to multiply two complex numbers together,

we multiply their magnitudes and add their arguments.

For the sake of brevity, we will ignore the proof for this theorem in this article.

Example 65
Find the locus of complex numbers z for which z3 is purely imaginary. Solution: 41

Walkthrough. It is possible to solve this problem by solving the equations z3 = ki and

z3 = −ki for any real k, but that is beyond the scope of this article. Instead, we’ll focus on
the argument of z.

1. Compute the possible values of arg(z3 ).

2. From the possibilities, find arg(z).

3. Consider the values that are at most 2π and finish.

Example 66 (AMC 12B 2009/23)

A region S in the complex plane is defined by

S = { x + iy : −1 ≤ x ≤ 1, −1 ≤ y ≤ 1}.

A complex number  z = x + iy is chosen uniformly at random from S. What is the

3 3
probability that + i z is also in S? Solution: 29
4 4

Walkthrough.
 
3 3
1. Note that + i z is simply a rotation; find the angle.
4 4

2. Find the shape of the intersection with S and the rotation described above (draw a
figure to visualize this).

3. The intersection is a nice polygon – find its area and divide by the area of S to finish.
43
NICE Journal NICE Committee (April 2, 2021)

â3.4 Rotations
One of the biggest reasons as to why complex number geometry is sometimes preferable
over Cartesian coordinate geometry is that complex numbers have a huge advantage
when it comes to dealing with rotations. As stated in a previous section, when you
multiply two complex numbers together, you multiply their magnitudes and add their
arguments.1 This is not very useful by itself, but the form that is infinitely useful is
when one of the complex numbers has magnitude equal to one. This is equivalent to the
rotation of a complex number, as the magnitude of the other complex number does not
change!
The easiest case to consider occurs when you need to rotate a complex number about
the origin by a certain angle θ.

Fact 67 (Complex Rotation). The original complex number p and the new complex
number q are related by the formula

q = peiθ .

Example 68
Determine the complex number that is a sixty degree counterclockwise rotation of
3 + 4i about the origin. Solution: 13

Walkthrough.
1. Use the Complex Rotation formula.
2. In particular, θ = π
3.

Now suppose that instead of rotating about the origin, we rotate about some other
complex number w. This is a bit more difficult to work with, but it is still easy: we can
perform a translation sending w to the origin. This in turn sends p to p − w and q to
q − w. As a result, we can now use the Complex Rotation formula to produce the general
case: if q is the result when p is rotated at an angle of θ about w, then

q − w = eiθ ( p − w) .

These two formulas, especially the latter, determine the very foundations of advanced
complex number geometry. There are several examples that can show this.

Example 69 (AoPS)
Square WXYZ is a square with center O. Let T be the midpoint of WX and S be

1 The proof follows by considering the exponential form of complex numbers, as (r1 eiθ1 )(r2 eiθ2 ) = r1 r2 ei(θ1 +θ2 ) .
44
NICE Committee (April 2, 2021) NICE Journal

the midpoint of OY. Using complex numbers, show that 4 TSZ is an isosceles right
triangle. Solution: 10

Walkthrough.
1. Set O as the origin, and calculate all points in terms of y.
2. Describe the result we want to show (4 TSZ an isosceles right triangle) in terms of
rotations.

3. Find the equation corresponding to the condition in the step above, and verify that
it holds.

Example 70
Let 4 ABC and 4CDE be two non-overlapping equilateral triangles. Let M be the
midpoint of CD, N be the midpoint of AC, and P be the midpoint of BE. Prove that
4 MNP is equilateral. Solution: 22

Walkthrough.

1. Choose a point to set as the origin.

2. Set variables for two of the other points, and calculate all the other points in terms
πi
of these two points and ω = e 3 .
3. Describe the result we want to prove in terms of rotations, and find the equation
corresponding to it.
4. Find an equation that ω satisfies (this should have degree 2). Using this, check that
the equation found in the step above is true.

â3.5 Problems
Here are some problems to practice these techniques on.

z |z|
Problem 33. Show that = for all complex numbers z and w
w |w|
• by letting z = a + bi and w = c + di.

• by using the identity |z|2 = zz.

45
NICE Journal NICE Committee (April 2, 2021)

Problem 34 (David Altizio). Define t to be the complex conjugate of the complex number
t - i.e. if t = a + bi then t = a − bi. Suppose that z is a complex number such that
|z − iz|2 = 50 and |z − iz|2 = 93. What is |z − iz|2 ?

Problem 35 (ACoPS). Prove that if z is a complex number such that |z| = 1, then
 
z
Im = 0.
( z + 1)2

Problem 36 (ARML 2012). On the complex plane, the parallelogram formed by the
points 0, z, 1z , and z + 1z has area 35
37 , and the real part of z is positive. If d is the smallest
possible value of |z + 1z |, compute d2 .

Problem 37 (Siddharth Prasad). Let z be a complex number such that |z − 1| ≤ 1 and

|z − 2| = 1. Find the largest possible value of |z|2 .

Problem 38 (AoPS). Let p and q be two complex numbers. Prove that if the two roots of
p
the equation x2 − px + q2 = 0 have equal magnitude, then q is real.

Problem 39 (AMC 12B 2005). A sequence of complex numbers z0 , z1 , z2 , . . . . is defined

by the rule
izn
z n +1 =
zn
where zn is the complex conjugate of zn and i2 = −1. Suppose that |z0 | = 1 and z2005 = 1.
How many possible values are there for z0 ?

Problem 40 (AoPS). Let a be a fixed real number, and suppose z is a complex number
1
such that z + = a.
z
1. Find the minimum value of |z|.
2. Find the maximum value of |z|.

46
4 Bounding between Squares
â4.1 Before Reading
At first, this might seems like a boring topic. However, the technique of bounding is
essentially one of the most basic topics, but is commonly used even in harder math
problems.

Bounding
Bounding refers to bounding the size of the solutions involved, which is useful when
one side of the equation will eventually grow faster than the other.

In this handout, we will demonstrate one of the most famous principles in bounding,
which is bounding between squares.

â4.2 Lecture Notes

â4.2.1 Introduction
We often overlook some facts as obvious, but actually they are essentially important in
solving problems.

Perfect Square
Define a natural number x to be a perfect square, or more simply square, if and only
if there exists a natural number y such that

x = y2 .

Exercise 71. Is 11025 a square?

Exercise 72. Is there any square between 100 and 121?

Exercise 73. What is the smallest perfect square greater than 196?

These questions might seem trivial, but this brings us to an important intuition for this
handout.
47
NICE Journal NICE Committee (April 2, 2021)

Lemma 74 (Bounding Lemma)

There are no perfect squares between any two consecutive perfect squares.

Proof. Let us suppose otherwise, that there exists a positive integer a and b such that

a2 < b2 < ( a + 1)2 .

Since a2 < b2 , this means a < b. Similarly, since b2 < ( a + 1)2 , this gives us b < a + 1.
This gives us
a < b < a + 1,
where a, b ∈ N. By the definition of N itself, this is a contradiction.

Corollary 75
If a is a perfect square greater than n2 , then

a ≥ ( n + 1)2 .

Proof. We have a > n2 . By Bounding Lemma, there doesn’t exist a perfect square in the
interval (n2 , (n + 1)2 ). Since a is a perfect square, then we must have a ≥ (n + 1)2 .
How do these seemingly obvious results help us in solving problems? Well, the key
insight of this technique lies on the fact that you want to force some value to be equal to
finite amount of cases to check.

Example 76 (Folklore)
How many pairs of positive integers ( x, y) are there such that x2 + 3y and y2 + 3x are
both perfect square numbers? Solution: 11

Walkthrough.
1. Let x ≤ y. Bound y2 + 3x between two perfect squares.
2. From the previous step, you should get a linear equation involving x and y. Substi-
tute into x2 + 3y and bound again.
3. For the possible perfect squares within range that are equal to x2 + 3y, solve for x.
Plug back in for y to finish.

Example 77 (USAJMO 2011/1)

Find, with proof, all positive integers n for which 2n + 12n + 2011n is a perfect square.
Solution: 32

Walkthrough.
48
NICE Committee (April 2, 2021) NICE Journal

1. Verify that n = 1 is a solution.

2. Use a modulo argument to show that if n > 1, then n is even.

3. Let n = 2n0 , and bound 20112n0 + 122n0 + 22n0 between two consecutive squares to
finish.

Remark 78. Actually, there exists a very simple solution using entirely modulo arguments. But
for the purpose of this chapter, we’ll demonstrate another way to solve where dealing the case
n is even.

â4.2.2 A Nontrivial Example

Example 79 (Greece TST 2018/3)
Find all functions f : Z>0 → Z>0 such that

x f ( x ) + ( f (y))2 + 2x f (y)
is a perfect square for all positive integers x, y. Solution: 8

Walkthrough.

1. Show that f (1) = 1, by bounding f (1)2 + 3 f (1) between two squares.

2. Use similar methods to show f (2) = 2.
3. Show that f ( x ) ≤ x for all x, using these values and more bounding between
squares.

4. Show that if p is prime, the expression from P( p, 1) must be ( p + 1)2 or ( p − 1)2 .

5. Eliminate the second case, and conclude that f ( p) = p.
6. Fix x and consider P( x, p) for large p. Conclude that f ( x ) = x for all x.

â4.3 Useful Theorems and Strategies

â4.3.1 Theorems
Lemma 80
If f and g are squares, then f g is square as well.

We’ll now see how the above lemma will help us in solving problems.

49
NICE Journal NICE Committee (April 2, 2021)

Example 81 (Valentio Iverson)

Determine all positive integers x such that both

x + 1 and x3 − 2

are perfect squares. Solution: 33

Walkthrough.
1. Show that x is odd.
2. Why can’t we use bounding between squares directly on one of the given expres-
sions?
3. Bound their product ( x + 1)( x3 − 2) between consecutive squares for large x. (To
find these squares, try to match the x4 , x3 , and x2 coefficients.)
4. Verify that x = 3 is the only solution below the bound you got in the step above.

Remark 82. Notice that we could instead just let x = a2 − 1 for a ∈ N and bound ( a2 − 1)3 − 2,
but bashing this expression requires a lot of work and is inefficient.

Theorem 83 (Sufficiently Large Squares Theorem)

If a polynomial in Z[ x ] takes square values for all sufficiently large numbers then it
must be a square in Z[ x ].

Remark 84. The proof of this lemma is beyond the scope of this handout. As far as I know, it
needs the aid of Schur, Hensel’s lemma, among others.
The following variation is also true: all sufficiently large powers of 2 take square values
grants the same result.

Now, let’s nuke the following problem.

Example 85
Given any positive integers a, b, c. Prove that there exists an integer ` such that
`3 + a`2 + b` + c is not a perfect square. Solution: 3

Walkthrough. We will prove that P(n) = n3 + an2 + bn + c is a perfect square at finite

values of n.
1. FTSoC assume that P(n) is a square for all sufficiently large n. Show that P is a
square.
2. Show that squares have even degrees, and finish the contradiction.

50
NICE Committee (April 2, 2021) NICE Journal

Remark 86. The proof of this problem without citing Sufficiently Large Squares Theorem is
actually fairly simple, which is by taking a large number n and setting ` = n2 , then bounding
the expression between two squares. This is left to the interested reader as a fun exercise.

â4.3.2 Grand Finale

Example 87 (ISL 2018/N5)
Four positive integers x, y, z and t satisfy the relations

xy − zt = x + y = z + t.

Is it possible that both xy and zt are perfect squares? Solution: 17

Walkthrough. Assume for contradiction that xy = a2 and zt = b2 .

1. Consider an expression in terms of x and y which must be a square, and rewrite it

in terms of a and b.

2. Do the same for z and t. You should get two expressions involving a and b (which
aren’t squares of a polynomial, so that we can prove that these two expressions
can’t both be squares).

3. Show that we can let a = m + n and b = m − n for positive integers m and n (or the
other way around).

4. Show that the two expressions, in terms of m and n, can’t both be squares, by
bounding their product between two consecutive squares.

â4.3.3 Summary of Strategies

To summarize the whole handout, we conclude that

• Bounding is essentially useful if we want to limit the range of examining cases

into finite amount of work, which could normally be dealt by either bashing or
examining modulo.

• Suppose f is a monic polynomial of even degree. If there doesn’t exist a polynomial

g such that f = g2 , then f must be square on finite values.

• Suppose we have two polynomials f , g which are perfect squares. If we couldn’t

bound f , g by the above lemma because f and g have odd degree, we could instead
bound f g which has even degree.

• If you have two expressions that should be a square, considering multiplying them
and bounding that expression instead.
51
NICE Journal NICE Committee (April 2, 2021)

â4.4 Problems
â4.4.1 Easier Problems
Problem 41. Let Sn = n2 + 20n + 12 where n is a positive integer. Determine the sum of
all n such that Sn is a square.

Problem 42 (Mathematics Reflections). Determine all integers ( a, b) such that 9a +

16b and 16a + 9b are both squares.

Problem 43 (Cyprus TST 2018/1). Determine all n ∈ N such that 11111 in base n is a
perfect square.

Problem 44 (Belgia). Determine all solutions ( x, y) of positive integers such that

x 4 + x 3 + x 2 + x = y2 + y

Problem 45 (APMO 2011/1). Let a, b, c be positive integers. Prove that it is impossible

to have all of the three numbers

a2 + b + c, b2 + c + a, c2 + a + b

to be perfect squares.

Problem 46 (Tuymaada MO 2019/6). Prove that the expression

(14 + 12 + 1)(24 + 22 + 1) . . . (n4 + n2 + 1)

is not square for all n ∈ N.

Problem 47 (Mathematics Reflections). Solve in positive integers the equation

min( x4 + 8y, 8x + y4 ) = ( x + y)2

Problem 48 (CWMO 2004/1). Find all integers n, such that the following number is a
perfect square.
N = n4 + 6n3 + 11n2 + 3n + 31

52
NICE Committee (April 2, 2021) NICE Journal

Some similar problems:

Exercise 88 (CWMO 2002/1). Find all positive integers n such that n4 − 4n3 + 22n2 − 36n + 18
is a perfect square.

Exercise 89 (CWMO 2019/1). Determine all the possible positive integer n, such that 3n + n2 +
2019 is a perfect square.

Problem 49 (Canada MO 2015/1). Let N = {1, 2, 3, . . .} be the set of positive inte-

gers. Find all functions f , defined on N and taking values in N, such that (n − 1)2 <
f (n) f ( f (n)) < n2 + n for every positive integer n.

Problem 50 (Folklore). Determine all positive integers k such that ∏ik=1 (i4 + 4) is a
perfect square.

Problem 51 (Romania MO Grade 9 2007/1). Let a, b, c, d, x be positive integers obeying

x2 − ( a2 + b2 + c2 + d2 + 1) x + ( a + c)(b + d) = 0.

Prove that x is a perfect square.

Problem 52 (Croatia TST 2003/1). Find all pairs (m, n) of natural numbers for which
the numbers m2 − 4n and n2 − 4m are both perfect squares.

â4.4.2 Challenging Problems

Problem 53 (IMO 2017/1). For each integer a0 > 1, define the sequence a0 , a1 , a2 , . . .
for n ≥ 0 as (√ √
an if an is an integer,
a n +1 =
an + 3 otherwise.
Determine all values of a0 such that there exists a number A such that an = A for infinitely
many values of n.

Problem 54 (Croatia TST 2016/4). Find all pairs ( p, q) of prime numbers such that

p( p2 − p − 1) = q(2q + 3).

53
NICE Journal NICE Committee (April 2, 2021)

Problem 55 (PUMaC NT 2014/A8). Find all positive integers a, b, c, d such that a2 + b +

c + d, b2 + c + d + a, c2 + d + a + b, d2 + a + b + c are all perfect squares.

Problem 56 (Istanbul National Science Olympiad 2019/2). Find all positive integers
(m, n) such that
m ( m + 5)
= p2
n ( n + 5)
such that p is a prime number.

Problem 57. Let P be a polynomial with integer coefficients of degree ≥ 3 which is

irreducible over Z[ x ]. Prove that the set of all x ∈ Z such that P( x ) is a square is finite.

Problem 58 (IMO 2003/2). Determine all pairs of positive integers ( a, b) such that

a2
2ab2 − b3 + 1
is a positive integer.

Problem 59 (EGMO 2020/6). Let m > 1 be an integer. A sequence a1 , a2 , a3 , . . . is

defined by a1 = a2 = 1, a3 = 4, and for all n ≥ 4,

a n = m ( a n −1 + a n −2 ) − a n −3

Determine all integers m such that every term of the sequence is a square.

Problem 60 (ELMO SL 2013/N1). Find all ordered triples of non-negative integers

( a, b, c) such that a2 + 2b + c, b2 + 2c + a, and c2 + 2a + b are all perfect squares.

Problem 61 (China TST 2001/3). Determine all positive integers x for which

f ( x ) = x6 + 15x5 + 85x4 + 225x3 + 274x2 + 120x + 1

is equal to a perfect square.

54
5 Soft Techniques
The goal of this chapter is to solve questions with emphasis on soft principles – the type
that goes through your mind but isn’t explicitly written down. More on the definition
can be found in Evan Chen’s blog post. The best (and only) way to actually understand
the ideas in this article is to solve them alongside, so please do!

â5.1 Symmetry
Example 90 (USAMO 2020/2)
An empty 2020 × 2020 × 2020 cube is given, and a 2020 × 2020 grid of square unit cells
is drawn on each of its six faces. A beam is a 1 × 1 × 2020 rectangular prism. Several
beams are placed inside the cube subject to the following conditions: The two 1 × 1
faces of each beam coincide with unit cells lying on opposite faces of the cube. (Hence,
there are 3 · 20202 possible positions for a beam.) No two beams have intersecting
interiors. The interiors of each of the four 1 × 2020 faces of each beam touch either
a face of the cube or the interior of the face of another beam. What is the smallest
positive number of beams that can be placed to satisfy these conditions? Solution: 31

Let’s concentrate on the thought process.

Because we’re asked for the smallest value of something, our intuition tells us to use
inequalities – we will find the minimum possible number and then we show it is possible
by construction.

Moral
This is a very common idea – one bound by algebra and the other bound by combina-
torics.

An important idea that comes to one’s mind is visualization. This is a 3D figure and as
such we must figure out a way to visualize this. The way I did it, and I think a rather
natural way to do it, is to look from one direction (say the z-axis) and cut it up into slices,
so that you get squares where the beams parallel to the z-axis intersect. Moreover, you
might notice that in a cross section, other than the squares, you will only have slices of
the left-right or top-bottom beams (which actually appear as squares in the cross section).
Convince yourself this is true. You can try to make a few more observations like this to
get more comfortable.
Now comes the part where you start trying constructions – keep in mind the goal is
to minimize the amount of beams! And this is where symmetry comes in – notice that
55
NICE Journal NICE Committee (April 2, 2021)

all 3 directions are very symmetric, so there’s a good chance our construction is also
symmetric. But since we are looking at one direction only, it is easy to forget this.

Moral
Looking from one angle can result in loss of symmetry (similar to how local ideas
delete global properties).

Using this and by trying out the 2 × 2 × 2 and 3 × 3 × 3 cube cases, and lots of dirty work
(start with a construction, and keep trying to optimize it until you think you have got a
nice solution), you’ll get the construction. It turns out that getting the inequality is not
hard at all if you get the construction.
You can probably try getting the inequality first to just have an idea of the lower bound
– but this direction is not that easy.
Note that symmetry is not written explicitly in the solution (and often never is) but
it plays a very important role in one’s thought process, especially when using trial and
error on unsymmetrical constructions.

Example 91 (USAMO 2010/6)

A blackboard contains 68 pairs of nonzero integers. Suppose that for each positive
integer k at most one of the pairs (k, k) and (−k, −k) is written on the blackboard. A
student erases some of the 136 integers, subject to the condition that no two erased
integers may add to 0. The student then scores one point for each of the 68 pairs in
which at least one integer is erased. Determine, with proof, the largest number N of
points that the student can guarantee to score regardless of which 68 pairs have been
written on the board. Solution: 25

This is a pretty hard problem and quite different from the previous one. But you should
see the similarity – this one is asking for a minimum/maximum as well. And like the
previous one, once we get the inequality and construction, our write up will be quite
short compared to the work done because the main work is in the thought process.
In this problem, the construction seems quite hard to get – an indication for this is the
fact that the conditions are weird. Let me clarify – in the USAMO 2020/2 problem, it may
appear that the conditions are weird at first but we used our properties effectively when
coming up with a construction. Here it seems simpler to start with the algebra.
Lets start with the visualization – here it is much simpler than the second, but there is
something very important to realize here – the numbers are just labels!
You can replace 2 with 20 million everywhere (as long as 20 million is not present
already) and it won’t change a thing. The only connection a number has is with its
additive inverse. This idea shows approaches where you plot points on the Cartesian
plane is doomed to fail. So perhaps a combinatorial graph is better suited for this problem
– and you can use it for visualization – but at the end of the day even just writing down
the pairs works fine.
Then we should note that for every number a, we will choose one of a and − a, because
why not? The difficulty lies in choosing whether to erase a or − a. Note that at this point
56
NICE Committee (April 2, 2021) NICE Journal

you might as well assume that any pair of the form is positive because switching a and
− a in the problem doesn’t affect it at all – we only need to minimize the maximum and
the only other number that any number x has a “relationship” with is − x.
Now we use expected value – as in, we choose positives with probability p = 12 and
negatives with the same probability, and find the expected score. The answer can’t go
above that (why?). But there’s something essential we are missing! The positives and
negatives are not symmetric. So it turns out the right way to do it would be choose
positives with some random probability p and negatives with 1 − p, then move p around
until you minimize it.
I won’t do all that here – but the important part was that we noticed that something
was unsymmetrical, and we treated it that way. This is not something we actually write
down. It is enough proof to just state the value of p and show some things (you can work
the details out), but the motivation behind the value is important to solving the problem.
In any case, the construction turns out to be quite hard to get, and it requires a lot of
thinking. After all, it is the 6th problem.
Just to summarize, we discussed both the idea of using algebra and combinatorics from
either side and more importantly – symmetry.

â5.2 Visualisation
Visualisation might just be one of the most important soft techniques out there. It’s well
known that diagrams for geometry problems are everything. What is less talked about
is that many combinatorics questions have complicated structures and wrapping our
brains around them is quite hard. We can usually see the small connections given in the
statement or use greedy algorithms or smoothing without necessarily understanding the
exact structure. But when it comes to looking at the entire structure at once (i.e. global
ideas), in order to understand the relationship between uncertain elements and make any
sort of nontrivial construction, we need to understand the structure better. And the best
way to do this is to try to visually represent all the information we have, thus organizing
our data. One of the best examples is the first problem we looked at – USAMO 2020/2.
3D structures are hard for most to get their mind around. So we look at 2D slices instead.
This may look like a trivial step, but it is a huge change in perspective. We are now
missing out on the whole picture obviously, but nevertheless we can form some intuition
and make progress better.

Remark 92. As a side note, this is common in many areas of olympiad math – we look at very
specific parts of the given problem or structure and gain information, because looking at it all
makes us dizzy. For instance, looking at a Diophantine equation modulo something in number
theory applies this – we are actually removing lots of information to reveal something very
specific, because we often only need one thing to finish the problem.

Another point to make is that visualisation might often feel like writing the same problem
in a different way (e.g. inversion in geometry). This is usually useful – trying to think
57
NICE Journal NICE Committee (April 2, 2021)

about the problem from a different perspective may not yield a lot, but it can give you
better intuition about the structure of the problem. But I digress.
Let’s start with a very famous example for visualisation:

Example 93 (ELMO 2015/2)

Let m, n, and x be positive integers. Prove that
n j x k  m j x k 
∑ min i
,m = ∑ min i
,n .
i =1 i =1

Solution: 7

This a pretty unique problem. When we try some cases, the sums almost add up like
magic. We can try a few special cases then – maybe m = 1? It’s not hard to prove the
problem for m = 1, since the LHS adds n 1s (check this!). This motivates the idea of
induction and there are indeed multiple induction solutions that involve quite a bit of
manipulation.
But let’s try out a different approach. Suppose we are trying to look for something to
make everything work out really nicely (you only get beautiful and crazy solutions by
looking for beautiful and crazy solutions). One thing to notice is the symmetry between
m and n. Clearly, whatever we do, we should consider them on equal footing. Now
we have lots of numbers, and the first thing to do when we have to store lots of related
numbers is to try a matrix, i.e. a table.
Notice that we actually don’t have much incentive to do this if look at our ‘evidence’
so far, but aesthetically it seems like a good idea. And what exactly do we store? This
is not so hard to figure – our sums run over m and n, and if we want our table to be of
any use, one side of our table need to have the numbers from 1 to n, and the other side
must contain 1 to m. In any case it makes sense to fix x as well. And now what do we put
inside?
Let’s think a little more about this – say we are looking at the sum with respect to n.
Then for any i, we have, say, a row of numbers m long. This must tie in with min(b xi c, m)
somehow. Furthermore, we need to bring in the x as well. All this looks like a headache.
What do we do in such scenarios? We simply do something obvious and improvise. This
is actually an unbelievably important olympiad strategy.

Moral
Instead of staring at the problem or whatever you have, do something lame/silly/ob-
vious/dumb and improvise.

Quite often, something silly works out and you’ll be sorry to have ignored it. So let’s
forget x and fill up the table in the most obvious way – just sum up the labels on the row
and column. Keep in mind that we can do a couple of other things – we can multiply
the labels, or maybe even write up 1 everywhere but just make sure the construction
is symmetric with respect to m and n. But back to the sum – how do we make sense
58
NICE Committee (April 2, 2021) NICE Journal

of the LHS? For example, if we consider i = 5 on the LHS, we need to get min(b 5x c, m)
somehow. Now we look at the 5th column (or row depending on how you labeled),
where we have numbers from 6 to m + 5. If you look at it, it doesn’t look nice at all. But
more importantly you should notice that the reason for this is that there is no way to
make sense of the 5x in series of consecutive numbers. If the problem said to subtract 5
instead of dividing by 5 (more generally, i), it would have been better to sum. So our
error lies in the fact that the relationship between x and i is multiplicative and we are
looking at sums. So we just switch our matrix to a multiplicative one – we multiply the
labels.
Now in the 5th column we have 5, 10, 15, . . . , 5m. This looks sort of relevant to the 5x .
Now let’s look at the two cases in the problem, i.e. when m is the minimum and when it is
not, for some fixed i. When m is minimum, i.e. we add m to the sum, we have x > 5m in
some sense. By now you should be getting the feeling that we are in the right path – the
5m we have is the last number in the series. And now if x < 5m, what does b 5x c represent
in the series of numbers above? Well this should actually become really obvious if you
try out a few cases, but we can also notice that since everything seems to the multiples
up with 5, we can simply divide by 5 and check. Either way we realise that it yields the
number of integers in the series 5, 10, . . . , 5m that are less than or equal to x (prove this!).
But when we had m as the minimum, we were doing that as well, except that then, since
x > 5m and we don’t want to count multiples not in the table, we are limiting ourselves
to the m multiples mentioned.
So what do we get when we sum with respect to n? We get the number of integers in
the multiplication table that are less than or equal to x in each column, which is equivalent
to the number of integers less than x in the whole table. And this will be same if we sum
with respect to m as well, and so we are done!
A couple of notes:

• In our LHS sum, the quantity had to be the same for the RHS as well, because the
table was symmetric in the first place.
• The actual solution is awfully short for all of our work. But that’s the whole point
of visualisation: it will make us see what we hadn’t seen before, and with this new
perspective we are done.

• There are many other solutions, and I recommend checking some of them here.
Now for the next problem:

Example 94 (ISL 2009/C2)

For any integer n ≥ 2, let N (n) be the maxima number of triples ( ai , bi , ci ), i =
1, . . . , N (n), consisting of nonnegative integers ai , bi and ci such that the following two
conditions are satisfied:
• ai + bi + ci = n for all i = 1, . . . , N (n),

59
NICE Journal NICE Committee (April 2, 2021)

• If i 6= j then ai 6= a j , bi 6= b j and ci 6= c j .
Determine N (n) for all n ≥ 2. Solution: 23

Hopefully this problem should feel like something you seriously need to mess around
with. Of course you can try writing some random triples ( ai , bi , ci ), but unfortunately this
doesn’t incorporate the sum condition. When we try to write something in a different
way, our motivation is often to make one or more of the conditions very easy to handle.
And here, the first sum condition is the evil twin. So if we are going to try to write this
up in a different way we need to deal with that.
Now this is actually something you might have seen before – if you have seen dumb-
assing in inequalities (see Evan’s handout) or barycentric coordinates (again, see Evan’s
handout), the crux move should be more or less obvious. The idea is this: we have 3
variables and we want a structure where say adding one to a and subtracting one from b
still makes sense in our structure. We are actually going to completely ignore our second
condition – we first represent all possible pairs according to the first condition, then fit the
second in later. The motivation is that the first condition is actually cleaner – finding pairs
that satisfy that condition isn’t too hard. But for the second one you need to compare all
possible pairs of triples, which is dizzying. So the natural thing to do is to first consider
all triples and then select specific ones.
Let’s come back to the visualisation. We create an equilateral triangle with side length
n using dots, such that the bottom row has n dots, the one above it has n − 1 dots, and so
on. Each variable gets a side. (This might sound like an excuse, but I haven’t included any
diagrams on purpose – you should try and draw it yourself!) We represent the vertices as
(n, 0, 0), (0, n, 0), (0, 0, n). Can you now label all the n(n2+1) points inside with triples?
If you did it right then you have a lattice triangle where each point represents a possible
tuple. Now you need to choose as many dots as possible so that the first condition is
satisfied. But wait, what does the first condition even mean here? This should be trivial
to figure out. I won’t go beyond this point, but now we have a purely combinatorial
question and what we need to do is find a general construction to choose as many points
as possible. Try small cases first. Of course, you will actually have to prove that the
answer you found is the maximum but that’s not very surprising. In fact, if you tried the
problem for a while you might have gotten the bound first.
In this problem we actually completely transformed the question into something
else. Also note how we converted an algebra/combinatorics hybrid using an idea from
geometry/inequalities. Crazy!
So to summarize, if you get stuck at any point, try to write the problem in a different
form. The biggest mistake that beginners in olympiad math make is to only use what’s
given in the problem – in some sense that’s often not enough.

â5.3 Problems
60
NICE Committee (April 2, 2021) NICE Journal

Problem 62 (AMC 12B 2019/13). A red ball and a green ball are randomly and inde-
pendently tossed into bins numbered with the positive integers so that for each ball, the
probability that it is tossed into bin k is 2−k for k = 1, 2, 3 . . . . What is the probability that
the red ball is tossed into a higher-numbered bin than the green ball?

Problem 63 (AMC 10B 2021/16). Bela and Jenn play the following game on the closed
interval [0, n] of the real number line, where n is a fixed integer greater than 4. They take
turns playing, with Bela going first. At his first turn, Bela chooses any real number in the
interval [0, n]. Thereafter, the player whose turn it is chooses a real number that is more
than one unit away from all numbers previously chosen by either player. A player unable
to choose such a number loses. Using optimal strategy, which player will win the game?

Problem 64. Two similar problems:

(a) A monk climbs a mountain and starts at the base at 9 A.M. and reaches the summit
at 9 P.M. He spends the night and the next day he again starts at 9 A.M. and reaches
base at 9 P.M. Prove that he was at the same time (24 hours later) at the same place
at some point.
(b) Consider a metal ring with a continuous temperature gradient (the temperature
doesn’t suddenly ‘jump’). Prove there are 2 diametrically opposite points with the
same temperature.

Problem 65. Given some non-negative numbers a, b, c, d, e such that ab + bc + cd + de =

2018, determine the minimum value of a + b + c + d + e.

Problem 66 (Pranav Sriram). Two players A and B each get an unlimited supply of
identical circular coins. A and B take turns placing the coins on a finite square table, in
such a way that no two coins overlap and each coin is completely on the table (that is, it
doesn’t stick out). The person who cannot legally place a coin loses. Assuming at least
one coin can fit on the table, prove that A has a winning strategy.

Problem 67. Let A and B be finite nonempty sets of real numbers. Let A + B = { a + b |
a ∈ A, b ∈ B}.
1. Prove that | A + B| ≥ | A| + | B| − 1.

2. Determine the equality cases.

61
NICE Journal NICE Committee (April 2, 2021)

Problem 68 (ISL 2001/C3). Define a k-clique to be a set of k people such that every pair
of them are acquainted with each other. At a certain party, every pair of 3-cliques has at
least one person in common, and there are no 5-cliques. Prove that there are two or fewer
people at the party whose departure leaves no 3-clique remaining.

Problem 69 (USAMO 2020/4). Suppose that ( a1 , b1 ), ( a2 , b2 ), . . . , ( a100 , b100 ) are distinct

ordered pairs of nonnegative integers. Let N denote the number of pairs of integers (i, j)
satisfying 1 ≤ i < j ≤ 100 and | ai b j − a j bi | = 1. Determine the largest possible value of
N over all possible choices of the 100 ordered pairs.

Problem 70 (USAMO 2014/6). Prove that there is a constant c > 0 with the following
property: if a, b, n are positive integers such that gcd( a + i, b + j) > 1 for all i, j ∈
{0, 1, . . . , n}, then
min{ a, b} > (cn)n/2 .

62
Editor’s Notes
Congrats, you made it to the end!

About the LATEX

I’m going to toot my own horn a bit.

How was this journal made?

This journal was compiled in Overleaf (sorry1 local users!). The limited runtime for
a non-premium account on Overleaf made it hard to compile such a large document,
however.

What is the style file used?

I used my own style file, dylanadi.sty. Feel free to use it yourself!

How were the diagrams made?

The diagrams were made using both Tikz and Asymptote, whose documentations can be
found here and here, respectively. The Asymptote diagrams also used olympiad.asy and
cse5.asy, both of which can be found here.

How you can help with NICE Journal

Tell us your thoughts
We are always open to suggestions about the journal. Please let us know how you feel
about it through our Contact Us page.

Submit your work to the journal

Those in the NICE committee aren’t the only people who can submit entries. If you are
interested in contributing an article, please private message freeman66 on AoPS.
1 Haha, no I’m not sorry.
63
NICE Journal NICE Committee (April 2, 2021)

Parting Words
The hidden purpose of NICE Journal
There are many articles that people write that simply don’t get any attention for some
reason or another. Through this journal, we hope to spread awareness about amazing
handouts and, of course, give math enthusiasts something to read.

How you can support NICE Journal

NICE Journal does not need monetary support. Instead, if you want to support the
journal, just read it! Our aim is to showcase quality articles, and the larger the audience,
the more motivation we have to continue this project.

That’s it for now! See you guys in the next issue.

Dylan Yu

64
A Key Parts
âA.1 List of Problems

Chapter 1
1 Example – Putnam 2015/B4 . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Example – HMMT February Algebra 2019/7 . . . . . . . . . . . . . . . . 11
3 Example – Folklore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4 Example – COMC 2014/4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5 Example – IMO 2002/4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6 Example – AMC 10A 2019/24 . . . . . . . . . . . . . . . . . . . . . . . . . 14
1 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Problem – AMC 12B 2018/7 . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Problem – AMC 12B 2018/9 . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 Problem – AIME I 2016/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5 Problem – AIME II 2005/3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6 Problem – HMMT February Algebra 2017/2 . . . . . . . . . . . . . . . . 15
7 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
8 Problem – AMC 12A 2018/19 . . . . . . . . . . . . . . . . . . . . . . . . . 15
9 Problem – AMC 12B 2019/8 . . . . . . . . . . . . . . . . . . . . . . . . . . 16
10 Problem – AIME I 2019/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
11 Problem – AIME I 2017/3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
12 Problem – AMC 12B 2016/25 . . . . . . . . . . . . . . . . . . . . . . . . . 16
13 Problem – AMC 12B 2016/21 . . . . . . . . . . . . . . . . . . . . . . . . . 16
14 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
15 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
16 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
17 Problem – SMT Advanced Topics 2011/2 . . . . . . . . . . . . . . . . . . 17
18 Problem – ARML Local Team 2019/15 . . . . . . . . . . . . . . . . . . . . 17
19 Problem – USAMTS 3/4/11 . . . . . . . . . . . . . . . . . . . . . . . . . . 17
20 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
21 Problem – AIME II 2000/15 . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Chapter 2
8 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
10 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
12 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
18 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
19 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
65
NICE Journal NICE Committee (April 2, 2021)

21 Example – AIME I 2017/7 . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

22 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
24 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
27 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
28 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
33 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
34 Example – Folklore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
35 Example – AIME II 2006/4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
37 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
38 Example – AMC 10B 2020/25 . . . . . . . . . . . . . . . . . . . . . . . . . 30
41 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
42 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
43 Example – AIME 1986/11 . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
46 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
47 Example – AIME I 2020/7 . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
50 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
51 Example – AIME 1993/7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
22 Problem – A(N)IME 2020/6 . . . . . . . . . . . . . . . . . . . . . . . . . . 35
23 Problem – AIME II 2008/12 . . . . . . . . . . . . . . . . . . . . . . . . . . 35
24 Problem – HMMT February Combinatorics 2007/6 . . . . . . . . . . . . . 35
25 Problem – HMMT February Combinatorics 2015/7 . . . . . . . . . . . . . 35
26 Problem – AMC 12B 2019/23 . . . . . . . . . . . . . . . . . . . . . . . . . 35
27 Problem – AIME II 2006/10 . . . . . . . . . . . . . . . . . . . . . . . . . . 36
28 Problem – AIME I 2015/12 . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
29 Problem – AMC 12B 2016/25 . . . . . . . . . . . . . . . . . . . . . . . . . 36
30 Problem – CMIMC Combinatorics 2016/9 . . . . . . . . . . . . . . . . . . 36
31 Problem – HMMT February Combinatorics 2014/10 . . . . . . . . . . . . 36
32 Problem – HMMT February Combinatorics 2007/10 . . . . . . . . . . . . 36

Chapter 3
54 Example – AoPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
55 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
56 Example – AIME I 2009/2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
58 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
59 Example – AoPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
60 Example – AoPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
62 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
63 Example – AoPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
65 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
66 Example – AMC 12B 2009/23 . . . . . . . . . . . . . . . . . . . . . . . . . 43
68 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
69 Example – AoPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
70 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
33 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
66
NICE Committee (April 2, 2021) NICE Journal

34 Problem – David Altizio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

35 Problem – ACoPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
36 Problem – ARML 2012 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
37 Problem – Siddharth Prasad . . . . . . . . . . . . . . . . . . . . . . . . . . 46
38 Problem – AoPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
39 Problem – AMC 12B 2005 . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
40 Problem – AoPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Chapter 4
71 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
72 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
73 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
76 Example – Folklore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
77 Example – USAJMO 2011/1 . . . . . . . . . . . . . . . . . . . . . . . . . . 48
79 Example – Greece TST 2018/3 . . . . . . . . . . . . . . . . . . . . . . . . . 49
81 Example – Valentio Iverson . . . . . . . . . . . . . . . . . . . . . . . . . . 50
85 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
87 Example – ISL 2018/N5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
41 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
42 Problem – Mathematics Reflections . . . . . . . . . . . . . . . . . . . . . . 52
43 Problem – Cyprus TST 2018/1 . . . . . . . . . . . . . . . . . . . . . . . . . 52
44 Problem – Belgia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
45 Problem – APMO 2011/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
46 Problem – Tuymaada MO 2019/6 . . . . . . . . . . . . . . . . . . . . . . . 52
47 Problem – Mathematics Reflections . . . . . . . . . . . . . . . . . . . . . . 52
48 Problem – CWMO 2004/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
88 Exercise – CWMO 2002/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
89 Exercise – CWMO 2019/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
49 Problem – Canada MO 2015/1 . . . . . . . . . . . . . . . . . . . . . . . . . 53
50 Problem – Folklore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
51 Problem – Romania MO Grade 9 2007/1 . . . . . . . . . . . . . . . . . . . 53
52 Problem – Croatia TST 2003/1 . . . . . . . . . . . . . . . . . . . . . . . . . 53
53 Problem – IMO 2017/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
54 Problem – Croatia TST 2016/4 . . . . . . . . . . . . . . . . . . . . . . . . . 53
55 Problem – PUMaC NT 2014/A8 . . . . . . . . . . . . . . . . . . . . . . . . 54
56 Problem – Istanbul National Science Olympiad 2019/2 . . . . . . . . . . 54
57 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
58 Problem – IMO 2003/2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
59 Problem – EGMO 2020/6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
60 Problem – ELMO SL 2013/N1 . . . . . . . . . . . . . . . . . . . . . . . . . 54
61 Problem – China TST 2001/3 . . . . . . . . . . . . . . . . . . . . . . . . . 54

Chapter 5
90 Example – USAMO 2020/2 . . . . . . . . . . . . . . . . . . . . . . . . . . 55
67
 91 Example – USAMO 2010/6 . . . . . . . . . . . . . . . . . . . . . . . . . . 56
93 Example – ELMO 2015/2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
94 Example – ISL 2009/C2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
62 Problem – AMC 12B 2019/13 . . . . . . . . . . . . . . . . . . . . . . . . . 61
63 Problem – AMC 10B 2021/16 . . . . . . . . . . . . . . . . . . . . . . . . . 61
64 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
65 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
66 Problem – Pranav Sriram . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
67 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
68 Problem – ISL 2001/C3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
69 Problem – USAMO 2020/4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
70 Problem – USAMO 2014/6 . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

âA.2 List of Theorems

Chapter 2
7 Theorem – Permutations of Items . . . . . . . . . . . . . . . . . . . . . . . 18
9 Theorem – Permuting with Duplicates . . . . . . . . . . . . . . . . . . . . 19
11 Theorem – Combination Closed Form . . . . . . . . . . . . . . . . . . . . 19
13 Fact . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
14 Theorem – Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 21
17 Theorem – Multinomial Coefficient . . . . . . . . . . . . . . . . . . . . . . 22
23 Theorem – Number of Paths . . . . . . . . . . . . . . . . . . . . . . . . . . 24
26 Theorem – Number of Paths Excluding One Point . . . . . . . . . . . . . 25
29 Theorem – Terms in Pascal’s Triangle . . . . . . . . . . . . . . . . . . . . . 26
30 Fact . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
31 Theorem – Pascal’s Identity . . . . . . . . . . . . . . . . . . . . . . . . . . 27
36 Theorem – Stars and Bars . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
39 Theorem – Hockey-Stick Identity . . . . . . . . . . . . . . . . . . . . . . . 30
44 Theorem – Vandermonde’s Identity . . . . . . . . . . . . . . . . . . . . . . 32
48 Theorem – Catalan Grid-Walking . . . . . . . . . . . . . . . . . . . . . . . 33
49 Theorem – Parentheses Orderings . . . . . . . . . . . . . . . . . . . . . . . 34

Chapter 3
52 Theorem – Spliting Conjugates . . . . . . . . . . . . . . . . . . . . . . . . 38
53 Theorem – Splitting Magnitudes . . . . . . . . . . . . . . . . . . . . . . . 38
57 Theorem – Complex Times Conjugate . . . . . . . . . . . . . . . . . . . . 40
61 Theorem – Triangle Inequality . . . . . . . . . . . . . . . . . . . . . . . . . 42
64 Fact – Complex Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . 43
67 Fact – Complex Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Chapter 4
74 Lemma – Bounding Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 48
68
NICE Committee (April 2, 2021) NICE Journal

75 Corollary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
80 Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
83 Theorem – Sufficiently Large Squares Theorem . . . . . . . . . . . . . . . 50

âA.3 Index

Argand plane, 37 complex number, 37 Pascal’s triangle, 25

argument, 37 perfect square, 47
global, 23
Bounding, 47
Ravi Substitution, 11
bounding between squares, Hensel’s lemma, 50
47 local, 23 Schur, 50
Catalan number, 33 square, 47
magnitude, 37
combination, 19 symmetry, 55
Combinatorics, 18 partial fraction decomposi-
complex conjugate, 37 tion, 10 visualization, 55

69
B Selected Solutions
1. First note that since w1 + w2 + w3 = 0, we have −w3 = w1 + w2 .

Claim — We have w1 w2 + w1 w2 = −1.

Proof. Note that |w3 | = | − w3 | = |w1 + w2 |, so |w1 + w2 | = 1. Squaring both sides gives
(w1 + w2 )(w1 + w2 ) = 1, so

w1 w1 + w1 w2 + w1 w2 + w2 w2 = 1.

Since w1 w1 = |w1 |2 = w2 w2 = |w2 |2 = 1, we have w1 w2 + w1 w2 = −1 as desired.

Note that

w12 + w22 + w32 = w12 + w22 + (w1 + w2 )2

= w12 + w22 + (w12 + 2w1 w2 + w22 )
= 2(w12 + w1 w2 + w22 ).

Since we already know that w1 w1 = 1 and w2 w2 = 1, we have

w12 + w1 w2 + w22 = w12 w2 w2 + w1 w2 + w22 w1 w1 = w1 w2 (w1 w2 + 1 + w2 w1 ) .

However, from our claim, we know that w1 w2 + w1 w2 + 1 = (−1) + 1 = 0. Therefore

w12 + w22 + w32 = 2(w12 + w1 w2 + w22 ) = 2(0) = 0,

which is what we wanted.

2. Applying Ravi substitution, we get
2y+1+2z+1 2y+2z
2 2 2 2
∑ 2z+1+2x +1 2x +1+2y+1
+ ∑ 2z+2x 2x +2y
2x +1,2y+1,2z+1≥1 3 2 5 2 2x,2y,2z≥2 3 2 5 2

  x  y  z
17 1 2 2 17
=
2 ∑ 15 5 3
=
21
.
x,y,z≥1

3. Suppose otherwise, i.e. that this polynomial P(n) = n3 + an2 + bn + c can attain square
values for all sufficiently large n.
By Sufficiently Large Squares Theorem, this polynomial must be a square. In particular, it
must have an even degree. However, the degree of this polynomial is 3, which is an odd
number, a contradiction.
70
NICE Committee (April 2, 2021) NICE Journal

4. Note that for a6 , we want a positive integer in [1, 12] such that there exist 11 distinct numbers
in [1, 12] that are greater than it. Clearly, we must have a6 = 1.
Now, realize that you can use the same type of logic as when you’re finding the number of
increasing sequences. If you choose an arbitrary group of five distinct positive integers in
[2, 12], there is a one-to-one correspondence between this and a valid permutation for the
sake of the problem, because using these five we determine ak for k ∈ [1, 5] and the rest is
also uniquely determined as the remaining 6 are just ordered in increasing order as detailed
in the problem. Thus, the bijection allows us to realize that our answer is just the number of
ways to choose 5 numbers from the 11 numbers in [1, 12] excluding 1. Thus, our answer is
 
11
= 462 .
5

5. Think of it using the idea of committee forming. Using this logic, (n0 ) is the number of
ways to create committees of 0 from n people. Similarly, (n1 ) is the number of ways to create
committees of 1 person from n people. If we sum this for each number from 0 to n, we’re
getting the number of ways to make a committee of any size from n people. Now, we know
that each person is either in a committee or they aren’t, with 2 choices each. Multiplying all
of these choices leads to a total of 2n ways.
6. Note that |zw|2 = (zw)(zw) = (zz)(ww) = |z|2 |w|2 , and since magnitudes are always
positive, taking the square root of both sides gives |zw| = |z||w| as desired.
7. Notice that if you create an m by n multiplication table, both the left and right sides of the
equation are counting the amount of values in this multiplication table that are less than or
equal to x. So, they are both equal.

8. The only solution is f ( x ) = x which works since

x f ( x ) + ( f (y))2 + 2x f (y) = x2 + y2 + 2xy = ( x + y)2

for all x, y ∈ Z>0 .

We’ll now prove that there are no other solutions. Let P( x, y) be the assertion of x and y to
the given functional equation. From P( x, x ), we have f ( x )2 + 3x f ( x ) is a perfect square for
all x ∈ N.

Claim — f (1) = 1 and f (2) = 2.

Proof. From P(1, 1), we know that f (1)2 + 3 f (1) has to be a square. However, since f (1) ∈
Z>0 , then we have

( f (1) + 1)2 = f (1)2 + 2 f (1) + 1 ≤ f (1)2 + 3 f (1) < ( f (1) + 2)2

Therefore, this forces f (1) = 1. From P(2, 2), we know that f (2)2 + 6 f (2) has to be a square.
Similarly, we have
( f (2) + 1)2 < f (2)2 + 6 f (2) < ( f (2) + 3)2
Therefore, we conclude that f (2)2 + 6 f (2) = ( f (2) + 2)2 , which forces f (2) = 2.

71
NICE Journal NICE Committee (April 2, 2021)

Claim — f ( x ) ≤ x for all x ∈ Z>0 .

Proof. Assume otherwise, that there exists x ∈ Z>0 such that f ( x ) > x. From P( x, 1) and
P( x, 2), we know that x f ( x ) + 2x + 1 and x f ( x ) + 4x + 4 are perfect squares. Therefore, by
letting
x2 + 2x + 1 < x f ( x ) + 2x + 1 = `2 ⇒ ` > x + 1
We have

`2 < x f ( x ) + 4x + 4
= ( x f ( x ) + 2x + 1) + (2x + 3)
= `2 + 2( x + 1) + 1
< `2 + 2` + 1
= (` + 1)2

This is a contradiction.

Claim — f ( p) = p for all primes p.

Proof. P( p, 1) gives us p f ( p) + 2p + 1 = `2 for some ` ∈ Z>0 . Notice that

`2 = p f ( p) + 2p + 1 ≤ p2 + 2p + 1 = ( p + 1)2

Furthermore, p( f ( p) + 2) = (` − 1)(` + 1). This forces ` = p − 1 or ` = p + 1.

• If ` = p − 1, we have
p ( f ( p ) + 2) = p ( p − 2)
forcing f ( p) = ( p − 4). However, we have p f ( p) + 4p + 4 = p2 + 4 being a square,
but for large primes p,
p2 < p2 + 4 < p2 + 2p + 1
which is a contradiction.
• If ` = p + 1, then we conclude that f ( p) = p, which is what we wanted.

Now, fix any natural number x and let p be a prime. We then have

p2 + 2p f ( x ) + x f ( x )

is a perfect square for any prime number p. However, taking p realy large, we could ensure
that
( p + f ( x ) − 1)2 < p2 + 2p f ( x ) + x f ( x ) ≤ ( p + f ( x ))2
Therefore, p2 + 2p f ( x ) + x f ( x ) = ( p + f ( x ))2 , forcing f ( x ) = x for all x ∈ N.
9. By PFD, we have
1 1
1 1
f (x) = = 2 − + 2 .
x ( x + 1)( x + 2) x x+1 x+2
72
NICE Committee (April 2, 2021) NICE Journal

Let’s list a few terms out:

1 1
2 1
f (1) = − + 2,
1 2 3
1 1
2 1
f (2) = − + 2,
2 3 4
1 1
2 1
f (3) = − + 2,
3 4 5
1 1
2 1
f (4) = − + 2,
4 5 6
1 1
2 1
f (5) = − + 2,
5 6 7
..
.
1 1
2 1
f (n) = − + 2 .
n n+1 n+2
The terms with denominators of 3, 4, . . . , n seem to cancel out. Thus, we are left with
1 1 1 1
2 1 1
f (1) + f (2) + f (3) + . . . + f ( n ) = − + 2 + 2 − + 2
1 2 2 n+1 n+1 n+2
1 1 503
= − > ,
4 2(n + 1)(n + 2) 2014
implying
(n + 1)(n + 2) > 2014.
The smallest positive integer n is therefore n = 44 .
10. Consider the following figure:

Z Y

W T X

Center the square on the complex plane with O as the origin, and let y denote the complex
number centered at point Y, etc. This means that Z = iy, W = −y, and X = −iy. Addition-
y w+x −y − iy y y
ally, this means that S = and T = = = − − i. Next we prove that T is
2 2 2 2 2
73
NICE Journal NICE Committee (April 2, 2021)

π
the result when Z is rotated about point S by . The point that is this complex number is
2
 y y y y
eπi/2 (z − s) + s = i iy − + = − − i.
2 2 2 2
Since this is exactly t, our proof is complete.
11. WLOG x ≤ y. We know that since x, y are positive integers, then y2 + 3x > y2 . We also know
that
y2 + 3x ≤ y2 + 3y < y2 + 4y + 4.
By Bounding Lemma, we have y2 + 3x = (y + 1)2 since it is bounded between y2 and
(y + 2)2 . Therefore, we have 3x = 2y + 1. Since x2 + 3y is a square, we must have that
9 3
x2 + x−
2 2
is a square. Now, notice that
9 3
x2 < x2 + x − < ( x + 3)2 .
2 2
Therefore, we must have x2 + 29 x − 3
2 to be equal to ( x + 1)2 or ( x + 2)2 . This gives us
(1, 1), (11, 16), (16, 11) as the solutions.
12 11 n n
12. Essentially, the problem is asking us for ∑11
n=1 ( n )(n−1). Also, note that ( k ) = (n−k ) because
the number of ways to choose k from n is also the number of ways to choose n − k not to
choose. Using this:
11    11   
12 11 12 11
∑ n n − 1 = ∑ n 12 − n .
n =1 n =1
Note that we can directly apply Vandermonde’s Identity here to get:
11     
12 11 23
∑ n 12 − n
=
12
.
n =1

After prime factorizing this, it is easy to see that the sum of the prime numbers that divide N
is 81 .
13. By using the Complex Rotation formula, the complex number in question is
πi
 π π
(3 + 4i )e 3 = (3 + 4i ) cos + i sin
3 3
√ ! √ !
1 i 3

3 √  3 3
= (3 + 4i ) + = −2 3 + +2 i .
2 2 2 2

14. Without loss of generality, assume that the 6 chosen numbers are x1 > x2 > x3 > x4 >
x5 > x6 . As the brick is enclosed in the box, we need the smaller pairs of chosen numbers
to be fully within the larger pairs of chosen numbers. This is actually equivalent to our
parentheses bijection! So, there are C3 ways to choose these 6 numbers in a valid way. We
74
NICE Committee (April 2, 2021) NICE Journal

also have (63) ways to choose the total number of ways, quite simply. Thus, our answer comes
out to be
C3 1
= → 5.
(6) 4
3

15. Let S be the sum in the problem statement. Since all terms in the summation are positive, we
may rearrange terms and swap a ↔ b to get
∞ ∞ ∞ ∞ ∞ ∞
ab(3a + c) ab(3b + c)
S= ∑∑∑ 4a+b+c ( a + b)(b + c)(c + a)
= ∑∑∑ 4a+b+c ( a + b)(b + c)(c + a)
.
b =1 a =1 c =1 a =1 b =1 c =1

Analogous reasoning implies that the sum remains constant when ab(3a + c) is replaced
with any permutation of the variables a, b, and c. Therefore,
∞ ∞ ∞ ∑sym ab(3a + c)
6S = ∑∑∑ a+b+c ( a + b )( b + c )( c + a )
a =1 b =1 c =1 4
∞ ∞ ∞
3( a2 b + ab2 + b2 c + bc2 + c2 a + ca2 ) + 6abc
= ∑∑∑ 4a+b+c ( a + b)(b + c)(c + a)
a =1 b =1 c =1
∞ ∞ ∞
3( a + b)(b + c)(c + a)
= ∑ ∑ ∑ a+b+c
a =1 b =1 c =1 4 ( a + b)(b + c)(c + a)
!3
∞ ∞ ∞ ∞
3 1 1
= ∑ ∑ ∑ a+b+c = 3 ∑ a = .
a =1 b =1 c =1 4 a =1
4 9

1
It follows that S = 54 .

16. Note that

1 1 1
= − .
n ( n + 1) n n+1
Thus, our sum is equivalent to

1 1 1 1 1 1 99
− + − +...+ − = .
1 2 2 3 99 100 100

17. The answer is no . Suppose otherwise, that there exists positive integers a, b such that
xy = a2 and zt = b2 . Therefore,

x + y = z + t = a2 − b2 .

Moreover, both of the following expressions

( x − y)2 = ( x + y)2 − 4xy = ( a2 − b2 )2 − 4a2

(z − t)2 = (z + t)2 − 4zt = ( a2 − b2 )2 − 4b2

are both squares as well since x − y, z − t ∈ Z.

75
NICE Journal NICE Committee (April 2, 2021)

Furthermore, a and b has to be the same parity, or otherwise, WLOG a is odd, then x and y
are both odd, resulting

a ≡ a2 ≡ a2 − b2 = x + y ≡ 0 (mod 2),

which is a contradiction. Therefore, we can WLOG a > b, and let a = m + n and b = m − n

for some positive integers m and n. Now, we need

(4mn)2 − 4(m + n)2 and (4mn)2 − 4(m − n)2

to both be squares. However, if both of them are squares, then their product should be a
square. However,

(4m2 n2 − m2 − n2 − 1)2 < (4m2 n2 − (m + n)2 )(4m2 n2 − (m − n)2 ) < (4m2 n2 − m2 − n2 )2 ,

which is a contradiction.
18. Let z = a + bi, for real a and b. Then z = a − bi. Substituting these into the equation gives
( a + bi ) + 2( a − bi ) = 3a − bi = 6 − 4i. It follows immediately that a = 2 and b = 4, so
z = 2 + 4i .

19. For simplicity, let a = z − 1 and b = z + 1. Note that since |z − a| = |b − z| = 1, z is the

midpoint of the line segment connecting the complex numbers a and b. Furthermore, |z| = 1
as well. Therefore, since the median from the origin to the segment ab has the same length as
the segments it divides ab into, the triangle formed by a, b, and the origin must be a right
triangle, and the origin must be the vertex of the right angle. Therefore, by the Pythagorean
Theorem,
| a|2 + |b|2 = |b − a|2 =⇒ |z − 1|2 + |z + 1|2 = 22 = 4,
as desired.
20. First, we must isolate z. Multiplying both sides of the equation by z + n gives

4ni
z = (z + n)4i =⇒ z(1 − 4i ) = 4ni =⇒ z = .
1 − 4i
The expression for z here is nice and not very ugly. However, there is no way to directly apply
the fact that =(z) = 164 here, and thus we must do some more manipulation. Multiplying
the numerator and denominator by 1 − 4i = 1 + 4i gives

1 + 4i 4ni + 16ni2 −16n + 4ni

 
4ni 16n 4ni
z= = = =− +
1 − 4i 1 + 4i 1 − 16i2 17 17 17
4n
Setting the two different expressions for =(z) equal to each other gives = 164 =⇒ n =
17
697 .
21. If we have n objects in a line, we want to place those k − 1 dividers in such a place that
between each set of dividers, there is at least 1 object.
The trick in this situation is to just “reserve” an object for each category. As the objects are
indistinguishable, we do not have to worry about which object and we can just start and take
k objects and place one into each category. From there, it’s just normal Stars and Bars! Now,
76
NICE Committee (April 2, 2021) NICE Journal

we have n − k indistinguishable objects and k distinguishable categories, and by applying

Stars and Bars, we have
n+1
 
.
k−1

22. Consider the following figure:

E
D

P
C

A B

Translate this diagram to the complex coordinate plane. For this problem, we see an obvious
choice for where to place the origin: since it seems to be the center of most of the activity
of this diagram, set the origin at c. In addition, let ω = eπi/3 . Then d = ωe and b = ωa.
Therefore, since c is the origin, by the definition of midpoint we have

a d ωe e+b e + ωa
n= , m= = , p= = .
2 2 2 2 2
We wish to prove that m is a sixty degree rotation of p about point n. This can be represented
by the equation

m − n = ω ( p − n ), or m = n + ω ( p − n ).
Substituting our expressions for m, n, and p gives

e + ωa a + ωe + (ω 2 − ω ) a
 
a a
n + ω ( p − n) = + ω − = .
2 2 2 2

Note that ω is a sixth root of unity; i.e. ω 6 = 1. However, it is clear that ω 3 6= 1 (since ω
can not be a primitive third root of unity). Therefore ω 3 + 1 = 0. Note also that by sum of
perfect cubes, this factors into (ω + 1)(ω 2 − ω + 1) = 0. But it is obvious that ω can’t equal
−1, so we must have ω 2 − ω + 1 = 0 and ω 2 − ω = −1. We can now finish off the problem:

a + ωe + (ω 2 − ω ) a a + ωe − a ωe
n + ω ( p − n) = = = = m.
2 2 2
77
NICE Journal NICE Committee (April 2, 2021)

Therefore we have proven that m is a sixty degree rotation of p about point n, so it must hold
true that 4 MNP is equilateral.
23. Note that for a given integer, it can appear at most 3 times in the set of triples at indices 1, 2,
and 3. Let’s say that there are k triples; then, by double counting sums, we get

3 · (0 + 1 + · · · + k − 1) ≤ k · n,
2n
which rearranges to k ≤ 3 + 1. Now, we construct based on the cases of n (mod 3).
• Case 1 (n = 3n0 or n = 3n0 + 1): In both cases, we get the bound of k ≤ 2n0 + 1. The
construction for 3n0 is

(0, n0 , 2n0 ), (1, n0 + 1, 2n0 − 2), · · · , (n0 , 2n0 , 0)

(n0 + 1, 0, 2n0 − 1), (n0 + 2, 1, 2n0 − 3), · · · , (2n0 , n0 − 1, 1).

For 3n0 + 1, we can basically just increment everything in the left by 1.

• Case 2 (n = 3n0 − 1): Here, we get the bound of k ≤ 2n0 . The construction here is
similar to the 3n0 case; just remove the (0, n0 , 2n0 ) triplet, and then subtract 1 from every
single leftmost entry.
24. Note that there is a one to one correspondence between strictly increasing sequences of five
positive integers and groups of five distinct positive integers that are chosen. After all, if you
choose five distinct positive integers in the interval, you can order them in an increasing
order and now you have a sequence. There is exactly one valid increasing order for each
group of five distinct positive integers, and thus we have a one-to-one correspondence
(bijection)!
Thus, our answer is the number of ways to choose 5 numbers from 1 to 50 and this comes
out to
 
50
.
5

25. WLOG just assume that all of the variables such as k, x, y refer to positive integer values.
Now, that this is defined, let’s proceed.
Let’s assume that p is the probability that an element of (k, k) is removed and 1 − p is the
probability that an element of (−k, −k) is removed.
Let’s address all of the cases of pairs, which are (k, k), ( a, b), (− a, −b), ( a, −b). We don’t have
to address (−k, −k) because this is the same if we just make it so that k, x, y refer to negative
integer values.
• If we have (k, k), the probability that an element is removed is p.
• If we have ( a, b), the probability that an element is removed is 1 − p2 .
• If we have ( a, −b), the probability that an element is removed is 1 − p(1 − p).
• If we have (− a, −b), the probability that an element is removed is 1 − (1 − p)2 .
Note that 1 − p(1 − p) > p and 1 − (1 − p)2 > p which are both seen obviously when
expanded out. We want the overall probability that a number is erased to be ≥ p so let’s
pick a case where 1 − p2 = p. So, the probability that an element is removed is ≥ p. So, the
78
NICE Committee (April 2, 2021) NICE Journal

expected
√
number of pairs that have a number removed is 68p which using the solution of
p = 52−1 should be between 42 and 43 points. So, this means that there must be a case
where greater than or equal to 43 points are scored.
Let’s now make a construction where the largest possible number of points scored is 43. Let’s
take a setup where we choose 5 instances of each of (1, 1), (2, 2), . . . , (8, 8) and choose all
possible pairs (− a, −b) such that a, b are in 1, 2, . . . , 8. This is a total of 68 pairs. With x as the
number of positive integers erased, there are 5x maximum points possible from the positive
numbers. This means that at most 28 − ( 2x ) negative numbers can be erased. As x is between
0 and 28, the total number of pairs with an erased number is ≤ 43.
As there must be a selection of erased points such that the score is ≥ 43 and there is a
construction where the maximum number of points is 43, this means that 43 is the largest N
such that the student can guarantee to score regardless of which 68 pairs have been written
on the board.
26. Once again, we can tackle this problem using committee forming strategies. If you remember
from one of the earlier exercises, it is true that
   
n n
= .
k n−k
So, this means that it is also true that
   
6 6
= .
a+b 6−a−b
So, instead of the expression given in the problem statement, we can instead deal with the
statement    
6 6 6
.
a b 6−a−b
If you think about it, it’s as if you are trying to pick a committee from the overall group of 18
people where you choose a from one group of 6, b from the second group of 6 and all of the
remaining people from last group of 6. Together, if you vary over all of the valid values of
a and b, you realize that there is a one-to-one correspondence between the product above
and 18 choose the sum of all of the things being chosen in each of the individual binomial
coefficients. In this case, we are looking at (186 ). From here, it is quite simple to compute out
the answer using the closed form we proved earlier.
27. Note that 96 = 3 · 25 . So, we can consider the 3 and the powers of 2 separately. If there are x
different factors in a factorization of 96, there are x ways to choose in which factor the 3 goes.
There must also be a power of 2 in each of the other factors at the very least to ensure that
each factor is strictly greater than 1.
There are now 5 − ( x − 1) = 6 − x powers of 2 remaining and x factors to place them in. The
number of ways to do this can be found with Stars and Bars. This is:
6−x+x−1
   
5
= .
6−x 6−x
So, if 96 is being factored into x factors, there are x (6−5 x ) ways to do this. So, the answer is:
6  
5
∑ x 6 − x = 1 + 10 + 30 + 40 + 25 + 6 = 112 .
x =1
79
NICE Journal NICE Committee (April 2, 2021)

28. Note that this equivalent to the situation in the Number of Paths formula with a and b both
equal to 5. Thus, our answer is:

5+5
 
number of ways = = 252 .
5

 
3 3
S0
29. Let be the set of points of the form + i z, where z ∈ S. First note that S is a square
4 4
of side length 2 centered at the origin. Now let’s see what happens when we multiply
3 3 3 3 3 3√
any complex number in S by + i. Note that + i = |1 + i | = 2 and that
  4 4 4  4  4 4
3 3 π 3 3
arg + i = . Therefore, the complex number + i z is equivalent to z being
4 4 4 4 4
3√
rotated 45◦ clockwise about the origin, followed by a dilation of 2. Both rotations and
4
dilations preserve similar figures, so S0 is a square√ with a different orientation than S0 . Finally,
since the length of a diagonal of square S is 2 2, the length of a diagonal of square S0 is
√ 3√
 
(2 2) 2 = 3. This gives us the picture shown below.
4

S0
S

Now all we need to do is to determine the probability that a point randomly picked in S0 also
lies in S. This is not hard. Since the figure is symmetrical with respect to all four quadrants
of the Argand plane, it suffices to reduce the problem to when z is located within the first
quadrant. Note that after some rote computations, we find that squares S and S0 intersect at
1 1
the points 1 + i and + i. This means that the portion of S0 not inside S consists of two
2 2
80
NICE Committee (April 2, 2021) NICE Journal

 2
1 1/2 1
right isosceles triangles with side length . These right triangles are each = the
2 3/2 9
 
1 7
size of our sample space, so the probabilty is 1 − 2 = .
9 9
30. By the Triangle Inequality, we have
|2 + z| + |1 + 4i − z| ≥ |(2 + z) + (1 + 4i − z)| = |3 + 4i | = 5.
Equality holds when z = 1 + 4i.
31. Let’s first start by defining the ways that we will refer to beams for the sake of making this
proof easier to understand. As there are 3 orientations in which beams can be placed, refer to
the three orientations as the a, b, and c orientations. Also, let a slice refer to a 1 · 2020 · 2020
rectangular prism that is part of the cube such that beams can be placed inside of it.

Claim — The smallest positive number of beams that can be placed to satisfy these
conditions is 3030.

Proof. Let’s start by proving that the number of beams used in each setup is ≥ 3030 and then
state the construction after. There are two cases we have to look at:
(a) beams of only 1 orientation are used, and
(b) beams of > 1 orientation are used.
The first case is quite obvious. WLOG, assume that we take an arbitrary a beam. Note that
this means there must also be an a beam next to it in all of the adjacent slices. Continue
inducting outward from this a beam. Eventually, there must be an a beam in every single
possible space. So, the minimum number of beams that can be placed to satisfy the conditions
if only one orientation is used is 20202 , which is clearly ≥ 3030.
Now let’s deal with the second case. Take an arbitrary a beam. Let’s only address the slices
to the left and right of it that are directly adjacent to it. Note that there must be a beam in
each of these slices, and so on for each of the beams placed in these slices. It follows that
every slice in that orientation must have at least one beam in it. We can do the same thing for
b and c beams to prove that every single slice must have at least one beam in it. Note that
every single beam is in exactly 2 slices. If X is the number of beams in a valid construction,
we have:
2X ≥ 6060 → X ≥ 3030.
Now that we’ve shown that in each case the number of beams in a construction must be
≥ 3030, it just suffices to give a construction. Note that there is a construction in which
in each orientation, one beam is placed at every other spot along a diagonal. Since each
diagonal has length 2020 and we are placing a beam at every other, the total number of
beams in this construction is 3 · 2020
2 = 3030.

32. For n = 1, 2n + 12n + 2011n = 452 . Now, if n > 1. Notice that

2n + 12n + 2011n ≡ (−1)n (mod 4)
Therefore, n has to be even. Let n = 2n0 . But this gives us
(2011n0 )2 < 22n0 + 122n0 + 20112n0 < (2011n0 + 1)2
if n0 ≥ 1. Therefore, the only solution is n = 1.
81
NICE Journal NICE Committee (April 2, 2021)

33. Checking x ≤ 4 by hand, we get that x = 3 satisfies the requirement. We’ll now prove that
it is the only solution. First of all, we claim that x has to be odd. Suppose otherwise, then x is
even, forcing 2 | x3 − 2, and since x3 − 2 is a perfect square, then 4 | x3 − 2. However, 4 | x3 .
This forces 4 | 2, which is a contradiction.
Notice that 2
x+1

( x + 1)( x3 − 2) = x4 + x3 − 2x − 2 < x2 +
2
and 2
x−1

( x + 1)( x3 − 2) = x4 + x3 − 2x − 2 > x2 +
2
which is true for all x ≥ 5. Therefore, we conclude that ( x + 1)( x3 − 2) can’t be a square
when x ≥ 5, and hence x = 3 is the only solution.
34. Let z = 4 + ai and w = b + 13i. Then z + w = (4 + b) + ( a + 13)i, so
q
|z + w| = (4 + b)2 + ( a + 13)2 = 25.

Since we are given that z and w are Gaussian integers, 4 + b and a + 13 are both integers, and
so (4 + b, a + 13, 25) is a Pythagorean Triple. Checking, we find that the only Pythagorean
triples with hypotenuse 25 are (7, 24, 25) and (15, 20, 25). Now, we handle the four possible
cases separately.
• If 4 + b = 15 and a + 13 = 20, then ( a, b) = (7, 11).
• If 4 + b = 20 and a + 13 = 15, then ( a, b) = (2, 16).
• If 4 + b = 7 and a + 13 = 24, then ( a, b) = (11, 3).
• If 4 + b = 24 and a + 13 = 7, then ( a, b) = (−6, 20). However, this case fails since z no
longer falls in the first quadrant.

Therefore, we have that there are 3 possible ordered pairs (z, w): (4 + 7i, 11 + 13i ), (4 +
2i, 16 + 13i ), (4 + 11i, 3 + 13i ).
35. Note that
n n n
d 1 d 2 + d 2 d 3 + . . . + d k −1 d k < n · + · +...,
2 2 3
and factoring out n2 from the RHS gives us
 
1 1
+ + . . . n2 ,
1·2 2·3

which we know is equivalent to n2 as desired.

Note that when n is prime, we must have n = d1 d2 , and so the expression divides n2 . When
n is not prime, let p be the smallest prime dividing n. Then

n2
d 1 d 2 + d 2 d 3 + . . . + d k −1 d k > d k d k −1 = ,
p

n2
and since p must be larger than dk−1 , but less than n2 , the expression will never divide n2 .
82
NICE Committee (April 2, 2021) NICE Journal

36. Just before we start, let’s get a diagram so that we can easily visualize what is going on:

The standard way to deal with these types of problems is to use the idea of complementary
counting, where you first find the number of total ways (both good and bad) and then
subtract out the bad ones. From the generic example, we know that the total number of ways
is equal to 252. However, we now need to find the number of paths that go from (0, 0) to
(5, 5) while passing through (3, 3) so that we can subtract them out.
Note that this is equal to the number of ways to go from (0, 0) to (3, 3) multiplied by the
number of ways to go from (3, 3) to (5, 5) as you can choose a way to go from (0, 0) to
(3, 3) and then multiply that by the number of choices of ways to finish the path from there.
Applying the Number of Paths formula yields:
   
6 4
number of “bad” paths = · = 120.
3 2

Note that we can generate the second binomial coefficient because we can simply shift the
origin from the Number of Paths formula to the point that we need it to be at. Now, we can
just finish off the problem by subtracting the number of bad ways from the total number of
ways and we get:

number of successful paths = 252 − 120 = 132 .

37. Note that because we have 6 letters, we know that if we were to simply reorder these
assuming that all of the letters were distinct, we would have 6! = 720 permutations. However,
we have a duplicate of the letter D, so it is not that simple. To account for the duplicate, the
idea is to divide by 2!, because we have to divide out all possible orderings of the D’s. So,
this comes out to
720
= 360 .
2

38. Note that by using our Complex Times Conjugate formula we have

|z − 1|2 = (z − 1)(z − 1) = (z − 1)(z − 1)

= zz − z − z + 1 = |z|2 − z − z + 1 = 2 − z − z
and
|z + 1|2 = (z + 1)(z + 1) = (z + 1)(z + 1)
83
NICE Journal NICE Committee (April 2, 2021)

= zz + z + z + 1 = |z|2 + z + z + 1 = 2 + z + z.
Therefore
|z − 1|2 + |z + 1|2 = (2 − z − z) + (2 + z + z) = 4,
as desired.
39. Let f ( x ) = 1 − x + x2 − x3 + · · · + x16 − x17 . Note that f ( x ) = (−1)k ( x + 1 − 1)k =
(−1)k (y − 1)k = (1 − y)k . By the Binomial Theorem, the coefficient of the y a term must be
(2a) for a ≥ 2. For a = 0, 1, the coefficients are 1 and −1 so they cancel out, meaning we don’t
have to worry about them. So, our answer is equal to:
17      
i 2 17
∑ 2 =
2
+ · · · +
2
.
i =2

By the Hockey-Stick Identity, this must be equal to (18

3 ) = 816 .
40. Note that we have:
             
37 37 37 37 38 38 39
+ + + = + = .
7 8 8 9 8 9 9

π 3π π
41. If z3 is to be purely imaginary, then arg(z3 ) must be either or . If arg(z3 ) = , then by
2 2 2
π π
our recently proven theorem, we have 3 arg(z) = =⇒ arg(z) = . But is that the only
2 6
π 5π 9π
possible value for arg(z)? No! In fact, on the complex plane, is the same angle as , ,
2 2 2
5π 3π
and so on. This gives more possible values for arg(z) : and . After this, the values for
6 2
3π
arg(z) will start to repeat themselves. Similarly, analyzing arg(z3 ) = gives three more
2
π 7π 11π
values of arg(z): , , and . Therefore the set of all numbers for which z3 is purely
2 6 6
imaginary is the set of complex numbers z such that
 
π π 5π 7π 3π 11π
arg(z) ∈ , , , , , .
6 2 6 6 2 6

42. Multiplying both sides of the given equation by (s − p)(s − q)(s − r ), we get

1 = A(s − q)(s − r ) + B(s − r )(s − p) + C (s − p)(s − q).

Plugging in s = p, gives us
1
= ( p − q)( p − r ).
A
Similarly,
1
= (q − r )(q − p),
B
1
= (r − p)(r − q).
C
84
NICE Committee (April 2, 2021) NICE Journal

Summing these 3 equations, we get

1 1 1
+ + = p2 + q2 + r2 − pq − qr − pr = ( p + q + r )2 − 3( pq + qr + pr ) = 244
A B C
by Vieta’s.

85