COMP2804: Discrete Structures II
$\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{\mathbf{E}}\DeclareMathOperator{\deg}{deg}\newcommand{\N}{\mathbb{N}}$
Assignment 1

Administrivia

Meat

1. ID

  1. 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.

  1. What is the number of dec-strings of length $n$?
  2. 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$?
  3. 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$?
  4. 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$?
  5. 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$?
  6. 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$.
  7. 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$?
  8. 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?
  9. 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.

  1. 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?
  2. 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?
  3. 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)?
  4. 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$.

  1. In how many of these permutations do $1,2,3,4$ appear consecutively and in this order?
  2. 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.)
  3. 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.)
  4. 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.

  1. Assuming my friend determined this entirely by testing, how many experiments did my friend have to perform?
  2. 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?
  3. 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?
  4. 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$?