upsc mathematics optional paper

Since every tree with 2 or more vertices is 2-chromatic. We see that a tree with even no. of vertices will have perfect matching as all vertices with the same color can be grouped together and a matching can be established between the two groups. If the tree has odd number of vertices,then no perfect matching can be established for obvious reason.    [proved ]

Since a tree is connected and has no cycle if one starts coloring any one vertex with a specific color and keeps on coloring every alternate vertex with another color, the entire graph can be colored with only two colors and since there is one and only one path between any two vertices in a tree, no two vertices will have the same color. Hence every Tree with 2 or more vertices is 2-Chromatic.    [Proved]                                                                 FIG (I)                                                                  FIG (II)

Let G be a Bi-partite graph.            So, V(G)=V1 U V2    Color every vertex in V1 by one color and every vertex in V2 by another Colour.    Then, clearly, this coloring is proper. Thus only two colors suffice to color G. so, G is 2 chromatic.    [Proved] image source :Google

Since n different objects are arranged in a circle, the relative positions not the linear positions determine the arrangement . Hence, if one of them is kept fixed, the remaining n-1 can be arranged in (n-1)! ways. This is exactly the number of circular permutations with n distinct objects.

If n pigeons are assigned to m pigeonholes and n>m, then at least one pigeonhole contains two or more pigeons. if there are n pigeonholes occupied by nk+1 pigeons, then there must be at least one pigeonhole occupied by k+1 or more pigeons.

If possible, let the number of prime numbers be finite and equal to n. Now according to the order of increasing magnitude. Let the prime number be  P1, P2, P3,...........Pn Let K=P1.P2.P3...........Pn Now, none of the P's is a division of (K+1) Therefore,(K+1) is either a prime  > Pn or has a prime (>Pn) as a divisor. But this contradicts our assumption, namely Pn is the greatest prime number. Hence numbers of primes are infinite.

Let :          au+bv=1          au=1-bv ............................(i) Squaring both sides of equation (i) : we get,       (au)^2=(1-bv)^2 ........................(ii)       a^2(u^2) + b(2v-bv^2)= 1   so,         gcd(a^2,b)=1 =>  (a^2)K1 + bK2 =1 =>  (bK2)^2=(1-a^2K1)^2 =>  b^2{(K2)^2}=1+a^4(K1)^2 -2(a^2)(K1) =>  b^2(K2)^2 +a^2(2K1-(a^2)(K1)^2)=1 =>  gcd(a^2,b^2)=1  {Proved}

Let all natural numbers be grouped as : {1,2,3,.............m-1,m},{m+1,m+2,m+3,................2m},{2m+1,2m+2,2m+3,...................3m},{3m+1,3m+2,............3m} If the sequence of m consecutive integers begin with 1,evidently the product contains m as a factor and hence is divisible by m. Every other string of m consecutive integers starting with 2 or 3 etc. up to m contains m as a factor and hence is divisible by m. If the sequence of m consecutive integers starting with 2m+1 or 2m+2 upto 2m contains 2m as a factor and hence is divisible by m. The argument is similar for every other strings of m consecutive integers. Hence,this proves that the product of any m consecutive integers is divisible by m.

 The duality theorem states that: • if the primal problem has an optimal solution, then so has the dual, and zP = zD; 1 • if the primal problem is unbounded, then the dual is infeasible; • if the primal problem is infeasible, then the dual is either infeasible or unbounded. Consider the following primal and dual problems : Maximize zP = c T x     Minimize zD = b T y subject to x ≥ 0, s ≥ 0    subject to y ≥ 0, t ≥ 0 Ax + s = b        AT y − t = c For optimal solutions, complementary slackness states that yisi = 0 (i = 1, . . . , m), tjxj = 0 (j = 1, . . . , n).  For feasible solutions of the primal and the dual, we have cj = 1, . . . , n zP = c T x = (y TA − t T )x = y T (b − s) − t T x = zD − y T s − t T For an optimal solution of the primal and dual, zP = zD  so , y T s + t T x = 0 Since variables are non-negative this implies that : yisi = 0 i = 1, . . . , m  tjxj = 0 j = 1, . . . , n

Section 1   Engineering Mathematics Discrete Mathematics:  Propositional and first order logic. Sets, relations, functions, partial orders and lattices. Groups. Graphs: connectivity, matching, coloring. Combinatorics: counting, recurrence relations, generating functions. Linear Algebra: Matrices, determinants, system of linear equations, eigenvalues and eigenvectors, LU decomposition. Calculus: Limits, continuity and differentiability. Maxima and minima. Mean value theorem. Integration. Probability: Random variables. Uniform, normal, exponential, poisson and binomial distributions. Mean, median, mode and standard deviation.Conditional probability and Bayes theorem.  Computer Science and Information Technology : Section 2:  Digital Logic Boolean algebra. Combinational and sequential circuits. Minimization. Number representations and computer arithmetic (fixed and floating point).   Section 3:  Computer Organization and Arc...