COMP 182: Algorithmic Thinking

Homework 7: Counting

Spring 2023

This homework is divided into three distinct parts. When you submit, you will need a file for each part.

---

Part 1

Problem 1 [7 pts]

How many bit strings of length 10 either start with 000 or end with 111?

Show your work.

---

Problem 2 [7 pts]

How many positive integers less than 1,000,000 have exactly one digit equal to 9 and have a sum of digits equal to 13?

Show your work.

---

Problem 3 [7 pts]

How many solutions are there to the inequality

$$x_1 + x_2 + x_3 \leq 11,$$

where $x_1$, $x_2$, and $x_3$ are nonnegative integers?

Show your work.

---

Problem 4 [8 pts]

Prove, without using induction, that in any set of $n + 1$ positive integers not exceeding $2n$ there must be two that are relatively prime.

---

Part 2

Problem 1 [8 pts]

Suppose that $p$ and $q$ are prime numbers, that $p \neq q$, and that $n = pq$. What is the number of positive integers not exceeding $n$ that are relatively prime to $n$?

Show your work.

---

Problem 2 [21 pts]

In celebration of the end of the semester, all the students and instructors in COMP 182 were invited to take a group picture. Assume that there are $n$ students and $m$ instructors. Exactly one instructor is designated as the lead instructor.

Show your work in each part.

(a) [7 pts]

How many ways are there to arrange all the students and instructors in a line such that all students are standing next to each other (no instructors between them)?

(b) [7 pts]

How many ways are there to arrange all the students and instructors in a line such that no two instructors are standing next to each other (the number of students in the course is so large that it allows us to consider this!)?

(c) [7 pts]

How many ways are there to arrange all the students and instructors in a line such that no student is standing next to the lead instructor?

---

Part 3

Problem 1 [14 pts]

How many ways are there to place 80 identical balls in 5 distinct bins such that no bin has more than 24 balls?

---

Problem 2 [14 pts]

What is the number of permutations of the letters in the word INDISTINGUISHABLE such that the strings GIT, TIN, and NAB do not appear in the permutation?

---

Problem 3 [14 pts]

How many 1-1 functions $f : \{1, \ldots, 20\} \to \{1, \ldots, 80\}$ without a fixed point are there?

A function $f : A \to B$ has a fixed point if there exists an $a \in A$ such that $f(a) = a$.

---

Point Distribution Summary