SOF IMO cheat sheet

Mathematical Reasoning and Logical Ability

• Divisibility rules: 3 and 9 use digit sums; 4 uses the last two digits; 8 uses the last three digits; 11 uses alternating digit sums; 6 requires divisibility by both 2 and 3.

• Sum of first n natural numbers = n(n+1)/2; sum of first n odd numbers = n²; sum of first n squares = n(n+1)(2n+1)/6.

• Remainder theorem: the remainder of P(x) divided by (x − a) equals P(a); for cyclic remainders use the period of powers modulo the divisor.

• Number of trailing zeros of n! = floor(n/5) + floor(n/25) + floor(n/125) + …, counting only positive terms.

• Counting: permutations nPr = n!/(n−r)!; combinations nCr = n!/(r!(n−r)!); arrangements of a multiset = n!/(p!q!…); circular arrangements of n distinct objects = (n−1)!.

• Inclusion–exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|; extend by alternating sums for three or more sets.

• Pigeonhole principle: placing more than k·n objects into n boxes forces at least one box to hold k+1 or more objects.

• Ratio and proportion: if a:b = c:d then ad = bc; for three quantities a:b:c, split a total T into parts T·a/(a+b+c) and so on.

• Handshake/counting pairs: in a group of n people the number of distinct pairs is n(n−1)/2; a graph with n vertices has at most n(n−1)/2 edges.