Lesson test: Counting without listing

Counting without listing

1.[2p]
A variable name is a single letter, or a letter followed by one character that is either a letter or a digit. With $26$ letters and $10$ digits, how many names are possible?

CorrectNot quite: 962

2.[2p]
How many integers from $1$ to $999$ contain at least one digit $7$ ?

CorrectNot quite: 271

3.[2p]
How many strings of length $4$ over the alphabet ${A, C, G, T}$ have no two adjacent letters equal?

CorrectNot quite: 108

4.[2p]
How many positive divisors does $360$ have?

CorrectNot quite: 24

5.[1p]
How many subsets of ${1, 2, \dots, 8}$ contain $1$ but not $8$ ?

CorrectNot quite: 64

6.[2p]
A knockout tournament starts with $100$ players, some of whom receive byes in early rounds. How many matches are played in total?

CorrectNot quite: 99

7.[2p]
What is the smallest number of people that guarantees at least four of them share a birth month?

CorrectNot quite: 37

8.[2p]
Why can no lossless compressor shorten every file of $n$ bits?

There are $2^{n}$ files of $n$ bits but only $2^{n} - 1$ shorter files, so two would share an output

Correct

Compression always adds a header longer than the savings

The answer is: There are $2^n$ files of $n$ bits but only $2^n - 1$ shorter files, so two would share an output

Random files contain no repeated patterns to exploit

The answer is: There are $2^n$ files of $n$ bits but only $2^n - 1$ shorter files, so two would share an output

A file of $n$ bits can only be shortened by at most one bit

The answer is: There are $2^n$ files of $n$ bits but only $2^n - 1$ shorter files, so two would share an output

9.[3p]
Which of these statements are correct?

Select all that apply

The sum rule requires the pieces being added to be pairwise disjoint

Correct

The product rule requires each stage to offer the same number of options whatever was chosen before, though not necessarily the same options

Correct

The pigeonhole principle identifies which box holds two objects

The answer is: The sum rule requires the pieces being added to be pairwise disjoint, The product rule requires each stage to offer the same number of options whatever was chosen before, though not necessarily the same options, Toggling one fixed element is a bijection between the even sized and odd sized subsets of a nonempty set

Toggling one fixed element is a bijection between the even sized and odd sized subsets of a nonempty set

Correct

1.[2p] A variable name is a single letter, or a letter followed by one character that is either a letter or a digit. With 26 letters and 10 digits, how many names are possible?

2.[2p] How many integers from 1 to 999 contain at least one digit 7?

3.[2p] How many strings of length 4 over the alphabet {A,C,G,T} have no two adjacent letters equal?

4.[2p] How many positive divisors does 360 have?

5.[1p] How many subsets of {1,2,…,8} contain 1 but not 8?

6.[2p] A knockout tournament starts with 100 players, some of whom receive byes in early rounds. How many matches are played in total?

7.[2p] What is the smallest number of people that guarantees at least four of them share a birth month?

8.[2p] Why can no lossless compressor shorten every file of n bits?

9.[3p] Which of these statements are correct?

1.[2p]
A variable name is a single letter, or a letter followed by one character that is either a letter or a digit. With $26$ letters and $10$ digits, how many names are possible?

2.[2p]
How many integers from $1$ to $999$ contain at least one digit $7$ ?

3.[2p]
How many strings of length $4$ over the alphabet ${A, C, G, T}$ have no two adjacent letters equal?

4.[2p]
How many positive divisors does $360$ have?

5.[1p]
How many subsets of ${1, 2, \dots, 8}$ contain $1$ but not $8$ ?

6.[2p]
A knockout tournament starts with $100$ players, some of whom receive byes in early rounds. How many matches are played in total?

7.[2p]
What is the smallest number of people that guarantees at least four of them share a birth month?

8.[2p]
Why can no lossless compressor shorten every file of $n$ bits?

9.[3p]
Which of these statements are correct?