Engineering

Carl Joshua Quines

March 29, 2020

1 What is engineering?
Engineering is finding the answer to a problem without solving it. It’s the
art of solving without solving, of finding the answer with less effort than it would take
us if we did the problem “properly”. The following techniques are engineering:
• Engineer’s induction: finding the answer for some cases, then generalizing.
• Carefully drawing a diagram and measuring the answer.
• Using extra degrees of freedom to find a numerical answer.
• Substituting choices of a multiple-choice problem to solve it.
• Using the answer format to assist in any of the above techniques.

Example 1.1 (PMO 2019 Qualifying III.4). In triangle ABC, D and E are points on
sides AB and AC respectively, such that BE is perpendicular to CD. Let X be a point
inside the triangle such that ∠XBC = ∠EBA and ∠XCB = ∠DCA. If ∠A = 54◦ ,
what is the measure of ∠EXD?

It’s possible to carefully draw a diagram and then measure it to get the answer.
You’ll get a measurement of about 35◦ . The nearest angle that’s a nice angle would
be 36◦ , which just happens to be 90◦ − 54◦ , so we guess 36◦ and move on. This is
engineering, but it’s risky.
Instead, here’s some better engineering: abuse degrees of freedom. The answer is
a number, so it must be the same no matter where the points are positioned. Knowing
this, we take the special case when D is very very close to A.

D Y

B C

Then E would be very close the foot of the perpendicular from B to AC, and X
would be very close to B. Then ∠EXD would be about ∠EBA. But triangle EBA is
right, so ∠EBA = 90◦ − ∠EAB = 36◦ , which is indeed the correct answer.
Engineering Carl Joshua Quines

Some important philosophical notes. I think engineering is a useful skill. It leads to

making exciting conjectures, and involves things like estimation that are important
outside of competitions. There are certainly lots of people who should use it more,
but I also think that there are people who should use it less.
Engineering is not a replacement for learning math. It shouldn’t be satisfying
to get an answer with engineering. Engineering a problem is like taking out a loan,
that you need to repay with learning the actual solution to the problem.
With that in mind, I think engineering is a skill that’s best learned when
you’re more experienced with math, rather than something you learn when you’re
starting out. Intuition is something that you need when engineering anyway, as I’ll
emphasize throughout the article, and intuition is something you pick up over time.
This handout can do more harm than good, and don’t say I didn’t warn you.

2 Engineer’s induction
Engineering takes its name from engineer’s induction, which is the primary engineering
technique. In its simplest form, engineer’s induction is about guessing the formula for
a sequence, and then convincing yourself that it’s true based on some small cases. So
the simplest kind of engineer’s induction is used in problems where there’s a sequence,
and you have to guess the formula:

Example 2.1 (PUMaC Algebra A 2018/2). If a1 , a2 , . . . is a sequence of real numbers

n  2
X k 1
such that for all n, ak = 1, find the smallest n such that an < .
n 2018
k=1

We find the first few terms. Substituting n = 1, we get

 2
1
a1 = 1 =⇒ a1 = 1.
1
Then substituting n = 2 gives
 2  2
1 2 3
a1 + a2 = 1 =⇒ a2 = .
2 2 4
We finally substitute n = 3 to get
 2  2  2
1 2 3 5
a1 + a2 + a3 = 1 =⇒ a3 = .
3 3 3 9
Looking at the numerators, we have 1, 3, 5, which looks like the odd numbers. Looking
at the denominators, we have 1, 4, 9, which looks like the perfect squares. So we would
guess that the formula is
2n − 1
an = .
n2
In this case, it’s not hard to prove the formula through actual induction. (If you don’t
immediately see how to do this, you should stop reading this handout.) From having
written lots of inductions before, we see why this is true, and that’s what engineer’s
induction is about—convincing yourself that something is true using examples, rather
than a proof.
2
Engineering Carl Joshua Quines

Exercise 2.2. We could always check another case to be sure. Do something similar to
what we did to find a4 , and verify that it matches our guess for the formula.

To finish the rest of the problem, we need the least n such that
2n − 1 1
2
< .
n 2018
2n 2
The fraction is approximately 2
, or . In this case, n = 4036 would make the fraction
n n
1
equal to 2018 . But 2n is larger than 2n − 1, so the actual fraction would be smaller.
1
So a4036 is indeed smaller than 2018 .
Is the answer 4035? Let’s check whether n = 4035 would make the fraction smaller
1
than 2018 . Here, let’s replace 2018 with n+12 :

2n − 1 1
? n+1 ⇐⇒ (2n − 1)(n + 1) ? 2n2 ,
n2 2

1
The left-hand side is larger than the right-hand side, so a4035 > 2018 . So a4035 is larger,
1
which means that a4036 is the first term smaller than 2018 , and the answer is 4036.

Exercises
Problem 2.3 (AMC 12A 2019/9). A sequence of numbers is defined by a1 = 1, a2 = 73 , and
an−2 · an−1
an =
2an−2 − an−1
p
for all n ≥ 3. Then a2019 can be written as q, where p and q are relatively prime positive
integers. What is p + q?
Problem 2.4 (ARML Team 2017/6). Let {an } be a sequence with a0 = 1, and for all n > 0,
n−1
1X
an = ai .
2 i=0

Compute the greatest value of n for which an < 2017. Hint: 9

2.1 Trying small cases

Engineer’s induction can also be applied even if the problem doesn’t have a sequence.
In this case, the sequence is made by trying small cases of the problem, guessing the
formula, and then applying it to the original problem. Here’s an example:

Example 2.5 (OMO Spring 2018/5). A mouse has a wheel of cheese which is cut into
2018 slices. The mouse also has a 2019-sided die, with faces labeled 0, 1, 2, . . . , 2018,
and with each face equally likely to come up. Every second, the mouse rolls the dice.
If the dice lands on k, and the mouse has at least k slices of cheese remaining, then
the mouse eats k slices of cheese; otherwise, the mouse does nothing. What is the
expected number of seconds until all the cheese is gone?

3
Engineering Carl Joshua Quines

The 2018 here is probably an arbitrary choice, and it’s asking us to replace it with
a smaller number. Let’s let this number be n, and we’re trying to look for the answer
in terms of n. That is, we have this new, restated problem:

Example 2.6. A mouse has a wheel of cheese which is cut into n slices. The mouse
also has a n + 1-sided die, with faces labeled 0, 1, 2, . . . , n, and with each face equally
likely to come up. Every second, the mouse rolls the dice. If the dice lands on k, and
the mouse has at least k slices of cheese remaining, then the mouse eats k slices of
cheese; otherwise, the mouse does nothing. What is the expected number of seconds
until all the cheese is gone?

