Difference between revisions of "Constructive counting"

Revision as of 12:49, 26 May 2021

In combinatorics, constructive counting is a counting method where one "constructs" a set to count it. It is a close cousin of casework, as constructive counting usually involves breaking the problem down into several smaller counting problems.

Examples

Here are some problems which can be cracked by constructive counting, in increasing difficulty. It's worth noting that as problem-solving ability becomes more advanced, there are fewer problems that can be completely solved by constructive counting. At the same time, there are many, many problems where constructive counting is a crucial intermediate step.

Example 1

How many four-digit numbers are there?

Solution: We construct the set of four-digit numbers. For the first digit, it can be any number from $1$ to $9$ (it cannot be zero, or else it ceases to be four-digit). As for the other three digits, they can be any number from $0$ to $10$ . From the multiplication principle, our answer is thus $9 \cdot 10 \cdot 10 \cdot 10 = 9000$ . $\square$

Example 2

How many permutations of $AAAABBB$ are there?

Solution: We construct the set of the permutations of $AAAABBB$ . We can imagine this as a row of seven boxes, like $\square \square \square \square \square \square \square.$ The total number of ways to place three $B$ s in these boxes is $_7 C_3 = 35$ , where $_n C_k$ is a combination. Here's one possibility: $\square B B \square \square B \square.$ From here, we let the four remaining boxes contain the $A$ s, which completes the construction. Thus, there are $35$ different permutations. $\square$ .

Example 3

2001 AMC 12 Problem 16: A spider has one sock and one shoe for each of its eight legs. In how many different orders can the spider put on its socks and shoes, assuming that, on each leg, the sock must be put on before the shoe?

Solution: We construct the orders the spider can get dressed, We can model the order as 16 boxes, where each box is populated with a certain sock or shoe. First, we choose where each sock-shoe pair is located in the 16 boxes. The first sock-shoe pair is $_{16} C_2$ , the second is $_{14} C_2$ , and so on. Thus, the total orders of sock-shoe pairs $\binom{16}{2}\binom{14}{2}\cdots\binom{2}{2}= \frac{16!}{2^8}.$ There is only one arrangement of the sock-shoe pair that leaves them in the correct order, so we don't need to permute them further. Thus, our final answer is $\frac{16!}{2^8}$ . $\square$

Example 4

2004 AIME I Problem 6: An integer is called snakelike if its decimal representation $a_1a_2a_3\cdots a_k$ satisfies $a_i<a_{i+1}$ if $i$ is odd and $a_i>a_{i+1}$ if $i$ is even. How many snakelike integers between 1000 and 9999 have four distinct digits?

Solution: We construct the set of snakelike integers. All the recursive requirement is saying is that the second digit must be greater than the first and third, and the fourth must be greater than the third. But before we start construction, we must divide our investigation into several cases, based on whether we allow zeroes

Case 1: Snakelike integers with no zero. First, we choose the four integers. They must be between $1$ and $9$ inclusive, so the combination that describes this is $_9 C_4 = 126$ . Next, we find out how many permutations of these digits keep the number snakelike. Without loss of generally, let our digits be $1$ , $3$ , $5$ , and $7$ . The total possibilities are $1537, 1735, 3517, 3715, \textrm{ and } 5713.$ If one would like to be rigorous about it, one could choose one digit to be first, then count how many possible permutations of the other three keep the integer snakelike. Hence, out of our $126$ digits, there are $5$ arrangements of them that keep the number snakelike, and thus we have $126 \cdot 5 = 630$ snakelike integers with four distinct digits and no zero.

Case 2: Snakelike integers with one zero. First, we choose the other three integers, which by similar logic above is $_9 C_3 = 84$ . Next, we permute these digits. Without loss of generality, let our other three digits be $1$ , $3$ , and $5$ . The total possibilities are $1305, 1503, \textrm{ and } 3501.$ Hence, there are $84 \cdot 3 = 252$ snakelike integers with four distinct digits and one zero.

It's easy to see that introducing a second zero would mandate them being the first and third digits. However, this breaks our requirement that our integers must be between $1000$ and $9999$ , so there are no four-digit snakelike integers with two or more zeroes. Thus, our total is $630 + 252 = 882$ snakelike integers with four distinct digits, as desired. $\square$ .

More examples

2005 AIME I Problems/Problem 5

Revision as of 20:22, 25 May 2021 (view source) Etmetalakret (talk \| contribs) ← Older edit		Revision as of 12:49, 26 May 2021 (view source) Etmetalakret (talk \| contribs) m Newer edit →
Line 17:		Line 17:
	''[[2001 AMC 12 Problems/Problem 16 \| 2001 AMC 12 Problem 16]]: A spider has one sock and one shoe for each of its eight legs. In how many different orders can the spider put on its socks and shoes, assuming that, on each leg, the sock must be put on before the shoe?		''[[2001 AMC 12 Problems/Problem 16 \| 2001 AMC 12 Problem 16]]: A spider has one sock and one shoe for each of its eight legs. In how many different orders can the spider put on its socks and shoes, assuming that, on each leg, the sock must be put on before the shoe?

−	'''Solution''': We construct the orders the spider can get dressed, We can model the order as 16 boxes, where each box is populated with a certain sock or shoe. First, we choose where each sock-shoe pair is in the 16 boxes. The first sock-shoe pair is <math>_{16} C_2</math>, the second is <math>_{14} C_2</math>, and so on. Thus, the total orders of sock-shoe pairs <cmath>\binom{16}{2}\binom{14}{2}\cdots\binom{2}{2}= \frac{16!}{2^8}.</cmath> There is only one arrangement of the sock-shoe pair that leaves them in the correct order, so we don't need to permute them further. Thus, our final answer is <math>\frac{16!}{2^8}</math>. <math>\square</math>	+	'''Solution''': We construct the orders the spider can get dressed, We can model the order as 16 boxes, where each box is populated with a certain sock or shoe. First, we choose where each sock-shoe pair is located in the 16 boxes. The first sock-shoe pair is <math>_{16} C_2</math>, the second is <math>_{14} C_2</math>, and so on. Thus, the total orders of sock-shoe pairs <cmath>\binom{16}{2}\binom{14}{2}\cdots\binom{2}{2}= \frac{16!}{2^8}.</cmath> There is only one arrangement of the sock-shoe pair that leaves them in the correct order, so we don't need to permute them further. Thus, our final answer is <math>\frac{16!}{2^8}</math>. <math>\square</math>

Page

Toolbox

Search