Quiz1 practice PDF

Preview

Summary

MATH-UA 120 (Discrete Mathematics) — Quiz 1 (Practice) SolutionsSection: 007, Semester: Fall 2017, Instructor: Nicholas Knight In how many ways can we arrange a standard deck of cards so that each suit appears contiguously? Solution: In this class, astandard deck of cardsalways means the 52 French p...

Description

MATH-UA 120 (Discrete Mathematics) — Quiz 1 (Practice) Solutions Section: 007, Semester: Fall 2017, Instructor: Nicholas Knight 1. In how many ways can we arrange a standard deck of cards so that each suit appears contiguously?

Solution: In this class, a standard deck of cards always means the 52 French playing cards, Suit Clubs Diamonds Hearts Spades

Rank Ace 2 3 4 5 6 7 8 9 10 Jack A♣ 2♣ 3♣ 4♣ 5♣ 6♣ 7♣ 8♣ 9♣ 10♣ J♣ A♦ 2♦ 3♦ 4♦ 5♦ 6♦ 7♦ 8♦ 9♦ 10♦ J♦ A♥ 2♥ 3♥ 4♥ 5♥ 6♥ 7♥ 8♥ 9♥ 10♥ J♥ A♠ 2♠ 3♠ 4♠ 5♠ 6♠ 7♠ 8♠ 9♠ 10♠ J♠

Queen Q♣ Q♦ Q♥ Q♠

King K♣ K♦ K♥ K♠

Here are two approaches for finding the correct solution: • There are 52 choices for the first card. After picking this card, the first suit is fixed, so there are only 12 choices for the second card, 11 for the third, and so on, with only 1 choice for the thirteenth card. Having exhausted a suit, there remain 52 − 13 = 39 choices for the fourteenth card; after picking this card, the second suit is fixed, leaving 12 choices for the fifteenth, 11 for the sixteenth, and so on, with only 1 choice for the twenty-sixth card. A similar reasoning applies for the last two suits. The number of arrangements is thus · 11 · · · 1} . · 11 · · · 1} · |13 · 12{z · 11 · · · 1} · 26 52 · 11 · · · 1} · 39 | · 12 {z | · 12 {z | · 12 {z first suit

second suit

third suit

fourth suit

• There are 13! ways to arrange the thirteen ranks within a suit, so for each of the 4! orderings of the four suits, there are 13! · 13! · 13! · 13! = 13!4 ways to arrange the cards with each suit appearing contiguously. The number of arrangements is thus 4! · 13!4 . This number is about 3.6 · 1040 ; you are not expected to evaluate it explicitly!

MATH-UA 120:007

Quiz 1 (Practice)

Page 2/3

2. What is the cardinality |A| of each of the following sets A? (a) A = ∅ (b) A = {∅} (c) A = {∅, {∅}} (d) A = {∅, {∅}, {∅, {∅}}

Solution: (a) |A| = 0. (b) |A| = 1. (c) |A| = 2. (d) |A| = 3. Remark: This is how most mathematicians define the natural numbers N = {0, 1, 2, 3, . . .}, as sets: 0 = ∅, 1 = {∅} = {0}, 2 = {∅, {∅}} = {0, 1}, 3 = {∅, {∅}, {∅, {∅}} = {0, 1, 2}, and so on, with n = {0, 1, . . . , n − 1} in general. (The symbols 0, 1, 2, 3, . . . are just convenient labels.)

3. For each set A, write its power set 2A . (a) A = ∅ (b) A = {∅} (c) A = {∅, {∅}}

Solution: (a) 2A = {∅}. (b) 2A = {∅, {∅}}. (c) 2A = {∅, {∅}, {{∅}}, {∅, {∅}}}. Hint: If you get confused by the ∅s and nested { }s, just rename the elements a, b, c, . . .. For example, in part (c) we have A = {a, b} and 2A = {∅, {a}, {b}, {a, b}}. Now substitute a = ∅ and b = {∅} to get the correct answer.

MATH-UA 120:007

Quiz 1 (Practice)

4. For each expression, write the most appropriate choice: A. True for any x; B. False for any x; C. True or false, depending on x. If you choose ‘C’, you must also give two examples demonstrating when it is true and false. (a) x = {x} (b) x ∈ {x} (c) x ⊆ {x}

Solution: (a) B: false for all x. (b) A: true for all x. (c) C: true when x = ∅, false for all x 6= ∅ (e.g., x = 1).

Page 3/3...