Intro to Discrete Structures Lecture 11 Pawel M Wocjan School of Electrical Engineering and Computer Science University of Central Florida wocjan eecs ucf edu Intro to Discrete StructuresLecture 11 p 1 29 Factorial Function The factorial function f N Z is denoted by f n n The value of f n n is the product of the first n positive integers so n 1 2 n 1 n and 0 1 Intro to Discrete StructuresLecture 11 p 2 29 Strictly Increasing Decreasing Definition 6 Let f A B with A B R The function f is called increasing if f x f y strictly increasing if f x f y whenever x y Intro to Discrete StructuresLecture 11 p 3 29 Addition Multiplication of Functions Definition 3 Let f1 f2 A R Then f1 f2 and f1 f2 are also functions from A to R defined by f1 f2 x f1 x f2 x f1 f2 x f1 x f2 x 1 2 Intro to Discrete StructuresLecture 11 p 4 29 Sequences and Summations Intro to Discrete StructuresLecture 11 p 5 29 Sequences Definition 1 A sequence is a function from a subset of the set of integers usually the set 0 1 2 or the set 1 2 3 to a set S We use the notation an to denote the image of the integer n We call an a term of the sequence Example 1 Consider the sequence an with an 1 n Intro to Discrete StructuresLecture 11 p 6 29 Geometric Progression Definition 2 A geometric progression is a sequence of the form a ar ar2 arn where the initial term a and the common ratio r are real numbers Remark A geometric progression is a discrete analogue of the exponential function f R R x 7 arx Intro to Discrete StructuresLecture 11 p 7 29 Arithmetic Progression Definition 2 An arithmetic progression is a sequence of the form a a d a 2d a nd where the initial term a and the common difference r are real numbers Remark A geometric progression is a discrete analogue of the linear function f R R x 7 dx a Intro to Discrete StructuresLecture 11 p 8 29 The Tower of Hanoi We are given a tower of n discs initially stacked in decreasing size on one of three pegs The objective is to transfer the entire tower to one of the other pegs moving only one disc at a time and never moving a larger one onto a smaller Find a simple expression for Tn the number of minimal moves required to accomplish this Intro to Discrete StructuresLecture 11 p 9 29 Slicing Pizza How many slices of pizza can a person obtain by making n straight cuts with a pizza knife Or more academically What is the maximum number of Ln of regions defined by n lines in the plane Find a simple expression for Ln Intro to Discrete StructuresLecture 11 p 10 29 The Josephus Problem We start with n people numbered 1 to n around a circle and we eliminate every second remaining person until only one survives Denote this person by Jn For example here s the starting configuration for n 10 The elimination order is 2 4 6 8 10 3 7 1 9 so J10 5 survives Intro to Discrete StructuresLecture 11 p 11 29 Solution to the Josephus Problem Find a closed form formula for an that makes it possible to efficiently compute Jn for large n Intro to Discrete StructuresLecture 11 p 12 29 Solution to the Josephus Problem Find a closed form formula for Jn that makes it possible to efficiently compute Jn for large n Every n N can be uniquely written as 2m with m 0 and 0 2m Observe that m log2 n and n 2m The solution is Jn 2 1 Intro to Discrete StructuresLecture 11 p 13 29 Summation We now introduce summation notation We begin by describing the notation used to express the sum of the terms am am 1 an from the sequence an We use the notation n X j m aj Pn j m aj or P 1 j n aj to represent am am 1 an Intro to Discrete StructuresLecture 11 p 14 29 Summation n X aj j m Here the variable j is called the index of summation and the choice of letter as the variable is arbitrary The index of summation runs through all integers starting with its lower limit m and ending with its upper limit n A large upper case Greek letter sigma denote the summation is used to Intro to Discrete StructuresLecture 11 p 15 29 Geometric sums Theorem 1 If a and r are real numbers and r 6 0 then n 1 n a a X if r 6 1 j r 1 ar n 1 a if r 1 j 0 Intro to Discrete StructuresLecture 11 p 16 29 Cardinality Definition 4 The sets A and B have the same cardinality iff there is a bijection from A to B Intro to Discrete StructuresLecture 11 p 17 29 Countable vs Uncountable Definition 5 A set that either finite or has the same cardinality as the set of natural numbers N 1 2 3 is called countable A set that is not countable is called uncountable The cardinality of a finite set S is denoted by S When an infinite set S is countable we denote the cardinality of S by 0 We write S 0 and say that S has cardinality aleph null Intro to Discrete StructuresLecture 11 p 18 29 Odd Numbers Example 18 Show that the set of odd natural numbers is a countable set Intro to Discrete StructuresLecture 11 p 19 29 Integers Example 19 Show that the set Z of all integers is countable Intro to Discrete StructuresLecture 11 p 20 29 Rational Numbers Example 19 Show that the set Q of positive rational numbers is countable Intro to Discrete StructuresLecture 11 p 21 29 Real Numbers Example 21 Show that the set R of real numbers is uncountable Assume the contrary Then there is a bijection N 0 1 r1 r2 r3 r4 d11 d12 d13 d14 d21 d22 d23 d24 d31 d32 d33 d34 d41 d42 d43 d44 P The decimal expansion ri j 1 dij 10j is unique provided we exclude that we disallows infinite tails 999 in the expansions Intro to Discrete StructuresLecture 11 p 22 29 Real Numbers Intro to Discrete StructuresLecture 11 p 23 29 Cantor Diagonalization Argument Form a new real number with decimal expansion r 0 d1 d2 d3 d4 where the decimal digits are determined by the following rule 4 if di i 6 4 di 5 if di i 4 Intro to Discrete StructuresLecture 11 p 24 29 Halting Problem In computability theory the halting problem is a decision problem which can be stated as follows given a description of a program decide whether the program finishes running or will run forever This is equivalent to the problem of deciding given a program and an input whether the program will eventually halt when run with that …
View Full Document
Unlocking...