Let’s call the answer to this problem Sn . We’re looking for S2018 . We will try to
guess the formula for Sn by finding it for small values of n.
When n = 1, then the die only has two faces, 0 and 1. It takes exactly s seconds
until all of the cheese is gone only if the first s − 1 rolls are all 0s, and the sth roll is 1.
1
This happens with probability s . So the expected number of seconds is
2
1 1 1
S1 = 1 · 1 + 2 · 2 + 3 · 3 + · · · .
2 2 2
1
To calculate this, we multiply both sides by 2 and subtract it from S1 , giving us
S1 1 1 1
= 1 · 2 + 2 · 3 + 3 · 4 + ···
2 2 2 2
S1 1 1 1
S1 − = 1 · 1 + (2 − 1) 2 + (3 − 2) 3 + · · ·
2 2 2 2
1
S1
= 2 1 = 1,
2 1− 2
which means that S1 = 2.
When n = 2, the problem is slightly harder, but it’s still doable. When does it take
exactly s seconds for all of the cheese to be eaten? Either:
• Both slices are eaten at the same time, which happens if the first s − 1 rolls are
1
0 and the sth roll is 2. This happens with probability s .
3
• The slices are eaten one at a time. There’s some number t such that the first
t − 1 rolls are 0, and then the tth roll is 1. Then the next s − t − 1 rolls can be
0 or 2, and the sth roll is 1 again. As t can be anything from 1 to s − 1, this
happens with probability
   s−2    2  s−3    s−1  
1 2 1 1 2 1 1 1 2s−1 − 1
+ + ··· + = .
3 3 3 3 3 3 3 3 3s
We can compute this series by noticing that the denominators are all 3s , while
the numerators form a geometric series.
In total, the probability that it takes exactly s seconds for all the cheese to be eaten is
2s−1
. To compute the expected number of seconds, we do a similar trick on
3s
20 21 22
S2 = 1 · + 2 · + 3 · + ··· .
31 32 33
4
Engineering Carl Joshua Quines

We multiply the whole series by 23 and then subtract it from the original series. This
allows us to solve for S2 = 3.
So these two answers allow us to make a “sequence” of answers for different n. The
sequence Sn begins as 2, 3. A good guess for the formula would be Sn = n + 1, which
means that we’d guess S2018 = 2019.
If we really wanted to be sure, we could find S3 . However, it’s already getting a
bit tedious at this point, since we have four cases. Instead, we can guess that the
3s−1
probability that it takes exactly s seconds for all of the cheese to be eaten is s .
4

Exercise 2.7. Let’s try to find S3 without going through all four cases.
3s−1
(a) We guess it takes exactly s seconds for all of the cheese to be eaten is .
4s
Verify that this is true for s = 1 and s = 2. The fact that we have a simple
formula, and that it’s true for s = 1 and s = 2, should make us believe that the
formula is true in general.

(b) Using a similar technique to what we did earlier, check that the sum

30 31 32
S3 = 1 · + 2 · + 3 · + ···
41 42 43
is indeed equal to 4.

At this point, we’ve seen that Sn = n + 1 for n = 1, 2, 3, so we should be pretty

confident that S2018 = 2019. And this is indeed the correct answer!
Think about this problem. The way we found the answer involved a lot of computa-
tion, but very few tricks were used in our technique. Solutions that use states
require knowing how to set up recursions, and the short intended solution is not easy
to come up with. Engineer’s induction may not always give the answer in a fast or
elegant way, but it’s often a method that requires knowing the least tricks.
Here’s a different kind of example, taken from the example in the previous section:

Example 2.8. Find the least positive integer n such that

2n − 1 1
2
< .
n 2018

Again, 2018 is an arbitrary number, so let’s replace it with small numbers and try
to guess the general answer. When we replace it with 1, we get
2n − 1
< 1,
n2
and the least n that works is 2. When we replace it with 2, we get
2n − 1 1
< ,
n2 2
and the least n that works is 4. And when we replace it with 3, we find that the least
n that works is 6. It always looks to be double the number we’re replacing. So we
would guess that in the original problem, with 2018, the least n that works is 4036,
which is correct.
5
Engineering Carl Joshua Quines

Exercises
Problem 2.9 (PUMaC Combinatorics A 2017/3). There is a box containing 100 balls, each of
which is either orange or black. The box is equally likely to contain any number of black balls
between 0 and 100, inclusive. A random black ball rolls out of the box. The probability that
the next ball to roll out of the box is also black can be written in the form pq where p and q
are relatively prime positive integers. Find p + q.
Problem 2.10 (PUMaC Combinatorics A 2016/4). A knight is placed at the origin of the
Cartesian plane. Each turn, the knight moves in an L-shape (2 units parallel to one axis and 1
unit parallel to the other) to one of eight posisble locations, chosen at random. After 2016 such
turns, what is the expected value of the square of the distance of the knight from the origin?
Problem 2.11 (HMMT Guts 2017/20). For positive integers a and N , let r(a, N ), a number
in {0, 1, . . . , N − 1} denote the remainder of a when divided by N . Determine the number of
positive integers n ≤ 1000000 for which r(n, 1000) > r(n, 1001). Hint: 13

2.1.1 Be fooled not by small numbers

Here’s one important consideration when considering when to apply engineer’s induc-
tion. We might only reach for it when the numbers in the problem are large, like
the current year, or 1000 or something. But sometimes, engineer’s induction can be
useful for small numbers too, and we shouldn’t dismiss using it just because the given
numbers are small. We can always make small numbers smaller.

Example 2.12. Eight points are equally spaced on a unit circle. What is the product
of the distances from one point to each other point?

Here, instead of tackling the problem directly, we use engineer’s induction, replacing
eight with smaller numbers:

• If there are only two points, then there is only one distance, 2, so the answer is 2.

• If there are three points, then this forms an equilateral triangle with height 32 ,
√
and by constructing
√ √a 30-60-90 triangle, we see that it must have side length 3.
So the answer is 3 · 3, which is 3.

• If there are four points, then this forms a square. The diagonal is 2, and by
drawing both
√ diagonals, we form √ a 45-45-90
√ triangle, which gives us the side
length of 2. Then the answer is 2 · 2 · 2, or 4.

This strongly suggests that for eight points, the answer is 8. We can further check this
by checking the case of the hexagon:

Exercise 2.13. Check that the answer is 6 for a regular hexagon as well. (Two of the
distances are part of an equilateral triangle, so we’ve done most of the work.)

And 8 is indeed the correct answer, which we found through a much simpler technique
than the intended solution of using complex numbers or trigonometry.

6
Engineering Carl Joshua Quines

