Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Constructive counting"
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. 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 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>
  
  

Revision as of 13:53, 24 May 2021

In combinatorics, constructive counting is a counting method where one "constructs" a set to count it. This strategy is useful for complicated counting or combinatorics questions, as the problem can be broken down into cases, the number of possibilities in each case can be computed, and those numbers can be added to find the final answer.

Examples

Here are some problems which can be cracked by constructive counting, in increasing difficulty. Note that for some of these problems, constructive counting is not the only solution method.

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

Resources

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Constructive_counting&oldid=154170"