Number Theory – II

IntroductionProblems in competitive programming which involve Mathematics are are usually about number theory, or geometry. If you know number theory, that increases your ammo heavily in solving a lot of tougher problems, and helps you in getting a strong hold on a lot of other problems, too.Problems in competitive programming require insight, so just knowing some topics is not enough at all. All of the problems requires more or less math tough. For instance, solving large systems of equations and approximating solutions to differential equations.Set TheoryBefore we proceed, let us get through the some common set operations.Q.) What is a Set?-In mathematics, a set is a collection of distinct objects, considered as an object in its own right.For example, the numbers 2, 4, and 6 are distinct objects when considered separately, but when they are considered collectively they form a single set of size three, written {2,4,6}.Sets are one of the most fundamental concepts in mathematics.A set of polygons in a Venn diagram.SubsetsIf every member of setAis also a member of setB, thenAis said to be asubsetofB, writtenA ⊆ B(also pronounced A is contained in B).Equivalently, we can writeB ⊇ A, read as B is asupersetof A, B includes A, or B contains A.The relationship between sets established by ⊆ is calledinclusionorcontainment.If A is a subset of, but not equal to, B, then A is called a proper subset of B, written A ⊊ B (Ais aproper subsetofB) or B ⊋ A (B is aproper supersetof A).Example:- {1, 3} ⊆ {1, 2, 3, 4}.- {1, 2, 3, 4} ⊆ {1, 2, 3, 4}.The empty set (denoted by the symbol ∅) is a subset of every set and every set is a subset of itself:- ∅ ⊆ A.- A ⊆ A.A is subset of B.Basic operations on SetsThere are several fundamental operations for constructing new sets from given sets.Unions:Two sets can be “added” together. The union of A and B, denoted by A ∪ B, is the set of all things that are members of either A or B.Examples:-{1, 2} ∪ {1, 2} = {1, 2}.-{1, 2} ∪ {2, 3} = {1, 2, 3}.-{1, 2, 3} ∪ {3, 4, 5} = {1, 2, 3, 4, 5}Theunionof A and B, denoted A ∪ B.Some basic properties of unions:-A ∪ B = B ∪ A.-A ∪ (B ∪ C) = (A ∪ B) ∪ C.-A ⊆ (A ∪ B).-A ∪ A = A.-A ∪ ∅ = A.-A ⊆ B if and only if A ∪ B = B.Intersections:A new set can also be constructed by determining which members two sets have “in common”. The intersection of A and B, denoted by A ∩ B, is the set of all things that are members of both A and B. If A ∩ B = ∅, then A and B are said to be disjoint.Examples:-{1, 2} ∩ {1, 2} = {1, 2}.-{1, 2} ∩ {2, 3} = {2}.Theintersectionof A and B, denoted A ∩ B.Some basic properties of intersections:-A ∩ B = B ∩ A.-A ∩ (B ∩ C) = (A ∩ B) ∩ C.-A ∩ B ⊆ A.-A ∩ A = A.-A ∩ ∅ = ∅.-A ⊆ B if and only if A ∩ B = A.Complements:
Two sets can also be “subtracted”. The relative complement of B in A (also called the set-theoretic difference of A and B), denoted by A B (or A − B), is the set of all elements that are members of A but not members of B. Note that it is valid to “subtract” members of a set that are not in the set, such as removing the element green from the set {1, 2, 3}; doing so has no effect.In certain settings all sets under discussion are considered to be subsets of a given universal set U. In such cases, U A is called the absolute complement or simply complement of A, and is denoted by A′.Examples:-{1, 2} {1, 2} = ∅.-{1, 2, 3, 4} {1, 3} = {2, 4}.-If U is the set of integers, E is the set of even integers, and O is the set of odd integers, then U E = E′ = O.Therelative complementof B in A.Thecomplementof A in U.Some basic properties of complements:-A B ≠ B A for A ≠ B.-A ∪ A′ = U.-A ∩ A′ = ∅.-(A′)′ = A.-A A = ∅.-A B = A ∩ B′.-U′ = ∅ and ∅′ = U.Basics of CombinatoricsNOTE:here denotes the number of elements in Set.The basic rules of combinatorics one must remember are:The Rule of Product:The product rule states that if there arepossibilities from setand, then there areways to combine one fromand one from.The Rule of Sum:The sum rule states that if there arepossibilities from setandpossibilities from set, then there areways for eitheroroccur assuming the elements ofandare distinct.Inclusion-Exclusion Formula: (also know as the sieve principle):Generalising the above formula, we get:The reason this works is that summing the sets double counts certain possibilities, namely, those occurring in both sets.Double counting is a slippery aspect of combinatorics, which can make it difficult to solve problems via inclusion-exclusion.These rules can be used for a finite collections of sets.Basics of PermutationPermutation of Distinct Objects:Suppose we have to permutekobjects out ofndistinct objects, then the total number of permutations is given byP = n * (n – 1) * (n – 2) * … * (n – k + 1)which when simplified gives usP = n! / (n – k)!wheren! = n * (n – 1) * (n – 2) * … * 2 * 1.Permutation with Repetition:If we have total n objects, where we have n1 objects of type 1, n2 objects of type 2 and so on upto k.Thusn1+n2+…+nk=n. So the number of permutations of these objects is given by:Combinatorial ObjectsA bijection is a one-to-one mapping between the elements of one set and the elements of another. Counting the size of one of the sets automatically gives you the size of the other set.
Exploiting bijections requires us to have a repertoire of sets which we know how to count, so we can map other objects to them.Combinations without repetition:In combinations we choose a set of elements (rather than an arrangement, as in permutations) so the order doesn’t matter. The number of different k-element subsets (when each element can be chosen only once) of n-element set is:Combinations with repetition:Let’s say we choose k elements from an n-element set, the order doesn’t matter and each element can be chosen more than once. In that case, the number of different combinations is:It is useful to know thatis also the number of integer solutions to this equation:Binary VectorsAccordingly, some knowledge of the basic combinatorial properties of binary vectors is rather important. Let’s have a look at some simple things associated with them:Number of binary vectors of lengthn:2n.Number of binary vectors of lengthnand withk‘1’ issince we just choosekpositions for our ‘1’s.The number of ordered pairs (a, b) of binary vectors, such that the distance between them (k) can be calculated as follows:.The distance between a and b is the number of components that differs in a and b.Recurrence RelationsRecurrence relations make it easy to count a variety of recursively defined structures. Recursively defined structures include trees, lists, well-formed formulae, and divide-and-conquer algorithms – so they lurk wherever computer scientists do.A recurrence relation is an equation which is defined in terms of itself. They are useful because many natural functions are easily expressed as recurrences:Polynomials:Exponentials:Weird but interesting functions otherwise hard to represent:It is often easy to find a recurrence as the answer to a counting problem. Solving the recurrence to get a nice closed form can be somewhat of an art, but as we shall see, computer programs can easily evaluate the value of a given recurrence even without the existence of a nice closed form.Binomial CoefficientsThe most important class of counting numbers are the binomial coefficients, wherecounts the number of ways to choosethings out ofpossibilities.Paths Across a Grid:How many ways are there to travel from the upper-left corner of angrid to the lower-right corner by walking only down and to the right? Every path must consist ofto the right. Every path with a different set of downward moves is distinct, so there aresuch sets/paths.Computation of binomial coefficients can sometimes cause arithmetic overflow in intermediate steps. So a more stable way to perform calculations is using the following formula:.Other Counting SequencesCatalan Numbers:
The recurrence and associated closed formCatalan Numbers and it’s uses.Eulerian Numbers: The Eulerian numberscount the number of permutations of lengthwith exactlyascending sequences or runs. A recurrence can be formulated by considering each permutationof 1,2,…,n-1. There are n places to insert element n, and each either splits an existing run of p or occurs immediately after the last element of an existing run, thus preserving the run count. Thus.Integer Partitions: An integer partition of n is an unordered set of positive integers which add up to n. For example, there are seven partitions of 5, namely, (5), (4, 1), (3, 2), (3, 1, 1), (2, 2, 1), (2, 1, 1, 1) and (1, 1, 1, 1, 1) .The easiest way to count them is to define a functionf(n,k)giving the number of integer partitions ofnwith largest part at mostk. In any acceptable partition the largest part either does or does not reach with limit, sof(n,k)=f(n-k,k)+f(n,k-1). The basic cases aref(1,1)=1andf(n,k)=0whenever k>n.Introduction to ProbabilitiesBasicsWorking with probabilities is much like conducting an experiment. Anoutcomeis the result of an experiment or other situation involving uncertainty. The set of all possible outcomes of a probability experiment is called asample space. Each possible result of such a study is represented by one and only one point in the sample space, which is usually denoted by S.Let’s consider the following experiments:Rolling a die once:
Sample space S = {1, 2, 3, 4, 5, 6}Tossing two coins:
Sample space S = {(Heads, Heads), (Heads, Tails), (Tails, Heads), (Tails, Tails)}We define aneventas any collection of outcomes of an experiment. Thus, an event is a subset of the sample space S. If we denote an event byE, we could say thatE⊆S. If an event consists of a single outcome in the sample space, it is called a simple event. Events which consist of more than one outcome are called compound events.What we are actually interested in is the probability of a certain event to occur, orP(E). By definition,P(E)is a real number between 0 and 1, where 0 denotes the impossible event and 1 denotes the certain event (or the whole sample space)..As stated earlier, each possible outcome is represented by exactly one point in the sample space. This leads us to the following formula:Independent EventsWhen two events are said to be independent of each other, what this means is that the probability that one event occurs in no way affects the probability of the other event occurring.An example of two independent events is as follows; say you rolled a die and flipped a coin. The probability of getting any number face on the die in no way influences the probability of getting a head or a tail on the coin.If two events A and B are independent, then neither can influence the other, and we can write.Conditional ProbabilityConditional probability deals with further defining dependence of events by looking at probability of an event given that some other event first occurs.Conditional probability is denoted by the following:.The above is read as theprobability that B occurs given that A has already occurred.The above is mathematically defined as:.Rules of ProbabilityWhen dealing with more than one event, there are certain rules that we must follow when studying probability of these events. These rules depend greatly on whether the events we are looking at are Independent or dependent on each other.First acknowledge thatMultiplication Rule (A∩B):This region is referred to as ‘A intersection B’ and in probability; this region refers to the event that bothAandBhappen. When we use the wordandwe are referring to multiplication, thusA and Bcan be thought of asAxBor (using dot notation which is more popular in probability)A•BIfAandBaredependentevents, the probability of this event happening can be calculated as shown below:.IfAandBareindependentevents, the probability of this event happening can be calculated as shown below:.Conditional probability for two independent events can be redefined using the relationship above to become:The above is consistent with the definition of independent events, the occurrence of eventAin no way influences the occurrence of eventB, and so the probability that eventBoccurs given that eventBhas occurred is the same as the probability of eventB.Additive Rule (A∪B):In probability we refer to the addition operator (+) asor. Thus when we want to we want to define some event such that the event can be A or B, to find the probability of that event:Thus it follows that:But remember from set theory that and from the way we defined our sample space above:and that:So we can now redefine out event asMutually Exclusive EventsTwo events are called mutually exclusive or disjoint if they do not have any outcome common between them. If the two eventsAandBare mutually exclusive, thenA∩B=ϕ (null set).For three mutually exclusive eventsA,BandC, we haveA∩B∩C=ϕ.Rules of Probability for Mutually Exclusive EventsMultiplication RuleFrom the definition of mutually exclusive events, we should quickly conclude the following:Addition RuleAs we defined above, the addition rule applies to mutually exclusive events as follows:Subtraction RuleFrom the addition rule above, we can conclude that the subtraction rule for mutually exclusive events takes the form:Conditional Probability for Mutually Exclusive EventsWe have defined conditional probability with the following equation:We can redefine the above using the multiplication rule:hence.Bayes’ TheoremIn probability theory and statistics, Bayes’ theorem describes the probability of an event, based on conditions that might be related to the event.Bayes’ theorem is stated mathematically as the following equation:where A and B are events
– P(A) and P(B) are the probabilities of A and B without regard to each other.
– P(A | B), a conditional probability, is the probability of A given that B is true.
– P(B | A), is the probability of B given that A is true.Extended FormOften, for some partition{Aj} of the event space, the event space is given or conceptualized in terms of P(Aj) and P(B | Aj). It is then useful to compute P(B) using the law of total probability:Randomized AlgorithmsWe call randomized algorithms those algorithms that use random numbers to make decisions during their execution. Unlike deterministic algorithms that for a fixed input always give the same output and the same running-time, a randomized algorithm behaves differently from execution to execution. Basically, we distinguish two kind of randomized algorithms:Monte Carlo algorithms: may sometimes produce an incorrect solution – we bound the probability of failure.Las Vegas algorithms: always give the correct solution, the only variation is the running time – we study the distribution of the running time.Read theselecture notesfrom the College of Engineering at UIUC for an example of how these algorithms work.The main goal of randomized algorithms is to build faster, and perhaps simpler solutions. Being able to tackle “harder” problems is also a benefit of randomized algorithms. As a result, these algorithms have become a research topic of major interest and have already been utilized to more easily solve many different problems.Some problems have many possible solutions, where a number of which are also optimal. The classical approach is to check them one by one, in an established order. But it cannot be guaranteed that the optima are uniformly distributed in the solution domain. Thus, a deterministic algorithm may not find you an optimum quickly enough. The advantage of a randomized algorithm is that there are actually no rules to set about the order in which the solutions are checked and for the cases when the optima are clustered together, it usually performs much better.Delving deeper into the Principle of Inclusion-ExclusionThe verbal formulaThe principle of inclusions-exclusions is as follows:To calculate the size of combining several sets, it is necessary to sum the sizes of these setsseparately, then subtract the size of allpairwiseintersections of these sets, add back the sizes of intersections of all possibletriplesof sets, subtract the sizes of the intersectionsof fours, and so on, up to the intersectionof allsets.The formulation in terms of setsIn mathematical form the above verbal formulation is as follows:It can be written more compactly, using the sum of the subsets. We denotethe set whose elements are. Then the principle of inclusions-exclusions takes the form:Formulation using Venn diagramsLet the chart shows three figures,and.Then the area of their Unionis equal to the sum of the areas,andless double-covered areas,andbut with the addition of three covered area:Similarly, it can be summarized to Association ofnfigures.The formulation in terms of probability theoryIf there are(i=1,…,n) events,their probabilities, the probability of their Association (i.e., what will happen to at least one of these events) is:This sum can also be written as the sum of the subsets of a setwhose elements are the events.Proof of principle of inclusions-exclusionsFor the proof it is convenient to use a mathematical formulation in terms of set theory:where, we recall, is the set consisting ofs.We need to prove that any element contained in at least one of the sets, will allow for a formula exactly once. (Note that other elements not contained in any of, can not be considered as absent on the right side of the formula).Consider an arbitrary elementxcontained in exactlyk>=1one of the sets of. We will show that it will be calculated by the formula exactly once.Note that:in those terms, in which, the itemxwill be counted exactlykonce, with a plus sign;in those terms, in which, the itemxwill be taken into account (with a minus sign) exactlyonce becausexit is counted only in those terms that correspond to two sets ofksets containingx;in those terms, in which, the itemxwill be counted exactlyonce, with a plus sign;…in those terms, in which, the itemxwill be counted exactlyonce, with the sign;in those terms, in which, the itemxwill be counted zero times.
Thus, we need to calculate a sum ofbinomial coefficients:Easiest way to calculate this amount is by comparing it to the decomposition in the Newton binomial expression.It can be seen thatx=1the expressionrepresents not that other, as. Therefore, what we wanted to prove.Implementations and Examples:Using the recurrent formulanCr=(n-1)C(r)+(n-1)C(r-1)we can calculate the nCr%non-prime or nCr%prime or simply nCr (for small n only):Check the implementation here.Computing binomial coefficients i.e. N choose R using O(n) precomputation. Use this for large value of N and when (NchooseR)%prime is needed.Check the implementation here.Example: The number of relatively Prime numbers in the given rangeThis is an easy question based on the principle of Inclusion-Exlcusion.Givenand. You want to count the number of integers in the interval, coprime with.Algorithm: Go straight to the inverse — calculate the number of not mutually Prime numbers.Consider all the Prime factors of a number; we denote them using.How many numbers are in the intervaldivisible by? They are:However, if we simply sum these numbers, we get the wrong answer — some numbers will be totaled several times (those that are divided to several). Therefore it is necessary to use the formula of inclusions-exclusions.For example,to iterate over a subset of the set of all’s, calculate their product, and to add or subtract in the formula of inclusions-exclusions next term.The finalimplementationis to count the number of relatively Prime numbers:You can check the main implementation part here.Problems for Practice:Utkarsh and Jumps:This is fairly easy problem based on probability and dynamic-programming.We know that the probability for Utkarsh to be at X=0 is 1.0. Using this we compute the probability of Utkarsh being at that position at some point of time.We use the fact the to reach ith position Utkarsh has 2 choices: either he could reach the ith position from (i-2)th positon or he could reach the ith position from (i-3)th position.So the probability to reach the ith position would be P(i-2) * (p/100.0) + P(i-3) * (1-p/100.0) where P(i) is the probability of Utkarsh being at the ith position.You can check my accepted solution for reference.My Code.Ankit and Race Team:This problem is based upon Combinatorics.We have to find the summation of minimum strengths of student in each group of size k. Naive approach of forming all groups of size k and then computing might give TLE. But we can use the fact that each after sorting all the students in increasing order of their strengths, we would know the exact number of times ith students would be minimum in all the groups in which he/she can be present.So after sorting we find the possible number of selections for ith student such that strength[i] would be minimum which comes out to be(n-i-1)C(k-1). Summing over all i’s we get the answer.You can check my accepted solution for reference.My Code.Tic Tac Toe:Easy level problem on Combinatorics.Roy and Little Mario:Problem can be reduced to implementation of Tribonacci Series.So Random:Given the probability of raining P, we know the probability of no rain will be (1-P) and since Raj will be out for time interval t, so the probability of not raining in this interval would be (1-P)^t.Since, we need the probability of rain in this interval, we subtract probability of no rain in the interval which is (1-P)^t from 1, which is our required answer.Author:Tanmay Chaudhari

News Reporter

Leave a Reply

Your email address will not be published. Required fields are marked *