組合數(shù)學(xué)英文原文

1、組合數(shù)學(xué)英文原文1 Pigeonhole Principle: Simple form Theorem 1.1. If n +1 objects are put into n boxes, then at least one box contains two or moreobjects.Proof. Trivial.Example 1.1. Among 13 people there are two who have their birthdays in the same month.nn.2. There are married couples. How many of the 2 peo

2、ple must beselected in Example 1order to guarantee that one has selected a married couple? Other principles related to the pigeonhole principle:nn objects are put into boxes and no box is empty, then each boxcontains exactly one , Ifobject.nn, If objects are put into boxes and no box gets more than

3、oneobject, then each box hasan object.The abstract formulation of the three principles: Let and be finitesets and let YXfXY:,be a function., If has more elements than , then f is not one-to-one. YX, If and have the same number of elements and f is onto, then f isone-to-one. YX,If and have the same n

4、umber of elements and f is one-to-one, then f is onto. YXExample 13 1n any group of n people there are at least two persons having the same numberxxfriends. (It is assumed that if a person is a friend of then isalso a friend of .) yyxProof. The number of friends of a person is an integer with . If t

5、here is a 01,knkperson whose number of friends is , then everyone is a friend of , that is, no one has yyn,1 aaa,0 friend. This means that 0 and can not be simultaneously the numbers of kkk1211 , , nfriends of some people in the group. The pigeonhole principle tells us that there are at least twopeo

6、ple having the same number of friends. aaa,n integers , not necessarily distinct, there exist integers Example 1.4. Given k12nnand with such that the sum is a multiple of . 0,kll,n11212312nnProof. Consider the integersaaaaaaaaa,nDividing these integers by , we haveaaaqnr, , , , , ,01,rnin,1,2, , 12i

7、iii rrr,r,0aaa , , , If one of the remainders is zero, say, , then is a multiple 12nk12k rrr,11,rnnof .If none of is zero, then two of them must the same (since for 12ni rr,aaa , , , all), say, with . This means that the two integers and kliki12k aaa, , , aaa, , , have the same remainder. Thus is a

8、multiple of n. kkl , , 1212lExample 1.5. A chess master who has 11 weeks to prepare for a tournament decides to play at least one game every day but, in order not to tire himself, he decides not to play more than 12 games during any calendar week.Show that there exists a succession of consecutive da

9、ys during which the chess master will have played exactly 21games.aa be the number of games played on the first day, the total number of games Proof. Let 12a the total number games played on the first, second, and played on the first and second days, 3third days, and son. Since at least one game is

10、played each day, the sequence of fll ,aaaaaanumbers, is strictly increasing, that is, . 77121277a,1Moreover, and since at most 12 games are played during any one week, 1a, , ,1211132 Thus 77 aaa . 1,1321277 aaa, , , 21,21,21Note that the sequence is also strictly increasing, and 1277 a, 21a, 21a, 21

11、 22, , ,132211532771Now consider the 154 numbers,aaaa , , , 21,21,21aa,; 77127712each of them is between 1 and 153. It follows that two of them must be equal. Since ,aaaa , , , 21,21,21aa,are distinct and are also distinct, then the two 77127712aaequal numbers must be of the forms and , 21iiaaSince

12、the number games played up to the ith day is = , we conclude that on the days , 21ii jji , 1,2, the chess master played a total of 21 games. 1,2,200Example 1.6. Given 101 integers from there are at least two integers such that one of them is divisible by the other.Proof. By factoring out as many 2s

13、as possible, we see that any integer can be written in the form k2,a,where and a is odd. The number a can be one of the 100 numbers k,0 Thus among the 101 integers chosen, two of them must have the same as when they 1,3,199rsare written in the form, say, and with . If r s, then the second one divide

14、s the first Example 1.7 (Chines Remainder Theorem). Let m and n be relatively prime positive integers.,xam,mod, , ,has a solution. Then thesystem,ybn,mod ,mnProof. We may assume that and . Let us consider the n integers 0,a0,b amamanma,2,1,mEach of these integers has remainder a when divided by . Su

15、ppose that two of them had thernsame remainder when divided by . Let the two numbers be and , where jma , ima,qq. Then there are integers and such that jn,10,ijiqnr, qnr, = and = jma , ima, jiSubtracting the first equation from the second, we have=qqn, jim, ，一，jiSince gcd= 1, we conclude that nji, N

16、ote that 0 r,1nrthen at leats one of the integers is greater than or equal to . Example 2.1. A basket of fruit is being arranged out of apples, bananas, and oranges. What is the smallest number of pieces of fruit that should be put in the basket in order to guarantee that either there are at least 8

17、 apples or at least 6 bananas or at least 9 oranges?,Answer: 8 + 6 + 9 3 + 1 = 21.Example 2.2. Given two disks, one smaller than the other. Each disk is divided into 200 congruent sectors. In the larger disk 100 sectors are chosen arbitrarily and painted red; the other 100 sectors are painted blue.

18、In the smaller disk each sector is painted either red or blue with no stipulation on the number of red and blue sectors. The smaller disk is placed on the larger disk so that the centers and sectors coincide. Show that it is possible to align the two disks so that the number of sectors of the smalle

19、r disk whose color matches the corresponding sector of the larger disk is at least 100. Proof. We fix the larger disk first then place the smaller disk on the top of the larger disk so that the centers and sectors coincide. There 200 ways to place the smaller disk in such a manner. For each such ali

20、gnment, some sectors of the two disks may have the same color. Since each sector of the smaller disk will match the same color sector of the larger disk 100 times among all the 200 ways and there are 200 sectors in the smaller disk, the total number of matched color sectors10020020,000, ,among the 2

21、00 ways is Note that there are only 200ways. Then there is at20,000least one way that the number of matched color sectors is ,100 or more. 200 2aaa,Example 2.3. Show that every sequence of n , 1 real numbers contains either 212n, 1an increasing subsequence of length or a decreasing subsequence oflength . n , 1n, 1Proof. Suppose