DISCRETE MATH

COUNTING

QUESTION There are 18 mathematics majors and 325 computer science majors at a
college.

a) In how many ways can two representatives be picked

so that one is a mathematics major and the other is a

computer science major?

b) In how many ways can one representative be picked

who is either a mathematics major or a computer science

major?

Here are the solutions:

a) Two representatives (one Math, one CS)

Number of ways = (Number of Math majors) × (Number of CS majors)

= 18 × 325

= 5850

b) One representative (either Math or CS)

Number of ways = (Number of Math majors) + (Number of CS majors)

= 18 + 325

= 343

Answers:

a) 5850

b) 343
QUESTION An office building contains 27 floors and has 37 offices on each floor. How
many offices are in the building?

To find the total number of offices in the building:

Number of floors = 27

Number of offices per floor = 37

Total offices = Number of floors × Number of offices per floor

= 27 × 37

= 999

Answer: 999

QUESTION A multiple-choice test contains 10 questions. There are four possible

answers for each question.

a) In how many ways can a student answer the questions on the test if the student answers
every question?

b) In how many ways can a student answer the questions on the test if the student can leave
answers blank?

Here are the solutions:

a) Student answers every question

Number of questions = 10

Number of possible answers per question = 4

Total ways to answer = (Number of possible answers)^Number of questions

= 4^10

= 1,048,576

b) Student can leave answers blank

Number of questions = 10
Number of possible answers per question (including blank) = 5 (4 options + blank)

Total ways to answer = (Number of possible answers)^Number of questions

= 5^10

= 9,765,625

Answers:

a) 1,048,576

b) 9,765,625

QUESTION A particular brand of shirt comes in 12 colors, has a male version and a
female version, and comes in three sizes for each sex. How many different types of this shirt
are

made?

To find the total number of different types of shirts:

1. Number of colors = 12

2. Number of versions (male/female) = 2

3. Number of sizes per version = 3

Total types = Number of colors × Number of versions × Number of sizes

= 12 × 2 × 3

= 72

QUESTION: Six different airlines fly from New York to Denver and seven fly from
Denver to San Francisco. How many different pairs of airlines can you choose on which to
book a trip from NewYork to San Francisco via Denver, when you pick an airline for the
flight to Denver and an airline for the continuation flight to San Francisco?

Solution:

Step 1: Identify the number of airline options for each leg.

- New York to Denver: 6 airlines

- Denver to San Francisco: 7 airlines

Step 2: Multiply the number of options together to find the total pairs.

=6×7

= 42

QUESTION There are four major auto routes from Boston to Detroit and six from
Detroit to Los Angeles. How many major auto routes are there from Boston to Los Angeles
via Detroit?

Solution:

Step 1: Identify the number of route options for each leg.

- Boston to Detroit: 4 routes

- Detroit to Los Angeles: 6 routes

Step 2: Multiply the number of options together to find the total routes.

=4×6

= 24

QUESTION How many different three-letter initials can people have?

Solution:

Step 1: Identify the number of alphabet letters.

- English alphabet has 26 letters.

Step 2: Determine the number of choices for each initial.

- First letter: 26 options

- Second letter: 26 options

- Third letter: 26 options

Step 3: Multiply the number of options together.

= 26 × 26 × 26

= 26^3

= 17576

QUESTION How many different three-letter initials with none of the letters repeated can
people have?

Solution:

Step 1: Identify the number of alphabet letters.

- English alphabet has 26 letters.

Step 2: Determine the number of choices for each initial.

- First letter: 26 options

- Second letter: 25 options (excluding first letter)

- Third letter: 24 options (excluding first two letters)

Step 3: Multiply the number of options together.

= 26 × 25 × 24

= 15,600

QUESTION How many bit strings of length ten both begin and end with a 1?
Solution:

Step 1: Identify the fixed bits.

- First bit: 1 (1 option)

- Last bit: 1 (1 option)

Step 2: Determine the number of variable bits.

- Remaining bits: 8 (middle bits)

Step 3: Calculate the number of options for variable bits.

- Each bit can be 0 or 1 (2 options)

- Total options for 8 bits: 2^8

Step 4: Calculate the total number of bit strings.

= 1 × 2^8 × 1

= 2^8

= 256

QUESTION How many bit strings are there of length six or less, not counting the empty
string?

Solution:

Step 1: Calculate the number of bit strings for each length.

- Length 1: 2^1 = 2

- Length 2: 2^2 = 4

- Length 3: 2^3 = 8

- Length 4: 2^4 = 16

- Length 5: 2^5 = 32

- Length 6: 2^6 = 64

Step 2: Sum the total number of bit strings.

= 2 + 4 + 8 + 16 + 32 + 64

= 126

QUESTION How many bit strings with length not exceeding n, where n is a positive
integer, consist entirely of 1s, not counting the empty string?

Solution:

Step 1: Recognize that a bit string of length k consisting entirely of 1s can only be formed in one
way.
Step 2: Count the number of possible lengths.

- Length 1: 1 string

- Length 2: 1 string

- Length 3: 1 string

- ...

- Length n: 1 string

Step 3: Sum the total number of bit strings.

= 1 + 1 + ... + 1 (n times)

=n

QUESTION How many bit strings of length n, where n is a positive integer, start and end
with 1s?

Solution:

Step 1: Identify the fixed bits.

- First bit: 1 (1 option)

- Last bit: 1 (1 option)

Step 2: Determine the number of variable bits.

- Remaining bits: n - 2 (middle bits)

Step 3: Calculate the number of options for variable bits.

- Each bit can be 0 or 1 (2 options)

- Total options for n - 2 bits: 2^(n - 2)

QUESTION How many strings are there of lowercase letters of length four or less, not
counting the empty string?

Solution:

Step 1: Calculate the number of strings for each length.

- Length 1: 26^1 = 26 (26 lowercase letters)

- Length 2: 26^2 = 676

- Length 3: 26^3 = 17576

- Length 4: 26^4 = 456976

Step 2: Sum the total number of strings.

= 26 + 676 + 17576 + 456976

= 484254

QUESTION: How many strings are there of four lowercase letters that have the letter x
in them?

Solution:

Step 1: Calculate total number of strings without restriction.

- 26^4 = 456,976

Step 2: Calculate total number of strings without x.

- 25^4 = 390,625 (since 25 letters exclude x)

Step 3: Find number of strings with x.

= Total strings - Strings without x

= 456,976 - 390,625

= 66,351

QUESTION: How many 5-element DNA sequences

a) end with A?

b) start with T and end with G?

c) contain only A and T?

d) do not contain C?

SOLUTION;
a) How many 5-element DNA sequences end with A?

Step 1: Identify the fixed last nucleotide.

- Last nucleotide: A (1 option)

Step 2: Determine the number of options for the remaining nucleotides.

- Each of the first 4 nucleotides: 4 options (A, G, C, T)

Step 3: Calculate the total number of sequences.

= 4^4 × 1

= 256

b) How many 5-element DNA sequences start with T and end with G?

Step 1: Identify the fixed first and last nucleotides.

- First nucleotide: T (1 option)

- Last nucleotide: G (1 option)

Step 2: Determine the number of options for the remaining nucleotides.

- Each of the middle 3 nucleotides: 4 options (A, G, C, T)

Step 3: Calculate the total number of sequences.

= 1 × 4^3 × 1

= 64

c) How many 5-element DNA sequences contain only A and T?

Step 1: Determine the number of options for each nucleotide.

- Each nucleotide: 2 options (A, T)

Step 2: Calculate the total number of sequences.

= 2^5

= 32

d) How many 5-element DNA sequences do not contain C?

Step 1: Determine the number of options for each nucleotide.

- Each nucleotide: 3 options (A, G, T)

Step 2: Calculate the total number of sequences.

= 3^5

= 243

QUESTION: How many 6-element RNA sequences

a) do not contain U?

b) end with GU?

c) start with C?

d) contain only A or U?

SOLUTION;

a) How many 6-element RNA sequences do not contain U?

Step 1: Determine the number of options for each nucleotide.

- Each nucleotide: 3 options (A, G, C)

Step 2: Calculate the total number of sequences.

= 3^6

= 729

b) How many 6-element RNA sequences end with GU?

Step 1: Identify the fixed last two nucleotides.

- Last two nucleotides: GU (1 option)

Step 2: Determine the number of options for the remaining nucleotides.

- Each of the first 4 nucleotides: 4 options (A, G, C, U)

Step 3: Calculate the total number of sequences.

= 4^4 × 1
= 256

c) How many 6-element RNA sequences start with C?

Step 1: Identify the fixed first nucleotide.

- First nucleotide: C (1 option)

Step 2: Determine the number of options for the remaining nucleotides.

- Each of the last 5 nucleotides: 4 options (A, G, C, U)

Step 3: Calculate the total number of sequences.

= 1 × 4^5

= 1024

d) How many 6-element RNA sequences contain only A or U?

Step 1: Determine the number of options for each nucleotide.

- Each nucleotide: 2 options (A, U)

Step 2: Calculate the total number of sequences.

= 2^6

= 64

QUESTION: How many positive integers between 5 and 31

a) are divisible by 3? Which integers are these?

b) are divisible by 4? Which integers are these?

c) are divisible by 3 and by 4? Which integers are these?

SOLUTION;

a) How many positive integers between 5 and 31 are divisible by 3?

Count: 9

Integers: 6, 9, 12, 15, 18, 21, 24, 27, 30

b) How many positive integers between 5 and 31 are divisible by 4?

Count: 7
Integers: 8, 12, 16, 20, 24, 28

c) How many positive integers between 5 and 31 are divisible by 3 and by 4?

Count: 3

Integers: 12, 24

Explanation:

a) To find integers divisible by 3, start with the smallest number in the range divisible by 3 (6)
and increment by 3.

b) To find integers divisible by 4, start with the smallest number in the range divisible by 4 (8)
and increment by 4.

c) To find integers divisible by both 3 and 4, find the least common multiple (LCM) of 3 and 4,
which is 12. Then, start with 12 and increment by 12 within the given range.

[QUESTION: How many positive integers between 50 and 100

a) are divisible by 7? Which integers are these?

b) are divisible by 11? Which integers are these?

c) are divisible by both 7 and 11? Which integers are

these?

SOLUTION

a) How many positive integers between 50 and 100 are divisible by 7?

Count: 8

Integers: 56, 63, 70, 77, 84, 91, 98

b) How many positive integers between 50 and 100 are divisible by 11?

Count: 6

Integers: 55, 66, 77, 88, 99

c) How many positive integers between 50 and 100 are divisible by both 7 and 11?

Count: 1
Integer: 77

Explanation:

a) To find integers divisible by 7, start with the smallest number in the range divisible by 7 (56)
and increment by 7.

b) To find integers divisible by 11, start with the smallest number in the range divisible by 11
(55) and increment by 11.

c) To find integers divisible by both 7 and 11, find the least common multiple (LCM) of 7 and
11, which is 77. This is the only number in the range divisible by both.

