Assignment 1

# Administrivia

- Your assignment must be submitted as a single PDF file through cuLearn
- Late assignments will not be accepted under any circumstances. If you're unable to complete the assignment due to a valid and documented medical or personal situation then the weight of this assignment can be shifted to the weight of the remaining assignments.
- You are encouraged to collaborate on assignments, but at the level of discussion only. When writing your solutions, you must do so in your own words.
- Past experience has shown conclusively that those who do not put adequate effort into the assignments do not learn the material and have a probability near 1 of doing poorly on the exams.
- When writing your solutions:
- You must justify your answers.
- The answers should be concise, clear and neat.
- When presenting proofs, every step should be justified.

# Meat

## 1. ID

- Make sure the first thing on page 1 of your assignment is your name and student number.

## 2. Decimal Strings

A *dec-string* is a sequence of characters from the 10-character alphabet $\lbrace 0,1,2,3,4,5,6,7,8,9\rbrace$. For example, these are dec-strings:

0 36562342320 49548362729

Let $n\ge 0$ be an integer.

- What is the number of dec-strings of length $n$?
- What is the number of dec-strings $d_1,\ldots,d_n$ of length $n$ such that $d_1d_2\neq 00$. In other words, what is the number of dec-strings of length $n$ that don't begin with $00$?
- What is the number of dec-strings $d_1,\ldots,d_n$ of length $n$ such that
$d_1d_2\neq 00$
*and*$d_2d_3\neq 11$? - What is the number of dec-strings $d_1,\ldots,d_n$ of length $n$ such that $d_1d_2\neq 00$
*and*$d_2d_3\neq 01$? - What is the number of dec-strings $d_1,\ldots,d_n$ of lenght $n$ such that $d_1d_2=00$
*or*$d_1d_2d_3=111$? - What is the number of dec-strings $d_1,\ldots,d_n$ of length $n\ge 4$ such that $d_1d_2\neq 00$
*or*$d_3d_4\neq 11$. - A dec-string $d_1,\ldots,d_n$ is
*bad*if $d_i=d_{i+1}$ or $d_{i}+d_{i+1}=9$ for at least one $i\in\lbrace 1,\ldots,n-1\rbrace$ and it is*good*otherwise. What is the number of good dec-strings of length $n$? - A dec-string $d_1,\ldots,d_n$ is
*2-bad*if, $d_i=d_j$ or $d_i+d_j=9$ for some $i< j \le i+2$ and it is*2-good*otherwise. What is the number of 2-good dec-strings? - A dec-string $d_1,\ldots,d_n$ is
*$k$-bad*if $d_i=d_j$ or $d_i+d_j=9$ for some $i<j\le i+k$ and is*$k$-good*otherwise. What is the number of $k$-good dec-strings of length $n$?

## 3. Collective Arts

Collective Arts Brewing currently makes 30 types of IPA and 6 types of Lager.

- The manager at Mike's Place needs to choose 4 types of IPA and 4 types of Lager. How many options does the manager have?
- The 8 beers (4 IPA and 4 Lager) selected in the previous question must be placed in a line on a display shelf so that no two IPA are adjacent and no two Lager are adjacent. How many ways are there to do this?
- Continuing from the previous question, suppose that two of the beers selected were All Together Now (an IPA) and Hot Pink (a Lager). Since both cans are pink, the manager doesn't want to place them adjacent to each other. How many ways are there to do this (while still alternating between IPA and Lager)?
- How many of the arrangements from the previous question have the All Together Now among from the 4 leftmost bottles and the bottle of Hot Pink among the 4 rightmost bottles?

## 4. Restricted Permutations

Consider all permutations of the integers $1,\ldots,1000$.

- In how many of these permutations do $1,2,3,4$ appear consecutively and in this order?
- In how many of these permutations do $1,2,3,4$ appear consecutively, but not necessarily in order? (For example, they may appear as $1,2,3,4$, or $4,2,3,1$, or $3,1,2,4$, or so on.)
- In how many of these permutations does $1$ appear before $2$, $2$ appear before $3$, and $3$ appear before $4$? (In other words, $1,2,3,4$ appear in order, but not necessarily consecutively.)
- In how many of these permutations do $1,2,3,4$ appear in order but no two are adjacent?

## 5. Drug Trials

A certain friend of mine has spent the better part of a lifetime testing recreational drugs. After thorough testing, this friend has identified 20 recreational drugs $D_1,\ldots,D_{20}$ and determined (experimentally) that any 3 of these drugs can be taken simultaneously with no adverse effects.

- Assuming my friend determined this entirely by testing, how many experiments did my friend have to perform?
- A new designer drug called $D_{21}$ has just hit the streets and my friend wants to know if $D_{21}$ can be added to their list. That is, can any triple of $D_1,\ldots,D_{21}$ be safely taken together? How many
*additional*experiments does my friend need to determine this? - Suppose my friend survives the experience and $D_{21}$ makes it onto the list. My friend takes scrupulous notes about all experiments and notices something peculiar about the answers to the preceding two questions. What combinatorial identity did my friend just discover?
- Suppose that an impatient novice wants to repeat my friends discovery using fewer experiments. This novice is willing to take 5 drugs at a time. What is the fewest number of experiments this novice can perform so that for any triple $D_i,D_j,D_k\in\lbrace D_1,\ldots,D_{21}\rbrace$, at least one of this novice's experiments includes $D_i$, $D_j$, and $D_k$?