Comb 5.

Problem statement: Prove that n! = n(n-1) … (n-k+1) * (n - k)!

Method:

Recall permutation rule n(n-1) … (n-k+1) = n!/(n-k)!
(n-k)! * (n!/(n-k)!) = n!

Proof of permutation rule:

Let s = set of n elements
We know n! = n(n-1)(n-2) … 1
rPn = n(n-1) … (n-r+1)
= n(n-1) … (n-r+1) * (n-r)!/(n-r)!
= (n(n-1) .. (n-r+1)(n-r) … 1) / (n-r)!
= n!/(n-r)!

Key observations:

Mental toughness, spend lots of time on problems
Try to come up with proofs for all answers
Logical reasoning
Use what is given (e.g. n! = n(n-1) … 1)

Comb 4.

Problem statement: Find the largest n such that 2^n divides 100!

Method:

Recall 100! = 100 * 99 * … * 1
= 2 * 4 * 6 * 8 * … * … * 1
= 2 * 2 * 2 * 2 * 2 for all even numbers in 100 * 2^2 * 2^2 * 2^2 for all multiples of 2^x …
Therefore, n = 50 (2^1) + 25 (2^2) + 12 (2^3) + 6 + 3 + 1 = 97

Comb 3.

Problem statement: How many trailing zeros in 103!

Method:

Recall n! = n(n-1) … 1
Zeros can be added by n * (10 * x) or 2n * 5x
floor(103/5) = 20, floor(103/5^2) = 4 Total = 24
If 5^3 < n, floor (n/5^3) would be added also

Comb 2.

Problem statement: GIven int n, find the number of divisors of n.

Method:

Prime factorization: n = a^x * b^y * c^z
Use combinatorics: number of ways to choose a^x * num ways to choose b^y * num ways to choose c^z = xyz
Therefore, number of divisors = xyz

Algorithm:

1. Using sieve of Eratosthenes
2. Combinatorial method
O(log n) prime factorization algorithm with O(n) for prime numbers
Use hashmap to store prime counts, multiply all counters
Optimizations: sieve, square root
Total complexity O(log n) or worst case O(n) compared to O(n) sieve for single test cases

Comb 1.

Topic: Combinatorics

Problem statement: How many odd numbers with 3rd digit 5 between 20000 and 69999?

Method:

How many ways to choose each digit?
20500 21500 … 69500
How many ways to choose the last digit?
00 … 99
50 * 50 = 2500

LT 3.

Topic: Proportionality I

Problem statement: It is 4 o’clock now. How many minutes will pass until the hands of the clock are coincident?

Method:

Notice an hour is directly proportional to minutes by 60 E.g when the minute hand moves 20 mins, the hour hand moves 20/60 = ⅓ hours
Let x = minutes passed. The hour hand has gone x/60 of the way from 4pm to 5pm
4 hours can also represent 20 mins for the minute hand. There are 5 minutes between the hourly intervals of 4 and 5.
Therefore, x = 20 + 5(x/60)
x = 240/11 mins

Key observations:

Direct and inverse proportions are constant (x/y, xy) given different values of xor x, y
Problems can be split into 2 proportions (LT 2), then combined like (LT 1)
Use algebra with proportions to find the solution. How can proportions be combined or represented in a common form? Time difference = current time + new time (LT 3)

LT 2.

Topic: Proportionality I

Problem statement: It takes 3 days for 4 people to paint 5 houses. How long will it take

2 people to paint 6 houses?

Method:

Notice days and people are directly proportional to houses and inversely proportional to each other
houses/(people)(days) = 5/12 (from problem statement 1)
Days = 12/5 * houses/people (algebra)
Days = 36/5

LT 1.

Topic: Proportionality I

Problem statement:

Proof (*):

Let x/y = a/b, where y = w/yz (from other question)
x = y * (a/b)

Method:

Notice x is directly proportional to y, x -> x/y and x/z are constant, xw is constant as it is inversely proportional
Therefore, combining -> xw/yz (is constant) = (4)(6)/(8)(5) = 5/12
x = w/yz * ⅗ (*)
x = 27/2

Key

LT -> Logical Thinking

Alg -> Algebra

Comb -> Combinatorics

Geo -> Geometry

NT -> Number Theory

NT 1.

Topic: Number theory

Problem statement: Perfect numbers

A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3 (excluding itself), and 1 + 2 + 3 = 6, so 6 is a perfect number.

The Euclid–Euler theorem is a theorem in number theory that relates perfect numbers to Mersenne primes. It states that an even number is perfect if and only if it has the form 2^(p−1) * (2p − 1), where 2p − 1 is a prime number. The theorem is named after mathematicians Euclid and Leonhard Euler, who respectively proved the "if" and "only if" aspects of the theorem.

Sufficiency Proof:

2^p - 1 is prime
σ(2^(p - 1)(2^p - 1)) = σ(2^(p - 1))σ(2^p - 1)
The divisors of 2^(p - 1) are 1, 2, 4, 8, …, 2^(p-1) form a geometric series that sum to 2^p - 1.
Since 2^p - 1 is prime, it has 2 divisors: 2^p - 1, 1. The sum of the divisors is 2^p
σ(2^(p - 1)(2^p - 1) = σ(2^(p - 1))σ(2^p - 1) = (2^p - 1)(2^p) = 2(2^(p - 1))(2^p - 1)
Therefore, 2^(p - 1)(2^p - 1) is perfect.

Necessity proof:

Suppose an even perfect number is given, and partially factor it as 2^(k)x = σ(2^(k)x) = (2^(k + 1) - 1)σ(x) *
The odd factor on the right, 2^(k + 1) - 1 is at least 3 and must divide x, the only odd factor on the left side -> y = x / 2(2^(k + 1) - 1) is a proper divisor of x
Dividing both sides of (*) by common factor 2^(k + 1) - 1 and taking into account known divisors x, y of x -> 2^(k + 1)y = σ(x) = x + y + … = 2^(k + 1)y + …
Therefore, there cannot be other divisors, y = 1, and x must be prime of the form 2^(k + 1) - 1.

Alg 1.

Topic: Logarithms & exponentiation

Problem statement: Given a != c, a^x = c^q, a^z = c^y. Prove that xy = qz.

Method:

Try multiplying the expressions to get a^x*c^q or …
Dead end -> return
Cancel out a to get c as the same base on both sides
How to cancel out a? a = (a^x)^(1/x) = c^(q/x) = (a^z)^(1/z) = c^(y/z)
Now we have c^(q/x) = c^(y/z) -> q/x = y/z -> xy = qz

Key takeaway:

Try multiple problem solving tactics. Think creatively.
Develop the thoughts through notation.

Think backwards & forwards (to prove that xy = qz, we need to extract the exponents. To extract the exponents, the base must be equal. Therefore, we have to construct either a^something = a^something else or c … etc.)

If there’s an equals sign, try to find equivalences
Read over the topic in the book for ideas