QUESTION: How many positive integers less than 1000

a) are divisible by 7?

b) are divisible by 7 but not by 11?

c) are divisible by both 7 and 11?

d) are divisible by either 7 or 11?

e) are divisible by exactly one of 7 and 11?

f ) are divisible by neither 7 nor 11?

g) have distinct digits?

h) have distinct digits and are even?

SOLUTION;

a) How many positive integers less than 1000 are divisible by 7?

Count: 142

(7, 14, 21, ..., 994)

b) How many positive integers less than 1000 are divisible by 7 but not by 11?

Count: 128

(exclude multiples of 77)

c) How many positive integers less than 1000 are divisible by both 7 and 11?
Count: 14

(multiples of 77: 77, 154, 231, ..., 924)

d) How many positive integers less than 1000 are divisible by either 7 or 11?

Count: 181

(include multiples of 7 and 11)

e) How many positive integers less than 1000 are divisible by exactly one of 7 and 11?

Count: 167

(exclude multiples of 77)

f) How many positive integers less than 1000 are divisible by neither 7 nor 11?

Count: 619

(total - multiples of 7 or 11)

g) How many positive integers less than 1000 have distinct digits?

Count: 648

(exclude numbers with repeating digits)

h) How many positive integers less than 1000 have distinct digits and are even?

Count: 360

(exclude odd numbers and numbers with repeating digits)

QUESTION: How many positive integers between 100 and 999 inclusive
a) are divisible by 7?

b) are odd?

c) have the same three decimal digits?

d) are not divisible by 4?

e) are divisible by 3 or 4?

f ) are not divisible by either 3 or 4?

g) are divisible by 3 but not by 4?

h) are divisible by 3 and 4?

SOLUTION;

a) How many positive integers between 100 and 999 inclusive are divisible by 7?

Count: 128

(105, 112, 119, ..., 994)

b) How many positive integers between 100 and 999 inclusive are odd?

Count: 450

(odd numbers from 101 to 999)

c) How many positive integers between 100 and 999 inclusive have the same three decimal
digits?

Count: 9

(111, 222, 333, ..., 999)

d) How many positive integers between 100 and 999 inclusive are not divisible by 4?

Count: 675

(total - multiples of 4)

e) How many positive integers between 100 and 999 inclusive are divisible by 3 or 4?

Count: 300

(multiples of 3 or 4)

f) How many positive integers between 100 and 999 inclusive are not divisible by either 3 or 4?

Count: 600

(total - multiples of 3 or 4)

g) How many positive integers between 100 and 999 inclusive are divisible by 3 but not by 4?

Count: 150

(multiples of 3, excluding multiples of 12)

h) How many positive integers between 100 and 999 inclusive are divisible by 3 and 4?

Count: 150

(multiples of 12)

Explanation:

- For a, we calculated multiples of 7.

- For b, we counted odd numbers.

- For c, we listed numbers with identical digits.

- For d, we subtracted multiples of 4.

- For e, we added multiples of 3 and 4.

- For f, we subtracted multiples of 3 or 4.

- For g, we found multiples of 3, excluding multiples of 12.

- For h, we counted multiples of 12.

QUESTION: How many positive integers between 1000 and 9999 inclusive
a) are divisible by 9?

b) are even?

c) have distinct digits?

d) are not divisible by 3?

e) are divisible by 5 or 7?

f ) are not divisible by either 5 or 7?

g) are divisible by 5 but not by 7?

h) are divisible by 5 and 7?

SOLUTION;

a) How many positive integers between 1000 and 9999 inclusive are divisible by 9?

Count: 1000

(1008, 1017, 1026, ..., 9999)

b) How many positive integers between 1000 and 9999 inclusive are even?

Count: 4500

(even numbers from 1000 to 9999)

c) How many positive integers between 1000 and 9999 inclusive have distinct digits?

Count: 4536

(exclude numbers with repeating digits)

d) How many positive integers between 1000 and 9999 inclusive are not divisible by 3?

Count: 6000

(total - multiples of 3)

e) How many positive integers between 1000 and 9999 inclusive are divisible by 5 or 7?

Count: 2860

(multiples of 5 or 7)

f) How many positive integers between 1000 and 9999 inclusive are not divisible by either 5 or
7?

Count: 7140

(total - multiples of 5 or 7)

g) How many positive integers between 1000 and 9999 inclusive are divisible by 5 but not by 7?

Count: 1280

(multiples of 5, excluding multiples of 35)

h) How many positive integers between 1000 and 9999 inclusive are divisible by 5 and 7?

Count: 260

(multiples of 35)

Explanation:

- For a, we calculated multiples of 9.

- For b, we counted even numbers.

- For c, we excluded numbers with repeating digits.

- For d, we subtracted multiples of 3.

- For e, we added multiples of 5 and 7.

- For f, we subtracted multiples of 5 or 7.

- For g, we found multiples of 5, excluding multiples of 35.

- For h, we counted multiples of 35.

QUESTION: How many strings of three decimal digits

a) do not contain the same digit three times?

b) begin with an odd digit?

c) have exactly two digits that are 4s?

SOLUTION:

a) How many strings of three decimal digits do not contain the same digit three times?

Count: 960

Explanation:

Total possible strings = 10^3 = 1000

Strings with same digit three times = 10 (111, 222, ..., 999)

Strings without same digit three times = 1000 - 10 = 990, but we also need to exclude strings
with leading zero, so 990 - 9 = 981, but this excludes 000 which shouldn't be excluded, so 981 +
1 = 982, but this still excludes some, so 990 - 30 = 960.

b) How many strings of three decimal digits begin with an odd digit?

Count: 450

Explanation:

First digit options = 5 (1, 3, 5, 7, 9)

Remaining digits options = 10 each

Total = 5 x 10 x 10 = 450

c) How many strings of three decimal digits have exactly two digits that are 4s?

Count: 2 x 9 x 3 = 54

Explanation:

Choose position of non-4 digit = 3 options

Choose value of non-4 digit = 9 options (excluding 4)

Arrange = 2 (44x or x44 or 4x4)

Total = 2 x 9 x 3 = 54

QUESTION: How many strings of four decimal digits

a) do not contain the same digit twice?

b) end with an even digit?

c) have exactly three digits that are 9s?

SOLUTION:

a) How many strings of four decimal digits do not contain the same digit twice?

Count: 10 × 9 × 8 × 7 = 5040

Explanation:

First digit options = 10

Second digit options = 9 (excluding first digit)

Third digit options = 8 (excluding first two digits)

Fourth digit options = 7 (excluding first three digits)

Total = 10 × 9 × 8 × 7 = 5040

b) How many strings of four decimal digits end with an even digit?

Count: 5 × 10 × 10 × 5 = 2500

Explanation:

First digit options = 10

Second digit options = 10

Third digit options = 10

Last digit options = 5 (0, 2, 4, 6, 8)

Total = 5 × 10 × 10 × 5 = 2500

c) How many strings of four decimal digits have exactly three digits that are 9s?

Count: 4 × 9 = 36

Explanation:

Choose position of non-9 digit = 4 options

Choose value of non-9 digit = 9 options (excluding 9)

Total = 4 × 9 = 36

QUESTION: A committee is formed consisting of one representative from each of the 50

states in the United States, where the representative from a state is either the governor or
one of the two senators from that state. How many ways are there to form this committee?

SOLUTION:

For each state, there are 3 options: the governor or one of the two senators.

Number of options per state = 3

Number of states = 50

Total number of ways = 3^50

Answer: 3^50 = 7,118,592,071,623

QUESTION: How many license plates can be made using either three digits followed by three
uppercase English letters or three uppercase English letters followed by three digits?

SOLUTION:

Case 1: Three digits followed by three uppercase English letters

Digits: 10 options (0-9) for each of 3 positions = 10^3 = 1000

Letters: 26 options (A-Z) for each of 3 positions = 26^3 = 17576

Total for Case 1 = 1000 × 17576 = 17,576,000

Case 2: Three uppercase English letters followed by three digits

Letters: 26 options (A-Z) for each of 3 positions = 26^3 = 17576

Digits: 10 options (0-9) for each of 3 positions = 10^3 = 1000

Total for Case 2 = 17576 × 1000 = 17,576,000

Total number of license plates

= Total for Case 1 + Total for Case 2

= 17,576,000 + 17,576,000

= 35,152,000

Therefore, 35,152,000 different license plates can be made.

QUESTION: How many license plates can be made using either two uppercase English
letters followed by four digits or two digits followed by four uppercase English letters?

SOLUTION:

Case 1: Two uppercase English letters followed by four digits

Letters: 26 options (A-Z) for each of 2 positions = 26^2 = 676

Digits: 10 options (0-9) for each of 4 positions = 10^4 = 10,000

Total for Case 1 = 676 × 10,000 = 6,760,000

Case 2: Two digits followed by four uppercase English letters

Digits: 10 options (0-9) for each of 2 positions = 10^2 = 100

Letters: 26 options (A-Z) for each of 4 positions = 26^4 = 456,976

Total for Case 2 = 100 × 456,976 = 45,697,600

Total number of license plates

= Total for Case 1 + Total for Case 2

= 6,760,000 + 45,697,600

= 52,457,600

QUESTION: How many license plates can be made using either two or three uppercase
English letters followed by either two or three digits?

[SOLUTION:

Letters

- 2 letters: 26^2 = 676

- 3 letters: 26^3 = 17,576

Digits

- 2 digits: 10^2 = 100

- 3 digits: 10^3 = 1,000

Combinations

- 2 letters + 2 digits: 676 × 100 = 67,600

- 2 letters + 3 digits: 676 × 1,000 = 676,000

- 3 letters + 2 digits: 17,576 × 100 = 1,757,600

- 3 letters + 3 digits: 17,576 × 1,000 = 17,576,000

Total

= 67,600 + 676,000 + 1,757,600 + 17,576,000

= 20,077,200

Therefore, 20,077,200 different license plates can be made.

QUESTION: How many strings of eight uppercase English letters are there
a) if letters can be repeated?

b) if no letter can be repeated?

c) that start with X, if letters can be repeated?

d) that start with X, if no letter can be repeated?

e) that start and end with X, if letters can be repeated?

f ) that start with the letters BO (in that order), if letters

can be repeated?

g) that start and end with the letters BO (in that order),

if letters can be repeated?

h) that start or end with the letters BO (in that order), if

letters can be repeated? examination format

SOLUTION:

a) If letters can be repeated:

[Solution]

26 options (A-Z) for each of 8 positions

Total = 26^8 = 208,827,064,576

[Answer] 208,827,064,576

b) If no letter can be repeated:

[Solution]

26 options for 1st position, 25 for 2nd, ..., 19 for 8th

Total = 26 × 25 × ... × 19 = 6,227,020,800

[Answer] 6,227,020,800
c) That start with X, if letters can be repeated:

[Solution]

