组合数学英文原文

2023年12月9日发(作者：甘肃高二会考数学试卷)

组合数学英文原文

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 more

objects.

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 people must be

selected in Example 1

order 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 box

contains exactly one , If

object.

nn, If objects are put into boxes and no box gets more than one

object, then each box has

an object.

The abstract formulation of the three principles: Let and be finite

sets and let YX

fXY:,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 is

one-to-one. YX , If and have the same number of elements and f is one-to-one, then

f is onto. YX

Example 1.3. In any group of n people there are at least two persons

having the same number

xxfriends. (It is assumed that if a person is a friend of then is

also a friend of .) yy

xProof. The number of friends of a person is an integer with . If

there is a 01,,,knk

person 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，，n

friends of some people in the group. The pigeonhole principle tells

us that there are at least two

people having the same number of friends.

aaa,,,n integers , not necessarily distinct, there exist integers

Example 1.4. Given k12n

nand with < such that the sum is a multiple of . 0,kll,n

nProof. Consider the integers

aaaaaaaaa,,,,，，，，， 11212312n nDividing these integers by , we have

aaaqnr，，，,，,01,,,rnin,1,2, , 12iiii

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 multiple of n.

kkl，，1212l

Example 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 days during which

the chess master will have played exactly 21

games. aa be the number of games played on the first day, the total number

of games Proof. Let 12

a the total number games played on the first, second, and played on

the first and second days, 3

third days, and son. Since at least one game is played each day, the

sequence of

,,aaaaaanumbers, is strictly increasing, that is, < < < . 77121277

a,1Moreover, and since at most 12 games are played during any one

week, 1

a,，,1211132 Thus 77

aaa< < < . 1,,1321277

aaa，，，21,21,,21Note that the sequence is also strictly increasing,

and 1277

a，21a，21a，21<<< 22,,，,1

Now consider the 154 numbers

,,aaaa，，，21,21,,21aa,,; 77127712 each 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 77127712

aaequal numbers must be of the forms and ，21ii

aaSince 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 2\'s 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

a\'s when they 1,3,,199

rsare written in the form, say, and with . If r < s, then the first

one divides the 2,a2,ars, second. If r > s, then the second one divides 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 . Suppose

that two of them had the

rnsame remainder when divided by . Let the two numbers be and ,

where jma，ima，

qq<. Then there are integers and such that jn,,10,iji

qnr，qnr，= and = jma，ima，ji

Subtracting the first equation from the second, we have

=qqn, jim,，，，，ji

Since gcd= 1, we conclude that nji, Note that 0

mn,，，，，

ncontradiction. Thus the integers have distinct

amamanma,,2,,1，，,，，，

nnremainders when divided by 0,1,2,,1n,. That is, each of the

numbers occur as a remainder. In particular, the number does. Let be the

integer with pb

n01,,,pn such that the number has remainder b when divided by . Then

xpma,，

xxqnb,，qnb，for some integer ,. So = and has the required property.

xpma,，q

2 Pigeonhole Principle: Strong Form

qqq,,,Theorem 2.1. Let be positive integers. If 12n

qqqn，，，,，1 12n

nqobjects are put into boxes, then either the 1st box contains at

least objects, or the 2nd box 1

qqcontains at least objects,, the nth box contains at least objects.

2n

q,1Proof. Suppose it is not true, that is, the th box contains at

most objects, = iii

n. Then the total number of objects contained in the boxes can be at

most 1,2,,n ,qqqn，，，, qqq,，,，，,111，，，，，，12n12n

which is one less than the number of objects distributed. This is a

contradiction. The simple form of the pigeonhole principle is obtained

from the strong form by taking qqq,,,,2 12n

Then

qqqn，，，,+1= = 21nn,，n，112n

In elementary mathematics the strong form of the pigeonhole

principle is most often applied in the

qqqr,,,,special case when . In this case the principle becomes: 12n

rn, If objects are put into boxes, then at least one of the boxes

contains or nr,，11，，

more of the objects.

Equivalently,

aaa,,,n, If the average of nonnegative integers is greater than ,

< r,112n

aaa，，，12n> r,1n

rthen 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 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. 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 smaller 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 alignment, 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 sectors 10020020,000，,among the 200 ways is Note that there are only 200

ways. Then there is at

20,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，1

an increasing subsequence of length or a decreasing subsequence of

length . n，1n，1Proof. Suppose there is no increasing subsequence of

length . We suffices to show that there n，1

must be a decreasing subsequence of length . n，1

laLet be the length of the longest increasing subsequence which

begins with , kk

2. Since it is assumed that there is no increasing subsequence of

length , we 11,,，knn，1

1,,lnhave for all . By the strong form of the pigeonhole principle,

of the kn，1k

2lll,,,integers must be equal, say, n，1212n，1

lll,,, kkk，112n

2aa,kkkkwhere << < . If there is one such that , n，21,,1,,in，，kki12n，1ii，1

lathen any increasing subsequence of length beginning with will

result a subsequence k，1kii，1

l，1aallof length beginning with by adding in the front; so > ,

which is k，1kkkk，1iiiii

llcontradictory to =. Thus we must have kk，1ii

aaa,,, kkk1211，，n

which is a decreasing subsequence of length . n，1

(美)Richard A. Brualdi Introductory Combinatorics (Third Edition)

America Prentice Hall 2002 年1月