(3) Foreveryrealnumber xsuchthat x = 0andforeverysubset Aof R

S.-T.Yau College Student Mathematics Contests 2011Analysis and Differential EquationsIndividual2:30–5:00pm,July 9,2011(Please select 5problems to solve)1.a)Compute the integral: ∞−∞x cos xdx (x 2+1)(x 2+2),b)Show that there is a continuous function f :[0,+∞)→(−∞,+∞)such that f ≡0and f (4x )=f (2x )+f (x ).2.Solve the following problem: d 2u dx 2−u (x )=4e −x ,x ∈(0,1),u (0)=0,dudx(0)=0.3.Find an explicit conformal transformation of an open set U ={|z |>1}\(−∞,−1]to the unit disc.4.Assume f ∈C 2[a,b ]satisfying |f (x )|≤A,|f(x )|≤B for each x ∈[a,b ]and there exists x 0∈[a,b ]such that |f (x 0)|≤D ,then |f (x )|≤2√AB +D,∀x ∈[a,b ].5.Let C ([0,1])denote the Banach space of real valued continuous functions on [0,1]with the sup norm,and suppose that X ⊂C ([0,1])is a dense linear subspace.Suppose l :X →R is a linear map (not assumed to be continuous in any sense)such that l (f )≥0if f ∈X and f ≥0.Show that there is a unique Borel measure µon [0,1]such that l (f )= fdµfor all f ∈X .6.For s ≥0,let H s (T )be the space of L 2functions f on the circle T =R /(2πZ )whose Fourier coefficients ˆf n = 2π0e−inx f (x )dx satisfy Σ(1+n 2)s ||ˆf n |2<∞,with norm ||f ||2s =(2π)−1Σ(1+n 2)s |ˆf n |2.a.Show that for r >s ≥0,the inclusion map i :H r (T )→H s (T )is compact.b.Show that if s >1/2,then H s (T )includes continuously into C (T ),the space of continuous functions on T ,and the inclusion map is compact.1S.-T.Yau College Student Mathematics Contests2011Geometry and TopologyIndividual9:30–12:00am,July10,2011(Please select5problems to solve)1.Suppose M is a closed smooth n-manifold.a)Does there always exist a smooth map f:M→S n from M into the n-sphere,such that f is essential(i.e.f is not homotopic to a constant map)?Justify your answer.b)Same question,replacing S n by the n-torus T n.2.Suppose(X,d)is a compact metric space and f:X→X is a map so that d(f(x),f(y))=d(x,y)for all x,y in X.Show that f is an onto map.3.Let C1,C2be two linked circles in R3.Show that C1cannot be homotopic to a point in R3\C2.4.Let M=R2/Z2be the two dimensional torus,L the line3x=7y in R2,and S=π(L)⊂M whereπ:R2→M is the projection map. Find a differential form on M which represents the Poincar´e dual of S.5.A regular curve C in R3is called a Bertrand Curve,if there existsa diffeomorphism f:C→D from C onto a different regular curve D in R3such that N x C=N f(x)D for any x∈C.Here N x C denotes the principal normal line of the curve C passing through x,and T x C will denote the tangent line of C at x.Prove that:a)The distance|x−f(x)|is constant for x∈C;and the angle made between the directions of the two tangent lines T x C and T f(x)D is also constant.b)If the curvature k and torsionτof C are nowhere zero,then there must be constantsλandµsuch thatλk+µτ=16.Let M be the closed surface generated by carrying a small circle with radius r around a closed curve C embedded in R3such that the center moves along C and the circle is in the normal plane to C at each point.Prove thatMH2dσ≥2π2,and the equality holds if and only if C is a circle with radius √2r.HereH is the mean curvature of M and dσis the area element of M.1S.-T.Yau College Student Mathematics Contests 2011Algebra,Number Theory andCombinatoricsIndividual2:30–5:00pm,July 10,2011(Please select 5problems to solve)For the following problems,every example and statement must be backed up by proof.Examples and statements without proof will re-ceive no-credit.1.Let K =Q (√−3),an imaginary quadratic field.(a)Does there exists a finite Galois extension L/Q which containsK such that Gal(L/Q )∼=S 3?(Here S 3is the symmetric group in 3letters.)(b)Does there exists a finite Galois extension L/Q which containsK such that Gal(L/Q )∼=Z /4Z ?(c)Does there exists a finite Galois extension L/Q which containsK such that Gal(L/Q )∼=Q ?Here Q is the quaternion group with 8elements {±1,±i,±j,±k },a finite subgroup of the group of units H ×of the ring H of all Hamiltonian quaternions.2.Let f be a two-dimensional (complex)representation of a finite group G such that 1is an eigenvalue of f (σ)for every σ∈G .Prove that f is a direct sum of two one-dimensional representations of G3.Let F ⊂R be the subset of all real numbers that are roots of monic polynomials f (X )∈Q [X ].(1)Show that F is a field.(2)Show that the only field automorphisms of F are the identityautomorphism α(x )=x for all x ∈F .4.Let V be a finite-dimensional vector space over R and T :V →V be a linear transformation such that(1)the minimal polynomial of T is irreducible;(2)there exists a vector v ∈V such that {T i v |i ≥0}spans V .Show that V contains no non-trivial proper T -invariant subspace.5.Given a commutative diagramA →B →C →D →E↓↓↓↓↓A →B →C →D →E1Algebra,Number Theory and Combinatorics,2011-Individual2 of Abelian groups,such that(i)both rows are exact sequences and(ii) every vertical map,except the middle one,is an isomorphism.Show that the middle map C→C is also an isomorphism.6.Prove that a group of order150is not simple.S.-T.Yau College Student Mathematics Contests 2011Applied Math.,Computational Math.,Probability and StatisticsIndividual6:30–9:00pm,July 9,2011(Please select 5problems to solve)1.Given a weight function ρ(x )>0,let the inner-product correspond-ing to ρ(x )be defined as follows:(f,g ):= baρ(x )f (x )g (x )d x,and let f :=(f,f ).(1)Define a sequence of polynomials as follows:p 0(x )=1,p 1(x )=x −a 1,p n (x )=(x −a n )p n −1(x )−b n p n −2(x ),n =2,3,···wherea n =(xp n −1,p n −1)(p n −1,p n −1),n =1,2,···b n =(xp n −1,p n −2)(p n −2,p n −2),n =2,3,···.Show that {p n (x )}is an orthogonal sequence of monic polyno-mials.(2)Let {q n (x )}be an orthogonal sequence of monic polynomialscorresponding to the ρinner product.(A polynomial is called monic if its leading coefficient is 1.)Show that {q n (x )}is unique and it minimizes q n amongst all monic polynomials of degree n .(3)Hence or otherwise,show that if ρ(x )=1/√1−x 2and [a,b ]=[−1,1],then the corresponding orthogonal sequence is the Cheby-shev polynomials:T n (x )=cos(n arccos x ),n =0,1,2,···.and the following recurrent formula holds:T n +1(x )=2xT n (x )−T n −1(x ),n =1,2,···.(4)Find the best quadratic approximation to f (x )=x 3on [−1,1]using ρ(x )=1/√1−x 2.1Applied Math.Prob.Stat.,2011-Individual 22.If two polynomials p (x )and q (x ),both of fifth degree,satisfyp (i )=q (i )=1i,i =2,3,4,5,6,andp (1)=1,q (1)=2,find p (0)−q (0)y aside m black balls and n red balls in a jug.Supposes 1≤r ≤k ≤n .Each time one draws a ball from the jug at random.1)If each time one draws a ball without return,what is the prob-ability that in the k -th time of drawing one obtains exactly the r -th red ball?2)If each time one draws a ball with return,what is the probability that in the first k times of drawings one obtained totally an odd number of red balls?4.Let X and Y be independent and identically distributed random variables.Show thatE [|X +Y |]≥E [|X |].Hint:Consider separately two cases:E [X +]≥E [X −]and E [X +]<E [X −].5.Suppose that X 1,···,X n are a random sample from the Bernoulli distribution with probability of success p 1and Y 1,···,Y n be an inde-pendent random sample from the Bernoulli distribution with probabil-ity of success p 2.(a)Give a minimum sufficient statistic and the UMVU (uniformlyminimum variance unbiased)estimator for θ=p 1−p 2.(b)Give the Cramer-Rao bound for the variance of the unbiasedestimators for v (p 1)=p 1(1−p 1)or the UMVU estimator for v (p 1).(c)Compute the asymptotic power of the test with critical region |√n (ˆp 1−ˆp 2)/ 2ˆp ˆq |≥z 1−αwhen p 1=p and p 2=p +n −1/2∆,where ˆp =0.5ˆp 1+0.5ˆp 2.6.Suppose that an experiment is conducted to measure a constant θ.Independent unbiased measurements y of θcan be made with either of two instruments,both of which measure with normal errors:fori =1,2,instrument i produces independent errors with a N (0,σ2i )distribution.The two error variances σ21and σ22are known.When ameasurement y is made,a record is kept of the instrument used so that after n measurements the data is (a 1,y 1),...,(a n ,y n ),where a m =i if y m is obtained using instrument i .The choice between instruments is made independently for each observation in such a way thatP (a m =1)=P (a m =2)=0.5,1≤m ≤n.Applied Math.Prob.Stat.,2011-Individual 3Let x denote the entire set of data available to the statistician,in this case (a 1,y 1),...,(a n ,y n ),and let l θ(x )denote the corresponding log likelihood function for θ.Let a =n m =1(2−a m ).(a)Show that the maximum likelihood estimate of θis given by ˆθ= n m =11/σ2a m −1 n m =1y m /σ2a m.(b)Express the expected Fisher information I θand the observedFisher information I x in terms of n ,σ21,σ22,and a .What hap-pens to the quantity I θ/I x as n →∞?(c)Show that a is an ancillary statistic,and that the conditional variance of ˆθgiven a equals 1/I x .Of the two approximations ˆθ·∼N (θ,1/I θ)and ˆθ·∼N (θ,1/I x ),which (if either)would you use for the purposes of inference,and why?S.-T.Yau College Student Mathematics Contests 2011Analysis and Differential EquationsTeam9:00–12:00am,July 9,2011(Please select 5problems to solve)1.Let H 2(∆)be the space of holomorphic functions in the unit disk ∆={|z |<1}such that ∆|f |2|dz |2<∞.Prove that H 2(∆)is a Hilbert space and that for any r <1,the map T :H 2(∆)→H 2(∆)given by T f (z ):=f (rz )is a compact operator.2.For any continuous function f (z )of period 1,show that the equation dϕdt=2πϕ+f (t )has a unique solution of period 1.3.Let h (x )be a C ∞function on the real line R .Find a C ∞function u (x,y )on an open subset of R containing the x -axis such that u x +2u y =u 2and u (x,0)=h (x ).4.Let S ={x ∈R ||x −p |≤c/q 3,for all p,q ∈Z ,q >0,c >0},show that S is uncountable and its measure is zero.5.Let sl (n )denote the set of all n ×n real matrices with trace equal to zero and let SL (n )be the set of all n ×n real matrices with deter-minant equal to one.Let ϕ(z )be a real analytic function defined in a neighborhood of z =0of the complex plane C satisfying the conditions ϕ(0)=1and ϕ (0)=1.(a)If ϕmaps any near zero matrix in sl (n )into SL (n )for some n ≥3,show that ϕ(z )=exp(z ).(b)Is the conclusion of (a)still true in the case n =2?If it is true,prove it.If not,give a counterexample.e mathematical analysis to show that:(a)e and πare irrational numbers;(b)e and πare also transcendental numbers.1S.-T.Yau College Student Mathematics Contests2011Applied Math.,Computational Math.,Probability and StatisticsTeam9:00–12:00am,July9,2011(Please select5problems to solve)1.Let A be an N-by-N symmetric positive definite matrix.The con-jugate gradient method can be described as follows:r0=b−A x0,p0=r0,x0=0FOR n=0,1,...αn= r n 22/(p TnA p n)x n+1=x n+αn p n r n+1=r n−αn A p nβn=−r Tk+1A p k/p TkA p kp n+1=r n+1+βn p nEND FORShow(a)αn minimizes f(x n+αp n)for allα∈R wheref(x)≡12x T A x−b T x.(b)p Ti r n=0for i<n and p TiA p j=0if i=j.(c)Span{p0,p1,...,p n−1}=Span{r0,r1,...,r n−1}≡K n.(d)r n is orthogonal to K n.2.We use the following scheme to solve the PDE u t+u x=0:u n+1 j =au nj−2+bu nj−1+cu njwhere a,b,c are constants which may depend on the CFL numberλ=∆t ∆x .Here x j=j∆x,t n=n∆t and u njis the numerical approximationto the exact solution u(x j,t n),with periodic boundary conditions.(i)Find a,b,c so that the scheme is second order accurate.(ii)Verify that the scheme you derived in Part(i)is exact(i.e.u nj =u(x j,t n))ifλ=1orλ=2.Does this imply that the scheme is stable forλ≤2?If not,findλ0such that the scheme is stable forλ≤λ0. Recall that a scheme is stable if there exist constants M and C,which are independent of the mesh sizes∆x and∆t,such thatu n ≤Me CT u0for all∆x,∆t and n such that t n≤T.You can use either the L∞norm or the L2norm to prove stability.1Applied Math.Prob.Stat.,2011-Team2 3.Let X and Y be independent random variables,identically dis-tributed according to the Normal distribution with mean0and variance 1,N(0,1).(a)Find the joint probability density function of(R,),whereR=(X2+Y2)1/2andθ=arctan(Y/X).(b)Are R andθindependent?Why,or why not?(c)Find a function U of R which has the uniform distribution on(0,1),Unif(0,1).(d)Find a function V ofθwhich is distributed as Unif(0,1).(e)Show how to transform two independent observations U and Vfrom Unif(0,1)into two independent observations X,Y fromN(0,1).4.Let X be a random variable such that E[|X|]<∞.Show thatE[|X−a|]=infE[|X−x|],x∈Rif and only if a is a median of X.5.Let Y1,...,Y n be iid observations from the distribution f(x−θ), whereθis unknown and f()is probability density function symmetric about zero.Suppose a priori thatθhas the improper priorθ∼Lebesgue(flat) on(−∞,∞).Write down the posterior distribution ofθ.Provides some arguments to show that thisflat prior is noninforma-tive.Show that with the posterior distribution in(a),a95%probability interval is also a95%confidence interval.6.Suppose we have two independent random samples{Y1,i=1,...,n} from Poisson with(unknown)meanλ1and{Y i,i=n+1,...,2n}from Poisson with(unknown)meanλ2Letθ=λ1/(λ1+λ2).(a)Find an unbiased estimator ofθ(b)Does your estimator have the minimum variance among all un-biased estimators?If yes,prove it.If not,find one that has theminimum variance(and prove it).(c)Does the unbiased minimum variance estimator you found at-tain the Fisher information bound?If yes,show it.If no,whynot?S.-T.Yau College Student Mathematics Contests2011Geometry and TopologyTeam9:00–12:00am,July9,2011(Please select5problems to solve)1.Suppose K is afinite connected simplicial complex.True or false:a)Ifπ1(K)isfinite,then the universal cover of K is compact.b)If the universal cover of K is compact thenπ1(K)isfinite.pute all homology groups of the the m-skeleton of an n-simplex, 0≤m≤n.3.Let M be an n-dimensional compact oriented Riemannian manifold with boundary and X a smooth vectorfield on M.If n is the inward unit normal vector of the boundary,show thatM div(X)dV M=∂MX·n dV∂M.4.Let F k(M)be the space of all C∞k-forms on a differentiable man-ifold M.Suppose U and V are open subsets of M.a)Explain carefully how the usual exact sequence0−→F(U∪V)−→F(U)⊕F V)−→F(U∩V)−→0 arises.b)Write down the“long exact sequence”in de Rham cohomology as-sociated to the short exact sequence in part(a)and describe explicitly how the mapH kdeR (U∩V)−→H k+1deR(U∪V)arises.5.Let M be a Riemannian n-manifold.Show that the scalar curvature R(p)at p∈M is given byR(p)=1vol(S n−1)S n−1Ric p(x)dS n−1,where Ric p(x)is the Ricci curvature in direction x∈S n−1⊂T p M, vol(S n−1)is the volume of S n−1and dS n−1is the volume element of S n−1.1Geometry and Topology,2011-Team2 6.Prove the Schur’s Lemma:If on a Riemannian manifold of dimension at least three,the Ricci curvature depends only on the base point but not on the tangent direction,then the Ricci curvature must be constant everywhere,i.e.,the manifold is Einstein.S.-T.Yau College Student Mathematics Contests 2011Algebra,Number Theory andCombinatoricsTeam9:00–12:00pm,July 9,2011(Please select 5problems to solve)For the following problems,every example and statement must be backed up by proof.Examples and statements without proof will re-ceive no-credit.1.Let F be a field and ¯Fthe algebraic closure of F .Let f (x,y )and g (x,y )be polynomials in F [x,y ]such that g .c .d .(f,g )=1in F [x,y ].Show that there are only finitely many (a,b )∈¯F×2such that f (a,b )=g (a,b )=0.Can you generalize this to the cases of more than two-variables?2.Let D be a PID,and D n the free module of rank n over D .Then any submodule of D n is a free module of rank m ≤n .3.Identify pairs of integers n =m ∈Z +such that the quotient rings Z [x,y ]/(x 2−y n )∼=Z [x,y ]/(x 2−y m );and identify pairs of integers n =m ∈Z +such that Z [x,y ]/(x 2−y n )∼=Z [x,y ]/(x 2−y m ).4.Is it possible to find an integer n >1such that the sum1+12+13+14+ (1)is an integer?5.Recall that F 7is the finite field with 7elements,and GL 3(F 7)is the group of all invertible 3×3matrices with entries in F 7.(a)Find a 7-Sylow subgroup P 7of GL 3(F 7).(b)Determine the normalizer subgroup N of the 7-Sylow subgroupyou found in (a).(c)Find a 2-Sylow subgroup of GL 3(F 7).6.For a ring R ,let SL 2(R )denote the group of invertible 2×2matrices.Show that SL 2(Z )is generated by T = 1101 and S = 01−10 .What about SL 2(R )?1。