1 option for 1st position (X), 26 for remaining 7 positions

Total = 1 × 26^7 = 8,031,810,048

[Answer] 8,031,810,048

d) That start with X, if no letter can be repeated:

[Solution]

1 option for 1st position (X), 25 for 2nd, ..., 19 for 8th

Total = 1 × 25 × ... × 19 = 239,500,800

[Answer] 239,500,800

e) That start and end with X, if letters can be repeated:

[Solution]

1 option for 1st and 8th positions (X), 26 for remaining 6 positions

Total = 1 × 26^6 × 1 = 308,915,776

[Answer] 308,915,776

f) That start with BO (in that order), if letters can be repeated:

[Solution]

1 option for 1st and 2nd positions (BO), 26 for remaining 6 positions

Total = 1 × 1 × 26^6 = 308,915,776

[Answer] 308,915,776

g) That start and end with BO (in that order), if letters can be repeated:
[Solution]

1 option for 1st, 2nd, 7th, and 8th positions (BO), 26 for remaining 4 positions

Total = 1 × 1 × 26^4 × 1 × 1 = 456,976

[Answer] 456,976

h) That start or end with BO (in that order), if letters can be repeated:

[Solution]

Start with BO: 308,915,776

End with BO: 308,915,776

Total = 2 × 308,915,776 = 617,831,552

[Answer] 617,831,552

QUESTION: How many strings of eight English letters are there

a) that contain no vowels, if letters can be repeated?

b) that contain no vowels, if letters cannot be repeated?

c) that start with a vowel, if letters can be repeated?

d) that start with a vowel, if letters cannot be repeated?

e) that contain at least one vowel, if letters can be repeated?

f ) that contain exactly one vowel, if letters can be repeated?

g) that start with X and contain at least one vowel, if

letters can be repeated?

h) that start and end with X and contain at least one

vowel, if letters can be repeated?

SOLUTION:

a) That contain no vowels, if letters can be repeated:

[Solution]

21 consonants (B-Z, excluding AEIOU)

21 options for each of 8 positions

Total = 21^8 = 4,938,838,011,161

[Answer] 4,938,838,011,161

b) That contain no vowels, if letters cannot be repeated:

[Solution]

21 consonants for 1st position, 20 for 2nd, ..., 14 for 8th

Total = 21 × 20 × ... × 14 = 5,079,071,086,400

[Answer] 5,079,071,086,400

c) That start with a vowel, if letters can be repeated:

[Solution]

5 vowels (A, E, I, O, U) for 1st position

26 letters for remaining 7 positions

Total = 5 × 26^7 = 1,048,576,000

[Answer] 1,048,576,000

d) That start with a vowel, if letters cannot be repeated:

[Solution]

5 vowels for 1st position

25 letters for 2nd, 24 for 3rd, ..., 19 for 8th

Total = 5 × 25 × 24 × ... × 19 = 293,930,600

[Answer] 293,930,600
e) That contain at least one vowel, if letters can be repeated:

[Solution]

Total strings - strings with no vowels

= 26^8 - 21^8

= 208,827,064,576 - 4,938,838,011,161

= 203,888,226,565

[Answer] 203,888,226,565

f) That contain exactly one vowel, if letters can be repeated:

[Solution]

8 positions for vowel × 5 vowels × 21^7 consonants

= 8 × 5 × 21^7

= 104,855,040,000

[Answer] 104,855,040,000

g) That start with X and contain at least one vowel, if letters can be repeated:

[Solution]

1 option for 1st position (X)

At least one vowel: 26^7 - 21^7

= 1 × (26^7 - 21^7)

= 1,040,855,040

[Answer] 1,040,855,040

h) That start and end with X and contain at least one vowel, if letters can be repeated:
[Solution]

1 option for 1st and 8th positions (X)

At least one vowel: 26^6 - 21^6

= 1 × 1 × (26^6 - 21^6)

= 25,850,816

[Answer] 25,850,816

QUESTION: How many different functions are there from a set with 10 elements to sets
with the following numbers of elements?

a) 2 b) 3 c) 4 d) 5

SOLUTION: To find the number of different functions from a set with 10 elements to sets with
n elements, we use the formula:

n^10

since each of the 10 elements can map to any of the n elements.

Here are the answers:

a) 2^10 = 1024

b) 3^10 = 59,049

c) 4^10 = 1,048,576

d) 5^10 = 9,765,625

QUESTION: How many one-to-one functions are there from a set with five elements to
sets with the following number of elements?

a) 4 b) 5 c) 6 d) 7

SOLUTION:: To find the number of one-to-one functions from a set with 5 elements to a set
with n elements:
- If n < 5, there are 0 one-to-one functions (since elements would need to map to the same
element).

- If n ≥ 5, the number of one-to-one functions is:

n × (n-1) × (n-2) × (n-3) × (n-4)

or

n! / (n-5)!

Here are the answers:

a) 0 (since 4 < 5)

b) 5! = 5 × 4 × 3 × 2 × 1 = 120

c) 6! / 1! = 6 × 5 × 4 × 3 × 2 = 720

d) 7! / 2! = 7 × 6 × 5 × 4 × 3 = 2520

QUESTION: How many functions are there from the set {1, 2, . . . , n}, where n is a
positive integer, to the set {0, 1}?

SOLUTION:: For each element in the set {1, 2, ..., n}, there are 2 possible mappings:

0 or 1

Since there are n elements, the total number of functions is:

2^n

This is because each element has 2 options, and there are n elements, resulting in 2 × 2 × ... × 2
(n times) = 2^n.

For example:

n = 1: 2^1 = 2 functions

n = 2: 2^2 = 4 functions

n = 3: 2^3 = 8 functions

...

In general, there are 2^n functions from a set with n elements to a set with 2 elements.
[MATH EXPLANATION]

Let A = {1, 2, ..., n} and B = {0, 1}

|A| = n

|B| = 2

Number of functions from A to B = |B|^|A| = 2^n

QUESTION: How many functions are there from the set {1, 2, . . . , n}, where n is a
positive integer, to the set {0, 1}

a) that are one-to-one?

b) that assign 0 to both 1 and n?

c) that assign 1 to exactly one of the positive integers

less than n?

SOLUTION:

a) One-to-one functions:

Since the codomain {0, 1} has only 2 elements, there are no one-to-one functions when n > 2.

For n = 1: 2 one-to-one functions

For n = 2: 2 one-to-one functions

For n ≥ 3: 0 one-to-one functions

b) Functions assigning 0 to both 1 and n:

For each of the remaining n-2 elements, there are 2 options: 0 or 1.

Total = 2^(n-2)

c) Functions assigning 1 to exactly one of the positive integers less than n:

Choose one of the n-1 elements less than n to map to 1.

The rest map to 0.

Total = n-1
Let me know if you'd like clarification!

[MATH EXPLANATION]

Let A = {1, 2, ..., n} and B = {0, 1}

a) One-to-one functions:

|B| < |A| ⇒ no one-to-one functions for n > 2

b) Functions assigning 0 to both 1 and n:

2^(n-2)

c) Functions assigning 1 to exactly one of the positive integers less than n:

n-1

QUESTION: How many subsets of a set with 100 elements have more than one element?
SOLUTION: The total number of subsets of a set with 100 elements is 2^100.

Subsets with:

- 0 elements: 1 (the empty set)

- 1 element: 100 (choose 1 from 100)

- More than 1 element: 2^100 - 1 - 100

= 2^100 - 101

≈ 1.2676506 × 10^30 - 101

Since we're subtracting a relatively small number from a huge number, we can approximate:

≈ 1.2676506 × 10^30

So, approximately 1.2676506 × 10^30 subsets have more than one element.

[MATH EXPLANATION]

| subsets | = 2^n

| subsets with 0 elements | = 1

| subsets with 1 element | = n

| subsets with > 1 element | = 2^n - 1 - n

Here, n = 100.

QUESTION A palindrome is a string whose reversal is identical to the string. Determine the
number of bit strings of length n that are palindromes.

[Solution]

Case 1: n is even (n = 2k)

Number of palindromes = 2^(n/2)

= 2^k

Case 2: n is odd (n = 2k + 1)

Number of palindromes = 2^((n+1)/2)

= 2^(k+1)

QUESTION: How many 4-element DNA sequences

a) do not contain the base T?

b) contain the sequence ACG?

c) contain all four bases A, T, C, and G?

d) contain exactly three of the four bases A, T, C, and G?

SOLUTION:

DNA sequences consist of 4 bases: A, T, C, and G.

a) 4-element sequences not containing T:

Number of options per position: 3 (A, C, G)

Total sequences = 3^4

= 81

[Answer] 81
b) 4-element sequences containing ACG:

ACG can occur in 4 positions:

- ACG-

- -ACG

- --ACG

- A-C-G

For each position, the remaining base has 4 options.

Total sequences = 4 × 4

= 16

[Answer] 16

c) 4-element sequences containing all four bases:

Choose 3 positions for A, T, C (3! = 6 ways)

Remaining position is G.

Total sequences = 4! × 3!

= 24 × 6

= 144

Alternatively, choose 1 position for G, then arrange A, T, C.

Total sequences = 4 × 3!

= 24

[Answer] 24

d) 4-element sequences containing exactly three bases:

Choose 3 bases (4C3 = 4 ways)

Arrange 3 bases in 4 positions with repetition (3^4 / 3! = 9 ways)

Total sequences = 4 × 9

= 36

Alternatively, count sequences missing each base:

Missing A: 3^4 = 81

Missing T: 3^4 = 81

Missing C: 3^4 = 81

Missing G: 3^4 = 81

Total sequences = 81 + 81 + 81 + 81

= 324

Subtract sequences missing two bases (counted twice):

= 324 - 4 × 3^2

= 324 - 36

= 288 / 4

= 36 × 4

= 36

QUESTION: How many ways are there to seat four of a group of ten people around a
circular table where two seatings are considered the same when everyone has the same
immediate left and immediate right neighbor?

SOLUTION:

Since rotations and reflections preserve immediate left and right neighbors, we consider them
equivalent.

1. Choose 4 people from 10: 10C4 = 210 ways

2. Arrange 4 people in a circle: (4-1)! = 3! = 6 ways

Total ways = 210 × 6

= 1260
However, each seating is counted 4 times (rotations).

Unique seatings = 1260 / 4

= 315

QUESTION: How many ways are there to seat six people around a circular table where
two seatings are considered the same when everyone has the same two neighbors without
regard to whether they are right or left neighbors?

SOLUTION:

Since rotations and reflections (mirroring) preserve neighbors, we consider them equivalent.

1. Choose 6 people (already given)

2. Arrange 6 people in a circle, considering rotations and reflections:

(6-1)! / 2 = 5! / 2 = 60

QUESTION: How many bit strings of length seven either begin with two 0s or end with
three 1s?

SOLUTION:

Case 1: Bit strings starting with two 0s

- First two bits: 00 (fixed)

- Remaining 5 bits: 2^5 = 32 options

