2017 - 2018 Spring Semseter
MATH 3050 Discrete Mathematics Section 101 ( Barsamian )
Class Presentations
Each of you will be called upon to make class presentations ten times during the semester. Sometimes these presentations will be about introducing a new concept to the class. Other times, the presentations will involve presenting an example that illustrates a new concept. They will always involve new concepts, which means that to prepare for them, you will need to learn material that has not yet been presented in class. You will always receive your presentation assignment at least a week before you have to make the presentation, and you are welcome to come and discuss your assignment with me in the week before your presentation. Please note that the Class Presentations cannot be made-up in the case of absence, because they involve material that is part of a class lesson plan.
Fri Jan 19 ( Meeting Number 2 )
Section 2.2 Conditional Statements
- Ashley Bendict CP01: Consider these two statements:
- A: If the moon is made of green cheese, then the Chicago Cubs win the 2016 World Series.
- B: If the moon is made of green cheese, then the world is flat.
Is either of the statements true ? Explain.
- Noah Collins CP01: Use a truth table to prove that p → q is logically equivalent to ~ p ∨ q
- Matthew Connell CP01:
- Given that p → q ≡ ~ p ∨ q, use DeMorgan's Laws to find ~ ( p → q )
- Negate Statement S: If Bob is green then Carol is red.
- Devon Destocki CP01:
- Suppose that the conditional statement p → q is false. What are values of p, q ?
- Suppose that the conditional statement p → q is true. Can you determine the values of p, q ? Explain.
- Ryan Alcorn CP01:
- How does the book define the expression "P only if Q" ?
- Translate "I will have a bagel today only if today is Thursday" into a standard conditional statement.
Mon Jan 22 ( Meeting Number 3 )
Section 2.3 Valid and Invalid Arguments
Benjamin Fryman CP01: Consider Example #1 of a Statement form, shown at right.
- Make a truth table to determine if it is a valid argument form.
- Valid or not, the argument form is famous. What is it called ?
|
p → q p ∴ q |
Avery Gallagan CP01: Consider Example #2 of a Statement form, shown at right.
- Make a truth table to determine if it is a valid argument form.
- Valid or not, the argument form is famous. What is it called ?
|
p → q ~q ∴ ~p |
Alyssa Hall CP01: Consider Example #3 of a Statement form, shown at right.
- Make a truth table to determine if it is a valid argument form.
- Valid or not, the argument form is famous. What is it called ?
|
p → q q ∴ p |
Blue Kennedy CP01: Consider Example #4 of a Statement form, shown at right.
- Make a truth table to determine if it is a valid argument form.
- Valid or not, the argument form is famous. What is it called ?
|
p → q ~p ∴ ~q |
Five of you will answer questions about valid arguments.
- Kristen McLean CP01: Give an example of an invalid argument that commits the Converse Error. ( Make up your own example. )
- Peter Metro CP01: Give an example of an invalid argument that commits the Inverse Error. ( Make up your own example. )
- Jalen Perkins CP01: Give an example of a valid argument that has false premises and a true conclusion. ( Make up your own example. )
- Alexandria Schira CP01: Give an example of a valid argument that has false premises and a false conclusion. ( Make up your own example. )
- Johnathon Schmelzer CP01: Give an example of an invalid argument that has true premises and a true conclusion. ( Make up your own example. )
Wed Jan 24 ( Meeting Number 4 )
Section 3.1 Predicates and Quantified Statements I
- Allison Vedder CP01: Consider the predicate A(x) that is the following sentence: "x2 > x."
- Let variable x have domain the D = { -3, -2, 2, 3 }. What is the truth set of predicate A(x)?
- Let variable x have domain the D = R. What is the truth set of predicate A(x)?
- John Whitt CP01:
- Let x be a variable with domain R, and let P( x ) be the predicate "x ≤ 5 → x2 ≤ 25." Find the truth set.
Hint: Break the domain up into smaller sets. For instance, a smart way would to be consider the following five sets:
{x: x < -5},{-5},{x: -5 < x < 5},{5},{x: 5 < x}
Determine whether P( x ) is true on each of those five sets. Then use that information to determine the truth set of P( x ).
- Again let x be a variable with domain R, but let Q( x ) be the predicate "x2 ≤ 25 → x ≤ 5." Find the truth set of Q( x ).
- Hayden Yamamoto CP01: Let m,n be variables with domain the set Z.
- Let predicate P( m,n ) be the sentence "m/n is an integer."
- Give an example of two integers a,b such that P( a,b ) is true.
- Give an example of two integers c,d such that P( c,d ) is true.
- Give an example of two integers e,f such that P( e,f ) is true and P( f,e ) is false.
- Give an example of two integers g,h such that P( g,h ) is true and P( h,g ) is also true.
- Now let predicate Q( m,n ) be the sentence "If m/n is an integer then n/m is an integer."
That is predicate Q( m,n ) is the sentence "If P( m,n ) then P( n,m )."
- Give three examples of pair of integers ( m,n ) that are in the truth set of Q( m,n ).
- Ashley Benedict CP02:
- Let A be the following statement: ∀ x ∈ Z ( x2 ≥ x ). Is statement A true? Explain.
- Let B be the following statement: ∀ x ∈ R ( x2 ≥ x ). Is statement B true? Explain.
- Ryan Alcorn CP02:
- Let A be the following statement: ∃ x ∈ R ( x2 < x ). Is statement A true? Explain.
- Let B be the following statement: ∃ x ∈ R ( |x| < x ). Is statement B true? Explain.
- Noah Collins CP02:
- Consider the predicate P( x ) from earlier: "x ≤ 5 → x2 ≤ 25."
Suppose that we park a universal quantifier in front of the predicate to get the following statement A:
∀ x ∈ R ( x ≤ 5 → x2 ≤ 25).
Is statement A true ? Explain.
- Consider the predicate Q( x ) from earlier: "x2 ≤ 25 → x ≤ 5."
Suppose that we park a universal quantifier in front of the predicate to get the following statement B:
∀ x ∈ R (x2 ≤ 25 → x ≤ 5).
Is statement B true ? Explain.
Fri Jan 26 ( Meeting Number 5 )
Section 3.2 Predicates and Quantified Statements II
- Matthew Connell CP02:
- Let A be the statement "Every car in the Morton Hall parking lot is silver". What is ~ A?
- More generally, let A be the universal statement, ∀ x in D ( Q( x ) ). What is ~ A ?
- Devon Destocki CP02:
- Let B be the statement “There exists a car in the Morton Hall parking lot that is neon green”. What is ~ B?
- More generally, let B be the existential statement, ∃ x in D ( Q( x ) ). What is ~ B?
- Benjamin Fryman CP02:
- Let C be the universal conditional statement ∀ x in D ( If P( x ) then Q( x ) ). What is the negation, ~ C?
- As a specific example, let C be the following universal conditional statement: ∀ x ∈ R ( x ≤ 5 → x2 ≤ 25 ). Find the negation ~ C.
- For the specific example given, which is true, C or ~ C ? Explain.
- Avery Gallagan CP02:
- Let S be the following universal statement: "Every prime number is odd." Find the negation, ~ S.
- Which is true, S or ~ S ? Explain.
- Start over. Rewrite the original statement S as a universal conditional statement (also called S).
- Find the negation of the universal conditional statement version of S.
- Alyssa Hall CP02:
- Consider again the universal conditional statement C that Fryman discussed earlier: ∀ x ∈ R ( x ≤ 5 → x2 ≤ 25 ).
- Write the converse, contrapositive, and inverse of C
- Consider the four statments: original statement C, converse, contrapositve, inverse. Which are true and which are false? Explain.
- Blue Kennedy CP02:
- Let S be the following universal conditional statement: ∀ n ∈ Z ( If 6/n is an integer, then n=2 or n=3 ).
- Write the converse, contrapositive, inverse, and negation of S
- Consider the five statments: original statement S, converse, contrapositve, inverse, negation. Which are true and which are false? Explain.
Mon Jan 29 ( Meeting Number 6 )
Section 3.3 Statements with Multiple Quantifiers
Remark about New Notation for Sets of Numbers
We have used the symbols R, Q, R for the sets of Real Numbers, Rational Numbers, and Integers. Superscripts can be added to these symbols to describe subsets of those sets. Here are the common superscripts, shown only for subsets of Real Numbers, but equally applicable to subsets of Rational Numbers and subsets of Integers.
- R+ = Rpos = the set of all positive real numbers. That is, x > 0.
- Rnonneg = the set of all nonnegative real numbers. That is, x ≥ 0.
- R* = Rnonzero = the set of all nonzero real numbers. That is, x ≠ 0.
Changing the order of multiple quantifiers.
In each pair of statements, Statement B is obtained by switching the order the quantifiers of Statement A.
- Which of the statements are true ? ( might be one or both ) Explain.
- One of the two statments is famous property of real numbers. Which statement? Bonus (2 points): What is the name of the property? Explain.
- Find the negation of any of any of the statements that are false.
- Kristen McLean CP02:
- Statement A: ∀ x ∈ R ( ∃ y ∈ Z ( x < y ) )
- Statement B: ∃ y ∈ Z ( ∀ x ∈ R ( x < y ) )
- Peter Metro CP02:
- Statement A: ∀ x ∈ R ( ∃ y ∈ R ( x + y = x ) )
- Statement B: ∃ y ∈ R ( ∀ x ∈ R ( x + y = x ) )
- Jalen Perkins CP02:
- Statement A: ∀ x ∈ R ( ∃ y ∈ R ( x + y = 0 ) )
- Statement B: ∃ y ∈ R ( ∀ x ∈ R ( x + y = 0 ) )
- Alexandria Schira CP02:
- Statement A: ∀ x ∈ R ( ∃ y ∈ R ( xy = x ) )
- Statement B: ∃ y ∈ R ( ∀ x ∈ R ( xy = x ) )
- Johnathon Schmelzer CP02:
- Statement A: ∀ x ∈ R* ( ∃ y ∈ R* ( xy = 1 ) )
- Statement B: ∃ y ∈ R* ( ∀ x ∈ R* ( xy = 1 ) )
Changing the domain in quantifiers.
Consider statement S: ∃ x ∈ D ( ∀ y ∈ D ( xy > y ) ).
- Allison Vedder CP02: Write the negation for S.
- John Whitt CP02: Is Statement S true when D = Z ? Explain.
- Hayden Yamamoto CP02: Is Statement S true when D = R ? Explain.
- Ryan Alcorn CP03: Is Statement S true when D = R+ ? Explain.
Interchanging ∀ and ∃ in multiple quantifiers.
- Ashley Benedict CP03: Consider Statement A and Statement B, which is obtained by interchanging ∀ and ∃ in the quantifiers of Statement A.
- Statement A: ∀ x ∈ R+ ( ∃ y ∈ R+ ( y < x )
- Statement B: ∃ x ∈ R+ ( ∀ y ∈ R+ ( y < x )
Is either of these statements true ? Explain.
Interchanging x and y in the quantifiers.
Consider Statement A and Statement B, which is obtained by interchanging x and y in the quantifiers of Statement A.
- Statement A: ∀ x ∈ D ( ∃ y ∈ D ( y = 2x + 1 )
- Statement B: ∀ y ∈ D ( ∃ x ∈ D ( y = 2x + 1 )
- Noah Collins CP03: Let the domain D be the set R. Is either of the statements A, B true ? Explain.
- Matthew Connell CP03: Let the domain D be the set Z. Is either of the statements A, B true ? Explain.
Choosing correct order for symbols to create a true statement.
- Devon Destocki CP03: Consider the sentence ∀ x ∈ ____ ( ∃ y ∈ _____ ( y = 1/x ) ). Choose domains that work from this list of possible domains: R+, Q, Z*. Explain. ( You can only use a domain once. )
- Benjamin Fryman CP03: You find thirteen cards scattered on the ground. They have the following symbols on them:
R |
Z+ |
x |
y |
y = √ x |
∀ |
∃ |
∈ |
∈ |
( |
( | ) |
) |
Assemble the cards in an order that makes a correct statement. Explain.
Wed Jan 31 ( Meeting Number 7 )
3.4 Arguments with Quantified Statements
Seven Students: Are these arguments valid or invalid ? Justify by citing a valid argument form or common error form. If possible, draw a Venn diagram to illustrate.
- Alyssa Hall CP03:
All freshmen must take writing.
Caroline is a freshman.
∴ Caroline must take writing.
- Blue Kennedy CP03:
For all students, if the student is a Freshman then the student must take writing.
Caroline is a student and is a freshman.
∴ Caroline must take writing.
- Kristen McLean CP03:
For all pairs of real numbers, if the product of the numbers is 0, then at least one of the numbers is zero.
x is a real number such that neither (2x + 1) nor (x - 7) equals 0.
∴ the product (2x + 1)(x - 7) is not 0.
- Peter Metro CP03:
All polynomial functions are differentiable.
All differentiable functions are continuous.
∴ all polynomial functions are continuous.
- Jalen Perkins CP03:
All healthy people eat an apple a day.
Keisha eats an apple a day.
∴ Keisha is a healthy person.
- Alexandria Schira CP03:
All healthy people eat an apple a day.
Herbert is not a healthy person.
∴ Herbert does not eat an apple a day.
- Johnathon Schmelzer CP03:
The sum of any two rational numbers is rational.
The sum r + s is rational.
∴ The numbers r and s are both rational.
Next Three Students: Rewrite the argument so that its first statement is in the form of a universal conditional statement. (Notice that this can be done in two ways, because once you find a universal conditional statement that works, you can also use the contrapositive of that statement.) Are these arguments valid or invalid ? Justify by citing a valid argument form or common error form. If possible, draw a Venn diagram to illustrate.
- Allison Vedder CP03:
No good car is cheap.
A Yaris is cheap.
Therefore a Yaris is not good.
- John Whitt CP03:
No good car is cheap.
A Jeep Patriot is not a good car.
Therefore a Jeep Patriot is cheap.
- Hayden Yamamoto CP03:
No perfect squares are prime.
n is not a perfect square.
Therefore, n is prime.
Mon Feb 5 ( Meeting Number 9 )
4.1 Direct Proof and Counterexample I: Introduction
- Ryan Alcorn CP04:
- Is 0 even ? Explain
- Can negative numbers be even ? Can they be odd ? Explain.
- Student: Are even & odd opposites ? That is, is every integer either even or odd ? Explain.
- Assume that r and s are particular integers (a) is 4rs even ? (b) is 6r + 4s2 + 3 odd ? Explain.
- Ashley Benedict CP04:
- Is 1 prime ? Explain.
- Can negative numbers be prime ? Can they be composite ? Explain.
- Are prime & composite opposites ? That is, is every integer either prime or composite ? Explain.
- If r and s are positive integers, is r2 + 2rs + s2 is prime or composite or neither ? Explain.
- Noah Collins: Prove or disprove the following statements.
- ∃ n ∈ Z (2n2 - 5n + 2 is prime.)
- ∀ n ∈ Z (2n2 - 5n + 2 is composite.)
- ∀ n ∈ Z (2n2 - 5n + 2 is prime OR 2n2 - 5n + 2 is composite.)
- Matthew Connell CP04: Prove or disprove: ∀ n ∈ Z ( If n is odd then (n - 1)/2 is odd.)
- Devon Destocki CP04: Consider Statement S: ∀ n ∈ D (n2 - n + 11 is prime.)
- Let D = {1,2,3,4,5,6,7,8,9,10}. Prove that S is true using the method of exhaustion.
- Now let D = Z+. Is S true or false? Explain.
Wed Feb 7 ( Meeting Number 10 )
4.2 Direct Proof and Counterexample II: Rational Numbers
- Benjamin Fryman CP04:
Consider the list of numbers below. Which represent rational numbers. Which represent real numbers? Explain.
- 7
- -5
- 0
- 0/5
- 5/0
- 753.86234
- 753.86234234234… (repeating decimal)
- Prove this statement: Every integer is a rational number.
- Consider numbers whose decimal expansions terminate. Are they rational numbers or irrational ? Explain with an example. (It can be an example that you have already discussed.)
- Consider numbers whose decimal expansions repeat. Are they rational numbers or irrational ? Explain with an example. (It can be an example that you have already discussed.)
- Is π rational ?
- Does the exact decimal expansion for π ever ever terminate or ever repeat ? How do you know ? Explain.
- Alyssa Hall CP04:
- What is the Zero Product Property ?
- Write the Zero Product Property as a universal conditional statement. Then write the contrapositive of that universal conditional statement.
- Why is the Zero Product Property introduced in this section on Rational Numbers ? Give an example of how the Zero Product Property is used in Section 4.2.
- Blue Kennedy CP04: Prove: ∀ n ∈ Z (If n is odd then n2+n is even.)
- Kristen McLean CP04: Consider the statement "If p is any even integer and q is any odd integer, then (p + 1)2 – (q - 1)2 is odd."
- Rewrite the statement more clearly using quantifiers.
- Prove the statement.
- Peter Metro CP04: Consider the statement "The square of any rational number is rational"
- Rewrite the statement more clearly using quantifiers.
- Prove the statement.
- Jalen Perkins CP04: Consider the statement "The product of any two rational numbers is rational"
- Rewrite the statement more clearly using quantifiers.
- Prove the statement.
Fri Feb 9 (Meeting Number 11 )
4.3 Direct Proof and Counterexample III: Divisibility
- Alexandria Schira CP04:
- Do the symbols 5 / 7 and 5 | 7 mean the same thing ? Explain.
- Do the symbols 2 / 6 and 2 | 6 mean the same thing ? Explain.
- Frick and Frack are arguing. Frick says that 3 / 0 is undefined. Frack says that 3 | 0 is true. Who is right ? Explain.
- Donkey and Elephant are arguing. Donkey says that 0 / 5 is zero. Elephant says that 0 | 5 is false. Who is right ? Explain.
- Johnathon Schmelzer CP04: Consider the statement "If ab | c then a | c and b | c."
- Write the statement more precisely using quantifiers.
- Prove or disprove the statement.
- Allison Vedder CP04: Consider the statement "If a | bc then a | b or a | c."
- Write the statement more precisely using quantifiers.
- Prove or disprove the statement.
- John Whitt CP04: Consider the statement "If a | b then a2 | b2."
- Write the statement more precisely using quantifiers.
- Prove or disprove the statement.
Mon Feb 12 (Meeting Number 12 )
4.4 Direct Proof and Counterexample IV: Division into Cases and the Quotient-Remainder Theorem
- Ryan Alcorn CP05:
- Find 50 div 7 and 50 mod 7 and show the corresponding n = dq + r equation.
- Find -50 div 7 and -50 mod 7 and how the corresponding n = dq + r equation.
- Find 56 div 7 and 56 mod 7 and show the corresponding n = dq + r equation.
- Ashley Benedict CP05: If c is an integer such that c mod 13 = 5, then what is 6c mod 13? In other words if division of c by 13 gives a remainder of 5, what is the remainder when 6c is divided by 13? Explain using n = dq + r equations.
- Noah Collins CP05: What is the parity property, and what is the parity property theorem? Explain
- Matthew Connell CP05: Use quotient remainder theorem with d = 3 to prove that the square of any integer has form 3k or 3k + 1
Wed Feb 14 (Meeting Number 13)
Section 4.6: Indirect Argument: Contraposition and Contradiction
- Devon Destocki CP05: (A claim to be proven directly.) Consider the following statement S: "There is no least positive rational number"
- Write statement S using variables p,q with domain the set Q+ of positive rational numbers and appropriate quantifiers.
- Prove S directly.
- Benjamin Fryman CP05: (A claim to be proven directly.)
- Write the Quotient Remainder Theorem with d = 5 and an unknown n. What does the remainder r have to be if the unknown n is going to be divisible by 5?
- Let n be the quantity 5m + 2, and think about what the Quotient Remainder Theorem tells you. Is n divisible by 5?
- Prove the following statement S: ∀ m ∈ Z (5m + 2 is not divisible by 5.)
- Alyssa Hall CP05: (A claim to be proven by proving the contrapositive)
The goal is to prove statement A: ∀ n ∈ Z ( If n2 is even then n is even.)
- Write the contrapositive of A.
- Prove the contrapositive.
- Blue Kennedy CP05: (A claim to be proven by proving the contrapositive)
The goal is to prove statement B: ∀ a,b,c ∈ Z ( If a does not divide bc then a does not divide b.)
- Write the contrapositive of B.
- Prove the contrapositive.
Fri Feb 16 (Meeting Number 14)
Section 4.7: Indirect Argument: Two Classical Theorems
- Kristen McLean CP05:
- Simplify (pm )n
- Simplify (pm )2
- Simplify (pmqn)2
- Peter Metro CP05: Suggested Exercise 4.7 # 4 asks you to prove or disprove this claim: "3sqrt(2) - 7 is irrational". Find two resources in Section 4.7 of the book that provide models that will show you how to do that exercise. (You don't have to do the exercise. Just find the two resources.)
- Jalen Perkins CP05:
- Find an example of positive irrational numbers x,y whose sum x + y is rational."
- Find an example of positive irrational numbers x,y whose sum x + y is irrational."
- Alexandria Schira CP05:
- Find an example of positive irrational numbers x,y whose product xy is rational."
- Find an example of positive irrational numbers x,y whose product xy is irrational."
- Johnathon Schmelzer CP05:
- Find an example of a positive rational number x whose square root, sqrt(x), is rational."
- Find an example of a positive rational number x whose square root, sqrt(x), is irrational."
- Allison Vedder CP05: Consider Statement S: ∀ x ∈ Z, p ∈ Primes ( If p ∣ n then p ∤ (n + 1) )
- Find ~S
- (Question about proof structure.) Suppose that the goal is to use the Method of Contradiction to prove S. How will the proof have to start? (You don't have to do the proof. Just explain how the proof would have to start.)
- John Whitt CP05:
- Find the negation of this statement: ∀ p ∈ B (∀ x,y,z ∈ Z (xp + yp ≠ zp))
- Find the negation of this statement: ∀ n ∈ C (∀ x,y,z ∈ Z (xn + yn ≠ zn))
- Find the contrapositive of this statement: If (∀ p ∈ B (∀ x,y,z ∈ Z (xp + yp ≠ zp))) then ( ∀ n ∈ C (∀ x,y,z ∈ Z (xn + yn ≠ zn)))
Wed Feb 21 (Meeting Number 16 )
Section 5.1 Sequences
Three examples involving converting an explicit expression to one abbreviated using summation or product notation
- Ryan Alcorn CP06: 5.1 # 44
- Ashley Benedict CP06: 5.1 # 45
- Noah Collins CP06: 5.1 # 50
Five examples involving computing the values of sums and products
- Matthew Connell CP06: 5.1 # 21
- Devon Destocki CP06: 5.1 # 22
- Benjamin Fryman CP06: 5.1 # 24
- Alyssa Hall CP06: 5.1 # 25
- Blue Kennedy CP06: 5.1 # 26
Fri Feb 23 (Meeting Number 17 )
Section 5.1 Sequences, continued
Four examples involving computing the value of expressions involving factorial notation.
- Kristen McLean CP06: Compute 6!/4! Show the details clearly.
- Peter Metro CP06: Compute 6!/1! Show the details clearly.
- Jalen Perkins CP06: Compute 6!/0! Show the details clearly.
- Alexandria Schira CP06: Compute n!/(n - 2)! Show the details clearly.
Three examples involving computing the value of expressions involving n choose r notation.
- Johnathon Schmelzer CP06: 5.1 # 72 Show the details clearly.
- Allison Vedder CP06: 5.1 # 74 Show the details clearly.
- John Whitt CP06: 5.1 # 76 Show the details clearly.
Fri Mar 2 (Meeting Number 19 )
Section 5.2 Induction II
Preparatory Work for Induction Proofs of Statements about Divibility
Mark will be presenting proofs of the following two Statements about Divisibility using the Method of Proof by Induction
- Statement A is ∀ n ∈ Z, n ≥ 0 ( n2 - 10n + 6 is divisible by 3.)
- Statement B is ∀ n ∈ Z, n ≥ 0 ( 9n - 5n is divisible by 4.)
Your job is to do the following preliminary work for the proofs
- Write the predicate P(n).
- What is the number playing the role of a ?
- Write the expression for P(a).
- Write the expression for P(k).
- Write the expression for P(k+1).
(Your job is not to do the proof. Mark will do the proof. You just do the preliminary work.)
- Ryan Alcorn CP07: Do the preliminary work for the proof of Statement A.
- Ashley Benedict CP07: Do the preliminary work for the proof of Statement B.
Mon Mar 5 (Meeting Number 20 )
Section 5.2 Induction II
Preparatory Work for Induction Proofs of Statements Involving Inequalities
Mark will be presenting proofs of the following three Statements Involving Inequalities using the Method of Proof by Induction
- Statement C is ∀ n ∈ Z, n ≥ 4 ( 3n < (n + 1)! )
- Statement D is ∀ n ∈ Z, n ≥ 3 ( (1 + 2n) < 2n )
- Statement E is ∀ n ∈ Z, n ≥ 10 ( n3 < 2n )
Your job is to do the following preliminary work for the proofs
- Write the predicate P(n).
- What is the number playing the role of a ?
- Write the expression for P(a).
- Write the expression for P(k).
- Write the expression for P(k+1).
(Your job is not to do the proof. Mark will do the proof. You just do the preliminary work.)
- Noah Collins CP07: Do the preliminary work for the proof of Statement C.
- Matthew Connell CP07: Do the preliminary work for the proof of Statement D.
- Devon Destocki CP07: Do the preliminary work for the proof of Statement E.
Wed Mar 7 (Meeting Number 21 )
Section 6.1 Set Theory
- Benjamin Fryman CP07: Exercise 6.1#18. (The symbol φ represents the empty set.)
- Is the number 0 in φ ? Explain.
- Is φ = {φ} ? Explain.
- Is φ ∈ {φ} ? Explain.
- Is φ ∈ φ ? Explain.
- Is φ ⊆ φ ? Explain.
- Alyssa Hall CP07:
- Do Even & Odd Numbers form a partition of the Integers? Explain.
- Do Prime & Composite Numbers form a partition of the Integers? Explain.
- Do Positive & Negative Numbers form a partion of the Real Numbers? Explain.
- Do Integers & Rationals form a partition of the Real Numbers? Explain.
- Do Rational & Irrational numbers form a partion of the Real Numbers? Explain.
- Blue Kennedy CP07: Write the Power Set of {a,b,c}
- Kristen McLean CP07: Suppose X = {a,b} and Y = {1,2}.
- Write X × Y.
- Find the Power Set of X × Y.
Fri Mar 9 (Meeting Number 22 )
Section 6.2 Properties of Sets
- Peter Metro CP07: The goal is to understand and prove the following subset relation
Theorem 6.2.1(2)(a): ∀ A,B ( A ⊆ A ∪ B )
- Draw a Venn Diagram to illustrate.
- Proof Structure: How will the proof have to begin and end? (Show the frame)
- Do the proof. Hint: The book proves another simple subset relation in Example 6.2.1. The book’s proof is only three lines long. (Then the author discusses the proof for a few paragraphs.) That should give you an idea of how to build a proof.
- Jalen Perkins CP07: (Exercise 6.2#7) The goal is to understand and then write the structure of the proof of the following set equality:
Theorem 6.2.2(9)(b): ∀ A,B ( (A ∩ B)c = Ac ∪ Bc )
- Draw a Venn Diagram to illustrate.
- Proof Structure: Show the structure of the proof (the frame). (You don’t have to do the proof.)
- Hint: The book provides an example of the structure of a proof on page 357 in Example 6.2.2, which discusses the proof of Theorem 6.2.2(3)(a). That should give you an idea of how to illustrate the structure of a proof.
- Hint: The book also provides a proof of a similar Theorem 6.2.2(9)(a) on pages 360-361. That should give you an idea of the content of the structure.
- Alexandria Schira CP07: (Exercise 6.2#15) The goal is to build a simple proof of the following statement:
∀ A,B ( If A ⊆ B then Bc ⊆ Ac )
- Draw a Venn Diagram to illustrate.
- Proof Structure: How will the proof have to begin and end? (Show the frame)
- Do the proof. Hint: Work forward from the beginning statement. As the second statement in the proof, write the universal conditional statement that corresponds to A ⊆ B.
And work backward from the ending statement. As the second-to-last statement in the proof, write the universal conditional statement that corresponds to Bc ⊆ Ac.
This narrows the gap in the proof structure.
Mon Mar 19 (Meeting Number 23)
Section 6.3 Proofs, Disproofs, and Algebraic Proofs
Remember that you are welcome to discuss your Class Presentation with Mark Barsamian.
- Johnathon Schmelzer CP07: (suggested exercises 6.3#10,13)
Consider the following two statements:
- Statement I: For all sets A and B, if A ⊆ B then A ∩ Bc = φ
- Statement II: For all sets A, B, and C, A ∪ ( B - C ) = ( A ∪ B) - ( A ∪ C )
For each statement, do the following:
- Draw Venn Diagrams that will illustrate whether the statement is true or false
- If the statement is true, prove it using the element method of proof. (That is, prove it using the methods of Sections 6.1 and 6.2). If the statement is false, demonstrate a counterexample.
- Allison Vedder CP07: (suggested exercise 6.3#20,21)
Consider the following two statements:
- Statement I: For all sets A and B, PowerSet(A ∩ B) = PowerSet(A) ∩ PowerSet(B)
- Statement II: For all sets A, B, PowerSet(A × B) = PowerSet(A) × PowerSet(B)
For each statement, do the following:
- If the statement is true, prove it using the element method of proof. (That is, prove it using the methods of Sections 6.1 and 6.2). If the statement is false, demonstrate a counterexample.
- John Whitt CP07: (suggested exercise 6.3#34)
Consider the following statement:
- Statement: For all sets A, B, and C, (A - B) - C = A - (B ∪ C)
Do the following:
- Draw Venn Diagrams that will illustrate that the statement is true.
- Construct an algebraic proof for the statement. Cite a property from Theorem 6.2.2 Set Identitites for every step.
Fri Mar 23 (Meeting Number 25 )
Section 7.1 Functions Defined on General Sets
- Ryan Alcorn CP08:
(This is a rewording of suggested exercise 7.1#3. The problem is about a careful reading of the definition of function on page 384 of the book.)
Suppose f : X → Y is a function from a set X to a set Y.
For each statement, say whether the statement is true or false. Justify your answers. (Refer to the definition of function in your explanations.)
- If x1 = x2,
then f (x1) = f (x2).
- If f (x1) = f (x2),
then x1 = x2.
- The function f can have the same output for more than one input.
- The function f can have the same input for more than one output.
- Ashley Benedict CP08: (similar to suggested exercises 7.1#13,14 and Example 7.1.3, about function equality)
Define the set J5 = {0,1,2,3,4}.
- Define function f : J5 → J5 by f (x) = ((x + 3)2) mod 5.
- Define function g : J5 → J5 by g (x) = (x2 + 3x + 4) mod 5.
- Define function h : J5 → J5 by h (x) = (x2 + x + 4) mod 5.
Are any of these three functions equal? Explain.
- Noah Collins CP08:
(similar to suggested exercises 7.1#6 and Example 7.1.5, about thinking of sequences as functions and about the concept of function equality)
Consider the sequence 1, -1/2, 1/4, -1/8, 1/16, …
- Find an explicit formula for the sequence, using symbol an with n ≥ 0.
- Find another explicit formula for the sequence, using symbol bn with n ≥ 0.
- Find another explicit formula for the sequence, using symbol cn with n ≥ 1.
The three explicit formulas that you have found all produce the same sequence. Does that mean that the three explicit formulas are equal as functions? Discuss.
- Matthew Connell CP08: (about function equality) Consider these two functions:
- f (x) = x + 2
- g (x) = (x - 1)(x + 2)/(x - 1)
Are f and g equal as functions? Discuss.
- Devon Destocki CP08: What is IX ? Explain.
Mon Mar 26 (Meeting Number 26 )
Section 7.2: One-to-One Functions; Onto Functions
- Benjamin Fryman CP08: (problem similar to 7.2#5) Which of these are correct ways to express the fact that a function f is onto?
- every element in the codomain is the image of some element in the domain
- every element in the domain has a corresponding image in the codomain
- ∀ y ∈ Y ( ∃ x ∈ X ( f (x) = y ))
- ∀ x ∈ X ( ∃ y ∈ Y ( f (x) = y ))
- The range of f is the same as the codomain of f .
- Alyssa Hall CP08: (similar to Examples 7.2.1 and 7.2.4 and suggested exercise 7.2#9)
Let X = {a,b,c,d} and Y = {1,2,3,4,5} and Z = {p,q,r}
- Define a function f : X → Y that is one-to-one but not onto.
- Define a function g : X → Z that is onto but not one-to-one.
- Define a function h : X → X that is neither one-to-one nor onto.
- Define a function j : X → X that is both one-to-one and onto but is not the identify function IX.
- Blue Kennedy CP08: (similar to suggested exercise 7.2#18)
Consider the function f (x) = (x - 2)/(x - 3)
- What is the domain D of the function?
- Considered as a function f : D → R, is f one-to-one? Is it onto? (Hint: get a graph of f , either by hand or by using Desmos [when you present in class, use a hand-drawn graph]. Consider the line tests for one-to-one and onto.)
- What’s the range?
- Kristen McLean CP08: (similar to Blue's problem)
Consider the function f (x) = e(x).
- What is the domain D of the function?
- Considered as a function f : D → R, is f one-to-one? Is it onto? (Hint: get a graph of f , either by hand or by using Desmos [when you present in class, use a hand-drawn graph]. Consider the line tests for one-to-one and onto.)
- What’s the range?
- Peter Metro CP08: (Similar to Example 7.2.5 and suggested exercises 7.2#11,12)
- Define a function f : Z → Z by the formula f (x) = 6x + 5.
- Is f one-to-one? Prove or give a counterexample.
- Is f onto? Prove or give a counterexample.
- Define a function g : R → R by the formula g (x) = 6x + 5.
- Is g one-to-one? Prove or give a counterexample.
- Is g onto? Prove or give a counterexample.
Wed Mar 28 (Meeting Number 27 )
Section 7.2: Inverse Functions
Three students will discuss Properties of Inverse Maps in examples
- Instructions: Given a function f (x),
- Draw a graph of f.
- Draw a graph of f -1. (Refer to the instructions on the web page Graphing an Inverse Map if you need guidance.)
- Indicate which of the line tests f and f -1 pass or fail. (Explain to the class.)
- Jalen Perkins CP08: Do the above steps for the function f (x) = x2
- Alexandria Schira CP08: Do the above steps for the function f (x) = (x - 1)(x - 2)(x - 3) = x3 - 6x2 + 11x - 6
- Johnathon Schmelzer CP08: Do the above steps for the function f (x) = x3
Two students will find Formulas for Inverse Maps in examples
Allison Vedder CP08: This problem is related to 7.2#18 involving f (x) = (x - 2)/(x - 3) that Blue Kennedy discussed in class on Monday.
- Sketch a graph of f. (You can figure out the shape by using Desmos, or by using skills from precalc and calculus.)
- Sketch a graph of the inverse map f -1. (Refer to the instructions on the web page Graphing an Inverse Map if you need guidance.)
- Note the following observations about your graphs:
- Considered as a map f : R → R, the map f is not qualified to be called a function, because when x = 3, there is no corresponding y value. (The graph fails the vertical line test for functions.)
- If we define the set A = {x ∈ R | x ≠ 3}, then considered as as a map f : A → R, the map f is qualified to be called a function, because it now passes the vertical line test for function. But it fails to be onto. (Its graph fails the horizontal line test for onto because the horizontal line y = 1 does not intersect the graph. In other words for the desired output y = 1, there is no input x that will produce the output f (x) = 1.)
- If we define the set B = {x ∈ R | x ≠ 1}, then considered as as a map f : A → B, the map f is qualified to be called a function, and it is both one-to-one and onto, so its inverse map f -1 : B → A will be qualified to be called a function.
- Since the inverse map f -1 : B → A is qualified to be called a function, it should be possible to get a mathematical formula for the function f -1. The goal now is to get a mathematical formula for f -1.
- Observe that the formula f (x) = (x - 2)/(x - 3) gives you an equation y = (x - 2)/(x - 3). This equation expresses the relationship between x and y, and it is solved for y in terms of x. That is y = f (x).
- Show the steps to solve the equation y = (x - 2)/(x - 3) for x in terms of y.
- The new equation that you get expresses the same relationship between x and y as the original equation, but it is solved for x in terms of y. Any (x,y) pair that satisfies the original equation (with x considered as the input and y considered as the output) will correspond to a (y,x) pair that satisfies the new equation x = some expression involving y (with y considered as the input and x considered as the output). In other words, when you solved the equation for x in terms of y, the resulting equation is a formula for x = f -1(y).
- If one wanted, one could leave this new formula as it is, with y considered as the input and x considered as the output. But it is most common to use x as the input and y as the output.
- In your formula x = f -1(y), interchange the letters x,y to get a formula for y = f -1(x).
John Whitt CP08: This problem is related to 7.2#12 involving f (x) = 6x + 5 that Peter Metro discussed in class on Monday.
- Sketch a graph of f. (You can figure out the shape by using Desmos, or by using skills from precalc and calculus.)
- Sketch a graph of the inverse map f -1. (Refer to the instructions on the web page Graphing an Inverse Map if you need guidance.)
- Note the following observations about your graphs:
- Considered as a map f : R → R, the map f is qualified to be called a function, and it is both one-to-one and onto, so its inverse map f -1 : R → R will be qualified to be called a function.
- Since the inverse map f -1 : R → R is qualified to be called a function, it should be possible to get a mathematical formula for the function f -1. The goal now is to get a mathematical formula for f -1.
- Observe that the formula f (x) = 6x + 5 gives you an equation y = (x - 2)/(x - 3). This equation expresses the relationship between x and y, and it is solved for y in terms of x. That is y = f (x).
- Show the steps to solve the equation f (x) = 6x + 5 for x in terms of y.
- The new equation that you get expresses the same relationship between x and y as the original equation, but it is solved for x in terms of y. Any (x,y) pair that satisfies the original equation (with x considered as the input and y considered as the output) will correspond to a (y,x) pair that satisfies the new equation x = some expression involving y (with y considered as the input and x considered as the output). In other words, when you solved the equation for x in terms of y, the resulting equation is a formula for x = f -1(y).
- If one wanted, one could leave this new formula as it is, with y considered as the input and x considered as the output. But it is most common to use x as the input and y as the output.
- In your formula x = f -1(y), interchange the letters x,y to get a formula for y = f -1(x).
Fri Mar 30 (Meeting Number 28 )
Section 7.3 Composition of functions
- Ryan Alcorn CP09: Let f (x) = 3x2 + 5x + 7 and g(x) = x + 1.
Find f ○ g and g ○ f . (Show the calculations.)
- Ashley Benedict CP09: Let f (x) = (x - 2)/(x - 3) and g(x) = (3x - 2)/(x - 1).
Find f ○ g and g ○ f . (Show the calculations.)
- Noah Collins CP09: Two questions:
- Let f (x) = (x - 3)/(x - 5) and g(x) = (x - 5)/(x - 3). Are f and g inverses? Explain.
- Let f (x) = (x - 3)/(x - 5) and g(x) = (5x - 3)/(x - 1). Are f and g inverses? Explain.
- Matthew Connell CP09: Two questions:
- Let f (x) = x2 and g(x) = x1/2. Are f and g inverses? Explain.
- Let f (x) = x3 and g(x) = x1/3. Are f and g inverses? Explain.
- Devon Destocki CP09: Finding examples. (Some of your examples can be used more than once.)
- Define sets A = {a1, a2, a3} and
B = {b1, b2, b3}
and C = {c1, c2, c3}
- Find an example of maps f : A → B and g : B → C such that g ○ f is one-to-one and both f and g are one-to-one.
- Find an example of maps f : A → B and g : B → C such that g ○ f is onto and both f and g are both onto.
- Now define sets A = {a1, a2, a3} and
B = {b1, b2, b3, b4}
and C = {c1, c2, c3}
- Find an example of maps f : A → B and g : B → C such that g ○ f is one-to-one and f and g are not both one-to-one.
- Find an example of maps f : A → B and g : B → C such that g ○ f is onto and f and g are not both onto.
Wed Apr 4 (Meeting Number 30 )
Section 8.1 Relations
In class, we will see that to say that S is a relation on the set of real numbers means simply that S is a subset of R × R. That is, S is simply some set of ordered pairs of real numbers. And we will see that the symbol x S y is spoken x is related to y, and it means that the ordered pair (x,y) is an element of the set S. To define an actual relation, it must be specified what it actually means to x S y. That is, it must be specified what it actually means to say x is related to y.
For example one could say that x S y means y = 5x + 3. Then observe that the ordered pair (x,y) = (1,8) is an element of S, because the equation 8 = 5(1) +3 is true. We would say that 1 is related to 8. This could be abbreviated 1 S 8. But the ordered pair (8,1) is not an element of S, because the equation 1 = 5(8) + 3 is not true. We would say that 8 is not related to 1.
Relations on the set of real numbers can be visualized, because they are subsets of the cartesian plane R × R. A graph of a relation S on the set of real numbers is simply a picture of all of the elements of the set S. In the case of the relation S introduced above, the graph of S is just a picture of all of the ordered pairs (x,y) that satisfy the equation y = 5x + 3. In other words, the graph of S is just a line with slope m = 5 and y-intercept at (x,y) = (0,1).
Five students will each be given descriptions of relations on the set of real numbers. That means, they will be given a specification of what it actually means to say x is related to y. Their job is to draw a graph of the relation.
- Benjamin Fryman CP09: x S y means y = x2.
- Alyssa Hall CP09: x S y means y > x.
- Blue Kennedy CP09: x S y means y ≥ x.
- Kristen McLean CP09: x S y means xy = 0.
- Peter Metro CP09: x S y means y = x + some multiple of 10.
Fri Apr 6 (Meeting Number 31 )
Section 8.2 Properties of Relations
- Jalen Perkins CP09: An example of a relation, its directed graph, and its properties
Define the set A = {1,2,3,4,5,6}.
Define the set S = {(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(1,2),(2,1),(3,4),(4,3),(4,5),(5,4),(3,5),(5,3)}.
Observe that S is a relation on A. That is, S ⊆ A × A. That is, the elements of set S are ordered pairs of elements of A.
- Draw a directed graph of S.
- Is S reflexive? Explain.
- Is S symmetric? Explain.
- Is S transitive? Explain.
- Alexandria Schira CP09: An example of a relation, its graph, and its properties
Define the relation S on the set of real numbers R by saying that the symbol x S y means |x| = |y|. That is, the words x is related to y mean |x| = |y|.
- Draw the graph of S.
- Is S reflexive? Explain.
- Is S symmetric? Explain.
- Is S transitive? Explain.
- Allison Vedder CP09: An example of a relation and its properties
Define the set A = {ordered pairs (p,q such that p,q ∈ Z and q ≠ 0}.
Define the relation S on the set A by saying that the symbol (a,b) S (c,d) means ad = bc. That is, the words (a,b) is related to (c,d) mean ad = bc.
- Is S reflexive? Explain.
- Is S symmetric? Explain.
- Is S transitive? Explain.
Fri Apr 13 (Meeting Number 34 )
Section 9.1 Intro to Counting and Probability
- Ryan Alcorn CP10: Throwing two 4-sided dice. (Similar to Suggested Exercises 9.1#7,9 and Assigned Exercise H9 [2].)
Not all dice have 6 sides; other numbers of sides are possible. 4-sided dice are made in the shape of a tetrahedron (four equilateral triangles form the sides), with a number on each side. Since three sides will be facing up and one side will be facing down and hidden, it is the number that is facing down that is considered to be the value of the roll for that die.
Suppose that two 4-sided dice are thrown. One of the dice is red; the other, white. The values of the red and white rolls are recorded.
- Draw the sample space S using a table and find N(S).
- Define E to be the event that the sum of the numbers is exactly 3. Illustrate E on your drawing of the sample space, find N(E), and find P(E).
- Define F to be the event that the sum of the numbers is at most 3. Illustrate F on your drawing of the sample space, find N(F), and find P(F).
- When rolling two 4-sided dice, what is the most likely sum? Explain using your illustration of the sample space.
- Ashley Benedict CP10: Flipping a coin four times. (Similar to Suggested Exercises 9.1#11,12.)
A coin is flipped four times and the value of each flip (H or T for Heads or Tails) is recorded.
- Draw the sample space S using a table and find N(S).
- Define E to be the event that the number of heads is exactly 3. Illustrate E on your drawing of the sample space, find N(E), and find P(E).
- Define F to be the event that the number of heads is at least 3. Illustrate F on your drawing of the sample space, find N(F), and find P(F).
- When flipping a coin four times, what is the most likely number of heads? Explain using your illustration of the sample space.
- Noah Collins CP10: Urn O'Balls. (Similar to Suggested Exercises 9.1#16,18 and Assigned Exercise H9 [3].)
An urn contains two white balls labeled W1,W2, two red balls labeled R1,R2, and two green balls labeled G1,G2. In this experiment, a ball is drawn from the urn, its color recorded. Then the ball is put back into the urn and a ball is again drawn from the urn, its color recorded.
- Draw the sample space S using a table and find N(S).
- Define E to be the event that the two drawn balls are the same color. Illustrate E on your drawing of the sample space, find N(E), and find P(E).
- Define F to be the event that the two drawn balls are not the same color. Illustrate F on your drawing of the sample space, find N(F), and find P(F).
- Matthew Connell CP10: Another Urn O'Balls. (Similar to Suggested Exercises 9.1#16,18 and 9.2#6,7 and Assigned Exercise H9 [4].)
Same problem as Noah, but "without replacement". That is, the first ball drawn is not put back into the urn before the second ball is drawn.
Mon Apr 16 (Meeting Number 35 )
Section 9.2: Possibility Trees and the Multiplication Rule
- Devon Destocki CP10: World Series (Similar to Book Example 9.2.1 and Suggested Exercise 9.2#1)
In the World Series, the first team to win four games wins the series. The Indians are playing the Cubs.
- Suppose the Indians win first three games. How may ways can the series be completed? Make a possibility tree to illustrate.
- If all outcomes are equally likely and the Indians have won the first 3 games, what is the probability that the Cubs will win the Series?
- Benjamin Fryman CP10: License Plates (Similar to Book Example 9.2.2 and Suggested Exercise 9.2#14)
Ohio license plates have the form AA##AA, where the As stand for letters and the #s stand for digits.
- How many different license plates are possible?
- How many different plates if no character can be used more than once?
- The digits 0,1 and the letters O,I are problematic, because it is easy to mistake the letter for the number, and vice versa. How many plates are possible if the “bad” characters are not used (but characters are allowed to be used more than once)?
(Present your solutions to each question by identifying steps and determining how many ways each step can be performed, and then using the Multiplication Rule.)
- Alyssa Hall CP10: Choosing a Crew (Similar to Book Example 9.2.7 and Suggested Exercise 9.2#19)
A gang has four members: Arsenic, Bangs, Chopper, and Doris. They are planning a bank heist and need to choose a crew consisting of a holdup person, a lookout person, and a getaway car driver. Suppose that Arsenic cannot be the lookout person or the getaway car driver, because he is nearsighted. And Bangs cannot be the getaway car driver because his license has expired.
- Make a possibility tree showing all the ways that the heist crew can be selected, in a way that the multiplication rule cannot be used.
- Make another possiblity tree showing all the ways that the heist crew can be selected, in a way that the multiplication rule can be used.
(Be sure to study Book Example 9.2.7 and the discussion preceeding it, to get an idea of how to do this problem.)
- Blue Kennedy CP10: Counting Relations and Functions (Similar to Suggested Exercises 9.2 # 21,22)
Suppose A is a set with m elements and B is a set with n elements.
- How many relations from A to B? (This is an old question, using concepts from previous sections, but you might need to review the concepts. Remember: a relation from A to B is just a subset of the cartesian product A × B. So you’ll need to figure out how many elements are in the cartesian product A × B, and then figure out how many subsets there will be.)
- How many functions are there from A to B? (Hint: Think of describing a function f as being a process that involves numbered tasks. Task #1 is to specify the output of f that will result if the input is a1. How many ways can this task be done? Call that number n1. Task #2 is to specify the output that will result if the input is a2. (Regardless of the output that was chosen for the input a1) How many ways can this task be done? Call that number n2.
Consider having a task of choosing the output that will result from each of the possible inputs. Then use the multiplication rule: To fully describe the function, you must do all of those tasks. How many ways can that be done?
- How many one-to-one functions are there from A to B? Similar to question (b), but the idea is that when you choose the output that will result if the input is a2, it cannot be the same output that you choose for the input aa1. That will change your value of n2. And when you choose the output that will result if the input is a3, it cannot be the same as the outputs for the inputs a1 or a2. That will change your value of n3. And so on...
Wed Apr 18 (Meeting Number 36 )
Section 9.2: Permutations
- Kristen McLean CP10: Number of Ways to Seat a Group (Similar to Example 9.2#11 and Suggested Exercises 9.2 #32,33,34.)
Seven people sitting together in a row at a soccer game.
- How many ways can they be seated together in the row?
- Suppose it is a family that wants to sit with the parents on the end (with the mom on the left) and the five kids in the middle. How many ways can the family be seated?
- Suppose it is a family, and the parents want to be seated together (with the mom on the left). How many ways can the family be seated?
- Suppose it is a family that wants to sit with the parents on the end (with no preference for who sits on the left) and the five kids in the middle. How many ways can the family be seated?
- Suppose it is a family, and the parents want to be seated together (with no preference for who sits on the left). How many ways can the family be seated?
- Peter Metro CP10: Examples of Permutations (Similar to Suggested Exercise 9.2#35.)
- Give examples of three permutations of the set {a,b,c,d,e,f,g}
- Give examples of 3-permutations of the set {a,b,c,d,e,f,g}
- Jalen Perkins CP10: Computing Number of Permutations (Similar to Suggested Exercise 9.2#37)
Find P(5,3), P(5,1), P(5,5), P(5,0). (Show the computations clearly.)
- Alexandria Schira CP10: Electing Officers (Similar to Example 9.2#11 and Suggested Exercises 9.2#39)
A club has 20 members.
- How many ways are there to select a president, vice-president, secretary, treasurer?
- How many ways are there to select a the four officers if Frank insists that he be president?
Fri Apr 20 (Meeting Number 37)
Section 9.3 Counting Elements of Sets
- Ryan Alcorn CP11: Proving an Abstract Property of P(n,r) (Suggested Exercise 9.2#42)
Prove: ∀ n ∈ Z, n ≥ 3 ( P(n + 1,3) - P(n,3) = 3P(n,2) )
Hint: Don’t multiply out any of the factors. Work with the factored forms.
- Ashley Benedict CP11: Counting Strings of More Than One Size (Similar to Example 9.3.1 and Suggested Exercise 9.3#2)
How many Hexadecimal strings consist of 1 through 5 characters?
- Noah Collins CP11: Counting Strings With and Without Repeated Letters (Similar to Example 9.3.3 and Suggested Exercises 9.3#3,16)
You must choose a 5-letter string as password for an account. Any five lower case letters can be used.
- How many 5-letter strings are possible?
- How many 5-letter strings do not have any repeated letters? ("Repeated" means letters used more than once. Repeated letters do not have to be adjacent in the 5-letter string; they just have to appear more than once in the string.)
- How many 5-letter strings do have repeated letters?
- What is the probability that a randomly chosen 5-letter string does have repeated letters?
- Matthew Connell CP11: A Group of People Each Picking a Number (similar to suggested exercise 9.3#31)
A group of six people, A, B, C, D, E, F each picks an integer from 1 through 100. Their six integers are denoted mA, mB, mC, mD, mE, mF .
- What is the total number of ways in which the six integers mA, mB, mC, mD, mE, mF could be chosen?
- What is the total number of ways in which the six integers could be chosen so that no two people chose the same integer?
- What is the total number of ways in which the six integers could be chosen so that at least two people share an integer?
- What is the probability that at least two people in the group share an integer?
- Devon Destocki CP11: Counting Numbers in a List (similar to Examples 9.1.4 and 9.3.6 and suggested exercise 9.3#23)
- How many integers from 1 through 1000 are multiples of 7 or multiples of 11?
- Suppose that an integer from 1 through 1000 is chosen at random. What is the probability that the integer is a multiple of 7 or a multiple of 11?
- How many integers from 1 through 1000 are neither multiples of 7 nor multiples of 11?
Mon Apr 23 (Meeting Number 38 )
Section 9.5 Combinations
- Benjamin Fryman CP11: (Leftover from Section 9.2) Proving an Abstract Property of P(n,r)
(Suggested Exercise 9.2#42)
Prove: ∀ n ∈ Z, n ≥ 3 ( P(n + 1,3) - P(n,3) = 3P(n,2) )
Hint: Don’t multiply out any of the factors. Work with the factored forms.
- Alyssa Hall CP11: Relationship between Combinations and Permutations
(Similar to Example 9.5.3 and Suggested Exercises 9.5#3,5)
- Compute the number of 5-permutations chosen from a set of 16 elements. Show the math.
- Compute the number of 5-combinations chosen from a set of 16 elements. Show the math.
- What is the relationship between number of 5-permutations and number of 5-combinations?
- Blue Kennedy CP11: Selecting Members of a Club with Extra Requirement
(Uses formula for Number of Combinations (Section 9.3) in conjunction with the Addition Rule (Section 9.2))
(Similar to Example 9.5.5 and 9.5.6 and Suggested Exercise 9.5#6)
A class has 16 students
- How many ways can a club of 5 be selected?
- Alan and Bob are best friends and will only be in a club if the other is in the club. Now how many ways? (Hint: For part (b), you will need to use the Addition Rule from Section 9.3 along with the concept of the number of combinations from Section 9.5. Count the number of ways to form a club with neither Alan nor Bob, and count the number of ways to form a club with both Alan and Bob.)
- Alan and Bob just had an argument and refuse to be in club if the other is in the club. Now how many ways to form a club? (Hint: there is more than one way to do this part. You can use the Addition Rule, but you can also use the Subtraction Rule.)
- Kristen McLean CP11: Sampling
(Uses formula for Number of Combinations and Uses the Complement Rule)
(Similar to Suggested Exercise 9.5#16)
A jar contains a total of 100 jelly beans. 7 are black licorice flavored, which is a vile flavor and should not even be used as a flavor for candy.
A sample of 10 beans is to be taken from the jar.
- How many different 10-bean samples are possible? (Notice that order is not important. So you are really being asked to determine how many 10-element subsets can be chosen from a set of 100 elements.)
- How many 10-bean samples do not contain any licorice flavored beans?
- How many 10-bean samples will contain at least one licorice flavored bean?
- What is the probability that a randomly chosen 10-bean sample will contain at least one licorice flavored bean?
Wed Apr 25 (Meeting Number 39)
Section 9.6 r-Combinations with Repetition Allowed
- Peter Metro CP11: Selecting 12 Vegetables of Seven Different Types
(Similar to Example 9.6.2ab and Suggested Exercise 9.6#3)
A group of of 12 students goes to a farm stand. Each will buy one vegetable.
The farm stand stocks 7 different kinds of vegetables. (Assume that there are at least 12 vegetables of each kind.)
How many different selections of 12 vegetables are possible?
(Explain how you get your answer. You do not need to simplify your answer.)
- Jalen Perkins CP11: Adding a Constraint to Peter's Example
(Similar to Example 9.6.2c and Suggested Exercise 9.6#19)
- Suppose that the farm stand from Peter’s example only has 3 zucchini, but has at least 12 of each of the other 6 kinds of vegetables. How many different selections of 12 vegetables are possible in this situation?
- Suppose that the farm stand only has 3 zucchini and 4 eggplant, but has at least 12 of each of the other 5 kinds of vegetables. How many different selections of 12 vegetables are possible in this situation?
- Alexandria Schira CP11: The Number of Integer Solutions of an Equation
(Similar to Suggested Exercise 9.6#10)
How many solutions to the equation x1 + x2 + x3 + x4 = 30 are there where each xi is a non-negative integer?
- Allison Vedder CP10: The Number of Integer Solutions of an Equation
(Similar to Suggested Exercise 9.6#11)
How many solutions to the equation x1 + x2 + x3 + x4 = 30 are there where each xi is a positive integer?
Fri Apr 27 (Meeting Number 40 )
Section 9.2 Computations Involving Permutations and Section 9.5 Poker Hands
Proving an Abstract Property of P(n,r) (Leftover from Section 9.2)
- Ryan Alcorn CP12:
Prove: ∀ n ∈ Z, n ≥ 2 ( P(n,2) + P(n,1) = n2 )
Hint: Don’t multiply out any of the factors. Work with the factored forms.
- Ashley Benedict CP12: (Suggested Exercise 9.2#40)
Prove: ∀ n ∈ Z, n ≥ 2 ( P(n + 1,3) = n3 - n)
Hint: Don’t multiply out any of the factors. Work with the factored forms.
- Noah Collins CP12: (Suggested Exercise 9.2#43)
Prove: ∀ n ∈ Z, n ≥ 2 ( P(n,n) = P(n, n - 1))
Hint: Don’t multiply out any of the factors. Work with the factored forms.
Poker Hands Problems (Leftover from Section 9.5)
For each of the poker hands listed below, do the following two things:
- Find the number of five-card poker hands with that holding. You can find this number through a web search. But I want you to show how the number is obtained. Do this by identifying a list of tasks that must be done to specify a poker hand of the kind that you are assigned. Count the number of ways to do each task. Then use the Multiplication Rule. (See textbook Example 9.5.8 on page 574 for a model.)
- Find the probability that a randomly chosen set of five cards has that holding.
Here are the assignments of poker hands:
- Benjamin Fryman, Alyssa Hall CP12: Four of a Kind (Four cards of one denomination, and a 5th card of a different denomination)
- Devon Destocki, Kristen McLean CP09: Full House (Three cards of one denomination, and a pair of cards of a different denomination)
- Peter Metro, Blue Kennedy CP12: Flush (but not straight flush) (Five cards of one suit, but not of sequential denomination) (Hint: Simplest if you use the Difference Rule. That is, find the total number of Flushes including Straight Flushes, then subtract the number of straight flushes.)
- Matthew Connell, Jalen Perkins CP12: Three of a Kind (Three cards of one denomination, and two cards of two different denominations)
- Alexandria Schira CP12, Allison Vedder CP11: One Pair (A pair of cards of one denomination, and three cards of three different denominations)
(page maintained by Mark Barsamian, last updated Apr 24, 2018)