复旦大学：《离散数学 Discrete Mathematics（上）》英文课件（赵一鸣）07/30

3.5 Paradox ☆1. Russells paradox 令A∈A,AgA。 o Russells paradox: Let SAAsA. The question is, does s∈S sie.S∈ Sor SEs? IsEs, 冷IfS∈S, ☆ The statements"S∈s"and"SgS" cannot both be true. thus the contradiction

3.5 Paradox ❖ 1.Russell’s paradox ❖ AA, AA。 ❖ Russell’s paradox: Let S={A|AA}. The question is, does SS? ❖ i.e. SS or SS? ❖ If SS, ❖ If SS, ❖ The statements " SS " and " SS " cannot both be true, thus the contradiction

☆2. Cantor, s paradox 81899, Cantor's paradox, sometimes called the paradox of the greatest cardinal expresses what its second name would imply--that there is no cardinal larger than every other cardinal 冷 Let s be the set of all sets..S?≤|P(S)or P(S)?≤(S .g The third crisis in mathematics

❖ 2.Cantor’s paradox ❖ 1899,Cantor's paradox, sometimes called the paradox of the greatest cardinal, expresses what its second name would imply--that there is no cardinal larger than every other cardinal. ❖ Let S be the set of all sets. |S|?|P (S)| or |P (S)|?|(S)| ❖ The Third Crisis in Mathematics

II Introductory Combinatorics Chapter 4 Introductory Combinatorics Counting

II Introductory Combinatorics Chapter 4 Introductory Combinatorics Counting

Combinatorics, is an important part of discrete mathematics Techniques for counting are important in computer science, especially in the analysis of algorithm. ☆ sorting, searching g combinatorial algorithms . Combinatorics

❖ Combinatorics, is an important part of discrete mathematics. ❖ Techniques for counting are important in computer science, especially in the analysis of algorithm. ❖ sorting,searching ❖ combinatorial algorithms ❖ Combinatorics

☆ existence counting 今 construction ☆ optimization 4 existence Pigeonhole principle .& o Counting techniques for permutation and combinations, and Generating function, and Recurrence relations

❖ existence ❖ counting ❖ construction ❖ optimization ❖ existence :Pigeonhole principle ❖ Counting techniques for permutation and combinations,and Generating function, and Recurrence relations

4.1 Pigeonhole principle .o Dirichlet 1805-1859 ☆ shoebox principle

4.1 Pigeonhole principle ❖ Dirichlet,1805-1859 ❖ shoebox principle

4.1.1 Pigeonhole principle Simple form o If n pigeons are assigned to m pigeonholes, and m<n, then at least one pigeonhole contains two or more pigeons. &o Theorem 4.1: If n+1 objects are put into n boxes. then at least one box contain tow or more of the objects

4.1.1 Pigeonhole principle :Simple Form ❖ If n pigeons are assigned to m pigeonholes, and m<n, then at least one pigeonhole contains two or more pigeons. ❖ Theorem 4.1: If n+1 objects are put into n boxes, then at least one box contain tow or more of the objects

o Example 1: Among 13 people there are two who have their birthdays in the same month. g Example 2: Among 70 people there are six who have their birthdays in the same month. Example 3: From the integers 1, 2,..., 2n, we choose n+l intergers. Show that among the integers chosen there are two such that one of them is divisible by the other. 令2k×a 2r×aand28×a

❖ Example 1: Among 13 people there are two who have their birthdays in the same month. ❖ Example 2: Among 70 people there are six who have their birthdays in the same month. ❖ Example 3:From the integers 1,2,…,2n, we choose n+1 intergers. Show that among the integers chosen there are two such that one of them is divisible by the other. ❖ 2 ka ❖ 2 ra and 2sa

g Example 4: Given n integers a1,a2,. an, there exist integers k and with0≤k<≤ n such that ak+i+ak+2+. +ar is divisible by n ☆a1,a1+a2,a1+a2+a3y…,a1+a2+…+an 4 Example 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

❖ Example 4:Given n integers a1 ,a2 ,…,an , there exist integers k and l with 0k<ln such that ak+1+ak+2+…+al is divisible by n. ❖ a1 , a1+a2 , a1+a2+a3 ,…,a1+a2+…+an . ❖ Example 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

4 Concerning Application 5, Show that there exists a succession of (consecutive) days during which the chess master will have played exactly 22 games. o(1The chess master plays few than 12 games at least one week 8(2)The chess master plays exactly 12 games each week

❖ Concerning Application 5, Show that there exists a succession of (consecutive) days during which the chess master will have played exactly 22 games. ❖ (1)The chess master plays few than 12 games at least one week ❖ (2)The chess master plays exactly 12 games each week