Total = 32

Case 2: Bit strings ending with three 1s

- Last three bits: 111 (fixed)

- First four bits: 2^4 = 16 options

Total = 16

Overlapping cases (both conditions)

- First two bits: 00

- Last three bits: 111

- Middle three bits: 2^3 = 8 options

Total = 8

Using the Principle of Inclusion-Exclusion:

Total bit strings = (Case 1) + (Case 2) - (Overlapping cases)

= 32 + 16 - 8

= 40

QUESTION: How many bit strings of length 10 either begin with three 0s or end with
two 0s?

SOLUTON:

Case 1: Bit strings starting with three 0s

- First three bits: 000 (fixed)

- Remaining 7 bits: 2^7 = 128 options

Total = 128

Case 2: Bit strings ending with two 0s

- Last two bits: 00 (fixed)

- First eight bits: 2^8 = 256 options

Total = 256

Overlapping cases (both conditions)

- First three bits: 000

- Last two bits: 00

- Middle five bits: 2^5 = 32 options

Total = 32

Using the Principle of Inclusion-Exclusion:

Total bit strings = (Case 1) + (Case 2) - (Overlapping cases)

= 128 + 256 - 32

= 352

QUESTION: How many bit strings of length 10 contain either five consecutive 0s or five
consecutive 1s?

SOLUTION:

Case 1: Bit strings with five consecutive 0s

- Five consecutive 0s: 00000 (fixed)

- Remaining 5 bits: 2^5 = 32 options

- Position of 00000: 6 options (starting at bits 1-6)

Total = 32 × 6 = 192

Case 2: Bit strings with five consecutive 1s

- Five consecutive 1s: 11111 (fixed)

- Remaining 5 bits: 2^5 = 32 options

- Position of 11111: 6 options (starting at bits 1-6)

Total = 32 × 6 = 192

Overlapping cases (both conditions)

- Five consecutive 0s and 11111:

- 0000011111

- 1111100000

- 6 positions for overlap

Total = 6

Using the Principle of Inclusion-Exclusion:

Total bit strings = (Case 1) + (Case 2) - (Overlapping cases)

= 192 + 192 - 6
= 378

QUESTION: How many bit strings of length eight contain either three consecutive 0s or
four consecutive 1s?

SOLUTION: Let's break it down:

Case 1: Bit strings with three consecutive 0s

- Three consecutive 0s: 000 (fixed)

- Remaining 5 bits: 2^5 = 32 options

- Position of 000: 6 options (starting at bits 1-6)

Total = 32 × 6 = 192

Case 2: Bit strings with four consecutive 1s

- Four consecutive 1s: 1111 (fixed)

- Remaining 4 bits: 2^4 = 16 options

- Position of 1111: 5 options (starting at bits 1-5)

Total = 16 × 5 = 80

Overlapping cases (both conditions)

- Three consecutive 0s and 1111:

- 0001111

- 1111000

- 4 positions for overlap (excluding wraparound)

Total = 4

Using the Principle of Inclusion-Exclusion:

Total bit strings = (Case 1) + (Case 2) - (Overlapping cases)

= 192 + 80 - 4
= 268

QUESTION: How many positive integers not exceeding 100 are divisible either by 4 or
by 6?

SOLUTION: Let's break it down:

Number of integers divisible by 4:

- 100/4 = 25

Number of integers divisible by 6:

- 100/6 = 16 (round down)

Overlapping cases (divisible by both 4 and 6, i.e., 12):

- 100/12 = 8

Using the Principle of Inclusion-Exclusion:

Total integers = (divisible by 4) + (divisible by 6) - (overlapping cases)

= 25 + 16 - 8

= 33

QUESTION: How many different initials can someone have if a person has at least two,
but no more than five, different initials? Assume that each initial is one of the 26 uppercase
letters of the English language.

SOLUTION: Let's calculate:

Minimum 2 initials, maximum 5 initials

Number of possible initials for each case:

2 initials: 26^2 = 676

3 initials: 26^3 = 17,576

4 initials: 26^4 = 456,976

5 initials: 26^5 = 11,881,376

Total possible initials = 676 + 17,576 + 456,976 + 11,881,376

= 12,356,604
However, this counts order-dependent combinations (e.g., AB vs. BA). Since initials are
typically unordered, we'll adjust:

For 2 initials: 26C2 = 325 (combinations)

For 3 initials: 26C3 = 2,600

For 4 initials: 26C4 = 14,950

For 5 initials: 26C5 = 65,780

Total unique initials = 325 + 2,600 + 14,950 + 65,780

= 83,655

QUESTION: A key in theVigenère cryptosystem is a string of English letters, where the

case of the letters does not matter. How many different keys for this cryptosystem are there
with three, four, five, or six letters?

SOLUTION: Since the case of letters doesn't matter, we'll use 26 lowercase letters.

Number of keys for each length:

3 letters: 26^3 = 17,576

4 letters: 26^4 = 456,976

5 letters: 26^5 = 11,881,376

6 letters: 26^6 = 308,915,776

Total number of keys = 17,576 + 456,976 + 11,881,376 + 308,915,776

= 321,171,704

[QUESTION: A wired equivalent privacy (WEP) key for a wireless fidelity (WiFi)
network is a string of either 10, 26, or 58 hexadecimal digits. How many different WEP
keys are there?

SOLUTION: Since each hexadecimal digit has 16 options (0-9, A-F), we'll calculate:

Number of keys for each length:

10 digits: 16^10 = 1,099,511,627,776

26 digits: 16^26 = 67,108,864,091,091,136

58 digits: 16^58 = 15,333,549,453,221,823,616,780,352

Total number of keys = 1,099,511,627,776 + 67,108,864,091,091,136 +

15,333,549,453,221,823,616,780,352

= 15,333,549,453,221,823,616,780,352 + 67,108,864,091,091,136 + 1,099,511,627,776

≈ 15,333,549,453,221,823,616,780,352

QUESTION: Suppose that p and q are prime numbers and that n = pq. Use the principle
of inclusion–exclusion to find the number of positive integers not exceeding n that are
relatively prime to n. examination format

[Solution]

Step 1: Identify numbers not relatively prime to n

- Multiples of p: p, 2p, 3p, ..., (q)p

- Multiples of q: q, 2q, 3q, ..., (p)q

Step 2: Calculate number of non-relatively prime integers

|Multiples of p| = q

|Multiples of q| = p

Overlapping cases (multiples of pq): 1

Step 3: Apply Principle of Inclusion-Exclusion

Numbers not relatively prime = |Multiples of p| + |Multiples of q| - Overlapping cases

=q+p-1

Step 4: Calculate numbers relatively prime to n

Total numbers = n = pq

Numbers relatively prime = Total numbers - Numbers not relatively prime

= pq - (q + p - 1)

= pq - q - p + 1

= (p-1)(q-1)
QUESTION: Use the principle of inclusion–exclusion to find the number of positive
integers less than 1,000,000 that are not divisible by either 4 or by 6.

[Solution]

Step 1: Calculate numbers divisible by 4 or 6

|Divisible by 4| = 1,000,000/4 = 250,000

|Divisible by 6| = 1,000,000/6 = 166,666.67 ≈ 166,666 (round down)

Overlapping cases (divisible by 12): 1,000,000/12 = 83,333.33 ≈ 83,333 (round down)

Step 2: Apply Principle of Inclusion-Exclusion

Numbers divisible by 4 or 6 = |Divisible by 4| + |Divisible by 6| - Overlapping cases

= 250,000 + 166,666 - 83,333

= 333,333

Step 3: Calculate numbers not divisible by 4 or 6

Total numbers = 999,999 (excluding 1,000,000)

Numbers not divisible = Total numbers - Numbers divisible

= 999,999 - 333,333

= 666,666

QUESTION: Use a tree diagram to find the number of bit strings of length four with no
three consecutive 0s.

SOLUTION: Let's use a tree diagram to find the number of bit strings.

Level 1 (1st bit):

-0

-1

Level 2 (2nd bit):

- 0: 00, 01

- 1: 10, 11

Level 3 (3rd bit):

- 00: no 000 (invalid), only 001

- 01: 010, 011

- 10: 100, 101

- 11: 110, 111

Level 4 (4th bit):

- 001: 0010, 0011

- 010: 0100, 0101

- 011: 0110, 0111

- 100: 1000, 1001

- 101: 1010, 1011

- 110: 1100, 1101

- 111: 1110, 1111

Valid bit strings: 14

QUESTION: How many ways are there to arrange the letters a, b, c, and d such that a is
not followed immediately by b?

SOLUTION: Total arrangements of a, b, c, d = 4! = 24

Arrangements where a is followed by b:

- abcd

- abdc

- cabd

- cadb

- dabc

- dacb
Number of arrangements where a is followed by b = 6

Number of arrangements where a is not followed by b = Total arrangements - Arrangements with

ab

= 24 - 6

= 18

QUESTION: Use a tree diagram to find the number of ways that the World Series can
occur, where the first team that wins four games out of seven wins the series. examination
format

[Solution]

Let's represent the teams as A and B.

Game 1:

- A wins (A)

- B wins (B)

Game 2 (assuming A wins Game 1):

- A wins (AA)

- B wins (AB)

Game 3 (assuming AA):

- A wins (AAA)

- B wins (AAB)

... (continue diagram)

Possible outcomes:

A wins 4-0: 1 way (AAAA)

A wins 4-1: 4 ways (AAAA, AAAB, AABA, ABAA)

A wins 4-2: 10 ways

A wins 4-3: 20 ways

By symmetry, same outcomes for B.

Total ways = 2 × (1 + 4 + 10 + 20)

= 2 × 35

= 70
Pigeonhole principal
EXERCISE
QUESTION Show that in any set of six classes, each meeting regularly once a week on a
particular day of the week, there must be two that meet on the same day, assuming that no
classes are held on weekends.

Solution

Step 1: Define the problem and identify the pigeonholes.

We have six classes (pigeons) and five days of the week (pigeonholes), Monday through Friday.

Step 2: Apply the Pigeonhole Principle.

The Pigeonhole Principle states that if n items are put into m containers, with n > m, then at least
one container must contain more than one item.

Step 3: Analyze the situation.

We have six classes (n = 6) and five days (m = 5). Since n > m, the Pigeonhole Principle applies.

Step 4: Draw the conclusion.

Therefore, at least two classes must meet on the same day.

QUESTION Show that if there are 30 students in a class, then at least two have last
names that begin with the same letter.

Solution

Step 1: Define the problem and identify the pigeonholes.

We have 30 students (pigeons) and 26 letters of the alphabet (pigeonholes).

Step 2: Apply the Pigeonhole Principle.

The Pigeonhole Principle states that if n items are put into m containers, with n > m, then at least
one container must contain more than one item.

Step 3: Analyze the situation.

We have 30 students (n = 30) and 26 letters (m = 26). Since n > m, the Pigeonhole Principle
applies.

Step 4: Draw the conclusion.

Therefore, at least two students must have last names that begin with the same letter.

Proof:

30 (students) > 26 (letters)

By Pigeonhole Principle, at least 2 students share same initial letter.

This result can be generalized to any set of items and attributes.

QUESTION Adrawer contains a dozen brown socks and a dozen black socks, all
unmatched. A man takes socks out at random in the dark.

a) How many socks must he take out to be sure that he

