Difference between revisions of "Constructive counting"
m |
(→Resources) |
||
| Line 59: | Line 59: | ||
== Resources == | == Resources == | ||
| − | * [https://artofproblemsolving.com/videos/counting/chapter2/ | + | * [https://artofproblemsolving.com/videos/counting/chapter2/190 AoPS Constructive Counting Part 1] |
| − | * [https://artofproblemsolving.com/videos/counting/chapter2/186 AoPS | + | * [https://artofproblemsolving.com/videos/counting/chapter2/186 AoPS Casework Counting Part 1] |
== See also == | == See also == | ||
Revision as of 14:32, 29 January 2022
In combinatorics, constructive counting is a counting method where one constructs a set to count it. There exists no consensus on an exact definition, but this construction roughly involves breaking a problem down into several components which can be counted individually, then reassembling the components to arrive at the original problem.
Along with casework and complementary counting, constructive counting is among the most fundamental tools used to solve counting problems. It is related to but distinctly different from casework, as the examples listed here should illustrate.
Contents
Introductory Examples
Here are some introductory-level problems with solutions that utilize constructive counting.
Example 1
How many four-digit numbers are there?
Solution: We break up the problem into the number of choices each digit can be. For the first digit, it can be any number from one to nine — zero excluded, or else it ceases to have four digits — so it has 
possibilities choices. As for the other three digits, they can be any number from zero to ten, so they all have 
possibilities. We then multiply these together to get an answer of 
. 
This may seem like a frivolous and fruitless trick, but the technique of breaking a problem down into several problems, each with its own possibilities is truly fundamental and appears everywhere in combinatorics. Also, the words "possibility," "choice," and "option" are interchangeable in the context of constructive counting.
Example 2
How many lists of seven numbers are there such that each entry is between 
and inclusive and no two consecutive entries are equal?
Solution: We can model this situation as a row of 7 boxes, like this: ![\[\square \square \square \square \square \square \square,\]](http://latex.artofproblemsolving.com/c/8/4/c847aa1be7dcbe8bd792afb93b9612d0dcea12d8.png)
which we must populate with numbers between and including and ; the key restriction here is that no two boxes right next to each other can have the same number.
A constructive approach is the simplest way to attack this question. Let each option be a digit out of the seven numbers. The first digit can be any digit from to , of which there are 
such options. The second can be any of to too, with the sole exception of the previous digit. Regardless of whatever the first digit is, we know that it removes one option, so there are 
options for the second digit.
The exact same logic applies to the third digit; it can be any of the digits except the one before it, so it has 
options. This continues until the seventh digit, which means that digits to all have options. Then our answer is 
, as desired.
These two examples use options specifically based on digits, but this isn't the entire picture of constructive counting. In general, constructive techniques include any breakage of a counting problem into several smaller counting problems. The following example displays this well:
Example 3
How many permutations of 
are there?
Solution: We can model the question as a row of seven boxes, like this: which we have to populate with 
s and 
s. Using constructive counting is an idea, but there are multiple ways one might proceed with the construction. If we were to go like before and break the problem down by each box, we'd get a fairly messy solution.
Instead, one might think to break it down by first placing the s separately, then placing the s. Starting with the s, we must choose the boxes of their placement; because all the s are indistinguishable, this is given by 
, where 
is a combination. One example among many placements of the s is ![\[\square A A \square A \square A.\]](http://latex.artofproblemsolving.com/d/0/3/d03d74e13968b8328d23546af890883efe3bcbf7.png)
For the s, their position is actually predetermined by choosing the s; the only place the three s can go is in the three empty boxes, so we don't have to account for them after choosing the s. Thus, there are 
different permutations of , as required. .
Like in this problem, there are sometimes multiple independent ways to construct a set. In others, however, an alternative method is not apparent, as with the next example:
Example 4
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: Note that each leg has one designated shoe and a designated sock; each leg's shoe and sock belong to only that leg. The question is then only asking about the order in time in which it puts on all 16 socks and shoes. We can model the different orders as 16 boxes, where each box is populated with a certain sock or shoe, like this: ![\[\square \square \square \square \square \square \square \square \square \square \square \square \square \square \square \square.\]](http://latex.artofproblemsolving.com/d/8/a/d8a87f9fae3f24f03d8a641ced5a18afc17448e3.png)
Breaking up the problem by each box leads to a dead end. Instead, we can use a similar approach to example three to solve this problem — we can first choose two boxes in which each leg's sock-shoe pair is located, then we permute them. For the first leg, the location of its sock and shoe's two boxes are given by 
; but on permuting them, we know that the sock appears first in the list, which implies that only one permutation exists.
So, there are just different places in which the first leg's sock and shoe can be located in the 16 boxes. By similar logic, the second leg has 
places in the boxes, the third has 
, and so on. The final answer is then the product of the leg's choices, which is ![\[\binom{16}{2}\binom{14}{2}\cdots\binom{2}{2} = \left(\frac{16 \cdot 15}{2}\right) \left(\frac{14 \cdot 13}{2}\right) \cdots \left(\frac{2 \cdot 1 }{2}\right) = \frac{16!}{2^8}.\]](http://latex.artofproblemsolving.com/9/f/6/9f65b14a87579712f663db65a0739f8a5e0bc56f.png)
Thus, our final answer is 
. .
This problem was much more challenging than the others mentioned thus far, but it's a lovely illustration of just how piercing a cleverly chosen construction can be to counting problems.
Example 5
2004 AIME I Problem 6: An integer is called snakelike if its decimal representation 
satisfies 
if 
is odd and 
if 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 
and inclusive, and no digit can be repeated, so the combination that describes this is 
. Next, we find out how many permutations of these digits keep the number snakelike. For simplicity, consider the case of , , 
, and . The total possibilities are ![\[1537, 1735, 3517, 3715, \textrm{ and } 5713.\]](http://latex.artofproblemsolving.com/b/3/d/b3d9ad89e3efb401d50317ad493ed39bc1eec532.png)
This applies to all snakelike integers with no zero, which means there arrangements that keep the number snakelike. Thus we have 
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 
. Next, we permute these digits. Without loss of generality, let our other three digits be , , and . The total possibilities are ![\[1305, 1503, \textrm{ and } 3501.\]](http://latex.artofproblemsolving.com/1/c/0/1c08524b87154cf483676a371742d9433dd629d2.png)
Hence, there are 
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 
and 
, so there are no four-digit snakelike integers with two or more zeroes. Thus, our total is 
snakelike integers with four distinct digits, as desired. .
It's worth noting that as problem-solving ability becomes more advanced, there are fewer problems that can be solved by constructive counting alone; the list of examples terminates at a late-introductory level consequentially. At the same time, there are many, many more problems at a higher level where constructive counting is a crucial intermediate step, combined with other counting strategies to reach an answer.