Exercises
Problem 2.14 (PMO 2017 Areas I.18). A railway passes through four towns A, B, C, and D,
in that order. The railway forms a complete loop and trains go in both directions. Suppose
that a trip between two adjacent towns costs one ticket. Using exactly eight tickets, how many
distinct ways are there of travelling from town A and ending at town A? (Note that passing
through A somewhere in the middle of the trip is allowed.)
Problem 2.15 (OMO Spring 2014/9). Eighteen students participate in a team selection test
with three problems, each worth up to seven points. All scores are nonnegative integers. After
the competition, the results are posted by Evan in a table with 3 columns: the student’s
name, score, and rank (allowing ties), respectively. Here, a student’s rank is one greater
than the number of students with strictly higher scores (for example, if seven students score
0, 0, 7, 8, 8, 14, 21 then their ranks would be 6, 6, 5, 3, 3, 2, 1 respectively).
When Richard comes by to read the results, he accidentally reads the rank column as
the score column and vice versa. Coincidentally, the results still made sense! If the scores
of the students were x1 ≤ x2 ≤ · · · ≤ x18 , determine the number of possible values the
18-tuple (x1 , x2 , . . . , x18 ). In other words, determine the number of possible multisets (sets
with repetition) of scores.
Problem 2.16 (PUMAC Algebra B 2014/5). Given that

an an−2 − a2n−1 + an − nan−2 = −n2 + 3n − 1

and a0 = 1, a1 = 3, find a20 . Hint: 14

Problem 2.17 (HMMT Algebra 2013/7). Compute
∞ X
∞ ∞
X X a1 + a2 + · · · + a7
··· .
a1 =0 a2 =0 a =0
3a1 +a2 +···+a7
7

2.2 Choosing what to induct on

Another thing to think about when doing engineer’s induction is how exactly we
induct. What exactly do we change? How exactly are we going to make the sequence?
Sometimes it’s clear, but sometimes need to be more creative:

62  
X 2014
Example 2.18 (AMC 12B 2014/23). The number 2017 is prime. Let S = .
k
k=0
What is the remainder when S is divided by 2017?

Here, there are several choices of what to try. We can see that 2014 and 2017 are
related, so we might consider replacing the two numbers, with something like 4 and
7. But then, how are both numbers related to 62? Indeed, the number that we want
to change isn’t 2014 and 2017, but the 62. Since it doesn’t really matter, we should
consider what happens when we let it
vary.
In particular, let’s try finding 2014
k modulo 2017 for small values of k:
• When k = 0, it’s just 1.
• When k = 1, it’s 2014, which would be nicer if we wrote it as −3.
• When k = 2, it’s
2014 · 2013 (−3)(−4)
≡ ≡ 6.
2 2
7
Engineering Carl Joshua Quines

At this point I’d say that the pattern is strong enough to guess: 1, −3, 6 are the
triangular numbers, except that the signs alternate.

Exercise 2.19. Verify that the pattern continues for k = 3 by using the same trick;
you should get −10.

We find the sums of the first few terms, and we get 1, −2, 4, −6, 9. We can then guess
the positive terms are the perfect squares, so the sum from k = 0 to k = 62 would give
322 , or 1024.

Exercises
Problem 2.20 (AMC 12A 2014/16). The product (8)(888 . . . 8), where the second factor has k
digits, is an integer whose digits have a sum of 1000. What is k?
Problem 2.21 (AIME I 2018/1). Let S be the number of ordered pairs of integers (a, b) with
1 ≤ a ≤ 100 and b ≥ 0 such that the polynomial x2 + ax + b can be factored into the product
of two (not necessarily distinct) linear factors with integer coefficients. Find the remainder
when S is divided by 1000.
1
Problem 2.22 (AMC 12A 2014/23). The fraction 2 = [Link]−1 bn−2 . . . b2 b1 b0 , where n is the
99
length of the period of the repeating decimal expansion. What is the sum b0 + b1 + · · · + bn−1 ?
Hint: 7

2.2.1 Two free variables

Sometimes, we may want to have two free variables instead of just one. This is slightly
harder than only one free variable, because there are way, way more possible formulas.
One of the tricks is to only change one variable at a time.

Example 2.23 (HMMT Combinatorics 2017/6). Emily starts with an empty bucket.
Every second, she either adds a stone or removes a stone from the bucket, each with
probability 12 . If she wants to remove a stone from the bucket and the bucket is
currently empty, she does nothing for that second (still with probability 12 ). What is
the probability that after 2017 seconds her bucket contains exactly 1337 stones?

Here, we have two clear numbers that we want to do engineer’s induction on, 2017
and 1337. Let’s call the number of seconds s. We can just find the answer for all small
s, since there are only a limited number of possible stones. When s = 1, we have 0
stones or 1 stone with probability 12 .
In the former case, half the time we get 0 stones and half the time we get 1 stone.
In the latter case, half the time we get 0 stones and the other half we get 2 stones. So
in total, for s = 2, we have 0 stones with probability 24 , 1 stone with 14 , and 2 stones
with 14 .
Again, we can use these numbers to find the results for s = 3. It’s 0 stones with
probability 38 , 1 stone with 38 , 2 stones with 18 , and 3 stones with 18 . Now the numerators,
3, 3, 1, 1, are familiar—they’re the binomial coefficients of the form x3 !

8
Engineering Carl Joshua Quines

Exercise 2.24. Verify that for s = 4, the probabilities for getting 0, 1, . . . , 5 stones are
6 4 4 1 1
, , , , .
24 24 24 24 24
Can you guess the formula for the probability of having x stones after s seconds?

2017


340
From here, we see that the answer should be .
22017

Exercises
Problem 2.25 (SMT Discrete 2018/7). Let S be the set of all 1000 element subsets of the
set {1, 2, 3, . . . 2018}. What is the expected value of the minimum element of a set chosen
uniformly at random from S?
Problem 2.26 (HMMT Guts 2019/18). 2019 points are chosen independently and uniformly at
random on the interval [0, 1]. Tairitsu picks 1000 of them randomly and colors them black,
leaving the remaining ones white. Hikari then computes the sum of the positions of the leftmost
white point and the rightmost black point. What is the probability that this sum is at most 1?
Problem 2.27 (HMMT Combinatorics 2013/9). Given a permutation σ of {1, 2, . . . , 2013}, let
f (σ) be the number of fixed points of σ – that is, the number of k ∈ {1, 2, . . . , 2013} such that
σ(k) = k. If S is the set of all possible permutations σ, compute
X
f (s)4 .
σ∈S

(A permutation σ is a bijective mapping from {1, 2, . . . , 2013} to {1, 2, . . . , 2013}.) Hint: 4

2.2.2 Trigonometric sums and products

