Estimation

Michael Luo
18 September 2024

arml estimathon was the second time at a competition where my team loses first place
to minnesota in the last ∼10 minutes with the first being cmimc
—MathWizard10 on AoPS

Contents
1 Background and theory 2

2 Examples 3

3 Sums and products 5

3.1 Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Number-theoretic sums (optional) . . . . . . . . . . . . . . . . . . . . . . 7

4 Combinatorics 10

1
Michael Luo — 18 September 2024 Estimation

§1 Background and theory

Throughout, we use the convention that A is the actual answer and E is the estimate.
Additionally, log denotes the natural logarithm.
Estimation problems on Guts sets commonly come in combinatoric, algebraic, and
number-theoretic varieties. There are also meta-problems and a few weird ones involving
convex hulls of the schools of the organizers, but we shall ignore those. To get better at
those, try Fermi questions (rip).
Let’s start with a few theorems. It might be beneficial to skim these and try the
examples below using this as a cheat-sheet.

Theorem 1.1 (Prime number theorem)

log n
There are approximately n primes below n.

It’s often useful to think of the primes as being “random”: the “probability” of n being
prime can be thought of log1 n .

Theorem 1.2 (Prime number theorem for arithmetic progressions)

The primes are evenly distributed in the coprime residue classes modulo n.

3
Essentially, if you know n is not 0 or 2 modulo 6, then it has “probability” 2 log n of
1
being prime, and if you know n is 1 modulo 4, it has “probability” 2 log n of being prime.

Theorem 1.3 (Central limit theorem)

If you add many random variables, the resulting distribution is approximately
normal.

This is pretty useful when you have a bunch of random variables and want to find
the probability of them being within certain bounds. We also have the famous Stir-
ling’s approximation, which allows for the approximation of the factorial and binomial
coefficients.

Theorem 1.4 (Stirling’s approximation)

√  n n
n! ≈ 2πn .
e

Use of logarithms allows one to quickly compute otherwise-difficult expressions. Laplace

famously said logarithms “by shortening the labors, doubled the life of an astronomer.”

Theorem 1.5 (Logarithms)

We have log 2 ≈ 0.69, log 3 ≈ 1.10, log 5 ≈ 1.61, log 7 ≈ 1.95. In particular,
log 10 ≈ 2.30.

We also have the following useful form of Stirling:

2
Michael Luo — 18 September 2024 Estimation

Theorem 1.6 (Logarithm of Stirling)

1
log n! ≈ n (log n − 1) + log n + 0.92.
2

§2 Examples
The examples below are relatively straightforward with the above theorems. Please try
them before reading the solution.

Example 2.1 (MNYMO Guts 2024 Shortlist)

Ryan Niu flips 1000 coins. Estimate the probability he gets between 490 and 510
heads, inclusive. 
You will earn 20 min(A/E, E/A)4 points.


Solution. We present two approaches, one with Stirling, and one with central limit
theorem, which both give the estimate
21
√ ≈ 0.53.
500π
ˆ Let n = 500. The probability p is approximately
 
21 2n
.
22n n
√
n
But from Stirling’s approximation, n! ≈ 2πn ne , we have
√
21 2π · 2n( 2n
e )
2n
21
p ≈ 2n · n 2n ≈√ .
2 2πn( e ) 500π

ˆ Let Xi for 1 ≤ i ≤ 1000 be random variables evaluating to 1 if the i-th flip is heads
and −1 if the i-th flip is tails. We want the probability

X := X1 + · · · + X1000

is between −20 and 20, inclusive. By central limit theorem, X is approximately

normal, with µX = 0 and
√ p √
σX = Var X = Var X1 + · · · + Var X1000 = 10 10.

Now p is approximately the probability X is between −21 and 21, which is approx-
imately
21 − (−21) 1 21
·√ =√
σX 2π 500π
by scaling X to be standard normal.

The actual answer is 0.513, so we earned 17 points. ■

3
Michael Luo — 18 September 2024 Estimation

Example 2.2 (HMMT Guts 2015/33)

1000


