Basic Maths For CP

GCD and LCM

The GCD (Greatest Common Divisor) of two numbers is defined as the largest integer that divides both the numbers. For example, 2 is the GCD of 4 and 6. From this concept, follows something called co-primes. Two numbers are said to be co-prime if their GCD is 1. For example, 9 and 8 are co-primes because their GCD is 1.

LCM (Least Common Multiple) is defined as the smallest integer that is divisible by both the numbers. For example, 10 is the LCM of 2 and 5.

Euclid's Algorithm

Consider two numbers a and b. The procedure of Euclid's algorithm can be broken down into a sequence of equations,

a = q₀b + r₀
b = q₁r₀ + r₁
r₀ = q₂r₁ + r₂
r₁ = q₃r₂ + r₃
...

If a is smaller than b, the first step of the algorithm swaps the numbers. For example, if a < b, the initial quotient is zero and the remainder is a. Thus, r_k is smaller than it's predecessor r_k-1.

Since the remainders decrease with every iteration, a remainder r_N must eventually equal 0, at which point this algorithm stops. The final non-zero remainder r_N-1 is the greatest common divisor for a and b.

g = gcd(a, b) = gcd(b, r₀) = gcd(r₀, r₁) = … = gcd(r_N-2, r_N-1) = r_N-1.

For proof of the algorithm, visit here.

A simple implementation of Euclid's GCD algorithm in C++ would be,

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

Once we calculate the GCD of two numbers, we can calculate the LCM very easily.

int lcm(int a,int b)
{
    return (a*b)/gcd(a,b);
}

Combinatronics

Combinatorics is the branch of mathematics that deals with combinations of elements belonging to a finite set in accordance with some constraints.

Principle of Addition

The principle of addition states if one task can be done in m ways and another task which is mutually exclusive of the first task can be done in n ways, then the number of possible ways in which either can be done is m+n.

Principle of Multiplication

The principle of multiplication states that if one task can be done in m ways and another task which is independent of the first task can be done in n ways, after the first task has been performed, then the number of possible ways in which both the tasks can be done is m×n.

Combinations of Objects

Number of ways in which you can select n objects taken r at a time. (Order does not matter.)

ⁿC_r = n! / ( r! (n - r)! )

Permutations of Objects

Number of ways you can order n objects taken r at a time. (Order matters.)

ⁿP_r = n! / (n - r)!

Stars and Bars

Theorem one

For any pair of positive integers n and k, the number of k-tuples of positive integers whose sum is n is equal to the number of (k − 1)-element subsets of a set with n − 1 elements.

Let us say that we need to distribute 7 (n) cookies to 4 (k) kids such that they all have at least 1. We can represent it as stars and bars.

                            			* * * | * | * | * *

Here the 4 kids get 3, 1, 1 and 2 cookies respectively. We can say that we can place (k-1) bars between (n-1) spaces between the stars. Thus, the answer is ⁶C₃.

This can be generalized as ^(n-1)C_(k-1).

Theorem two

For any pair of positive integers n and k, the number of k-tuples of non-negative integers whose sum is n is equal to the number of multisets of cardinality k − 1 taken from a set of size n + 1.

Let us say that we need to distribute 7 cookies among 4 kids where each kid may get none or more cookies. We can represent this situation using stars and bars as well.

		                         	* * * | | * * | * *

Here the 4 kids get 3, 0, 2 and 2 cookies respectively. So there are 10 symbols out of which 3 have to be bars. Thus, the answer is ¹⁰C₃.

This can be generalized as ^(n+k-1)C_(k-1).

Properties of Combinations