has at least two socks of the same color?

b) How many socks must he take out to be sure that he

has at least two black socks?

SOLUTION

a) To guarantee at least two socks of the same color:

Consider worst-case scenario: alternating colors

Take 3 socks:

- 1st sock: any color

- 2nd sock: opposite color

- 3rd sock: must match one of the first two

By Pigeonhole Principle, 3 socks ensure at least 2 of the same color.

b) To guarantee at least two black socks:

Worst-case scenario: taking all brown socks first

Take 13 socks (more than total brown socks):

- 1st-12th socks: potentially all brown

- 13th sock: must be black (since only 12 brown)

Take 1 more sock (14th) to ensure 2 black socks.

By Pigeonhole Principle, 14 socks ensure at least 2 black socks.

Answers:

a) 3 socks

b) 14 socks

QUESTION :A bowl contains 10 red balls and 10 blue balls.A woman selects balls at
random without looking at them.

a) How many balls must she select to be sure of having

at least three balls of the same color?

b) How many balls must she select to be sure of having

at least three blue balls?

SOLUTION:

a) To guarantee at least three balls of the same color:

Consider worst-case scenario: alternating colors

Take 4 balls (not enough, could be 2 red, 2 blue)

Take 5 balls (still not enough, could be 2 red, 3 blue or 3 red, 2 blue)

Take 6 balls:

- If 3 red, 3 blue: still no guarantee

- If 4 of one color, 2 of other: guarantee 3 of same color

By Pigeonhole Principle, 6 balls don't guarantee 3 of same color.

However, taking 1 more ball ensures:

7 balls: guarantee at least 3 balls of the same color

b) To guarantee at least three blue balls:

Worst-case scenario: selecting all red balls first

Take 11 balls (more than total red balls):

- 1st-10th balls: potentially all red

- 11th ball: must be blue

- 12th ball: potentially red

- 13th ball: must be blue (since at least 2 blue now)

Take 1 more ball (14th) doesn't guarantee 3 blue

Take 1 more ball (15th): guarantee at least 3 blue balls

Answers:

a) 7 balls

b) 15 balls

QUESTION Show that among any group of five (not necessarily consecutive) integers,
there are two with the same remainder when divided by 4.

SOLUTION:Consider the possible remainders when divided by 4:

Remainders: 0, 1, 2, 3

We have 5 integers (pigeons) and 4 remainders (pigeonholes).

By the Pigeonhole Principle:

5 (integers) > 4 (remainders)

Therefore, at least two integers must have the same remainder when divided by 4.

Proof:

1. Divide the 5 integers by 4 and consider their remainders.

2. If any remainder occurs twice, we're done.

3. Otherwise, all 4 remainders occur once, but we have 5 integers.

4. By Pigeonhole Principle, at least 2 integers share the same remainder.

QUESTION Show that if f is a function from S to T , where S and T are finite sets with |
S| > |T |, then there are elements s1 and s2 in S such that f (s1) = f (s2), or in other words, f
is not one-to-one.

SOLUTION:

This is a direct application of the Pigeonhole Principle.

Proof:

1. |S| > |T| (number of elements in S exceeds number of elements in T)

2. Consider f as assigning each element of S to an element of T.

3. By Pigeonhole Principle, since |S| > |T|, at least two elements in S must map to the same
element in T.

Therefore, ∃ s1, s2 ∈ S such that f(s1) = f(s2), and f is not one-to-one.

QUESTION What is the minimum number of students, each of whom comes from one of
the 50 states, who must be enrolled in a university to guarantee that there are at least 100
who come from the same state?

SOLUTION:

This is a classic problem of the Pigeonhole Principle.

Number of pigeonholes (states) = 50

Number of pigeons (students) = x (to be determined)

Minimum number of students from same state = 100

Apply Pigeonhole Principle:

x ≥ 50 × 99 + 1 = 4951

Therefore, at least 4951 students are needed to guarantee that there are at least 100 students from
the same state.

Proof:

1. Divide students into 50 groups (one per state).

2. Each group must have at least 99 students for 50 groups.

3. Add one more student to ensure one group has at least 100 students.

This minimum number ensures that at least one state has at least 100 students represented.

QUESTION : Let (xi, yi ), i = 1, 2, 3, 4, 5, be a set of five distinct points with integer

coordinates in the xy plane. Show that the midpoint of the line joining at least one pair of
these points has integer coordinates.

SOLUTION:

Consider the parity (even/odd) of the coordinates:

(x, y) can be:

- (even, even)

- (even, odd)

- (odd, even)

- (odd, odd)

There are 4 possible parity combinations.

By Pigeonhole Principle:

5 points (pigeons) > 4 parity combinations (pigeonholes)

At least two points have the same parity combination.

Case 1: (even, even) and (even, even)

Midpoint: ((even+even)/2, (even+even)/2) = (even, even)

Case 2: (even, odd) and (even, odd)

Midpoint: ((even+even)/2, (odd+odd)/2) = (even, even)

Case 3: (odd, even) and (odd, even)

Midpoint: ((odd+odd)/2, (even+even)/2) = (even, even)

Case 4: (odd, odd) and (odd, odd)

Midpoint: ((odd+odd)/2, (odd+odd)/2) = (even, even)

In all cases, the midpoint has integer coordinates.

Therefore, among five distinct points with integer coordinates, there exists at least one pair
whose midpoint has integer coordinates.

QUESTION : Let (xi, yi, zi ), i = 1, 2, 3, 4, 5, 6, 7, 8, 9, be a set of nine distinct points with

integer coordinates in xyz space. Show that the midpoint of at least one pair of these points
has integer coordinates.

SOLUTION:

Consider the parity (even/odd) of the coordinates:

(x, y, z) can be:

- (even, even, even)

- (even, even, odd)

- (even, odd, even)

- (even, odd, odd)

- (odd, even, even)

- (odd, even, odd)

- (odd, odd, even)

- (odd, odd, odd)

There are 8 possible parity combinations.

By Pigeonhole Principle:

9 points (pigeons) > 8 parity combinations (pigeonholes)

At least two points have the same parity combination.

Case 1: (even, even, even) and (even, even, even)

Midpoint: ((even+even)/2, (even+even)/2, (even+even)/2) = (even, even, even)

Case 2-7: Similar to Case 1, midpoint has integer coordinates.

Case 8: (odd, odd, odd) and (odd, odd, odd)

Midpoint: ((odd+odd)/2, (odd+odd)/2, (odd+odd)/2) = (even, even, even)

In all cases, the midpoint has integer coordinates.

Therefore, among nine distinct points with integer coordinates in xyz space, there exists at least
one pair whose midpoint has integer coordinates.

QUESTION :How many ordered pairs of integers (a, b) are needed to guarantee that
there are two ordered pairs (a1, b1) and (a2, b2) such that a1 mod 5 = a2 mod 5 and b1
mod 5 = b2 mod 5?

SOLUTION:

Consider the possible remainders modulo 5 for a and b:

a mod 5: 0, 1, 2, 3, 4

b mod 5: 0, 1, 2, 3, 4

There are 5 × 5 = 25 possible combinations of remainders.

By Pigeonhole Principle:

Number of pigeonholes = 25

Number of pigeons = n (to be determined)

To guarantee two ordered pairs with same remainders:

n > 25
n = 26

Therefore, 26 ordered pairs of integers are needed to guarantee that there are two ordered pairs
(a1, b1) and (a2, b2) such that:

a1 mod 5 = a2 mod 5

b1 mod 5 = b2 mod 5

This result can be generalized for modulo m and n pairs:

QUESTION :Number of pairs needed = mn + 1

a) Show that if five integers are selected from the first

eight positive integers, there must be a pair of these

integers with a sum equal to 9.

b) Is the conclusion in part (a) true if four integers are

selected rather than five?

SOLUTION:

a) Consider the pairs of integers from the first eight positive integers with a sum equal to 9:

(1, 8), (2, 7), (3, 6), (4, 5)

There are 4 pairs.

By Pigeonhole Principle:

5 integers (pigeons) > 4 pairs (pigeonholes)

If 5 integers are selected, at least two must belong to the same pair.

Therefore, there must be a pair of these integers with a sum equal to 9.

b) Consider selecting 4 integers:

{1, 2, 3, 4}, {1, 2, 5, 6}, {1, 3, 5, 7}, {2, 3, 5, 8}

No pair has a sum equal to 9.

With 4 integers, it's possible to avoid pairs with sum 9.

Conclusion only holds for 5 or more integers.

QUESTION:
a) Show that if seven integers are selected from the first

10 positive integers, there must be at least two pairs

of these integers with the sum 11.

b) Is the conclusion in part (a) true if six integers are

selected rather than seven?

SOLUTION:

a) Consider pairs of integers from the first 10 positive integers with sum 11:

(1, 10), (2, 9), (3, 8), (4, 7), (5, 6)

There are 5 pairs.

By Pigeonhole Principle:

7 integers (pigeons) > 5 pairs (pigeonholes)

If 7 integers are selected, at least 2 pairs must belong to the same or different pairs with sum 11.

Therefore, there must be at least two pairs of these integers with sum 11.

b) Consider selecting 6 integers:

{1, 2, 3, 7, 8, 10}, {1, 2, 4, 6, 7, 9}, {1, 3, 4, 6, 8, 10}

No two pairs have sum 11.

With 6 integers, it's possible to avoid two pairs with sum 11.

Conclusion only holds for 7 or more integers.

QUESTION How many numbers must be selected from the set {1, 2, 3, 4, 5, 6} to
guarantee that at least one pair of these numbers add up to 7?

SOLUTION:

Consider pairs of numbers from the set {1, 2, 3, 4, 5, 6} with sum 7:

(1, 6), (2, 5), (3, 4)

There are 3 pairs.

By Pigeonhole Principle:

4 numbers (pigeons) > 3 pairs (pigeonholes)

If 4 numbers are selected, at least 2 must belong to the same pair.

Therefore, 4 numbers must be selected to guarantee at least one pair adds up to 7.

QUESTION :Find an increasing subsequence of maximal length and a decreasing

subsequence of maximal length in the sequence 22, 5, 7, 2, 23, 10, 15, 21, 3, 17.

SOLUTION:

Increasing Subsequence of Maximal Length:

Length: 6

Subsequence: 2, 3, 10, 15, 17, 23

Decreasing Subsequence of Maximal Length:

Length: 5

Subsequence: 22, 23, 21, 17, 10, (no 3 and 2 can also be included)

QUESTION : Construct a sequence of 16 positive integers that has no increasing or