Estimate the sum of the decimal digits of 100 .
You will earn 25(0.99)|A−E| points.

Solution. In this solution, log denotes the base 10 logarithm. We will estimate log 1000


100
and multiply by 4.5, assuming the digits are random. Let a = 100 and b = 900. We use
a very rough form of logarithmic Stirling by dropping the logn + 0.92 term:
 
a+b
log ≈ (a + b) log(a + b) − a log a − b log b
a
= a(log(a + b) − log a) + b(log(a + b) − log b) ≈ 100 + 900 · 0.044 = 140.6.

So our estimate is 4.5 · 140.6 ≈ 633. Since the answer is 621, we earn 22 points. ■

Remark. It’s insane how easy it was to earn points using estimation “back in the day.” We
got 22 points from this! For reference, this is a problem worth 20 points from the same year:
A wealthy king has his blacksmith fashion him a large cup, whose inside is a cone
of height 9 inches and base diameter 6 inches (that is, the opening at the top of
the cup is 6 inches in diameter). At one of his many feasts, he orders the mug to
be filled to the brim with cranberry juice. For each positive integer n, the king stirs
his drink vigorously and takes a sip such that the height of fluid left in his cup after
the sip goes down by n12 inches. Shortly afterwards, while the king is distracted,
the court jester adds pure Soylent to the cup until it’s once again full. The king
takes sips precisely every minute, and his first sip is exactly one minute after the
feast begins.
As time progresses, the amount of juice consumed by the king (in cubic inches)
approaches a number r. Find r.
Nowadays, it’s a lot harder to get points from estimation.

Example 2.3 (HMMT Guts 2020/34)

For odd primes p, let f (p) denote the smallest integer a such that there does not
exist an integer n satisfying p | n2 − a. Estimate the sum of f (p)2 over the first 105
odd primes p. 
You will earn 22 min(E/A, A/E)3 points.


Solution. Note that f (p) is the smallest quadratic nonresidue modulo p, which must be
prime (since −1 = ( ab a b a b
p ) = ( p )( p ) implies ( p ) = −1 or ( p ) = −1.) We assume each prime
p has a 12 chance of being a quadratic nonresidue, so then the expected value of f (p)2 is

22 32 52 72
+ + + + · · · ≈ 23,
2 4 8 16
by taking the first few terms and bounding, so our estimate is 2300000. Since the actual
answer was 2266067, we earned 21 points. ■

4
Michael Luo — 18 September 2024 Estimation

§3 Sums and products

§3.1 Integration
Along with your general toolkit (switching orders of summation, generating functions),
there are some special tricks more common in estimation problems. The most common
is by far estimating sums using integrals. For example:

Example 3.1
1
Estimate the nth harmonic number Hn = 1 + · · · + n1 .

Solution. Just observe Z n

1 1 1
+ ··· + ≈ = log n. ■
1 n 1 n
This estimate can actually be improved, a better approximation is log n + γ, where
γ ≈ 0.577 is the Euler-Mascheroni constant.
Our next example uses a logarithm to turn a product into a sum.

Example 3.2 (HMMT Guts 2020/33)

Estimate
∞
−1.25
Y
nn .
n=1

You will earn ⌊22 min(A/E, E/A)⌋ points.

Solution. Instead approximate

∞ Z ∞
X log n log x
log A = ≈ dx = 16,
n=1
n5/4 1 x5/4

by integration by parts. Then,

1010
N ≈ e16 ≈ e10 log 5 = 510 ≈ ≈ 107 .
210
The exact answer is 8282580, so we earn 18 points. ■

This example shows the importance of looking at the answer extraction: the expression
⌊22 min(A/E, E/A)⌋ is much more forgiving than, say 22 min(A/E, E/A)4 . So we
 

could use very rough estimates such as 16 ≈ 10 log 5 in the exponent of e.

Example 3.3 (HMMT Guts 2015/34)

For an integer n, let f (n) denote the number of pairs of integers (x, y) such that
x2 + xy + y 2 = n. Compute
106
X
nf (n).
n=1