This is a particular kind of engineer’s induction that I’ve seen often enough that it
gets its own section. The key idea that I want to emphasize is that degrees are
arbitrary, and that every time you see a trigonometric sum or product with degrees,
you should be thinking about using engineer’s induction.

Example 2.28 (Titu). Evaluate

1 3 9 27
+ + + .
cot 9◦ − 3 tan 9 ◦ ◦
cot 27 − 3 tan 27 ◦ ◦
cot 81 − 3 tan 81 ◦ cot 243 − 3 tan 243◦
◦

First, we recognize that the degrees are arbitrary, and probably the only important
part is that it triples each time. Replace 9◦ with x to get
1 3 9 27
+ + + .
cot x − 3 tan x cot 3x − 3 tan 3x cot 9x − 3 tan 9x cot 27x − 3 tan 27x
Now we can try different values of x and see what we get. Convenient ones to try are
x = 45◦ and x = 135◦ . Let’s try the first one. This gives us
1 3 9 27 −1 + 3 − 9 + 27
+ + + = = 10.
1 − 3 −1 + 3 1 − 3 −1 + 3 2
Similarly, check that if we try x = 135◦ , we get −10.
9
Engineering Carl Joshua Quines

Now, we know the answer should depend on x in some way, most likely tan x or
cot x. Can it be something like 10 (tan x)2 ? If it was, then the answer for x = 45◦ and
x = 135◦ would be the same, but it isn’t.
So we expect it to be in terms of either tan x or cot x. The nicest option would be
either something like 10 tan x or 10 cot x, which matches what we have. What we’ve
done so far can’t distinguish between the two of them, but we can use size to figure
out which one:

Exercise 2.29. Say that x was very small. Then tan x would be very small, and cot x
would be very large. Convince yourself that, in this case, the sum is closer to 10 tan x
than it is to 10 cot x.

So we have a good guess of 10 tan x. What we’d really like is if we had another x to
try it on. Unfortunately, neither 0 nor 30◦ nor 60◦ give anything defined. Instead, we
can use 15◦ .
√
Exercise 2.30. Recall (or derive) that tan 15◦ = 2 − 3. Then check that for x = 15◦ ,
the above sum really is 10 tan x.

And indeed, the answer really is 10 tan 9◦ . In short-answer type contests, the answer
format is typically given, which makes things a bit easier:

Example 2.31 (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◦

The denominators form this arithmetic sequence 45◦ , 46◦ , . . . , 134◦ , and the next
term would have been 135◦ . Again, the common difference being 1◦ is definitely
arbitrary—the important facts seem to be that it starts with 45◦ , ends with 135◦ , and
has an odd number of terms. And also, the n◦ on the right-hand side is probably just
n times the common difference.
If the sum had only one term, the sequence would be 45◦ , 90◦ , 135◦ . And then the
sum would be
1 1
◦ ◦
= =⇒ n = 1.
sin 45 sin 90 sin 45n◦
If we were unsure, we could see what would happen if the sum had more terms. One
choice would be the sequence 45◦ , 60◦ , 75◦ , 90◦ , 105◦ , 120◦ , 135◦ , which would give us
the sum
1 1 1 1
◦ ◦
+ ◦ ◦
+ ◦ ◦
=
sin 45 sin 60 sin 75 sin 90 sin 105 120 sin 15n◦

Exercise 2.32. Evaluate the above sum, and show that n = 1 here as well. It may be
easier to note that sin 75◦ = sin 105◦ = cos 15◦
√ , not evaluate these until the end, and
◦
then use the earlier fact that tan 15 = 2 − 3.

10
Engineering Carl Joshua Quines

Again, if we really wanted to be sure, we can also check it for when the sum has two
terms. But at this point we should be pretty confident that the answer is just 1, which
is correct.

Exercises
 π     
2π 2019π
Problem 2.33. Find the value of sin sin · · · sin .
2020 2020 2020
Problem 2.34 (HMMT February Guts 2018/17). Find the value of

cos 30.5◦ + cos 31.5◦ + · · · + cos 44.5◦

.
sin 30.5◦ + sin 31.5◦ + · · · + sin 44.5◦
45
Y
Problem 2.35 (AIME I 2015/13). The product csc2 (2k − 1)◦ = mn , where m and n are
k=1
integers greater than 1. Find m + n.
2018  
X 1009 − k
Problem 2.36 (Sipnayan 2018 SHS SF A VD 5). Evaluate arcsin . Recall that
2018
h π πi k=1
arcsin(x) returns a value in the range − , radians. Give your answer in radians.
2 2

2.3 Sequence guessing skills

The other component of doing engineer’s induction effectively is being able to recognize
sequences when they come up. There are a couple sequences that come a lot. For
many common sequences, the first three terms should give an instinctive
guess. For example:
• 1, 1, 2 are the Fibonacci numbers.
• 1, 2, 4 are the powers of two.
• 1, 2, 6 are the factorials.
• 1, 3, 5 are the odd numbers.
• 1, 3, 6 are the triangular numbers.
• 1, 4, 9 are the perfect squares.
Sequences like these should be pretty immediate, although if you see them, do a
sanity check to make sure that it makes sense. Other sequences that should be clear
after three terms are arithmetic sequences and geometric sequences. For everything
else, you may need to do some investigation.

Example 2.37. What is the next term in the following sequence: 1, 2, 4, 10, 26, . . .?

First, we take the differences, which often helps. Here, it’s 1, 2, 6, 16. These terms
are pretty composite. In particular, note that the nth term here is divisible by n, so
we divide it out. This gives us 1, 1, 2, 4, . . ., which is the original sequence! So this
gives us the recurrence an+1 = an + nan−1 .

11
Engineering Carl Joshua Quines

Exercise 2.38. Guess the next term in each of the following sequences:
• 2, 4, 7, 11, 16, . . .
• 1, 5, 13, 29, 61, . . .
• 1, 3, 11, 43, 171, . . .
• 4, 10, 22, 46, 94, . . .
• 1, 3, 15, 84, 495, . . .
• 1, 2, 6, 20, 70, . . .

Here are a list of tricks to try:

• Taking differences between terms always helps. These can rule out sequences
that are polynomial, because they’ll have the same difference after a while. In
practice, polynomial sequences tend to be either quadratic or cubic, so you should
be able to tell after four or five terms.
To elaborate, consider a sequence like 2, 4, 7, 11, 16. The first differences are
2, 3, 4, 5. Taking the second differences gives

1, 1, 1. Since this is constant, the
n
sequence must be quadratic; indeed it’s 2 + 1. Similarly, if the third differences
are constant, the sequence is cubic.

• The multiplicative version of this is taking ratios of consecutive terms, which

can help you figure out whether the sequence has some exponential component.
Consider a sequence like 1, 5, 13, 29, 61. The ratios are all approximately 2, so
it’s a good idea to compare the sequence to 2n . From here, we can guess the
formula 2n+2 − 3.
Similarly, consider a sequence like 1, 3, 11, 43, 171. Each term looks like it’s about
4 times the previous one. In fact, it’s 4 times the previous term minus 1.

• If all of the terms look “very” composite, try factoring the terms. You might
be able to rule out some exponential component, like if the nth term had 2n as
a factor, or if the nth term had n as a factor.
The other possibility is that all of your terms are binomial coefficients, which
is likely if your terms get “more and more composite” as the sequence goes
on. That is, if the terms seem to get more and more factors. A sequence like
1, 3, 15, 84, 495 is a good candidate. More about this in the next section.

• Finally, if you know that the problem is combinatorial and probably involves
recursion, you can always force a linear recurrence. Four terms are enough
to find any linear recurrence of the form an+1 = xan + yan−1 . Again, more about
this later.

If the sequence does fall in one of the patterns above, you can usually tell it after
three or four terms, maybe five terms. Often, doing the brute force until the fifth term
isn’t too bad, especially if you don’t have an alternative. There isn’t really much else
to talk about this, so here are the problems:

12
Engineering Carl Joshua Quines

Exercises
Problem 2.39 (HMMT Guts 2017/15). Start by writing the integers 1, 2, 4, 6 on the blackboard.
At each step, write the smallest positive integer n that satisfies both of the following properties
on the board.
• n is larger than any integer on the board currently.
• n cannot be written as the sum of 2 distinct integers on the board.
Find the 100th positive integer you write on the board. Recall that at the beginning, there are
already 4 integers on the board.
60 X
k
X n2
Problem 2.40 (HMMT Guts 2018/11). Find the value of . Hint: 11
n=1
61 − 2n
k=1

Problem 2.41 (CMIMC Combinatorics 2018/9). Compute the number of rearrangements

a1 , a2 , . . . , a2018 of the sequence 1, 2, . . . , 2018 such that the inequality ak > k is true for
exactly one value of k.
Problem 2.42 (HMMT Combinatorics 2015/5). For positive integers x, let g(x) be the number
of blocks of consecutive 1’s in the binary expansion of x. For example, g(19) = 2 because
19 = 100112 has a block of one 1 at the beginning and a block of two 1’s at the end, and g(7) = 1
because 7 = 1112 only has a single block of three 1’s. Compute g(1) + g(2) + g(3) + · · · + g(256).
Problem 2.43 (HMMT Guts 2010/15). Pick a random integer between 0 and 4095, inclusive.
Write it in base 2 (without any leading zeroes). What is the expected number of consecutive
digits that are not the same (that is, the expected number of occurrences of either 01 or 10 in
the base 2 representation)?

2.3.1 Binomial coefficients

As mentioned in the previous section, if the terms have a lot of factors, they
may be binomial coefficients. This should be especially true if you know it’s a
combinatorics problem and the answer could involve binomial coefficients. In these
cases, it’s helpful to draw out the first few rows of Pascal’s triangle and start looking.
Here’s a simple example:

Example 2.44 (PMO 2020 Areas I.4). Determine the number of ordered quadruples
(a, b, c, d) of odd positive integers that satisfy the equation a + b + c + d = 30.

Since the minimum sum is 4, and the sum can only ever be even, we can try replacing
30 with 4, 6, 8, and count.
There’s only 1 solution to a + b + c + d = 4. There are 4 solutions to a + b + c + d = 6,
corresponding to (3, 1, 1, 1) and the 4 ways to arrange it. For a + b + c + d = 8, there’s
(3, 3, 1, 1) which we can arrange in 6 ways, and then (5, 1, 1, 1) which we can arrange
in 4 ways, making a total of 10. So the sequence goes 1, 4, 10. This is already enough
to make a guess!

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
13
Engineering Carl Joshua Quines

Drawing
the
first few
rows of Pascal’s triangle, we can spot 1, 4, 10 as a line going

through 33 , 43 , and 53 . So we’d guess that for a + b + c + d = 2n, the answer should
be n+1


3 . Note that this is also roughly the correct order of magnitude—it’s growing
16


like a cubic polynomial, so it isn’t too slow nor too fast. And indeed, 3 = 560 is the
correct answer for this problem.
f (n)

Usually the pattern is something like f (n)


n , or k for some constant k, up to
shifting. In particular, you wouldn’t expect the pattern to lie only on a single row;
you kind of expect it to lie on a diagonal of Pascal’s triangle.

Exercises
Problem 2.45. How many four-digit numbers ABCD satisfy A ≥ B ≥ C ≥ D? Hint: 6
Problem 2.46 (HMMT Feb Guts 2016/6). Consider a 2 × n grid of points and a path consisting
of 2n − 1 straight line segments connecting all these 2n points, starting from the bottom left
corner and ending at the upper right corner. Such a path is called efficient if each point is
only passed through once and no two line segments intersect. How many efficient paths are
there when n = 2016?
Problem 2.47 (HMMT Combinatorics 2007/9). Let S denote the set of all triples (i, j, k) of
positive integers where i + j + k = 17. Compute
X
ijk.
(i,j,k)∈S

Problem 2.48 (HMMT Guts 2004/34). Find the number of 20-tuples of integers x1 , . . ., x10 ,
y1 , . . ., y10 with the following properties:
• 1 ≤ xi ≤ 10 and 1 ≤ yi ≤ 10 for each i;
• xi ≤ xi+1 for i = 1, . . . , 9;
• if xi = xi+1 then yi ≤ yi+1 .

2.3.2 Linear recurrences

As a last resort, and only as a last resort, if you know that the problem is the kind
of problem where you’re expected to set up a linear recursion and extend it a couple
terms, you could always solve for a linear recurrence that fits.
If there are two “base cases”, then the recurrence is probably of the form an+1 =
xan + yan−1 . Solving for an equation like this requires only four terms. If x and y end
up being integers, and it matches the fifth term, then you’re likely correct. Similarly,
if there are three “bases cases”, then you’ll need six terms to solve for the coefficients,
and a seventh term to check.
This really is only applicable to a few cases. Many problems that look like they
have recursion-ish solutions don’t have linear recurrences as solutions.

Example 2.49 (PMO 2019 Areas I.11). A Vitas word is a string of letters that satisfies
the following conditions:
• It consists of only the letters B, L, R.
• It begins with a B and ends in an L.
• No two consecutive letters are the same.
How many Vitas words are there with 11 letters?

14
Engineering Carl Joshua Quines

Upon reading the problem, it feels like exactly the kind of problem where you’d
expect the answers to form some kind of linear recurrence. How far back would this
linear recurrence be? Since the condition only involves two consecutive letters, it only
really needs to look back by two. So from an+1 , it only “cares” about an and an−1 .
This means we’d expect a linear recurrence of the form an+1 = xan + yan−1 .
Now let’s begin listing the answers for small n. For n = 1, there’s nothing, so 0. For
n = 2 it’s just BL, so 1. Similarly, for n = 3 it’s just BLR, so 1. For n = 4, there are 3:
BRBL, BLBL, BLRL. This gives us the sequence 0, 1, 1, 3, and if we solve the system

1 = 1x + 0y 3 = 1x + 1y

we get x = 1 and y = 2. So we expect the recursion to be an+1 = an + 2an−1 . We can

check this by going one step further:

Exercise 2.50. Check that there are 11 different Vitas words with 5 letters.

From here, we can continue the recursion to get 11, 21, 43, 85, 171, 341, which gives
us the correct answer.

Exercises
Problem 2.51 (PMO 2020 Qualifying III.3). A string of 6 digits, each taken from the set {0, 1, 2},
is to be formed. The string should not contain any of the substrings 012, 120, and 201. How
many such 6-digit strings can be formed?
Problem 2.52 (AMC 12A 2007/25). Call a set of integers spacy if it contains no more than
one out of any three consecutive integers. How many subsets of {1, 2, 3, . . . , 12}, including the
empty set, are spacy?
Problem 2.53 (AIME I 2001/14). A mail carrier delivers mail to the nineteen houses on the
east side of Elm Street. The carrier notices that no two adjacent houses ever get mail on the
same day, but that there are never more than two houses in a row that get no mail on the
same day. How many different patterns of mail delivery are possible?

3 And other tricks

Other than engineer’s induction, which is the namesake of this handout, there are
some other engineering-flavored tricks. Here we present three of them: abusing degrees
of freedom, using the answer choices, and using the answer format.

3.1 Abusing degrees of freedom

In the introduction, we talked about PMO 2019 Qualifying III.4, where we can abuse
the degrees of freedom in the problem. For short-answer contests, we often know that
the answer has to be numerical. This means that the answer should be the same no
matter what configuration we pick, so we only have to try a specific case to find it.

Example 3.1 (PMO 2017 Areas I.4). Suppose that Sk is the sum of the first k terms
of an arithmetic sequence with common difference 3. If the value of S3n /Sn does not
depend on n, what is the 100th term of the sequence?

15
Engineering Carl Joshua Quines

The morally correct way to solve this would be by writing out Sn in terms of n,
writing out the ratio S3n /Sn , and choosing the value of the first term such that the n
cancels out or something.
But we don’t have to do this. Since we know the problem is correct anyway, we can
just pick two specific values of n and equate them. In particular, let’s equate S3 /S1
and S9 /S3 .

Exercise 3.2. Letting a be the first term, write S1 , S3 , and S9 in terms of a. Check
that S3 /S1 = S9 /S3 becomes S32 = S1 S9 , and the 9a2 on both sides cancel to make a
nice linear equation. From here, solve for a = 23 .

A problem can seem to signal something deeper. It could be that S3n /Sn is a
ratio that doesn’t depend on n, or that given a functional equation, then the value of
f (x + 1) − f (x) is always the same. Generally it’s of the form, given this condition, all
the solutions share this property. We don’t actually have to show that this is true—we
can just take it for granted, find a specific solution, and then use that.
Not really much to talk about here again, so here are problems:

Exercises
Problem 3.3 (AMC 10B 2002/20). Let a, b, and c be real numbers such that a − 7b + 8c = 4
and 8a + 4b − c = 7. What is the value of a2 − b2 + c2 ?
Problem 3.4 (PUMaC Algebra B 2014/2). The function f : Z≥0 → Z≥0 satisfies, for all n ∈ Z≥0 ,
f (f (n)) + f (n) = 2n + 3. Find f (2014).
Problem 3.5 (Mathira Elims 2018/2). Each square of a 69 × 69 board is colored either maroon
or green. Each maroon square not adjacent to an edge is adjacent exactly 5 green squares out
of its 8 neighbors. Each green square not adjacent to an edge is adjacent to exactly 4 maroon
squares out of its 8 neighbors. Find the number of maroon squares.
Problem 3.6. Complex numbers x, y, and z satisfy |x| = |y| = |z| = xyz = 1 and x + y + z = 0.
Find |(2 + x)(2 + y)(2 + z)|. Hint: 15
Problem 3.7 (AMC 10A 2016/23). A binary operation ♦ has the properties that a ♦ (b ♦ c) =
(a ♦ b) · c and that a ♦ a = 1 for all nonzero real numbers a, b, and c. (Here · represents
multiplication). The solution to the equation 2016 ♦ (6 ♦ x) = 100 can be written as pq , where
p and q are relatively prime positive integers. What is p + q?

3.1.1 Take the boundaries

For geometry problems in particular, this means taking degenerate cases. This
doesn’t happen a lot, since often the conditions in a geometry problem make it so that
there’s only one possible configuration. But if there are multiple possible configurations,
we can exploit this. If you have a point P that is allowed to be anywhere on a segment
AB, why not take the limit as P = A or P = B? If your triangle can be anything,
make it equilateral, or make all the points collinear.

Example 3.8 (HMMT Guts 2017/6). Let ABCD be a convex quadrilateral with AC = 7
and BD = 17. Let M , P , N , Q be the midpoints of sides AB, BC, CD, DA,
respectively. Compute M N 2 + P Q2 .

16
Engineering Carl Joshua Quines

Note that we can pick any quadrilateral where AC = 7 and BD = 17, so it’s best to
pick something that’s easy to work with. One option is a rhombus, where all the sides
are equal. In a rhombus, the diagonals are perpendicular bisectors, and M N and P Q
both pass through their intersection, which we’ll call O.
A
M Q
O
B D
P N
C

So we only have to find M O. But look at right triangle ABO. Then M O is the
segment joining the midpoint of the hypotenuse to the opposite vertex, which means
it’s half the length of the hypotenuse.

q

7 2

2
Exercise 3.9. Show that M O = 2 + 17
2 . Don’t simplify it yet. Note that the
2 2
final answer is M N + P Q , and as M N = P Q = 2M O. From here, show that the
2 2
final answer is 7 +17
2 = 169.

Of course, there’s an even simpler solution than using a rhombus—just make all the
four points collinear! Let the points B, A, C, and D be on a line in that order. Then
we can pick BA = 5, AC = 7, and CD = 5, and this will still satisfy the conditions.

A A
B D B D
C C

The only condition that it doesn’t satisfy, technically, is convexity. But we can
wiggle around the points so that it becomes convex. The answer would still be the
same; the lengths can’t change that much.

Exercise 3.10. Show that, in this case, M N 2 + P Q2 is still 169.

In fact, it might be even easier to just take A = B, AC = 7, and then CD = 10,

which would still satisfy the conditions. Either way, here are problems:

Exercises
Problem 3.11 (AIMO 2019/6). Let ABCD be a parallelogram. Point P is on AB produced
such that DP bisects BC at N . Point Q is on BA produced such that CQ bisects AD at M .
Lines DP and CQ meet at O. If the area of parallelogram ABCD is 192, find the area of
triangle P OQ.
Problem 3.12 (HMMT Geometry 2017/4). Let ABCD be a convex quadrilateral with AB = 5,
BC = 6, CD = 7, and DA = 8. Let M , P , N , Q be the midpoints of sides AB, BC, CD,
DA, respectively. Compute M N 2 − P Q2 .
Problem 3.13. Triangle ABC satisfies AB = 5, BC = 6, and CA = 7. Let point P lie on side
BC. Let I1 and I2 be the incenters of triangles ABP and ACP , respectively. The circumcircle
of triangle P I1 I2 passes through a fixed point X as P varies on side BC. Find the ratio
BX/CX. Hint: 2

17
Engineering Carl Joshua Quines

Problem 3.14 (HMMT Geometry 2018/6). Let ABC be an equilateral triangle of side length
1. For a real number 0 < x < 0.5, let A1 and A2 be the points on side BC such that
A1 B = A2 C = x, and let TA = 4AA1 A2 . Construct the triangles TB = 4BB1 B2 and
TC = 4CC1 C2 similarly.
There exist positive rational numbers b, c such that the region of points inside all three
triangles TA , TB , TC is a hexagon with area
√
8x2 − bx + c 3
· .
(2 − x)(x + 1) 4

Find (b, c).

3.2 Using choices

We can sometimes use answer choices, if they exist, to solve the problem. We can
eliminate incorrect answers through modulo or divisibility considerations; the
answer should be
√ even, the denominator should be divisible by 7, it should be a rational
number times 17. We can also eliminate incorrect choices through estimating size.
And of course, we can also just substitute each of the choices to see which
one works. Most of the time problems are written to avoid this from happening, but
sometimes there are problems where we can just do this.

Example 3.15 (AMC 12 2001/5). What is the product of all positive odd integers less
than 10000?
10000! 10000! 9999! 10000! 5000!
(A) (B) 5000 (C) 5000 (D) 5000 (E) 5000
(5000!)2 2 2 2 · 5000! 2

Here, let’s use a divisibility consideration. Let’s say that p is some prime slightly
less than 5000. Then in the final answer, a factor of p should appear once, and exactly
once, because it’s a prime. So let’s look at all the choices and count how many times p
appears as a factor:

(A) It appears in the numerator twice, once for p and once for 2p. It also appears
in the denominator twice: once each in 5000!. So it doesn’t appear in (A) as a
factor at all.

(B) It appears in the numerator twice, and it doesn’t appear in the denominator at
all. So it appears twice, and this answer has to be wrong.

(C) Like (B), it appears in the numerator twice, and doesn’t appear in the denomi-
nator at all, so this choice has to be wrong.

Exercise 3.16. Finish the analysis for the remaining two choices (D) and (E). Does
this eliminate one of them as incorrect? If not, what other considerations can you use
to get the correct answer?

Often, tricks that eliminate answer choices won’t eliminate all of them as cleanly as
in this one. But divisibility and estimation are great ways to sanity check an answer
anyway, so it’s good practice for those.
18
Engineering Carl Joshua Quines

Exercises
Problem 3.17 (PMO 2016 Qualifying I.10). In triangle ABC, BD is the angle bisector of ∠ABC,
and AB = BD. Moreover, E is a point on AB such that AE = AD. If ∠ACB = 36◦ , find
∠BDE.
(A) 24◦ (B) 21◦ (C) 18◦ (D) 15◦ (E) 12◦
Problem 3.18 (AMC 12B 2016/17). In 4ABC, AB = 7, BC = 8, CA = 9, and AH is an
altitude. Points D and E lie on sides AC and AB, respectively, so that BD and CE are angle
bisectors, intersecting AH at Q and P , respectively. What is P Q?
5√ 4√ 8√ 6
(A) 1 (B) 3 (C) 2 (D) 5 (E)
8 5 15 5
Problem 3.19 (AMC 10A 2019/18). For some positive integer k, the repeating base-k repre-
7
sentation of the (base-ten) fraction is 0.23k = 0.232323...k . What is k?
51
(A) 13 (B) 14 (C) 15 (D) 16 (E) 17
Problem 3.20 (AMC 12A 2018/24). Alice, Bob, and Carol play a game in which each of them
chooses a real number between 0 and 1. The winner of the game is the one whose number is
between the numbers chosen by the other two players. Alice announces that she will choose her
number uniformly at random from all the numbers between 0 and 1, and Bob announces that
he will choose his number uniformly at random from all the numbers between 12 and 23 . Armed
with this information, what number should Carol choose to maximize her chance of winning?
1 13 7 5 2
(A) (B) (C) (D) (E)
2 24 12 8 3

3.3 Using the answer format

Ideally, the answer format of a problem shouldn’t reveal anything about how to solve
it. But when it does, we can abuse the answer format to make a very good guess
without actually solving the problem.

Example 3.21 (Sipnayan Finals JHS 2018/V/TM). Find the sum

2018
X
6x5 + 45x4 + 140x3 + 225x2 + 186x + 63 .


x=0

Express your answer in the form ab − 1 where a is minimized.

It’s likely that a and b are integers. The fact that they want us to minimize a is
just to prevent us from submitting, say, 92 − 1 if the answer was 34 − 1. In either case,
the answer is something that’s very close to a perfect power.
A first good step would be to figure out what b is. Can b be something huge, like
10? It’s unlikely. Remember that if we sum 1 + 2 + · · · + n, we get something that
grows like n2 . Similarly, the sum 1 + 4 + · · · + n2 grows like n3 . The largest terms in
our sum grow like 15 + 25 + · · · + n5 , which should be around n6 . So b = 6 would be a
good guess.
Now what is a? Again,
let’s estimate the sum, and only care about the largest part:
6 15 + 25 + · · · + 20185 . This is approximately the integral of 6x5 from x = 1 to
x = 2018. So we expect it to be around 20196 .
19
Engineering Carl Joshua Quines

Exercise 3.22. Convince yourself that the answer is larger than 20196 by considering
the contribution from the other parts. Using the same integral trick gives a pretty
good approximation.

Adding in the other parts would give us something slightly above 20196 . Since we
want b = 6, the next thing above 20196 would be 20206 .
Could it be 20216 ? We can check how much larger than 20196 we want to go by
expanding (2019 + 1)6 . In this case, the terms match up quite well with the estimates
you’d get from doing integrals. So the answer 20206 − 1 should be pretty convincing,
and it is in fact the correct answer.

Exercises
Problem 3.23 (Mathira 2018/T3-2). We define the Pabibo Najee sequence to consist of positive
integers that is determined by the following recursive formula. For k ≥ 2, ak = 2ak−1 + 9ak−2 ,
mk+1 − nk+1
where a0 = 1 and a1 = 2. Find real numbers m and n such that m > n and ak =
m−n
for all natural numbers k.
Problem 3.24 (Sipnayan SHS Elims 2018/V1). Let s0 = 6, s1 = 6, and sn = 2sn−1 + 8sn−2 for
n ≥ 2. Define
Xn
An = si .
i=0

Find A2018 . Express your answer in the form a + cd , where a, b, c, and d are positive integers.
b

Problem 3.25 (Sipnayan SHS Finals 2017/V/FOP). Lake Nick is an enormous underwater lake
enclosing 2017 islands arranged at the vertices of a regular 2017-gon. Adjacent islands are
joined with exactly two bridges. One day, Spongebob took a wrong bus from Bikini Bottom
and ended up in one island in Lake Nick. When Spongebob remembered that the Hash Slinging
Slasher was living in the lake, he started to think of destroying all the bridges. If the island he
is on has at least one bridge still joined to it, he randomly selects one such bridge, crosses it,
and immediately destroys it. Otherwise, he stops. What is the probability that Spongebob
 d
b
destroys all the bridges before he stops? Express your answer in the form a , where
c
a, b, c, d ∈ Z+ and b, c are prime numbers. Hint: 12

4 Grab bag
Here are some more problems that are susceptible to some sort of engineering, sorted
roughly by how hard they are to engineer.

Grab bag
Problem 4.1 (HMMT Guts 2017/19). Find (in terms of n ≥ 1) the number of terms with odd
coefficients after expanding the product:
Y
(xi + xj )
1≤i<j≤n

e.g., for n = 3 the expanded product is given by x21 x2 +x21 x3 +x22 x3 +x22 x1 +x23 x1 +x23 x2 +2x1 x2 x3
and so the answer would be 6.

20
Engineering Carl Joshua Quines

Problem 4.2 (Mathira 2019 T10-1). The diagram below shows a grid with n rows, with the
kth row being composed of 2k − 1 identical equilateral triangles for all k ∈ {1, . . . , n}. If there
are 513 different rhombuses each made up of two adjacent smaller triangles in the grid, what
must be the value of n?

Hint: 10

Problem 4.3 (Mathira 2017 T12-1). I draw a series of line segments such that B, the second
endpoint of a line segment AB, is the first endpoint of the next line segment BC, and
∠ABC = 120◦ . AB is the first line segment, BC is the second, CD is the third, DE is the
fourth, and so on, with ∠ABC, ∠BCD, and ∠CDE all equal to 120◦ and 4ABC overlaps
with 4BCD, 4BCD overlaps with 4CDE and so on. If every line segment is half of the
length of the previous one, the series of line segments eventually becomes a single point X.
What is the ratio of AX to AB? Hint: 8
Problem 4.4 (ARML Individuals 2017/6). A diagonal of a regular 2017-gon is chosen at random.
Compute the probability that the chosen diagonal is longer than the median length of all of
the diagonals.
Problem 4.5 (OMO Spring 2014/25). If
∞ 1 1 1
X
1 + 2 + ··· + n p
n+100

=
n=1 100
q

for relatively prime positive integers p, q, find p + q.

Problem 4.6 (AMC 10A 2018/23). Farmer Pythagoras has a field in the shape of a right
triangle. The right triangle’s legs have lengths 3 and 4 units. In the corner where those sides
meet at a right angle, he leaves a small unplanted square S so that from the air it looks like
the right angle symbol. The rest of the field is planted. The shortest distance from S to the
hypotenuse is 2 units. What fraction of the field is planted?

3
2
S 4

Hint: 3

Problem 4.7 (HMMT Algebra and Number Theory 2019/8). There is a unique function f : N → R
such that f (1) > 0 and such that
X n
f (d)f =1
d
d|n

for all n ≥ 1. What is f 20182019 ? Hint: 1

21
 Engineering Carl Joshua Quines

Problem 4.8 (PUMaC Combinatorics A 2018/4). If a and b are selected uniformly from
{0, 1, . . . , 511} with replacement, the expected number of 1’s in the binary representation
of a + b can be written in simplest form as m n . Compute m + n.
Problem 4.9 (HMMT Algebra and Number Theory 2017/7). Determine the largest real number
c such that for any 2017 real numbers x1 , x2 , . . . , x2017 , the inequality
2016
X
xi (xi + xi+1 ) ≥ c · x22017
i=1

holds.
2017 πk


X 5 + cos 1009
Problem 4.10 (CMIMC Algebra 2018/7). Compute πk

. Hint: 5
k=0
26 + 10 cos 1009

5 Hints
1. When computing f (p), f (p2 ), f (p3 ), do not simplify fractions.
2. Let I be the incenter. Moving P to B, the circle becomes the one with diameter BI.
3. If S has side length s, the shortest distance in the problem is linear in terms of s.
4. Find it when the exponent is 1 by replacing 2013. Then find it for 2, then 3.
5. This is tricky. Replacing 1009 with n, notice that the denominators divide 52n − 1.
6. Engineer on the base. How many are there in base 1, base 2, base 3?
7. What’s 1/9 in base 10?
8. Draw a good diagram. Your first reasonable guess is probably right.
9. When you have a guess, expand (1 + 0.5)n . Most terms are small and can be ignored.
10. Estimate. “Most” triangles are part of 3 rhombi, and each rhombus contains 2 triangles.
11. Replacing 60 with n, the answer has to be cubic in terms of n.
12. Tricky. Replace 2017 with n and engineer. Assume b and c are constant over all n.
13. Replace 1000 with n, 1001 with n + 1, and 1000000 with n2 .
14. Guessing the sequence is hard. Try again after reading section 2.3.
15. Pick three nice numbers on the unit circle that sum to zero.

Acknowledgments
Thanks to Ankan Bhattacharya and Vincent Huang for references, David Altizio for
suggestions about the introduction, and Avi Mehra for typo corrections. If you spot a
typo, see an error, have a suggestion, or want to ask a question, feel free to contact
me at cj@[Link] W.

22