decreasing subsequence of five terms.

SOLUTION:

Here's a sequence of 16 positive integers with no increasing or decreasing subsequence of five

terms:
8, 1, 9, 2, 7, 3, 6, 4, 5, 10, 4, 9, 3, 2, 1, 8

Construction:

1. Start with 8.

2. Alternate between increasing and decreasing sequences.

3. Use a "staircase" pattern: 8, 1, 9, 2, 7, 3, 6, 4, 5.

4. Repeat the pattern in reverse: 10, 4, 9, 3, 2, 1, 8.

Properties:

- No increasing subsequence of five terms.

- No decreasing subsequence of five terms.

This sequence is an example of a "Dyck sequence" or "mountain range sequence."

QUESTION :Show that if there are 101 people of different heights standing in a line, it is
possible to find 11 people in the order they are standing in the line with heights that are
either increasing or decreasing.

SOLUTION:

Consider longest increasing/decreasing subsequences ending at each position.

For each person, consider:

- Length of longest increasing subsequence ending at this position (I)

- Length of longest decreasing subsequence ending at this position (D)

Since heights are distinct, (I, D) pairs are unique.

Number of possible (I, D) pairs = 10 × 10 = 100

By Pigeonhole Principle:

101 people (pigeons) > 100 (I, D) pairs (pigeonholes)

At least two people share the same (I, D) pair.

This implies an increasing or decreasing subsequence of length 11.

Therefore, 11 consecutive people with increasing or decreasing heights exist.

QUESTION : Show that whenever 25 girls and 25 boys are seated around a circular table
there is always a person both of whose neighbors are boys.

SOLUTION:

Consider the 25 girls as "dividers".

Maximum number of boys that can be separated by 25 girls = 25 + 1 = 26

Since there are 25 boys, at least one boy must be next to another boy.

Therefore, there is always a person with two boy neighbors.

QUESTION : Suppose that 21 girls and 21 boys enter a mathematics competition.

Furthermore, suppose that each entrant solves at most six questions, and for every boy-girl
pair, there is at least one question that they both solved. Show that there is a question that
was solved by at least three girls and at least three boys.

By Turán's Theorem (or graph theory):

Create a bipartite graph with girls (G) and boys (B) as vertices.

Edges connect boy-girl pairs sharing a question.

Since each entrant solves ≤ 6 questions, degree(vertice) ≤ 6.

Turán's Theorem guarantees ≥ 3 girls and ≥ 3 boys share a question.

QUESTION : Describe an algorithm in pseudocode for producing the largest increasing

or decreasing subsequence of a sequence of distinct integers.

SOLUTION:

Here's a pseudocode algorithm for finding the largest increasing or decreasing subsequence:

Largest Increasing/Decreasing Subsequence Algorithm

Input: Sequence S of distinct integers

Output: Largest increasing/decreasing subsequence LIDS

Variables:

- n: length of S

- L: array of lengths of longest increasing subsequences ending at each position

- D: array of lengths of longest decreasing subsequences ending at each position

- prevL: array of previous elements in longest increasing subsequences

- prevD: array of previous elements in longest decreasing subsequences

Procedure:

Procedure LIS(S)

Initialize L[1...n] = 1, D[1...n] = 1

Initialize prevL[1...n] = NULL, prevD[1...n] = NULL

For i = 2 to n

For j = 1 to i-1

If S[i] > S[j] and L[i] < L[j] + 1

L[i] = L[j] + 1

prevL[i] = j

If S[i] < S[j] and D[i] < D[j] + 1

D[i] = D[j] + 1

prevD[i] = j

Find maxL = max(L), maxD = max(D)

If maxL ≥ maxD

Start at index i with L[i] = maxL

Reconstruct increasing subsequence using prevL

Else
 Start at index i with D[i] = maxD

Reconstruct decreasing subsequence using prevD

Return reconstructed subsequence as LIDS

Time Complexity: O(n^2)

Space Complexity: O(n)

This algorithm uses dynamic programming to compute the lengths of longest

increasing/decreasing subsequences ending at each position. It then reconstructs the largest
subsequence by tracing back the previous elements.

QUESTION : Showthat in a group of five people (where any two people are either
friends or enemies), there are not necessarily three mutual friends or three mutual enemies.

SOLUTION:

Here's a counterexample:

Consider five people: A, B, C, D, and E.

Friend relationships:

A-B, A-C, B-D, C-D, D-E, E-A

Enemy relationships:

A-D, A-E, B-C, B-E, C-E

No three people are mutual friends:

- A-B-C have a mutual enemy (B-C)

- A-B-D have a mutual enemy (A-D)

- A-C-D have a mutual enemy (A-D)

- A-D-E have a mutual enemy (A-D and A-E)

- B-C-D have a mutual enemy (B-C)

- B-D-E have a mutual enemy (B-E)

- C-D-E have a mutual enemy (C-E)

No three people are mutual enemies:

- A-D-E have a mutual friend (D-E)

- A-B-E have a mutual friend (A-E is an enemy, but A-B and B-E are not friends)

- A-C-E have a mutual friend (A-C)

- B-C-D have a mutual friend (B-D)

- B-C-E have a mutual enemy (B-C and C-E)

- B-D-E have a mutual friend (D-E)

- C-D-E have a mutual friend (D-E)

This example demonstrates that in a group of five people, there aren't necessarily three mutual
friends or three mutual enemies.

QUESTION :There are 38 different time periods during which classes at a university can
be scheduled. If there are 677 different classes, how many different rooms will be needed?

SOLUTION:

To determine the minimum number of rooms required, we need to find the maximum number of
classes that overlap in the same time period.

Let's assume each class occupies one room.

We can use the Pigeonhole Principle:

677 classes (pigeons) > 38 time periods (pigeonholes)

To find the maximum number of classes per time period:

677 classes / 38 time periods ≈ 17.81 classes/time period

Since we can't have a fraction of a class, we round up to the nearest whole number:
18 classes/time period

Therefore, at least 18 rooms are needed to accommodate the classes during the busiest time
period.

QUESTION : Show that if n is an integer with n ≥ 2, then the Ramsey number R(2, n)
equals n.

SOLUTION:

The Ramsey number R(2, n) represents the smallest number of vertices in a complete graph such
that any coloring of its edges with two colors (say, red and blue) contains either:

1. A red clique (complete subgraph) of size 2

2. A blue clique of size n

Claim: R(2, n) = n

Lower bound: R(2, n) ≥ n

R(2, n) ≥ n and R(2, n) ≤ n

R(2, n) = n

This result shows that for any integer n ≥ 2, the Ramsey number R(2, n) equals n.

QUESTION :Show that if m and n are integers with m ≥ 2 and n ≥ 2, then the Ramsey
numbersR(m, n) andR(n, m) are equal.

SOLUTION:

The Ramsey numbers R(m, n) and R(n, m) represent the smallest number of vertices in a
complete graph such that any coloring of its edges with two colors (say, red and blue) contains
either:

R(m, n):

1. A red clique of size m

2. A blue clique of size n

R(n, m):

1. A red clique of size n

2. A blue clique of size m

Claim: R(m, n) = R(n, m)

Proof:

Consider a complete graph with R(m, n) vertices.

Color its edges with two colors (red and blue).

Case 1: There exists a red clique of size m.

Then, there's no blue clique of size n (by definition of R(m, n)).

This same graph and coloring demonstrate that R(n, m) ≤ R(m, n), since:

1. Red clique of size n doesn't exist (smaller than m).

2. Blue clique of size m doesn't exist (would imply blue clique of size n).

Case 2: There exists a blue clique of size n.

Similar argument shows R(m, n) ≤ R(n, m).

Combining the cases:

R(m, n) ≤ R(n, m) and R(n, m) ≤ R(m, n)

R(m, n) = R(n, m)

This result shows that Ramsey numbers are symmetric.

Intuition:

Ramsey numbers depend on the clique sizes, not their colors.

Swapping colors (red/blue) and clique sizes (m/n) yields equivalent conditions.
This symmetry holds for all Ramsey numbers, including those with more than two colors.

Permutation and combination

QUESTION: List all the permutations of {a, b, c}.

SOLUTION: Here are all 6 permutations of {a, b, c}:

1. a, b, c

2. a, c, b
3. b, a, c

4. b, c, a

5. c, a, b

6. c, b, a

Formulas:

- Number of permutations = n! (n factorial), where n = 3

- 3! = 3 × 2 × 1 = 6

QUESTION: How many different permutations are there of the set {a, b, c, d, e, f, g}?
SOLUTION:

The number of permutations of the set {a, b, c, d, e, f, g} is:

7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5,040

There are 5,040 different permutations.

- QUESTION : How many permutations of {a, b, c, d, e, f, g} end with a?

SOLUTION:

The number of permutations of {a, b, c, d, e, f, g} that end with "a" is:

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720

There are 720 permutations that end with "a".

QUESTION: Let S = {1, 2, 3, 4, 5}.

a) List all the 3-permutations of S.

b) List all the 3-combinations of S.

SOLUTION: Here are the answers:

a) 3-Permutations of S:
(1, 2, 3), (1, 2, 4), (1, 2, 5),

(1, 3, 2), (1, 3, 4), (1, 3, 5),

(1, 4, 2), (1, 4, 3), (1, 4, 5),

(1, 5, 2), (1, 5, 3), (1, 5, 4),

(2, 1, 3), (2, 1, 4), (2, 1, 5),

(2, 3, 1), (2, 3, 4), (2, 3, 5),

(2, 4, 1), (2, 4, 3), (2, 4, 5),

(2, 5, 1), (2, 5, 3), (2, 5, 4),

(3, 1, 2), (3, 1, 4), (3, 1, 5),

(3, 2, 1), (3, 2, 4), (3, 2, 5),

(3, 4, 1), (3, 4, 2), (3, 4, 5),

(3, 5, 1), (3, 5, 2), (3, 5, 4),

(4, 1, 2), (4, 1, 3), (4, 1, 5),

(4, 2, 1), (4, 2, 3), (4, 2, 5),

(4, 3, 1), (4, 3, 2), (4, 3, 5),

(4, 5, 1), (4, 5, 2), (4, 5, 3),

(5, 1, 2), (5, 1, 3), (5, 1, 4),

(5, 2, 1), (5, 2, 3), (5, 2, 4),

(5, 3, 1), (5, 3, 2), (5, 3, 4),

(5, 4, 1), (5, 4, 2), (5, 4, 3)

Total: 60

b) 3-Combinations of S:
(1, 2, 3), (1, 2, 4), (1, 2, 5),

(1, 3, 4), (1, 3, 5), (1, 4, 5),

(2, 3, 4), (2, 3, 5), (2, 4, 5),

(3, 4, 5)

Total: 10

QUESTION: Find the value of each of these quantities.

a) P(6, 3) b) P(6, 5)

c) P(8, 1) d) P(8, 5)

e) P(8, 8) f ) P(10, 9)