You will earn max(0, 25 − ⌊100| log10 (A/E)|⌋) points.

5
Michael Luo — 18 September 2024 Estimation

Solution. Let N = 106 . The sum becomes

X X X
n= n.
n≤N x2 +xy+y 2 =n x2 +xy+y 2 ≤N

Estimate this sum with an integral and evaluate using change of variables:
ZZ
π
x2 + xy + y 2 dx dy = √ N 2 ≈ 1.8 · 1012 .
x2 +xy+y 2 ≤N 3

The exact answer is approximately 1.81376 · 1012 , so this earns 25 points. ■

Remark. This problem is how I learned how to take a double integral.

Here’s a slightly harder example also utilizing integrals to estimate sums, but with
prime number theorem this time:

Example 3.4 (HMMT Guts 2024/34)

Estimate the number of positive integers n ≤ 106 such that n2 + 1 has a prime factor
greater than n.
You will earn $ 5 %!
E 106 − E

max 0, 20 min , + 0.5
A 106 − A
points.

Solution. Let N = 106 , we sum over primes p | n2 + 1. For an odd prime p, there are 2
solutions to p | n2 + 1 with n < p if p ≡ 1 mod 4 and no solutions otherwise. Now let p
be a 1 mod 4 prime.
If p ≤ N , p contributes two solutions. Otherwise, assume that the solutions to
2
n ≡ −1 mod p are uniformly distributed modulo p, so if p > N , there are on average
2N 2 2
p solutions to p | n + 1 with n ≤ N . And if p > N , there are zero solutions, full stop.
Therefore, the answer is
X X 2N
2+ .
2
p
p≤N N <p<N

From the prime number theorem for arithmetic progressions, a positive integer x has
1
“probability” 2 log x of being a 1 mod 4 prime. Therefore, the sum becomes

Z N Z N2
X 1 X 2N 1 1 N
·2+ · ≈ dx + dx
2 log x x 2 log x 1 log x N x log x
x≤N N <x<N 2
Z N
1
≈ dx + N (log(log N 2 ) − log(log N ))
1 log N
 
1
≈N + log 2
log N
≈ 765530.

The exact answer is 757575, so this estimate earns 17 points. ■

6
Michael Luo — 18 September 2024 Estimation

Example 3.5
The number 2027 is prime. For i = 1, . . . , 2026, let pi be the smallest prime such
that pi ≡ i (mod 2027). Estimate max(p
 1 , . . . , p2026 ).
8
You will earn 25 min(E/A, A/E) points.

1
Solution. We assume each prime has probability 2026 of being 1, . . . , 2026 modulo 2027
and compute the expected number of primes needed to cover every nonzero residue class
modulo 2027. Let n = 2026, then by linearity of expectation, this is
n n n
+ + · · · + ≈ n log n.
n n−1 1
And since the mth prime is approximately m log m, our estimate is

n log n log(n log n) = n log n(log n + log log n) ≈ 2026 · 7.6 · (7.6 + 2.02) ≈ 150000.

where we have estimated

log n ≈ log 2048 = 11 log 2 ≈ 7.6

and
log log n ≈ log 7.5 = log 3 + log 5 − log 2 ≈ 1.1 + 1.61 − 0.69 ≈ 2.02.
Since the exact answer is 113779, we earned 2 points. ■

Remark. The official solution uses a similar method to obtain

n log n log(n log n),

but then uses the questionable estimate

n log n log(n log n) ≈ n log2 n ≈ 117488,

which earns 19 points.

I frankly think it’s dishonest to “rig” the solution this way. It’s a much better decision to
keep the n log n log log n term, because the answer extraction has an exponent of 8, which is
extremely unforgiving. But as it turns out, dropping the term yields a much better estimate,
due to luck. If instead the answer had instead been closer to 150000, would the organizers
still use the above estimate? On a contest, you are not given the luxury of knowing what
the answer is. Contest organizers should write solutions for estimations before they compute
the exact answer.

§3.2 Number-theoretic sums (optional)