Chapter3Random V ariables and UnivariateDistributionsKey words:continuous random variable,cumulative distribution function,discrete random variable,probability density function,probability mass function,random variable,moments, moment generating function,mean,variance,skewness,kurtosis.Abstract:In this and next chapters,we will use advanced calculus to formalize the probability theory introduced in Chapter2.The use of mathematics enables us to investigate probability more deeply.A number of quantitative-oriented probability concepts will be introduced.In this chapter,we…rst introduce the concept of a random variable and characterize the distributions of a random variable and functions of a random variable by the cumulative distribution function,the probability mass function or probability density function,and the moment generating function and the characteristic function.We also introduce a class of moments as well as their relationships with a distribution.This chapter focuses on univariate distribution.3.1:Random Variables and Distribution FunctionsRead Sections1.4–1.6Review:Recall that B;Borel…eld(or -algebra),is a collection satisfying the following conditions:(i) 2B;(ii)If A2B then A c2B;(iii)If A j2B;j=1;2;:::;then[1j=1A j2B:When B is a -algebra,we call the pair(S;B)a measurable space.Also,a probability function is a mapping from B to R satisfying the following conditions(i).P(A) 0for all A2B;(ii).P(S)=1;(iii).If A j2B;j=1;2; ;are pairwise mutually exclusive,then P([1j=1A j)=P1j=1P(A j): De…nition[Probability Space]:Suppose P is a probability measure de…ned on the measurable space(S;B).Then(S;B;P)is a probability space.Remark:The space S and the associated -algebra di¤er according to the natures of random experiments.Example:A Coin is thrown.S=f H;T g:Example:Bush running for the next term of Presidency.S=f Win,Fail}.Example:Three coins are thrown.S=f HHH;HHT;HT H;HT T;T HH;T HT;T T H;T T T g.: Event A={two heads appear}=f HHT;HT H;T HH g:Then P(A)=38Example:Throwing a die,S=f1;2;3;4;5;6g.Remark:It is inconvenient to work with di¤erent sample spaces.In particular,a sample spaceS may be tedious to describe if the elements of S are not numbers.In many experiments,it is easier to deal with a summary variable than with the original probability structure.To developa uni…ed probability theory,we need to unify di¤erent sample spaces.For this purpose,we needto formulate a rule,or a set of rules,by which elements of S may be represented by numbers. This can be achieved by assigning a real number to each possible outcome in S.In other words, we construct a mapping from the original sample space S to a new sample space ,a set of real numbers.This transformations is called a random variable.A random variable is a function de…ned on a sample space.Its purpose is to facilitate the solution of a problem by transferring considerations to a new probability space with a simpler or more convenient structure.On the other hand,in many applications,we are interested only in a particular aspect of the outcomes of experiments,rather than all outcomes.For example,when we roll a number of dice, we are usually interested in the total,and not in the outcome of each dice.In such applications,a suitably de…ned random variables will serve for our purpose.De…nition[Random Variable]A random variable(r.v.)X( )is a B-measurable mapping(or point function)from the sample space S to the real line R such that to each outcome s2S there exists a corresponding unique real number,X(s):The collection of all possible values that the random variable X can take,also called the range of X( );constitutes a new sample space, denoted as .Example:S=f H;T g.De…ne X(H)=1and X(T)=0:Then =f1;0g:Example:S=f Win,Fail}:De…ne X(W in)=1and X(F ail)=0:Then =f1;0g:Remark:It is not necessary to have the same number of basic outcomes for S and :In some cases,it is more convenient to work with a suitably de…ned new sample space .Example:S=f T T T;T T H;T HT;HT T;HHT;HT H;T HH;HHH g.De…ne X(T;T;T)= 0;X(T;T;H)=1;X(T;H;T)=1;X(H;T;T)=1;X(H;H;T)=2;X(H;T;H)=2;X(T;H;H)= 2;X(H;H;H)=3:Then =f0;1;2;3g:Intuition:X(s)is the number of heads.Therefore,P(X=3)=P(A);where A=f s in S:X(s)=3g;denotes the probability that exactly three heads occur in the experiment.Example:S=f1;2;3;4;5;6g:De…ne X(s)=s:Then =S:Identity transformation.Need not change S because S consists of numbers already.Remark:The transformation need not be1 1.Question:Suppose the number of basic outcomes in S is countable.(a)Is it possible that the number of basic outcomes in is larger than that of S?(b)Smaller than that of S?Example:S=f s: 1<s<1g:X(s)=1if s>0and X(s)=0if s 0:Remark:This is useful for directional forecasts or investigation of asymmetric business cycles (e.g.,Neftci1984,“Are Economic Time Series Asymmetric Over the Business Cycles?”,JPE92, 307-328).Remark:The above de…nition of a random variable is limited to real-valued functions.This does not impose any restriction.We can de…ne complex-valued random variables by looking upon the real and imaginary parts separately as two real-valued random variables.Remark:In this book,we use a capital letter X to denote a random variable,and use a lowercase letter x to denote its realization.In de…ning a random variable X,we have also de…ned a new sample space (the range of the random variable X).The probability function de…ned on the original sample space S can be used for the random variable X.Suppose we have a sample space with…nite basic outcomesS=f s1;:::;s n gwith a probability function P( )and we de…ne a random variable X with the range=f x1;:::;x m g:We can de…ne the probability function P X( )on in the following way:P X(x i) P(X=x i)=P(C);where C is an event in S such thatC=f s2S:X(s)=x i g:Note that the left hand side,P X( );is an induced probability function on ;de…ned in terms of the original probability function P( ):This can be applied to the case where is countable. For an uncountable ;we can still de…ne the induced probability function,P X( );in a similar manner.More generally,for any set A2B ;where B is a Borel…eld generated from ;P X(A) P(X2A)=P(C)=P[s2S:X(s)2A];where C=f s2S:X(s)2A g is the set of basic outcomes in the original sample space S for which the random variable X has a value that is in A:Thus,a random variable X is a function that carries the probability from a sample space S to a space of real numbers.In this sense, with A2 ;the probability P X(A)is often called an induced probability function.It can be shown that when S is a countable sample space,the induced probability function P X( )satis…es the three axioms of the probability function.Remark:When S is continuous(e.g.S=R);we cannot use the above expressions immediately unless we can be sure that the set C=f s2S:X(s)2A g belongs to the -algebra B.Whether or not C2B depends on,of course,the form of mapping X( ).Question:What functional form X( )will ensure C2B?Or what condition on X( )will ensure that the set C is in B?The following condition ensures that C always belongs to B:De…nition[Measurable Function]:A function X:S!R is B-measurable(or measurable with respect to the sigma…eld B generated from S)if for every real number a;the set[s2S: X(s) a]2B:Dice S=f1;2;3;4;5;6g;=S;X(s)=s:Remarks:(i)When a function X is B-measurable,we can express the probability of an event,say "X a";in terms of the probability of event C in B;where C=f s2S:X(s) a g:In other words,the measurable function ensures that P(X2A)is always well-de…ned for all subsets A on B .If X( )is not a measurable function,then there exist subsets on the Boreal…eld in R for which probabilities are not de…ned.However,constructing such sets are very complicated.(ii)In what follows,we assume that the random variable X is always measurable with respect to some -algebra of S.In fact,in the advanced probability theory,the term“random variable”is restricted to be a B-measurable function from S!R:Theorem:Let B be a -algebra associated with sample space S.Let f and g be B-measurable real valued functions,and c be a real number.Then the functions c f;f+g;f g and j f j are also B-measurable.Proof:See White[1984,Proposition3.23],who says“see Bartle[1966,Lemma2.6]”. Remark:If one starts with function X(s)and Y(s)that are measurable mappings from S to ;then new functions Z(s)can be constructed by ordinary algebraic operations such as Z(s)=aX(s);Z(s)= X(s)+Y(s);Z(s)=X(s)Y(s);and Z(s)=X(s)=Y(s)are measurable.If one has a sequence X1(s);X2(s);:::of measurable functions and constructs Z(s)through limiting operations such as Z(s)=lim i!1Z i(s)or Z(s)=sup1 i<1f Z i(s)g;then Z(s)is measurable.A proof of these claims is not particularly di¢cult,but is beyond this course.All that is important for our purposes is to know that standard functions are measurable and that any standard sequence of countable operations on such functions will not destroy measurability.It can be shown that the induced probability P X( )satis…es the de…nition of a probability function.First,conditions(i)and(ii)are easily veri…ed by observing,for C=f s2S:X(s)2 A g;thatP X(A)=P(C) 0;and that S=f s2S and X(s)= g requiresP X( )=P(S)=1:In discussing condition(iii),let us restrict our attention to two mutually exclusive events A1and A2in :Here,P X(A1[A2)=P(C);where C=f s2S:X(s)2A1[A2g:However,we haveC=f s2S:X(s)2A1g[f s2S:X(s)2A2g;or for brevity,C=C1[C2:But C1and C2are disjoint sets in S.This must be so,for if some s were common,say s0;then X(s0)2A1and X(s0)2A2:That is,the same number X(s0) belongs to both A1and A2.This is a contradiction because A1and A2are disjoint sets in . Accordingly,P(C)=P(C1)+P(C2):However,by de…nition,P(C1)=P X(A1)and P(C2)=P X(A2);and thusP X(A1[A2)=P X(A1)+P X(A2):This is the condition(iii)for two disjoint sets when de…ning a probability function. Remark:The reason that we need the random variable X to be a Borel measurable function is to assure that we can…nd the induced probabilities on the sigma…eld B X generated from the subsets of :We need this requirement throughout this course for every function that is a random variable.Remark:P X( )is the probability function de…ned on the Borel…eld B X generated from :In many cases below,we will drop the subscript X and simply write P X(A)=P(A)for A B X:Example(Three Coins thrown,continued):S=f HHH;:::;T T T g; =f0;1;2;3g: P[0 X 1]=P f s2S:0 X(s) 1g:A=f s2S:0 X(s) 1g=f T T T;T T H;T HT;HT T g:P[0 X 1]=P(A)=1=8+1=8+1=8+1=8:Question:How to characterize a random variable X?Answer:Of course,we can use the probability function P X(A):Below,we introduce an alter-native function to characterize the distribution of X:Cumulative Distribution Function(CDF)of a random variable X is de…ned as:F X(x)=P(X x)for all x2R:Remark:The subscript X of the F function indicates that it is the CDF of the random variable X:Properties of F X(x):(i)lim x! 1F X(x)=0;lim x!+1F X(x)=1:(ii)F X(x)is non-decreasing,i.e.for any x1<x2;F X(x1) F X(x2).(iii)F X(x)is right-continuous,i.e.for all x and >0;lim!0+[F X(x+ ) F X(x)]=0:Implications and interpretations:0 F X(x) 1:Theorem:Let a<b:ThenP(a<X b)=F X(b) F X(a):Theorem:P(X>b)=1 F X(b):Example:If F(x)is a cumulative distribution function(cdf),is G(x)=1 F( x)a cdf too? Solution:(i)G( 1)=1 F[ ( 1)]=1 F(+1)=1 1=0;G(+1)=1 F( 1)=1 0=1:(ii)x1<x2:G(x1)=1 F( x1);G(x2)=1 F( x2):G(x2) G(x1)=[1 F( x2)] [1 F( x1)]=F( x1) F( x2)0:(iii)No.G(x)is left-continuous but not necessarily right-continuous.Example:Is P(X b)=1 F X(b)?Solution:P(X b)=P(X>b)+P(X=b)=1 F X(b)+P(X=b):Example:Suppose F1(x)and F2(x)are two cumulative distribution functions,isF(x)=pF1(x)+(1 p)F2(x)a cdf,where p is a constant.Remark:In application,p may depend on economic variables.An example of p=p(Z)isp(Z)=11+exp( 0Z);where Z is the state variable of economy,taking0with prob p and taking1with prob 1 p:This is a mixture distribution.A mixture of two distributions can provide a great deal of ‡exibility.Answer:Yes if0 p 1:Remark:When proper conditions on p are imposed,this is called a mixture of distributions.A well-known example in econometrics is the so-called Markov regime-switching model in which p depends on a state variable characterizing the business cycles(cf.Hamilton1994,Time Series Analysis).Remark:The de…nition of the cdf makes it clear that the probability function P X( )determines the cdf F X( ):It is true,although not so obvious,that a probability function P X( )can be found from a cdf F X( ):That is,P X( )and F X( )give the same information about the distribution of probability,and which function is used is a matter of convenience.Question:Why does the CDF F X(x)can characterize the probability distribution of random variable X?De…nition:Two random variables X and Y are identically distributed if for every set in B1;where B1is the smallest -…eld containing all the intervals of real numbers of the form (a;b);[a;b);(a;b];and[a;b];one hasP(X2A)=P(Y2A):Remark:Identical distribution does not imply X=Y:Theorem:Two random variables X and Y are identically distributed if and only ifF X(u)=F Y(u)for all 1<u<1:3.2Discrete Random Variable(D.R.V.)Read Sections3.1and3.2De…nition[Discrete v.s.Continuous Random Variables(R.V.)]:If a random variable X can only take a countable number of values,then X is called a discrete random variable(d.r.v.). Otherwise,if it can take any value in an interval,it is called a continuous random variable(c.r.v.). Examples:=f1;2;3;4;5;6g:=f0;1;2;3;::::g;e.g.,Poisson distribution.=R:=[0;1]:Prob(Mass)Function(pmf)of a discrete r.v.X is de…ned asf X(x)=P(X=x)for all x2R:Properties of pf/pmf:(i)0 f X(x) 1for all x2R:(ii)P x f X(x)=1:De…nition[Support of X]:The collection of the points at which a d.r.v.X has a positive probability is called the support of X;denoted asSupport(X)=f x2R:f X(x)>0g:Remark:Although f X(x)is de…ned on x2R;it su¢ces to know the support of a d.r.v.X and the probabilities of all points in the support.Geometric representation:Probability histogram.For example,it can show whether there are more than one mode,or“high points”.A mode is a bar in a histogram that is surrounded by bars of lower frequency.A histogram exhibiting two modes is said to be bimodal,and one having more than two modes is said to be multimodal.Question:Given the probability function,What can we obtain?Cumulative Distribution Function of a d.r.v.X isF X(x)=P(X x)=X y x f X(y)for any x2R;where the summation is over all values y that are less than or equal to x.Remark:The argument of F X( )runs continuously from 1to+1;i.e.x2( 1;1):It is di¤erent from the support of X:Example1:Uniform Distribution U(N);X12f X1=N1=NFind the distribution function.Solution:Case1:x<1.Then f X x g is ;andF X(x)=X x i x f X(x i)=0:How many x0i s that are less than or equal to x?“X x"= :Case 2:1 x <2.Then “X x ”=f 1g ;andF X (x )=X x i xf X (x i )=f X (1)=1=N:Case 3:2 x <3:Then “X x ”=f 1;2g ;and F X (x )=2=N:Case j :j 1 x <j;j N:Then “X x ”=f 1;2;3; ;j 1g ;andF X (x )=(j 1)=N:Case N +1:x N:Then"X x "=f 1;2;3; ;N g ;andF X (x )=1:In summary,F X (x )=8<:0x <1j=N j x <j +1;1 j <N;j 2Z 1x NRemark:F X (x )is a function on R ;so it is incomplete if you just compute F X (x )on x =1;2;3;4; ;N:Conclusion:Given f X (x );we can obtain F X (x ):Question :Suppose X is a d.r.v.that takes values of x 1<x 2<x 3< ;and its distribution function F X (x )is given,is it possible to recover f X (x )from F X (x )?ANS:For d.r.v.,F X (x )is a step function.The points f x i g where f x (x i )>0will be the jump points for F X (x ).Without loss of generality,we can arrange these points in an increasing sequential order.Then the probabilities at these points can be obtained fromf X (x i )=P (X =x i )=P (x i 1<X x i )=F X (x i ) F X (x i 1)for i =2;3;:::For i =1;we have f X (x 1)=F X (x 1)because f X (x 1)=P (X =x 1)=P (X x 1)=F X (x 1)given that x 1is the smallest value that X can take.f X =x 1g =f X x 1g Remark:f X (x )and F X (x )are equivalent ways to describe the discrete random variable X .Given f X (x )or F X (x );we can know “everything”of the probability law of X .Examples of D.R.V.Example[Bernoulli R.V.]:A d.r.v.X is called a Bernoulli(p)random variable if its pmff X(x)= p if x=11 p if x=0;where0<p<1:Remark:This distribution arises when one tosses a coin whose head shows up with probability p:Example[Binomial R.V.]:A d.r.v.X is called a Binomial(n;p)if its pmff X(x)=(n x)p x(1 p)n x;x=0;1;:::;n;where n 0and0<p<1:Remarks:When can this distribution arise?A person throws a coin n times independently. Each time the head has probability p and the tail q=1 p:How many heads can he get from these n trials?Interpretation:X=P n i=1X i;where X i is a sequence of independently identically distribu-tion(i.i.d.).Bernoulli random variable(p):Question:How to verifynX x=0(n x)p x(1 p)n x=1for all p2(0;1)?ANS:By the binomial theorem which states that for any real numbers x and y and integern 0;(x+y)n=nX i=0(n i)x i y n i:See p.90of the textbook.In our application,we put x=p and y=1 p:Question:Why is the binomial distribution useful?Example[Discrete Uniform Distribution]A d.r.v.X is a discrete uniform(1;N)distribution iff X(x)= 1N x=1;:::;N;0otherwise,where N is a speci…ed positive integer.Example[Poisson Distribution]A d.r.v.X follows a Poisson( )distribution if its pmff X(x)= e x x!;x=0;1;:::;0otherwise,where >0:The parameter is called an intensity parameter.Question:What is the interpretation of ?Answer:It is proportional to an instantaneous probability.Question:How to verify1X x=0e x x!=e 1X x=0 x x!=1?Hint:What is the Taylor series expansion of e y?For any y near zero,1X i=0y i i!e y=Put i=x;y= :Remark:Poisson distribution is very popular in…nance.It has been used to capture jumps in …nancial markets.3.3Continuous Random VariablesRead Section3.3De…nition[Continuous Random Variable]A r.v.X is called continuous if its distribution function F X(x)is continuous for all x.Alternatively,a r.v.X is discrete if F X(x)is a step function of x:Picture:F X(x)is a continuous function.A c.r.v.X provides a proper description of income, temperature,stock return,and so on.Question:Can we de…ne a pmf f X(x)for a continuous random variable X?Obviously,for any constant">0;0 P(X=x)P(x "=2<X x+"=2)=F X(x+"=2) F X(x "=2)!0as"!0:Thus,P(X=x)=0for all x:That is,if X is a continuous random variable,the probability that X takes a single point is zero.This has some important implications.For example,for a c.r.v.,we haveP(a<X b)=P(a X<b)=P(a X b):Question:Under what conditions,can we write F X(x)=R x 1f X(y)dy for some function f X(x)? De…nition[Absolute Continuity(AC)]:A function F:R!R is called absolutely contin-uous with respect to Lebesgue measure if F(x)is continuous on R and is di¤erentiable almost everywhere(i.e.for almost all x):Remark:What is meant by“almost everywhere”?Intuitively,in any…nite interval of R;there is a…nite number of points or an in…nite but countable number of points where F X(x)is not di¤erentiable.De…nition[Probability Density Function(pdf)]:Suppose the distribution function F X(x) of a c.r.v.X is absolutely continuous.Then there exists a function f X(x)such thatF X(x)=Z x 1f X(u)du for all x2( 1;1).The function f X(x):R!R is called a probability density function of X.Question:Is f X(x)a unique function for a given F X(x)?Remarks:(i)When the AC condition does not hold,X may not have the above relationship.Throughout this course,we will assume that F X(x)is AC.(ii)For those x’s where F0X(x)exists,we have from the above thatf X(x)=dF X(x) dx:Given that F X(x)is AC,the probability density function f X(x)exists almost everywhere. Question:How to de…ne f X(x)at the points where F0X(x)does not exist?Answer:Arbitrary but try to make f X(x)as smooth as possible.For a c.r.v.X with well-de…ned pdf f X(x);f X(x)and F X(x)are equivalent to each other. Given one,we can always recover the other.(iii)[Interpretation of pdf]:For any small constant">0;we have,by the mean value theoremP[x "=2<X x+"=2]=F X(x+"=2) F X(x "=2)=Z x+"=2x "=2f X(y)dy=f X( x)"for some x2[x "=2;x+"=2](by the mean-value theorem)=probability that X is between(x "=2;x+"=2]: Although f X(x)is not a probability measure,it is proportional to the probability that X takes values in a small interval centered at x:(iv)The fact that P(X=0)=0for a c.r.v.allows us to change the value of the pdf of a continuous random variable X at a single point without altering the distribution of X:For instance,the pdff X(x)= e x for0<x<1;0elsewhere,can be written asf X(x)= e x for0 x<1;0elsewhere,without changing P X(A)for any A in R:We observe these two functions di¤er only at x=0 and P(X=0)=0:More generally,if two pdf’s of continuous random variables di¤er only on a set having probability zero,the two corresponding probability set functions are exactly the same.Unlike the continuous random variables,the pmf of a discrete random variable may not be changed at any point,since a change in such a pmf alters the distribution of probability.(v)Because f X(x)is a slope that determines the change of a probability F X(x),f X(x)can be greater than1.(vi)Remark:Because of the property that P(X=x)=0for all x2R;the values of any pdf f X(x)can be changed at a…nite number of points or even at an in…nite sequence of points, without changing the value of the cdf F X(x):In other words,the values of the pdf of X can be changed arbitrarily at an in…nite sequence of points without a¤ecting any probabilities involving X;that is,without a¤ecting the probability of X:To the extent just described,the pdf is not unique.In many problems,however,there will be one version of the pdf that is more natural than any other pdf.For this reason,the pdf will, wherever possible,be continuous on the real line.Theorem[Properties of pdf]:A function f X(x)is a pdf of a c.r.v.X i¤(a)f X(x) 0for all x and(b)R1 1f X(x)dx=1:Proof:[Necessary]Suppose f X is a pdf,i.e.F X(x)=R x 1f X(y)dy:By the mean value theorem,F X(x+ ) F X(x)=f X( x) ;where x lies between x and x+ :It follows that f X( x) 0since F X( )is nondecreasing.Also,(b)follows because F X(1)=1:[Su¢ciency]The converse can be proved similarly by constructing F X(x)=R x 1f(y)dy and showing that F X(x)is a cdf of some random variable X.First,F X(x)is nondecreasing by the mean valued theorem and(a),F X(1)=1by(b),and F X( 1)=0by(a)and(b).Also, F X(x)=R x 1f(y)dy implies that F X(x)is continuous,becauseF X(x+ ) F X(x)=Z x+ x f(y)dy!0as !0;and so is right-continuous.Therefore,F X(x)is a cdf of some random variable X.Geometric Representation of pdf f X(x):Indicative of mode,skewness or symmetry,heavy tails,and etc.Questions:(i)Is it possible to construct a pdf f(x)from any nonnegative function g(x)with a…nite integral(i.e.,0<R1 1g(x)dx<1)?ANS:Yes,f(x)=g(x)=R1 1g(y)dy:An application in…nance:[stochastic discount factor and risk neutral probability density function]In a dynamic setting,…nancial derivatives prices are determined by the Euler equationE[M t;t+ Y(S t+ )j I t]=P t;where M t;t+ 0is the so-called stochastic discount factor of the representative economic agent, Y(S t+ )is the pay o¤scheme at the maturity date t+ ;S t+ is the price of the underlying asset (e.g.,Standard&Poor500closing price index)at time t+ ;P t is the price of the derivative at time t,and I t is the information available at time t:We can write the Euler equation equivalently as follows:ZM t;t+ Y(s)f t+ (s)ds=P t;where f t+ (s)is the pdf of S t+ conditional on I t:Now de…ne a so-called risk neutral pdff (s t+ j I t)=M t;t+ f t+ (s)E[M t;t+ j I t]=M t;t+ f t+ (s) R M t;t+ f t+ (s)ds:Then the Euler equation can be written ase r E [Y(S t+ )j I t]=P t;ore r Z Y(s)f t+ (s)ds=P t;where r is the compound interest rate,and E ( j I t)is the so-called expectation under the risk neutral pdf f t+ (s):(ii)Is it possible to construct a symmetric pdf f(x)from any nonnegative function g(x)with a…nite integral?Remark:symmetric if f(x)=f( x)for all x:ANS:f(x)=g(x)+g( x)2R1 1g(y)dy:De…nition[Support]:The support of a c.r.v.X is de…ned asSupport(X)=f x2R:f X(x)>0g;where f X(x)is the pdf of X:Remark:It su¢ces to focus on the support of X:Examples of c.r.v.Example [Uniform Distribution]A c.r.v.X follows a uniform distribution on [a;b ]if its pdff X (x )= 1b a a x b 0otherwise,where a <b:Example [Gamma Distribution]a c.r.v.X follows a Gamma ( ; )distribution iff X (x )= 1 ( ) x 1e x= 0<x <10otherwise,where ; >0:Question:What is the gamma function ( )?( )=Z 10t 1e t dt:Properties of ( ):(i) ( +1)= ( );(ii) (n )=(n 1)!if n is a positive integer.(iii) (12)=p :Question:How to verifyZ 10f X (x )dx =Z 101 ( )x 1e x= dx =1?Hint:By change of variable and de…nition of the gamma function.Z 1 1f X (x )dx =Z 101 ( ) x 1e x= dx =1 ( )Z 10(x= ) 1e (x= )d (x= )(set y =x= )=1 ( )Z 10y 1e y dy =1 ( ) ( )=1:Remark:The Gamma distribution has been popularity used to model the waiting time of economic events.Example[Exponential Distribution]X follows Exponential( )iff X(x)= 1 e x= 0<x<10otherwise,where >0:Remarks:(i)Exponential( )=Gamma(1; ):(ii)Exponential Distribution is popular in modelling duration between…nancial events or economic events.An example in labor economics:Let T be the unemployment duration of a worker which has a pdf f T(t).Then the so-called hazard rate is de…ned as(t)=limt!0+P(T t+ t j T t)t=f T(t)P(T t);which is the instantaneous probability that the worker will…nd a job after an umemployment duration of t:A simplest example is to assume thatf(t)=1e t= for t>0:Then the hazard rate will become(t)=1 ;which is a constant of time.(iii)An empirical stylized fact of high-frequency…nancial return f X t g is that j X t j approxi-mately follows an exponential distribution(see Ding,Granger and Engle1993,Journal of Em-pirical Finance.)Here,X t is the standardized…nancial return.Example[Normal Distribution]A normally distributed random variable,X N( ; 2);has thepdff X(x)=1p2 e (x )22 2; 1<x<1;where 1< <1and0< <1:Remark:A normal distribution is also called Gaussian distribution.Why?Answer:The normal distribution was discovered in1733by Abraham De Moivre(1667-1754)in his investigation of apprxomating coin tossing probabilities.he named the PDF of his discovery the exponetially bell-shaped curve.In1809,Carlk Friedrich Gauss(1777-1855)…rmly established the importance of the normal distribution by using it to predict the location of astronmical bodies.As a result,the normal distribution then became commonly known as the Gaussian distribution.Remarks:(i)X is called standard normal,denoted X N(0;1);if =0and =1:(ii)Normal distribution is the most important distribution in probability theory.The Central Limit Theorem(CLT)says that under suitable conditions,a sample average will converge to a normal distribution as the sample size increases.1 p nnX i=1X i!Normal distribution as n!1.This follows no matter whether X i is discrete or continuous,is compact supported or uncompact supported.(iii)Question:How to verifyZ1 11p2 exp (x )22 2 dx=1?Put y=(x )= :Then it becomesZ1 11p2 exp y22 dy=1:Question:How to verify this?Z1 1e x22dx 2=Z1 1e x22dx Z1 1e y22dy=Z1 1Z1 1e x2+y22dxdy(set x=r cos( );y=r sin( ))=Z10Z2 0e r22rdrd=2 Z10e r22rdr=2 :It follows that1p2 Z1 1e x22dx=1:Example[Beta distribution]X follows a Beta( ; )distribution iff X(x)= 1B( ; )x 1(1 x) 10<x<1;0otherwise,。

实数real numberreal numbers 实数 integers 整数 Fraction 分数decimals 小数 irrational Numbers 无理数 rational numbers 有理数positive number 正数 negative number 负数 opposite number 相反数count backwards 倒数Teaching aims1．了解无理数与实数的意义；Understanding of irrational Numbers and the notion of real Numbers2．了解有理数的运算法则(?)在实数范围内仍然适用；Understand the rational range of algorithms3．能利用化简对实数进行简单的四则运算；simple arithmetic of the real number by simplification4．了解实数的意义，能对实数按要求进行分类；The notion and the classification of the real numbers5．掌握有理数的运算法则在实数范围内仍然适用；Grasp the rational range of algorithms in real numbers6．能利用实数的性质熟练地进行四则运算；Master the arithmetic of the rational numbers well.7．注意：（1）无理数应满足：①是小数；②是无限小数；③不循环；Irrational Numbers should be: (1) a decimal number; (2) infinite decimals; (3)no cycles（2）无理数不是都带根号的数（例如π就是无理数），反之，带根号的数也不一定都是无理数（例如4，327就是有理数）．Not all irrational Numbers take square root (such as π is irrational ）,On the other hand, radicals are not necessarily irrational Numbers （for example4，327Is a rational number ）（1）按实数的定义分类：According to the definition of real Numbers ⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧⎭⎬⎫⎩⎨⎧⎪⎪⎪⎩⎪⎪⎪⎨⎧⎭⎬⎫⎩⎨⎧⎪⎩⎪⎨⎧decimal repeating -non infinite number irrational fraction negative fraction Positive fraction integer negative integer positive integer number rational 无限不循环小数负无理数正无理数无理数数有限小数或无限循环小负分数正分数分数负整数零正整数整数有理数实数zero（2）按实数的正负分类：⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧⎪⎩⎪⎨⎧⎩⎨⎧⎪⎩⎪⎨⎧⎩⎨⎧负无理数负分数负整数负有理数负实数数）（既不是正数也不是负零正无理数正分数正整数正有理数正实数实数number fractional negative integer negative number real negative negativenor positive Neither number arithmetic zero第1讲 实数的有关概念【知识要点】1．实数的性质（1）实数范围内仍然适用在有理数范围内定义的一些概念（如倒数，相反数）；Real number range applies within the scope of the rational definition of some concepts, suchas countdown, opposite)（2）两实数的大小关系：正数大于0，0大于负数；两个正实数，绝对值大的实数大；两个负实数，绝对值大的实数反而小；Relations between the two the size of the real Numbers: a positive number greater than zero, 0 is greater than the negative; Two positive real number, the absolute value of real number; Two negative real number, the absolute value of real Numbers instead of small（3）在实数范围内，加、减、乘、除（除数不为零）、乘方五种运算是畅通无阻的，但是开方运算要注意，正实数和零总能进行开方运算，而负实数只能开奇次方，不能开偶次方；Within the scope of the real Numbers, addition, subtraction, multiplication, and division (divisor is not zero), power five kinds of arithmetic is unobstructed, but root operation should pay attention to, are real Numbers and zero always root operation, while the negative real number can only be open power, can't open my power（4）有理数范围内的运算律和运算顺序在实数范围内仍然相同．Rational number operations within the scope of law and order of operations within the scopeof the real number is still the same2．实数与数轴的关系Real relationships with a number line每一个实数都可以用数轴上的一个点表示；反之，数轴上每一个点都表示一个实数，即数轴上的点与实数是一一对应关系．Every real number can be represented by a point on the number axis; On the other hand,every point on a number line represents a real, namely the points on the number line is one-to-one correspondence relationship with real Numbers3．实数的分类The classification of real Numbers⎪⎪⎪⎩⎪⎪⎪⎨⎧⎭⎬⎫⎩⎨⎧⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧无限不循环小数负无理数正无理数无理数数有限小数或无限循环小负有理数零正有理数有理数实数4．实数的大小比较The size of the real number两实数的大小关系如下：正实数都大于0，负实数都小于0，正数大于一切负数；两个正实数，绝对值大的实数较大；两个负实数，绝对值大的实数反而小．Relations between the two the size of the real number is as follows: positive number isgreater than zero, negative real Numbers are less than zero, the positive is greater than all thenegative; Two positive real number, the absolute value of real number; Two negative real number,the absolute value of real Numbers instead of small实数和数轴上的点一一对应，在数轴上表示的两个实数，右边的数总大于左边的数．Real Numbers and at a point on the number line one to one correspondence, said on a numberline of two real Numbers, the right of the number of total is greater than the number on the left.【典型例题】A typical example例1若a 为实数,下列代数式中,一定是负数的是( )If a is real number, the following algebraic expression, must be a negative number isA. －a 2B. －( a +1)2C.－2a D.－(a -+1)分析：本题主要考查负数和非负数的概念,同时涉及考查字母表示数这个知识点.Subjectmainly examines the concept of the negative and the negative, involving check letters for thisknowledge at the same time.由于a 为实数, Because it is the set of real Numbers. a 2、( a +1)2、2a 均为非负数Both as a negative number ，∴－a 2≤0，－( a +1)2≤0，－2a ≤0．而0既不是正数也不是负数，是介于正数与负数之间的中性数．Zero is neither positive nor negative,neutral number is between positive and negative.因此，A 、B 、C 不一定是负数．又依据绝对值的概念及性质知Therefore, A, B, C are not necessarily negative. And based on the concept andnature of the absolute value －(a -+1)﹤0．So the choice is D.例2 实数a 在数轴上的位置如图所示,Real Numbers a position on a number line, as shown in the figure化简:2)2(1-+-a a =分析：这里考查了数形结合的数学思想,要去掉绝对值符号,必须清楚绝对值符号内的数是正还是负.由数轴可知:1﹤a ﹤2,于是,22)2(,112a a a a a -=-=--=- 所以, 2)2(1-+-a a =a －1+2－a =1.例3 如图所示,数轴上A 、B 两点分别表示实数1，5，点B 关于点A 的对称点为C ，则点C 所表示的实数为（ ）As shown in the figure on the number line A and Btwo points respectively according to the set of real Numbers 1，5，Point symmetry about pointA pointB to C, and the pointC said the real number for which one （ ） A.5－2 B. 2－5 C. 5－3 D.3－5分析：这道题也考查了数形结合的数学思想,同时又考查了对称的性质．B 、C 两点关于点A 对称，因而B 、C 两点到点A 的距离是相同的，点B 到点A 的距离是5－1，所以点C 到点A 的距离也是5－1，设点C 到点O 的距离为a ，所以a +1=5－1，即a =5－2．又因为点C 所表示的实数为负数，所以点C 所表示的实数为2－5．例4 已知a 、b 是有理数，且满足3-b +（a －2）2=0，则a b 的值为多少 A and b is a rational number is known, and satisfaction 3-b +（a －2）2=0，in that way ，a b has a value of .分析：因为（a －2）2+3-b =0，所以a －2=0，b －3=0。

周期时变布尔网络的完全同步化韩吉;张化光;田辉【摘要】This paper mainly investigates the complete synchronization of two Boolean networks (BNs) coupled uni-directionally in the drive-response configuration, where the drive BN is periodically time-variant. We discuss it in two cases under the algebraic framework of logical systems. For each case, a necessary and sufficient criterion for complete synchronization is presented. Accordingly, two general design approaches to a synchronizing response BN are developed. Finally, numerical examples are given in order to illustrate the effectiveness of our results.%本文主要研究了驱动–响应结构下的布尔网络的完全同步化，其中驱动系统是一个周期性时变的布尔网络。

对于上述问题，本文基于逻辑系统的代数形式下分两种情况讨论。

对于每种情况，都将给出一个完全同步的充要条件。

相应地，提出了两个响应布尔网络的同步化方案。

最后，通过一些数值例子来说明本文结果的有效性。

【期刊名称】《控制理论与应用》【年(卷),期】2016(033)007【总页数】7页(P863-869)【关键词】布尔网络;周期性时变布尔网络;完全同步【作者】韩吉;张化光;田辉【作者单位】东北大学信息科学与工程学院，辽宁沈阳110819;东北大学信息科学与工程学院，辽宁沈阳110819;东北大学信息科学与工程学院，辽宁沈阳110819; 河南理工大学数学与信息科学学院，河南焦作454000【正文语种】中文【中图分类】TP273Boolean network was first introduced by Kauffman in 1969.Ithasbeen w idely used inmodeling complex systems such as gene regulatory networks，biological evolutionmodelsand neuralnetworks.Ateach discrete timepoint，every node ina BN can takeoneof two binary values，1 or0，where 1means that the node isactive and 0 inactive.Every nodeupdatesstate on thebasisof a logical relationship with the form of a Boolean function.Although themodelsof BNsare very simple，they can describe basic dynam ic behavior ofmany realsystemsand provide useful information.Therefore，lotsof issuesaboutBNshave been investigated such asstability，controllability，optimal controland so on[1-6].As we know，the synchronization problem of systemshasbeen attractingmany researchers from various fields，see[7-9].The complete synchronization of BN-swhich can be equivalently transformed into the linear discrete-time systemsby utilizing thesem i-tensorproduct（STP）[10]also caused a lot of attention and many results were provided.For example，a necessary and sufficientcriterion forcompletesynchronizationof BNs wasprovided in[11]，ageneralapproach for the design of a response BN was given in[12]and the synchronization problem of BNswithsome special cases such asdifferentupdate，time-delay and output-coupledwere investigated in[13-16]，respectively，and so on.Most of researchers just considered the situation that the BNs were time-invariant Boolean networks（TIBNs），while the synchronization problem of timevariantBoolean networks（TVBNs）was rarely studied. TVBNs havemany essential properties different from TIBNs.Asa specialcaseof TVBNs，periodically timevariantBoolean networks（PTVBNs）can beused to describemany systems such as the sw itched BNswhich have periodical sw itching signals[17]，the Boolean con-trol networks（BCNs）which have dynam ical control lers[18]，the perturbed BNswhich have periodical function perturbations[19]，and so on.Therefore，the study of synchronization of PTVBNs is significant.A lthough the problem of PTVBNs have been studied in few papers[20-21]，the problem of complete synchronization of PTVBNshas notbeen solved well.This is themotivation of our paper.In this paper，we investigate a special case of the complete synchronization problem for two BNs that the drive BN isperiodically time-variant.At first，we study the cycles of PTVBNs and provide some special propertieswhich never exist in the cycles of TIBNs.Then，according to these properties，the PTVBNs are divided into two categories.A fter that，the synchronization problemsaresolved forboth two categoriesby utilizing STPand the results are turned out to be quite different from each other.At last，two examples for both categories are provided to support our points.Themajor contributions of this paper：1）provide two necessaryand sufficient criteria for complete synchronization of PTVBNs；2）make two design approaches to a synchronizing response BN，which can complete synchronize with the drive BN in finite steps.Thispaper isorganized as follows.Problem formulation and some prelim inariesaregiven in Section 2.In Section 3，the periodically time-variant drive Boolean network is discussed in two casesand some criteria for completesynchronization and somegeneralapproaches for the design of a synchronizing response BN are provided.Two numericalexamples are given in Section 4 and a conclusion isdrawn in Section 5.First，we give some notations.1）N represents thesetofnon-negative integers，N+represents the setof positive integersand N[λ1，λ2]represents thesetof integersfromλ1toλ2whichmeans that N[λ1，λ2]=｛λ1，λ1+1，………，λ2｝.2）In∈Rn×nrepresents the identity matrix，represents the i-th column of In.3）∆nrepresents the set of，where i=1，2，………，n.4）ε（x）represents a bijection from∆2nto N[1，2n]such that5）Col（A）represents the setof all columns of A，where A∈Rm×n.6）B=］iscalled a logicalmatrix and its shorthand form is7）Φnrepresents a logicalmatrix such thatConsider two BNswith n nodes respectively coupled unidirectionally in the drive-response configurationwhereσ（t）=t%p+1 is a periodic function with period p，t%p represents the remainder of t/p，ϕ（t）is a function from N to N+，the xiandyirepresent the nodesof the drive BN and response BN，respectivelyandrepresentthe Boolean functions from｛1，0｝nto｛1，0｝and from｛1，0｝2nto｛1，0｝forevery i∈N[1，n]，j1∈N[1，p]andj2∈N+，respectively.Themainmathematical toolof thispaper is the STP，which is a generation of conventionalmatrix product. Sincemostproperties of the conventionalmatrix product remain true under STP，the product of this paper is usually considered as STP if there is no confusion. By[22]，the Boolean values1 and 0 can be equivalently transformed into the vectors=（1，0）Tand=（0，1）T，respectively.Take x（t）=x1（t）x2（t）………xn （t）and y（t）=y1（t）y2（t）………yn（t），then BNs（1）and（2）are equivalent to the follow ing discrete-time systems：where Fσ（t）∈ L2n×2nand Gϕ（t）∈ L2n×22nare the structurematricesof BNs（1）and（2），respectively.For convenience，let x（t，x（0））represent the trajectory of the drive BN（1）with initial state x（0）∈｛1，0｝nand y（t，x（0），y（0））be the trajectory of the responseBN（2）under the drive trajectory x（t，x（0））with the initial state y（0）∈｛1，0｝2n.Let the columnsof Fσ（t）and Gϕ（t）beand，respectively， whichmeans thatThe complete synchronization of BNs（1）and（2）is defined as follows. Definition 1 BNs（1）and（2）are completely synchronized if there is a positive integer k such that y（t，x（0），y（0））=x（t，x（0））forall x （0），y（0）∈∆2nand any t≥k.Because the complete synchronization for BNs is closely related to the attractors（including the fixed pointand cycles），we provide an introduction to the cyclesof PTVBNs.Definition 2[20] A state x0∈ ∆2nis called afixed point of BN（1）if Fσ（t）x0=x0for any t≥0. A sequence｛x（0），x（1），………，x（t），x（t+1），………｝is called a cycle of BN（1）with length l if：1）x（t+l）= x （t）for any t≥0；2）for any 0＜T＜l，there is a positive integer e t such that x（e t+T）/=x（e t）.In this paper，the periodic sequence｛x（0），x（1），………，x（t），x （t+1），………｝which is a cycle of BN（1）with length l isdenoted by where˜x（l）=x（0）and˜x（i）=x（i）for every i∈N[0，l-1].Forany t≥0，we call x（t）in thiscycle ifand only if x（t）=˜x（t%l）.For the cycles of PTVBNs，the follow ing Lemma can be obtained. Lemma 1 For BN（1），there isa positive integer k such that x（k）is in one of the cycles of BN（1）for every x（0）∈∆2nand any t≥k.Proof Take F =Fσ（p-1）Fσ（p-2）………Fσ（0），we have asasubsystem of BN（3）.Becauseof the infinitenessof the state space，for any x（0）∈∆2n，there are positive integers k and l such thatis one cycle of BN（7）for any t′≥k.It can be found thatisa cycleof BN（3）.So the proof is completed.Suppose thatBN（1）has s cycles represented asAccordingly，define a setC=｛x|x∈∆2n，there exist i∈N[1，s]andAbout the cyclesof PTVBNs，two casesneed to be introduced.1）There is x∈C which appears several times in a period of acycle.Forexample，considera PTVBN with period 2 and= δ2［2，1］.Thenisa cyclewith length 4，it can be found thatandboth appear tw ice in a period of thiscycle.2）There is x∈C which is inmore than one cycle. Forexample，letbe a PTVBN with period 2 and F1= δ4［2，3，1，2］，F2= δ4［2，4，3，1］.Thenis in two cycles of thisDefine a subsetof C as follows：It can be found that C′= ∆2in BN（12）and C′=，｝in BN（13），respectively.Therefore，C′isnot alwaysan empty set.Sowe divide complete synchronization problem for BNs（1）and（2）into two cases：1）C′=∅；2）C′/=∅.3.1 Case1:C′=∅Because C′=∅，consider the candidate response BN（2）asa TIBN.Then equation（6）is rew ritten asTherefore，the candidate response BN can be described as follows：Then by equations（3）（5）（15）and（16），wehavewhereThen the follow ing theorem can beobtained.Theorem 1 Assume C′=∅，where C′isdefined in（14）.BNs（1）and（2）are completely synchronized if and only if there isanon-negative integerk≤22n suchthatwhere p is the period of BN（1），Θ[0]=I22nandProof Sufficiency.According to equation（17），we haveBy Theorem 2 in[13]，x（t）=y（t）for every x（0），y（0）∈∆2nif and only if Col（Θ[t]）.For any t≥kp+1，there exist j∈N[1，p]and k′∈N such that t=kp+j+k′p.Meanwhile， it can be found that，whereΘθ=Θp）.ThenwehaveObviously，the follow ing equation isalso true：By utilizing equations（19）（21）and（22），we haveTherefore，x（t）=y（t）for every x（0），y（0）∈∆2nand anyt≥kp+1.Thismeans the complete synchronization of BNs（1）and（2）. Necessity.By Definition 1，if BNs（1）and（2）are completely synchronized，there is a positive integer k′such that x（t）=y（t）for every x（0），y（0）∈∆2nand any t≥k′.Hence，one can obtainThen，by equation（23），take a positive integer k such that kp+1≥k′，then equation（19）holds.By[22]，thereexistpositive integers r1＜r2≤22nsuch that，whichmeans thatfor anyτ≥0.So the BNs（1）and（2）can not be completely synchronized if there exist integers k′＞22np such that.Therefore，wehave k′≤22np and k≤22n.The proof is completed.For case1，letusprovidean approach for the design of a synchronizing response BN.Theorem 2 Assume C′=∅，the response BN（2）completely synchronizeswith the drive BN（1）ifProof By Lemma 1，there is a positive integer k such that x（t）=（j）is in one cycleof BN（1）forevery x（0）∈∆2nand any t≥k.By equations（16）-（18），for every y（0）∈∆2n.By（24），we have y（t+1）=（j+1）=x（t+1）.Therefore，y（t）=x（t）forevery x（0），y（0）∈∆2nand any t＞k. The proof is completely.3.2 Case2:C′̸=∅In order to get themain results，we give a lemma first.Lemma 2 There is no TIBN such that it completely synchronizeswith BN（1）if C′/=∅.Proof We prove itby reduction to absurdity.Assume that BN（2）is a TIBN and completely synchronizeswith BN（1）.By Definition 1，there is a positive integer k1such that y（t，x（0），y（0））=x（t，x（0））for every x（0），y（0）∈ ∆2nand any t≥ k1.BecauseC′/= ∅，there exists x0∈ C such that（j1）=）for someandTake x（0）=（0），wehavefor any k2≥0.Take k2such that k2li1≥k1，we can obtainBy equation（18），thismeans thatSim ilarly，take x（0）=（0），we can getBecauseε（x）is a bijection，we haveε（j1））= ε（j2））andε（j1+1））/=ε（j2+1））.Then the follow ing equationshold：Equations（31）and（32）lead to a contradiction.Therefore，the proof is completed.By Lemma 2，only TVBN is the candidate thatcan completely synchronizewith BN（1）in Case 2.By equations（3）-（6）we havewhereRemark 1 Ifϕ（t）is not a periodic function，may notbe periodically time-variant.In this case，becomesquite complex andwe can hardly provide aregular conclusion.Therefore，ϕ（t）is just considered as a periodic function.Remark 2 By Definition 1 and Lemma 1，if BNs（1）and（2）are completely synchronized，itmustsatisfyBecause C′̸=∅，there exist（j1），（j2）in the cycles of BNs（1）such that（j1）=（j2）（j1+1）̸=（j2+1）andσ（j1）̸=σ（j2）.Therefore，if theequality（35）holds forBN（1）in case 2，itmust satisfy condition（1）：for any j1，j2∈N，ifσ（j1）̸= σ（j2），thenϕ（j1）̸= ϕ（j2）.By Remark 1，take ϕ（t）=t%q+1，where q is the period ofϕ（t）.Then condition（1）is equivalent to condition（2）：for any j1，j2∈N，if j1%p̸=j2%p，thenj1%q̸=j2%q.It can be found that condition（2）holds if and only if q=m p，where m∈N+.This conclusion can be proved by utilizing the properties of integer and Euclidean algorithm.By Remark 1 and Remark 2，we just considerϕ（t）=t%（m p）+1 inCase2.Then the follow ing theorem can beobtained.Theorem 3 Assume C′/=∅，BNs（1）and（2）are completely synchronized if and only if there is a non-negative integer k≤22nsuch thatwhere m p is the period of BNs（2），=I22nandfor any t＞0.The proof issim ilar to Theorem 1.Weprovidean approach for thedesign ofasynchronizing response BN. Theorem 4 BNs（1）and（2）are completely synchronized in Case 2 ifThe proof issim ilar to Theorem 2.Remark 3 Obviously，a TIBN can be treated as a PTVBN with period m p such that Gϕ（t）≡G.Therefore，no matterwhich case PTVBN（1）with theperiod of p belongs to，thereexistsa PTVBN with the period of mp to completely synchronizewith it forany m∈N+.4.1 Example for Case1Givea drive BN as follows：Now，let us design a response BN to completely synchronizewith BN（38）by using Theorem 2.It can be obtained that F1= δ4［3，4，2，3］，F2=δ4［2，1，1，4］and the period is p=2.The cycle of（38）is C：.According to Theorem 2，takeandcan be chosen arbitrarily.Forexample，takeTherefore，thestructurematrix of the designed response BN isBy using the technique provided in[22]，the logical equations for the designed response BN areTake x（0）=（1，0）and y（0）=（0，0）.The Hamm ing distance H（t）=|x1（0）-y1（0）|+|x2（0）-y2（0）| versus the time t is plotted in Fig1.By Fig 1，these two BNsare completely synchronized from the fourth step.4.2 Exam p le for Case2Considera drive BN asLetusprovide the response BNs to completely synchronize with BN（39）by utilizing Theorem 4.It can be obtained that F1= δ4［1，4，2，3］，F2= δ4［2，3，1，2］and the period is p=_2.The cycles of（39）are C1:and1）Consider theperiod of the response BN q=p= 2.By Theorem 4，take andcan be chosen arbitrarily in｛1，2，3，4｝. For example，takeThen we can obtain the structurematrix of the designed response BNand the logicalequations for the designed response BN areTake x（0）=（0，0）and y（0）=（0，1）.The Hamm ing distance H（t）=|x1（0）-y1（0）|+|x2（0）-y2（0）| versus the time t isplotted in Fig 2.By Fig 2，these two BNsare completely synchronized from the fifth step. 2）Consider the period of the response BN q=2p =4.By Theorem 4，take Then we can obtain the structurematrix of the designed response BNand the logicalequations for the designed response BN areTake x（0）=（0，0）and y（0）=（0，1）.The Hamming distance H（t）=|x1（0）-y1（0）|+|x2（0）-y2（0）| versus the time t is plotted in Fig 3.By Fig 3，these two BNsare completely synchronized from the third step. In this paper，we have studied the problem of complete synchronization for two BNs，which are coupled unidirectionally in a drive-response configuration and the drive BN is a PTVBN.Because the structure of PTVBN ismore complex than TIBN’s.The dri ve BN has been considered in two different kinds.We have provided thenecessary and sufficiency criteria for complete synchronization，and general approaches for the design of a response BN for both kinds，respectively. Some numerical examples have been given to support these viewpoints.In the future work，we w ill investigate the complete synchronization of PTVBNs with time-delay and output-coupled.[1]LIH，WANG Y，LIU Z.Stability analysis for sw itched Boolean networks under arbitrary sw itching signals[J].IEEE Transactions on Automatic Control，2014，59（7）：1978-1982.[2]LI F，SUN J.Controllability and optimal control of a temporal Booleannetwork[J].Neural Networks–-the Official Journal of the InternationalNeuralNetwork Society，2012，34（4）：10-17.[3]CHENH，LIX，SUN J.Stabilization，controllability and optimalcontrolof Boolean networkswith impulsive effectsand state constraints[J].IEEETransactionson Automaic Control，2015，60（3）：806-811.[4]ZHAO Y，LIZ，CHENG D.Optimal control of logical controlnetworks[J].IEEE Transactions on Automatic Control，2011，56（8）：1766-1776.[5]FORNASINIE，VALCHERM E.Optimalcontrolof Boolean control networks[J].IEEE Transactionson Automatic Control，2014，59（5）：1258-1270.[6]TIAN H，WANG Z，HOU Y，et al.State feedback controller design for synchronization ofmaster-slave Boolean networksbased on core input-state cycles[J].Neurocomputing，2016，174（22）：1031-1037.[7]ZHANG H，ZHANG J，YANG G，etal.Leader-based optimal coordination control for the consensusproblem ofmulti-agentdifferential games via fuzzy adaptive dynam ic programm ing[J].IEEE Transactionson Fuzzy Systems，2015，23（1）：152-163.[8]ZHANGH，MA T，HUANG G，etal.Robustglobalexponentialsyncrhonization of uncertain chaotic delayed neural networks via dualstage impulsive control[J].IEEE Transactionson SystemsMan and Cybernetics PartB-Cybernetics，2010，40（3）：831-844.[9]ZHANG H，HUANGW，WANG Z，etal.Adaptive synchronization between two differentchaotic systemswith unknown parameters[J]. Physicsletter A，2006，350（5/6）：363-366.[10]QIH，CHENGD.Analysisand controlof Boolean networks：a sem itensorproductapproach[C]//Asian ControlConference.Hong Kong：IEEE，2009，8：1352-1356.[11]LIR，CHU plete synchronization of Boolean networks[J]. IEEE Transactionson NeuralNetworksand Learning Systems，2012，23（5）：840-846.[12]LIR，YANG M，CHU T.Synchronization design of Boolean networks via the sem i-tensor productmethod[J].IEEE Transactionson NeuralNetworksand Learning Systems，2013，24（6）：996-1001. [13]ZHANGH，WANG X，LIN X.Synchronization of Boolean networks with different update schemes[J].IEEE Transactions on Computational Biology and Bionformatics，2014，11（5）：965-972.[14]LI R，YANG M，CHU T.Synchronization of Boolean networks with time-delays[J].Applied Mathematics and Computation，2012，219（3）：917-927.[15]ZHONG J，LU J，LIUY，etal.Synchronization inanarrary ofoutputcoupled Boolean networkswith time delay[J].IEEETransactionson NeuralNetworksand Learning Systems，2014，25（12）：2288-2294. [16]LIR，CHU T.Synchronization in an arrary of coupled Boolean networks[J].Physics Letters A，2012，376（45）：3071-3075.[17]LI H，WANG Y.On reachability and controllability of sw itched Boolean control networks[J].Automatica，2012，48（11）：2917-2922.[18]CHENG D.Input-state approach to Boolean networks[J].IEEETransactionson NeuralNetworks，2009，20（3）：512-521.[19]XIAO Y，DOUGHERTY E R.The impact of function perturbations in Boolean networks[J].Bioinformatics，2007，23（10）：1265-1273. [20]ZOU Y，ZHU J.Cyclesofperiodically time-variantBoolean networks [J].Automatica，2015，51：175-179.[21]ZHANG H，TIAN H，WANG Z.Synchronization analysis and design of coupled Boolean networks based on periodic sw itching sequences[J].IEEE Transactions on Neural Networks and Learning Systems.2015，DOI：10.1109/TNNLS.2015.2499446.[22]CHENG D，QIH.A linear representation of dynamics of Boolean networks[J].IEEETransactionson Automatic Control，2010，55（10）：2251-2258.韩吉（1988-），男，博士研究生，目前研究方向为布尔网络、多智能体，E-mail：*****************；张化光（1959-），男，教授，博士生导师，目前研究方向为智能控制、近似动态规划、复杂网络建模与控制、分布式控制等，E-mail：****************；田辉（1980-），男，博士研究生，讲师，目前研究方向为逻辑动态系统和网络演化博弈，E-mail：*******************.cn.。

Problems Shortlisted to the 1991IMO Jury1.Let ABC be a triangle and P be an interior point.Let the feet of the perpendiculars from P to AC ,BC be P 1,P 2respectively,and let the feet of the perpendiculars from C to AP ,BP be Q 1,Q 2respectively.Show that P 1Q 2∩P 2Q 1∩AB =∅.2.Let ABC be an acute-angled triangle.Let M be the midpoint of BC and P be the point on AM such that MB =MP .Let H be the foot of the perpendicular from P to BC .The lines through H perpendicular to P B and P C meet AB and AC at Q and R respectively.Show that BC is tangent to the circle through Q,H,R at H .3.If S is a point on the circumcircle of the triangle P QR ,show that the feet of the perpendiculars from S to the lines P Q ,QR and RP are collinear.Denote the line by S P QR .If ABCDEF is an inscribed hexagon,show that the lines A BDF ,B ACE ,D ABF ,E ABC are concurrent if and only if CDEF is a rectangle.4.Let ABC be a triangle with ˆA=60◦and incenter I .Let P be a point on BC so that 3BP =BC .The point F is chosen on AB so that IF ||AC .Show that ∠BF P =∠F BI .5.Let O be the circumcenter of the tetrahedron ABCD .Let L,M,N be the midpoints of BC ,CA ,AB respectively.If AB +BC =AD +CD ,CB +CA =BD +AD and CA +AB =CD +BD the show that ∠LOM =∠MON =∠NOL .6.Given a set S of n points in the plane,no three collinear,show that we can find a set C of 2n −5points such that a point of C lies in the interior of every triangle whose vertices belong to S .7.A graph has 1991points and every point has degree at least 1593.Show that there is a complete subgraph with 6vertices,i.e.there are six points,each of which is joined to the others.Is 1593the smallest degree for which this holds?8.Prove that 11991 19910 −11990 19901 +11989 19892 −11988 19883 +...−1996 996995 =119919.No term of the sequence a 1,a 2,...,a n is divisible by n and the sum of all n terms is not divisible by n .Show that for n >1there are at least n different subsequences whose sum is divisible by n .10.The polynomial ax 2+bx +c has integer coefficients.For some prime p its values aresquares for 2p −1consecutive integers x .Show that p divides b 2−4ac .11.Let a n be the last non-zero digit of n !.Does the sequence a n become periodic after afinite number of terms?12.Find all positive integer solutions to 3m +4n =5k .13.What is the largest power of1991which divides199019911992+199219911990?14.Show that the only rational solution q∈(0,1)to the equation cos(3πq)+2cos(2πq)=0is23.15.Let k be the positive root of the equation x2=1991x+1.For positive integers m,ndefine m◦n=mn+ km kn .Show that the operation◦is associative.16.The polynomial P(x)=x1991+a1990x1990+...+a0has integer coefficients.Show thatthe equation P2(x)=9has at most1995distinct integer solutions.17.There is exactly one square with its vertices on the curve y=x3+ax2+bx+c wherea,b,c are real numbers.Show that the square must have side721/4.18.Let f(n):Z−→Z so that f(m+f(f(n)))=−f(f(m+1))−n for all integers m,n.The polynomial g(n)has integer coefficients and g(n)=g(f(n))for all n.Find f(1991) and the most general form for g(x).19.Find all odd integers n>1for which there is at least one permutation a1,a2,...,a n of{1,2,3,...,n}such that the sums a1−a2+a3−...+a n,a2−a3+a4−...−a n+a1, a3−a4+...+a n−a1+a2,...,a n−a1+a2−...+a n−1are all positive.20.Given n>1real numbers x i∈[0,1]show that for some i<n we havex i(1−x i+1)≥x1(1−x n)421.Let a1,a2,...,a n and b1,b2,...,b n be nonnegative reals such that a1+a2+...+a n=b1+b2+...+b n=1.Let p i=a1a2...a i−1b i a i+1...a n.If there is k∈[1,1]so thatb i≤k for all i then show thatp1+p2+...+p n≤k(n−1)n−122.Find the maximum possible value of1≤i<j≤nx i x j(x i+x j)for nonnegative real numbers x1,x2,...,x n with sum1.23.Find all subsets X of the real line such that for any stretch S there is a translationT such that S(X)=T(X).A stretch is a transformation x→h+k(x−h)where h and k=0are constants and a translation is a transformation x→x+t where t is a constant.24.Two people A and B and a referee R are playing the following game.A chooses apositive integer m and B chooses a positive integer n.Each gives his integer to R but not to the other player.R then writes two integers on a blackboard,one of which is m+n.R asks A if he knows n.If he does not,then R asks B if he knows m.If he does not,then R asks A if he knows n,and so on.Show that one player will be able to deduce the other’s number after afinite number of questions(assume that all players are honest).25.Let I be the incenter of the triangle ABC.The internal bisectors of angles A,B andC meet the opposite sides at A ,B and C respectively.Prove that1 4<AI·BI·CIAA ·BB ·CC≤82726.Let n>6be an integer and let a1,a2,...,a k be all the positive integers less than nand relatively prime to n.Ifa2−a1=a3−a2=...=a k−a k−1>0then prove that n must be either a prime number or a power of2.27.Let S={1,2,3,...,280}.Find the smallest integer n such that each n-element subsetof S containsfive numbers which are pairwise relatively prime.28.Suppose G is a connected graph with k edges.Prove that it is possible to label theedges1,2,...,k in such a way that at each vertex which belongs to two or more edges,the greatest common divisor of the integers labelling those edges is1(A graph is a set of points,called vertices,together with a set of edges joining certain pairs of distinct vertices.Each pair of edges belongs to at most one edge.The graph is connected if for each pair of distinct vertices x,y there is some sequence of vertices x=v0,v1,v2,...,v m=y such that each pair(v i,v i+1(0≤i<m)is joined by an edge).29.Let ABC be a triangle and X an interior point of ABC.Show that at least one of theangles∠XAB,∠XBC,∠XCA is less than or equal to30◦.30.Given any real number a>1construct a bounded infinite sequence x0,x1,x2,...suchthat|x i−x j||i−j|a≥1for every pair i=j(an infinite sequence x0,x1,x2,...of real numbers is bounded if there is a constant C such that|x i|<C for all i).。