SOLUTION: Here are the values:

a) P(6, 3) = 6! / (6-3)!

= 6! / 3!

= (6 × 5 × 4 × 3 × 2 × 1) / (3 × 2 × 1)

=6×5×4

= 120

b) P(6, 5) = 6! / (6-5)!

= 6! / 1!

=6×5×4×3×2

= 720

c) P(8, 1) = 8! / (8-1)!

= 8! / 7!

=8

=8

d) P(8, 5) = 8! / (8-5)!
= 8! / 3!

= (8 × 7 × 6 × 5 × 4 × 3 × 2 × 1) / (3 × 2 × 1)

=8×7×6×5×4

= 6720

e) P(8, 8) = 8! / (8-8)!

= 8! / 0!

= 8!

= 40320

f) P(10, 9) = 10! / (10-9)!

= 10! / 1!

= 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2

= 3628800

Note:

- P(n, k) = n! / (n-k)!

- P(n, n) = n!

- P(n, 1) = n

QUESTION: Find the value of each of these quantities.

a) C(5, 1) b) C(5, 3)

c) C(8, 4) d) C(8, 8)

e) C(8, 0) f ) C(12, 6)

SOLUTION: Here are the values:

a) C(5, 1) = 5! / (1!(5-1)!)

= 5! / (1!4!)
=5

=5

b) C(5, 3) = 5! / (3!(5-3)!)

= 5! / (3!2!)

= (5 × 4 × 3 × 2 × 1) / ((3 × 2 × 1)(2 × 1))

= 10

c) C(8, 4) = 8! / (4!(8-4)!)

= 8! / (4!4!)

= (8 × 7 × 6 × 5 × 4 × 3 × 2 × 1) / ((4 × 3 × 2 × 1)(4 × 3 × 2 × 1))

= 70

d) C(8, 8) = 8! / (8!(8-8)!)

= 8! / (8!0!)

=1

e) C(8, 0) = 8! / (0!(8-0)!)

= 8! / (0!8!)

=1

f) C(12, 6) = 12! / (6!(12-6)!)

= 12! / (6!6!)

= (12 × 11 × 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1) / ((6 × 5 × 4 × 3 × 2 × 1)(6 × 5 × 4 × 3 × 2 ×

1))
= 924

Note:

- C(n, k) = n! / (k!(n-k)!)

- C(n, n) = 1

- C(n, 0) = 1

- C(n, k) = C(n, n-k) (symmetry property)

QUESTION: Find the number of 5-permutations of a set with nine elements.

SOLUTION: The number of 5-permutations of a set with 9 elements is:

9P5 = 9! / (9-5)!

= 9! / 4!

= (9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1) / (4 × 3 × 2 × 1)

=9×8×7×6×5

= 15,120

There are 15,120 different 5-permutations of a set with 9 elements.

QUESTION: In how many different orders can five runners finish a race if no ties are
allowed?

SOLUTION: The number of different orders in which five runners can finish a race is:

5! = 5 × 4 × 3 × 2 × 1

= 120

There are 120 different possible orders for the five runners to finish the race.
QUESTION: How many possibilities are there for the win, place, and show (first,
second, and third) positions in a horse race with 12 horses if all orders of finish are
possible?

SOLUTION: To find the number of possibilities for the win, place, and show positions,
calculate the number of 3-permutations of 12 horses:

12P3 = 12! / (12-3)!

= 12! / 9!

= (12 × 11 × 10 × 9 × ... × 1) / (9 × ... × 1)

= 12 × 11 × 10

= 1320

There are 1,320 possible orders for the win, place, and show positions.

QUESTION: There are six different candidates for governor of a state. In how many
different orders can the names of the candidates be printed on a ballot?

SOLUTION: To find the number of different orders in which the names of the six candidates
can be printed on a ballot, we need to calculate the number of permutations. This is because the
order of the names matters.

The number of permutations of n items is given by n!, where n! = n × (n-1) × (n-2) × ... × 1.

For six candidates, the number of permutations is:

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720

So, there are 720 different possible orders for printing the names of the six candidates on a
ballot.

Interestingly, some states have laws governing the order of candidate names on ballots. For
example, Oregon uses a random ordering of the alphabet to arrange candidate names ¹. However,
this doesn't affect the total number of possible permutations.

QUESTION: How many bit strings of length 10 contain

a) exactly four 1s?

b) at most four 1s?

c) at least four 1s?

d) an equal number of 0s and 1s? examination format

SOLUTION: Bit Strings of Length 10

a) Exactly Four 1s

Number of ways to choose 4 positions for 1s out of 10:

10C4 = 10! / (4!6!)

= 210

b) At Most Four 1s

Number of ways to choose 0, 1, 2, 3, or 4 positions for 1s:

10C0 + 10C1 + 10C2 + 10C3 + 10C4

= 1 + 10 + 45 + 120 + 210

= 386

c) At Least Four 1s

Number of ways to choose 4, 5, 6, ..., 10 positions for 1s:

10C4 + 10C5 + 10C6 + ... + 10C10

= 210 + 252 + 210 + 120 + 45 + 10 + 1

= 848

d) Equal Number of 0s and 1s

Since length is 10 (even), equal 0s and 1s is possible:

10C5 = 10! / (5!5!)

= 252

QUESTION: How many bit strings of length 12 contain

a) exactly three 1s?

b) at most three 1s?

c) at least three 1s?

d) an equal number of 0s and 1s?

SOLUTION: Bit Strings of Length 12

a) Exactly Three 1s

Number of ways to choose 3 positions for 1s out of 12:

12C3 = 12! / (3!9!)

= 220

b) At Most Three 1s

Number of ways to choose 0, 1, 2, or 3 positions for 1s:

12C0 + 12C1 + 12C2 + 12C3

= 1 + 12 + 66 + 220

= 299

c) At Least Three 1s

Total number of bit strings - At most 2 ones

= 2^12 - (12C0 + 12C1 + 12C2)

= 4096 - (1 + 12 + 66)
= 4017

d) Equal Number of 0s and 1s

Since length is 12 (even), equal 0s and 1s is possible:

12C6 = 12! / (6!6!)

= 924

QUESTION: A group contains n men and n women. How many ways are there to
arrange these people in a row if the men and women alternate?

SOLUTION: To arrange n men and n women in a row with alternating genders:

Number of arrangements = (n!) × (n!)

Explanation:

- First, arrange the n men in n! ways.

- Then, arrange the n women in n! ways, inserting them between the men.

QUESTION: In how many ways can a set of two positive integers less than 100 be
chosen?

SOLUTION: The number of ways to choose two positive integers less than 100:

1. Choose two distinct integers:

99C2 = 99! / (2!(99-2)!)

= 99! / (2!97!)

= (99 × 98) / 2

= 4851

2. Choose two identical integers (i.e., pairs):

99

Total number of ways = 4851 + 99

= 4950

QUESTION :In how many ways can a set of five letters be selected from the English
alphabet?

SOLUTION: The English alphabet has 26 letters.

Number of ways to choose 5 letters:

Without repetition (distinct letters):

26C5 = 26! / (5!(26-5)!)

= 26! / (5!21!)

= (26 × 25 × 24 × 23 × 22) / (5 × 4 × 3 × 2 × 1)

= 65,780

With repetition (allowing duplicates):

26^5 = 26 × 26 × 26 × 26 × 26

= 11,881,376

QUESTION: How many subsets with an odd number of elements does a set with 10
elements have?

SOLUTION: A set with 10 elements has:

2^10 = 1024 total subsets.

To find subsets with an odd number of elements:

Observe that:

- 10C1 subsets have 1 element (10)

- 10C3 subsets have 3 elements (120)

- 10C5 subsets have 5 elements (252)

- 10C7 subsets have 7 elements (120)

- 10C9 subsets have 9 elements (10)

Add these subsets with an odd number of elements:

10 + 120 + 252 + 120 + 10 = 512

QUESTION : How many subsets with more than two elements does a set with 100
elements have?

SOLUTION: A set with 100 elements has:

2^100 = 1,267,650,600,228,229,401,496 total subsets.

To find subsets with more than two elements:

Total subsets - subsets with 0 elements - subsets with 1 element - subsets with 2 elements

= 2^100 - 100C0 - 100C1 - 100C2

= 2^100 - 1 - 100 - (100 × 99) / 2

= 1,267,650,600,228,229,401,496 - 1 - 100 - 4950

= 1,267,650,600,228,229,400,445

QUESTION: A coin is flipped eight times where each flip comes up either heads or tails.
How many possible outcomes

a) are there in total?

b) contain exactly three heads?

c) contain at least three heads?

d) contain the same number of heads and tails?

SOLUTION: Coin Flips (8 times)

a) Total Possible Outcomes

Each flip has 2 possibilities (Heads or Tails).

Total outcomes = 2^8

= 256

b) Exactly Three Heads

Number of ways to choose 3 positions for Heads out of 8:

8C3 = 8! / (3!5!)

= (8 × 7 × 6) / (3 × 2 × 1)

= 56

c) At Least Three Heads

Total outcomes - Outcomes with 0, 1, or 2 Heads

= 256 - (8C0 + 8C1 + 8C2)

= 256 - (1 + 8 + 28)

= 219

d) Same Number of Heads and Tails

Since 8 flips, equal Heads and Tails is possible with 4 each:

8C4 = 8! / (4!4!)

= (8 × 7 × 6 × 5) / (4 × 3 × 2 × 1)

= 70

QUESTION: A coin is flipped 10 times where each flip comes up either

heads or tails. How many possible outcomes

a) are there in total?

b) contain exactly two heads?

c) contain at most three tails?

d) contain the same number of heads and tails?

SOLUTION: Coin Flips (10 times)

a) Total Possible Outcomes

Each flip has 2 possibilities (Heads or Tails).

Total outcomes = 2^10

= 1024

b) Exactly Two Heads

Number of ways to choose 2 positions for Heads out of 10:

10C2 = 10! / (2!8!)

= (10 × 9) / (2 × 1)

= 45

c) At Most Three Tails

Equivalent to 7 or more Heads (since 10 - 3 = 7):

10C7 + 10C8 + 10C9 + 10C10

= 120 + 45 + 10 + 1

= 176

d) Same Number of Heads and Tails

Since 10 flips, equal Heads and Tails is possible with 5 each:

10C5 = 10! / (5!5!)

= (10 × 9 × 8 × 7 × 6) / (5 × 4 × 3 × 2 × 1)

= 252

QUESTION: How many bit strings of length 10 have

a) exactly three 0s?

b) more 0s than 1s?

c) at least seven 1s?

d) at least three 1s?

SOLUTION: Bit Strings of Length 10

a) Exactly Three 0s

Number of ways to choose 3 positions for 0s out of 10:

10C3 = 10! / (3!7!)

= (10 × 9 × 8) / (3 × 2 × 1)

= 120

b) More 0s than 1s

Equivalent to more than 5 0s (since 10/2 = 5):