Most of the problems in this section are from the OTIS unit ZNW-analyticnt.
Integrals work fine when you’re faced with functions like x1 and x log
1
x , but for number-
theoretic functions like φ, this doesn’t work.
This section is pretty technical. For background, skim “erm, what the σ,” which can be
found on the Minnetonka Math Team website. Make sure you know what the following
mean:

ˆ The Dirichlet convolution and the fact that it preserves multiplicativity.

ˆ The multiplicative arithmetic functions 1, id, d, σ, φ, and µ.

7
Michael Luo — 18 September 2024 Estimation

ˆ The Riemann zeta function ζ and the Euler product formula. In particular, you
2 4
should know ζ(2) = π6 and ζ(4) = π90 .

Now let’s try some examples.

Example 3.6
For all s > 1, show that
X µ(n)
= ζ(s)−1 .
ns
n≥1

Solution. We need to show

X µ(n) X 1
= 1.
ns ms
n≥1 m≥1

Summing over k = mn, the sum becomes

X (µ ∗ 1)(k)
= 1. ■
ks
k≥1

Also, by the definition of the Dirichlet convolution, we have the following:

Theorem 3.7 (Convolution method)

If f = g ∗ h, then
  
X X X
f (n) =  g(d)  h(e) .
n≤N d≤N e≤N/d

The above is quite useful, particularly when partial sums of h are easy to estimate.
Let’s see a few examples:

Example 3.8
In terms of x, estimate X
φ(n).
n≤x

Solution. Write φ = µ ∗ id. Then

X X X
φ(n) = µ(d) y
n≤x d≤x y≤ x
d
X x2
≈ µ(d) ·
2d2
d≤x
3 2
= x .
π2
■

8
Michael Luo — 18 September 2024 Estimation

Example 3.9
Two integers are randomly selected from {1, 2, . . . , n}. As n goes to infinity, compute
the probability they are coprime.

Solution. We compute
X XX X
1= µ(d)
x,y≤n,(x,y)=1 x≤n y≤n d|(x,y)
X X
= µ(d)
d≤n x,y≤n/d
X j n k2
= µ(d)
d
d≤n
X n2
≈ µ(d)
d2
d≤n
6 2
= n ,
π2
6
so the answer is π2
. ■

Example 3.10
In terms of x, estimate X
d(n).
n≤x

Solution. Write d = 1 ∗ 1, then

X X
d(n) = 1
n≤x ab≤x
X jxk X jxk X
= + − 1
√ a √ b √
a≤ x b≤ x a,b≤ x
√ 2
 
1
≈2 x log x + γx − x
2
= x log x + (2γ − 1)x. ■
In the above example, we also could have simply evaluated the sum
X X X X jxk
1= 1= ≈ x log x.
a
ab≤x a≤x b≤x/a a≤x

This estimate is slightly less precise though, since here you have to delete x floors, while
√
above you only have to delete 2 ⌊ x⌋ floors.
Warning: the next problem is hard.

Example 3.11
In terms of x, estimate
X 1
.
φ(n)
n≤x

9
Michael Luo — 18 September 2024 Estimation

1
Solution. Let f be a multiplicative function with f (1) = 1, f (p) = p(p−1) , and f (pα ) = 0
for α ≥ 2. Now φ1 = id
1
∗ f . The sum then becomes
X X 1 X
f (d) ≈ f (d)(log x − log d + γ)
e
d≤x e≤x/d d≤x
X
≈ log x f (d),
d≤x

where we have dropped the f (d) log d and f (d)γ terms since they are bounded by constants.
Now we compute
X X Y ζ(2)ζ(3)
f (d) ≈ f (d) = (1 + f (p)) = ,
p
ζ(6)
d≤x d≥1

ζ(2)ζ(3)
by Euler’s product formula. Therefore the sum is approximately ζ(6) log x. ■

Example 3.12 (MNYMO Guts 2024/27)

The MN Youth Math Outreach Board has birthdays B1 , B2 , . . . , B7 when written in
MMDDYYYY form. For example, if Taylor Swift was the eighth member of the MN
Youth Math Outreach Board, B8 would be 12131989, since her birthday is December
13th, 1989. Estimate the sum of the pairwise gcds of the Bi , or
X
gcd(Bi , Bj ).
1≤i<j≤7

