August 5 - Counting

August 5 - Counting

Roman Hall

Counting Techniques

• Constructive Counting

• Casework

• Complimentary Counting

• Overcounting

Constructive Counting

For constructive counting, we simply count the number of things by figuring out how to make one. We keep track of the number of possibilities for each step and then perform the needed manipulations to find the answer.

Open Ended

1. Define a good word as a sequence of letters that consists only of the letters A, B, and C - some of these letters may not appear in the sequence - and in which A is never immediately followed by B, B is never immediately followed by C, and C is never immediately followed by A. Compute the number of seven-letter good words.

Solution to Problem 1

There are three choices for the first letter in the word. For each letter that we choose, there are two possibilities for the next letter. For example, if the first letter is an A, then the second letter can either be an A or a C. Similarly, there are two choices for the third letter, and so on. Thus, there are  $3\cdot2^6=192$  total seven-letter good words.

Casework

Sometimes there are multiple cases that each behave differently. When this happens, we have to split the problem into several smaller parts to consider each case separately.

Open Ended

2. A salt shaker contains 4 red marbles and 6 blue marbles. A second salt shaker contains 16 red marbles and  $N$  blue marbles. A single marble is drawn at random from each salt shaker. The probability that both marbles are of the same color is  $0.58$ . Compute  $N$ .

Solution to Problem 2

We do casework based on which color is picked.

CASE 1: Both marbles are red. Then the requested probability is  $\frac{4}{4+6}\cdot\frac{16}{N+16}=\frac{32}{5\left(N+16\right)}$ .

CASE 2: Both marbles are blue. Then the requested probability is  $\frac{6}{4+6}\cdot\frac{N}{N+16}=\frac{3N}{5\left(N+16\right)}$ .

Adding both cases and setting it equal to the desired probability gives  $\frac{32+3N}{5\left(N+16\right)}=\frac{58}{100}\Longrightarrow\frac{3N+32}{N+16}=\frac{29}{10}$ . Solving gives  $N=144$ .

Complementary Counting

For complimentary counting, we simply find the number of things that aren't part of what we're trying to count and then subtract from the total number of things. It's easiest to see with an example.

Open Ended

3. Suppose there are eight Republicans running for President in 2024. Compute the number of ordered lists of the top three candidates if we insist that Ron DeSantis is on the list.

Solution to Problem 3

We instead count the number of ordered lists without Ron DeSantis. There are seven possibilities for the first candidate, six for the second, and five for the third, for a total of  $7\cdot6\cdot5=210$  lists. Since there are  $8\cdot7\cdot6=336$  lists in total, Ron DeSantis will be on exactly  $336-210=126$  lists.

Overcounting

Overcounting is exactly what it sounds like. We intentionally count too many things and then subtract what we overcounted. It's also easiest to see with an example.

Open Ended

4. Let  $S$  be the set of the first  $2021$  positive integers. Compute the number of elements in  $S$  that are divisible by  $4$  and/or  $17$ .

Solution to Problem 4 (from AKML 2021)

In the set  $S$ , there are  $\lfloor\frac{2021}{4}\rfloor=505$  multiples of  $4$  and  $\lfloor\frac{2021}{17}\rfloor=118$  multiples of  $17$ . Adding those up we get  $505+118=623$  total elements.

Now we subtract the elements that we double counted, which are the multiples of  $4$  AND  $17$ , or the multiples of  $\operatorname{lcm}\left(4,17\right)=68$ . There are  $\lfloor\frac{2021}{68}\rfloor=29$  multiples of  $68$ . The requested answer is  $623-29=594$ .