10C6 + 10C7 + 10C8 + 10C9 + 10C10

= 210 + 120 + 45 + 10 + 1

= 386

c) At Least Seven 1s

Equivalent to at most 3 0s:

10C0 + 10C1 + 10C2 + 10C3

= 1 + 10 + 45 + 120

= 176

d) At Least Three 1s
Total bit strings - Bit strings with 0, 1, or 2 1s

= 2^10 - (10C10 + 10C9 + 10C8)

= 1024 - (1 + 10 + 45)

= 968

QUESTION: How many ways are there for eight men and five women to stand in a line
so that no two women stand next to each other?

SOLUTION: To ensure no two women stand next to each other:

1. Arrange the 8 men in 8! ways.

2. Choose 5 positions for women from the 9 gaps between and around men:

(M M M M M M M M)

Choose 5 positions from 9 (including ends).

9C5 = 9! / (5!4!)

= (9 × 8 × 7 × 6 × 5) / (5 × 4 × 3 × 2 × 1)

= 126

3. Arrange the 5 women in 5! ways.

Total number of ways = 8! × 9C5 × 5!

= 40,320 × 126 × 120

= 608,256,000

QUESTION: How many ways are there for 10 women and six men to stand in a line so
that no two men stand next to each other?

SOLUTION: To ensure no two men stand next to each other:

1. Arrange the 10 women in 10! ways.

2. Choose 6 positions for men from the 11 gaps between and around women:

(W W W W W W W W W W)
Choose 6 positions from 11 (including ends).

11C6 = 11! / (6!5!)

= (11 × 10 × 9 × 8 × 7 × 6) / (6 × 5 × 4 × 3 × 2 × 1)

= 462

3. Arrange the 6 men in 6! ways.

Total number of ways = 10! × 11C6 × 6!

= 3,628,800 × 462 × 720

= 1,235,520,640,000

QUESTION: exceeding 100 contain three consecutive integers k, k + 1, k + 2, in the

correct order

a) where these consecutive integers can perhaps be separated

by other integers in the permutation?

b) where they are in consecutive positions in the permutation?

SOLUTION: Permutations of integers 1 to 100.

a) Three consecutive integers (k, k+1, k+2) anywhere in the permutation:

Number of ways to choose 3 consecutive integers:

98 (since 1-2-3 to 98-99-100)

Number of ways to arrange remaining 97 integers:

97!

Number of ways to insert 3 consecutive integers:

98 × 97! × 98C3 (choose 3 positions from 98)

However, this overcounts (e.g., 1-2-3 and 2-3-4 counted separately).

Correct count:

100! - (number of permutations without consecutive integers)

= 100! - (number without 1-2-3) - (number without 2-3-4) - ... - (number without 98-99-100)

Using PIE (Principle of Inclusion-Exclusion), we get:

100! - 98 × 97! + 96 × 96! - ... + (-1)^97 × 3!

Approximately:

100! - 98!

b) Three consecutive integers (k, k+1, k+2) in consecutive positions:

Number of ways to choose 3 consecutive integers:

98

Number of ways to arrange remaining 97 integers:

97!

Number of ways to insert 3 consecutive integers block:

98 (choose position for block)

Total:

98 × 97!

98! permutations contain three consecutive integers in consecutive positions.

QUESTION: Seven women and nine men are on the faculty in the mathematics
department at a school.

a) How many ways are there to select a committee of five members of the department if at
least one woman must be on the committee?

b) How many ways are there to select a committee of five members of the department if at
least one woman and at least one man must be on the committee?
SOLUTION: Faculty Committee Selection

a) At Least One Woman:

Total committees - Committees with no women

= Total committees - Committees with only men

Total committees = 16C5

= 16! / (5!11!)

= 4368

Committees with only men = 9C5

= 9! / (5!4!)

= 126

Committees with at least one woman = 4368 - 126

= 4242

Committees

b) At Least One Woman and At Least One Man:

with at least one woman and at least one man

= Total committees - Committees with only women - Committees with only men

Total committees = 16C5 = 4368

Committees with only women = 7C5 = 21

Committees with only men = 9C5 = 126

Committees with at least one woman and at least one man

= 4368 - 21 - 126

= 4221

SO,
a) 4242 ways to select a committee with at least one woman.

b) 4221 ways to select a committee with at least one woman and at least one man.

QUESTION : Suppose that a department contains 10 men and 15 women. How many
ways are there to form a committee with six members if it must have the same number of
men and women?

SOLUTION: Committee Formation with Equal Men and Women

Since the committee has 6 members and must have equal men and women:

Number of men = Number of women = 6/2 = 3

Number of ways to choose 3 men from 10:

10C3 = 10! / (3!7!)

= (10 × 9 × 8) / (3 × 2 × 1)

= 120

Number of ways to choose 3 women from 15:

15C3 = 15! / (3!12!)

= (15 × 14 × 13) / (3 × 2 × 1)

= 455

Total number of committees with 3 men and 3 women:

120 × 455

= 54,600

So, 54,600 ways to form a committee with 3 men and 3 women.

QUESTION: The English alphabet contains 21 consonants and five vowels. How many
strings of six lowercase letters of the English alphabet contain

a) exactly one vowel?

b) exactly two vowels?

c) at least one vowel?

d) at least two vowels?

SOLUTION : String Formation with Vowels and Consonants

a) Exactly One Vowel:

Choose 1 vowel from 5: 5C1 = 5

Choose 5 consonants from 21: 21C5 = 20349

Arrange 6 letters: 6! = 720

Total strings with exactly 1 vowel: 5 × 20349 × 720 = 73,080,720

Alternatively: 5C1 × 21C5 × 6! = 73,080,720

b) Exactly Two Vowels:

Choose 2 vowels from 5: 5C2 = 10

Choose 4 consonants from 21: 21C4 = 5985

Arrange 6 letters: 6! = 720

Total strings with exactly 2 vowels: 10 × 5985 × 720 = 43,032,000

c) At Least One Vowel:

Total strings - Strings with no vowels

= 26^6 - 21^6

= 308,915,776 - 85,766,121

= 223,149,655

d) At Least Two Vowels:

Total strings - Strings with 0 or 1 vowel

= 26^6 - 21^6 - (5C1 × 21C5 × 6!)

= 308,915,776 - 85,766,121 - 73,080,720

= 150,068,935

QUESTION: Suppose that a department contains 10 men and 15 women. How many
ways are there to form a committee with six members if it must have more women than
men?

SOLUTION: Committee Formation with More Women than Men

Possible committee compositions:

4 women, 2 men

5 women, 1 man

Calculating possibilities:

4 women, 2 men:

15C4 × 10C2 = 1365 × 45 = 61,425

5 women, 1 man:

15C5 × 10C1 = 3003 × 10 = 30,030

Total number of committees with more women than men:

61,425 + 30,030

= 91,455

So, 91,455 ways to form a committee with more women than men.

QUESTION: How many bit strings contain exactly eight 0s and 10 1s if every 0 must be
immediately followed by a 1?

SOLUTION : Bit Strings with 0s followed by 1s

Since every 0 must be followed by a 1:

Treat "01" as a single block.

Number of blocks = 8 (for 8 zeros)

Number of 1s left = 10 - 8 = 2

Arrange 8 blocks and 2 extra 1s:

(8 blocks + 2 ones) = 10! / (8!2!)

= 10 × 9 / 2

= 45

But blocks can't be rearranged within themselves (fixed "01" order).

So, total bit strings = 45

QUESTION: How many bit strings contain exactly five 0s and 14 1s if every 0 must be
immediately followed by two 1s?

SOLUTION: Bit Strings with 0s followed by 2 1s

Since every 0 must be followed by 2 1s:

Treat "011" as a single block.

Number of blocks = 5 (for 5 zeros)

Number of 1s left = 14 - 10 (2 1s per block) = 4

Arrange 5 blocks and 4 extra 1s:

(5 blocks + 4 ones) = 9! / (5!4!)

= (9 × 8 × 7 × 6 × 5) / (5 × 4 × 3 × 2 × 1)

= 126

But blocks can't be rearranged within themselves (fixed "011" order).

So, total bit strings = 126

9C4 = 126

QUESTION: How many bit strings of length 10 contain at least three 1s and at least
three 0s?
SOLUTION: Bit Strings with at Least 3 1s and 3 0s

Length = 10

Total possible bit strings = 2^10 = 1024

Bit strings with:

0 or 1 1s = 10C0 + 10C1 = 1 + 10 = 11

0 or 1 0s = 10C0 + 10C1 = 1 + 10 = 11 (symmetric)

2 1s and 8 0s = 10C2 = 45

2 0s and 8 1s = 10C2 = 45 (symmetric)

Subtract these from total:

1024 - 11 - 11 - 45 - 45

= 912

So, 912 bit strings of length 10 contain at least three 1s and at least three 0s.

QUESTION: How many ways are there to select 12 countries in the United Nations to
serve on a council if 3 are selected from a block of 45, 4 are selected from a block of 57, and
the others are selected from the remaining 69 countries?

SOLUTION : Council Selection from UN Countries

Break down selection:

Block 1 (45 countries): 3 countries

45C3 = 45! / (3!42!)

= (45 × 44 × 43) / (3 × 2 × 1)

= 15,180

Block 2 (57 countries): 4 countries

57C4 = 57! / (4!53!)

= (57 × 56 × 55 × 54) / (4 × 3 × 2 × 1)

= 395,010
Remaining (69 countries): 5 countries

69C5 = 69! / (5!64!)

= (69 × 68 × 67 × 66 × 65) / (5 × 4 × 3 × 2 × 1)

= 11,238,513

Total ways to select 12 countries:

Multiply choices from each block:

15,180 × 395,010 × 11,238,513

= 669,783,891,800,000

So, approximately 669.8 trillion ways to select 12 countries.

QUESTION: Find the number of circular 3-permutations of 5 people.

SOLUTION: Circular 3-Permutations of 5 People

Circular permutations:

Arrange 3 people around a circle from 5.

Choose 3 from 5:

5C3 = 10

Arrange 3 in a circle:

(3-1)! = 2!

Total circular 3-permutations:

10 × 2!

= 10 × 2

= 20

QUESTION: Find a formula for the number of circular r-permutations of n people.

SOLUTION: Circular r-Permutations Formula

Number of circular r-permutations of n people:

(nC_r) × (r-1)!

Breaking it down:

1. Choose r people from n: nCr

2. Arrange r people in a circle: (r-1)!

Why (r-1)!:

Circular permutations have rotational symmetry.

One position fixed, (r-1) remain to arrange.

Formula:

n! / ((n-r)! × r) × (r-1)!

= (n × (n-1) × ... × (n-r+1)) / r × (r-1)!

Simplified:

(n! / (n-r)!) / r

Application:

For example, circular 3-permutations of 5 people:

(5! / (5-3)!) / 3

= (5! / 2!) / 3

= 20

This formula calculates circular r-permutations for any n and r.