You will earn ⌊20 min(E/A, A/E)⌋ points.

Solution. Assume the birthdays are randomly chosen integers from 1 to 13000000. Let
N = 13000000, we compute the expected gcd of two integers chosen randomly from 1
to N . Since the probability of two integers chosen from {1, 2, . . . , N } being relatively
prime is approximately π62 , so the probability of the gcd being k for some k ≤ N is (kπ)6
2.

Therefore we estimate the expected value

X 6 6 X 1 6
2
= 2 ≈ 2 log N ≈ 10.
kπ π k π
k≤N k≤N

7


Since there are 2 possible pairs, our estimate is 210. Since the answer is 390, we earned
10 points. ■

§4 Combinatorics
Example 4.1 (HMMT Guts 2015/35)
Let P denote the set of all subsets of {1, . . . , 23}. A subset S ⊆ P is called good if
whenever A and B are sets in S, A∆B is in S, where A∆B is the set consisting of
the elements belonging to exactly one of A and B. Estimate the fraction of the good
subsets of P with between 2015 and 3015 elements, inclusive.
You will earn max(0, 25 − ⌊1000 |A − E|⌋) points.

10
Michael Luo — 18 September 2024 Estimation

Solution. The main idea is to interpret the sets in S as vectors in F23 2 , with the corre-
sponding vector of a set X ∈ S being (x1 , . . . , x23 ), where xi = 1 if i ∈ X and xi = 0
if i ̸∈ X. Then, one may interpret the symmetric difference as vector addition, so the
good sets are the subspaces of F23 23
2 . We want the fraction of subspaces of F2 with 11
dimensions.
By induction, we have the following facts about linear algebra over F2 :
ˆ There are (223 − 1) . . . (223 − 2n−1 ) ways to choose an ordered list of n linearly
independent vectors in F23 2 .

ˆ Each subspace of dimension n has (2n − 1)(2n − 2) . . . (2n − 2n−1 ) bases, with
ordering.
Therefore, there are
(223 − 1) . . . (224−n − 1)
.
(2n − 1)(2n − 2) . . . (2n − 2n−1 )
subspaces of F23
2 with dimension n. We can multiply this by constant factors since we
are calculating a ratio, so we may approximate this as
223n 23n−n2
f (n) := n2 = 2 .
2
Again scaling by a constant, this is
1 23 2
2 4 −(n− 2 ) .
Since this decays quickly when n is not close to 11 or 12, the ratio is approximately
f (11) f (11) 1 32
P23 ≈ P14 = −2 −6
= ≈ 0.395.
i=0 f (n) i=9 f (i)
2(1 + 2 + 2 ) 81
Since the answer is approximately 0.395020305, we earned 25 points. ■
You are allowed to use a scientific calculator for the next example.

Example 4.2 (HMMT Guts 2023/35)

The Fibonacci numbers are defined recursively by F0 = 0, √F1 =√ 1, and √ Fi =
Fi−1 + Fi−2 for i ≥ 2. Given 30 wooden blocks of weights 3 F2 , 3 F3 , . . . , 3 F31 ,
estimate the number of ways to paint each block either red or blue such that the
total weight of the red blocks and the total weight of the blue blocks differ by at
most 1.
You will earn 25 min(E/A, A/E)8 points.
 

√ √
Solution. Let Xi be a random variable that chooses 3 Fi , − 3 Fi at random. Let X =
X2 + · · · + X31 , we want to find the proability X is in the interval [−1, 1]. By central limit
theorem, X is approximately normal. Now by Binet the variance of X is approximately
31 31
X X φ2n/3 φ20 − 1
Var(Xi ) = √
3
= 2/3 · φ4/3 5−1/3 .
i=2 i=2
5 φ −1
Therefore the probability is approximately
1 2
√ ·p ,
2π Var(X)
so the number of ways is 230 times this, for an estimate of 4064732. Since the answer is
3892346, this earns 17 points. ■

11