Difference between revisions of "Constructive counting"

Latest revision as of 07:42, 19 August 2024

In combinatorics, constructive counting is a counting technique that involves constructing an item belonging to a set. Along with the construction, one counts the total possibilities of each step and assembles these to enumerate the full set.

Along with casework and complementary counting, constructive counting is among the most fundamental techniques in counting. Familiarity with constructive counting is essential in combinatorics, especially in intermediate competitions.

Introductory Examples

Example 1

How many four-digit numbers are there?

Solution: We can construct a four-digit by picking the first digit, then the second, and so on until the fourth. The first digit can be any number from one to nine — zero excluded, or else it ceases to have four digits — so it has $9$ possible choices. The other three digits can be any number from zero to nine (total 10 digits), so they all have $10$ possibilities. We multiply the possibilities for each digit to arrive at our answer: $9 \cdot 10 \cdot 10 \cdot 10 = 9000$ . $\square$

Constructive counting is a simple concept, more so than its definition might lead one to think. All we did was think about constructing a four-digit number by choosing its digits, compute the possible numbers each digit can be, and multiply the resulting numbers.

This is a problem where constructive counting is not the simplest way to proceed. This next example is one where constructive counting is essential:

Example 2

How many lists of seven numbers are there such that each entry is between $2$ and $9$ 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,$ which we must populate with numbers between and including $2$ and $9$ ; the key restriction here is that no two boxes right next to each other can have the same number.

The first digit can be any number from $2$ to $9$ , of which there are $8$ such options. The second can be any of $2$ to $9$ 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 $8 - 1 = 7$ options for the second digit.

The exact same logic applies to the third digit; it can be any of the $8$ digits except the one before it, so it has $7$ options. This continues until the seventh digit, which means that digits $2$ to $7$ all have $7$ options. Hence, our answer is $8 \cdot 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7 = 8 \cdot 7^6 = 941,192$ , as desired. $\square$

These two examples use options specifically based on digits, but this isn't the entire picture of constructive counting. The following example uses constructive counting in a different context.

Example 3

How many permutations of $AAAABBB$ are there?

Solution: We can model the question as a row of seven boxes, like this: $\square \square \square \square \square \square \square,$ which we have to populate with $4$ $A$ s and $3$ $B$ 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 $A$ s separately, then placing the $B$ s. Starting with the $A$ s, we must choose the $4$ boxes of their placement; because all the $A$ s are indistinguishable, this is given by $_7 C_4 = 35$ , where $_n C_k$ is a combination. One example among many placements of the $A$ s is $\square A A \square A \square A.$ For the $B$ s, their position is actually predetermined by choosing the $A$ s; the only place the three $B$ s can go is in the three empty boxes, so we don't have to account for them after choosing the $A$ s. Thus, there are $35$ different permutations of $AAAABBB$ , as required. $\square$ .

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.$ 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 $_{16} C_2$ ; but on permuting them, we know that the sock appears first in the list, which implies that only one permutation exists.

Example 5

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, and no digit can be repeated, 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. For simplicity, consider the case of $1$ , $3$ , $5$ , and $7$ . The total possibilities are $1537, 1735, 3517, 3715, \textrm{ and } 5713.$ This applies to all snakelike integers with no zero, which means there $5$ arrangements that keep the number snakelike. 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$ .

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.

Intermediate Examples

These problems are more advanced than the introductory examples, requiring greater creativity to solve.

Example 1

Russia 1998: A 10-digit number is said to be interesting if its digits are all distinct and it is a multiple of 11111. How many interesting numbers are there?

Solution: There doesn't seem to be a useful pattern in multiples of 11111 And even if there was one, it's not clear how to mediate it with the distinct digits condition. Thus, we look for additional restrictions that will help us count.

Let $n$ be any interesting number. Because $n$ has ten distinct digits, its digits must be an ordered arrangement of $0$ to $9$ used exactly once. From here, note that the sum of its digits, $1 + 2 + \cdots + 9 = 45$ , is divisible by $9$ . This implies through divisibility rules that $n$ is a multiple of $9$ ; therefore, $n$ is a multiple of $11111 \cdot 9 = 99999$ .

An idea from here is to utilize the special properties of $99999$ — namely, that $99999 = 10^5 - 1$ . The $10^5$ compells us to express $n$ as $\overline{uv}$ for some five-digit numbers $u$ and $v$ ; doing so gives that $n = 10^5 u + v = 99999u + (u + v).$ Both sides of this equation must be divisible by $99999$ , which implies that $u+v$ is divisible by $99999$ . It's easy to verify that even without this condition, the maximum of $u+v$ is $97531 + 86420$ , which is less than $2 \cdot 99999$ . Therefore, $u + v$ must be equal to $99999$ .

This also interacts with the distinct digits property; namely, that the corresponding digits of $u$ and $v$ add to $9$ . For example $67915 + 32084 = 99999$ , where $6+3 = 7+2 = 9+0 = 1+8 = 5+4 = 9$ . Thus, corresponding digits must come in pairs — which now enables us to construct $u$ and $v$ . We first place these pairs in $u$ (which places it in $v$ ), of which they can be in any order. There are then $5!$ options for the pairs' positions. The only thing left is which number in each pair goes to $u$ and which to $v$ ; there are $2$ ways we can divvy a pair up, which means there are $2^5$ total possibilities.

But wait! This construction counts numbers that start with zero — something that violates the 10-digit condition — as being interesting numbers. Note that in our count, each digit is equally likely to be first; thus, $1/10$ of our numbers start with $0$ , and only $9/10$ of our count keeps the number ten-digit. Putting this all together, there are $(9/10)(5!)(2^5) = 3456$ interesting numbers. $\square$

@@ Line 1: / Line 1: @@
-'''Constructive counting''' is counting the number of integers, lists, etc., that satisfy a certain property by "constructing" them. This is easier explained through examples.
+In [[combinatorics]], '''constructive counting''' is a [[counting]] technique that involves constructing an item belonging to a set. Along with the construction, one counts the total possibilities of each step and assembles these to enumerate the full set.
-== Examples ==
+Along with [[casework]] and [[complementary counting]], constructive counting is among the most fundamental techniques in counting. Familiarity with constructive counting is essential in combinatorics, especially in intermediate competitions.
-* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2004&p=377954 AIME 2004I/6]
+== Introductory Examples ==
-* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=509050#p509050 AIME 2003I/9]
+=== Example 1 ===
+''How many four-digit numbers are there?''
-===See also===
+'''Solution''': We can construct a four-digit by picking the first digit, then the second, and so on until the fourth. The first digit can be any number from one to nine — zero excluded, or else it ceases to have four digits — so it has <math>9</math> possible choices. The other three digits can be any number from zero to nine (total 10 digits), so they all have <math>10</math> possibilities. We multiply the possibilities for each digit to arrive at our answer: <math>9 \cdot 10 \cdot 10 \cdot 10 = 9000</math>. <math>\square</math>
-* [[Combinatorics]]
+Constructive counting is a simple concept, more so than its definition might lead one to think. All we did was think about constructing a four-digit number by choosing its digits, compute the possible numbers each digit can be, and multiply the resulting numbers.
+This is a problem where constructive counting is not the simplest way to proceed. This next example is one where constructive counting is essential:
+=== Example 2 ===
+''How many lists of seven numbers are there such that each entry is between <math>2</math> and <math>9</math> inclusive and no two consecutive entries are equal?''
+'''Solution''': We can model this situation as a row of 7 boxes, like this: <cmath>\square \square \square \square \square \square \square,</cmath> which we must populate with numbers between and including <math>2</math> and <math>9</math>; the key restriction here is that no two boxes right next to each other can have the same number.
+The first digit can be any number from <math>2</math> to <math>9</math>, of which there are <math>8</math> such options. The second can be any of <math>2</math> to <math>9</math> 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 <math>8 - 1 = 7</math> options for the second digit.
+The exact same logic applies to the third digit; it can be any of the <math>8</math> digits except the one before it, so it has <math>7</math> options. This continues until the seventh digit, which means that digits <math>2</math> to <math>7</math> all have <math>7</math> options. Hence, our answer is <math>8 \cdot 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7 = 8 \cdot 7^6 = 941,192</math>, as desired. <math>\square</math>
+These two examples use options specifically based on digits, but this isn't the entire picture of constructive counting. The following example uses constructive counting in a different context.
+=== Example 3 ===
+''How many [[permutations]] of <math>AAAABBB</math> are there?''
+'''Solution''': We can model the question as a row of seven boxes, like this: <cmath>\square \square \square \square \square \square \square,</cmath> which we have to populate with <math>4</math> <math>A</math>s and <math>3</math> <math>B</math>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 <math>A</math>s separately, then placing the <math>B</math>s. Starting with the <math>A</math>s, we must choose the <math>4</math> boxes of their placement; because all the <math>A</math>s are indistinguishable, this is given by <math>_7 C_4 = 35</math>, where <math>_n C_k</math> is a [[combination]]. One example among many placements of the <math>A</math>s is <cmath>\square A A \square A \square A.</cmath> For the <math>B</math>s, their position is actually predetermined by choosing the <math>A</math>s; the only place the three <math>B</math>s can go is in the three empty boxes, so we don't have to account for them after choosing the <math>A</math>s. Thus, there are <math>35</math> different permutations of <math>AAAABBB</math>, as required. <math>\square</math>.
+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 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''': 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: <cmath>\square \square \square \square \square \square \square \square \square \square \square \square \square \square \square \square.</cmath> 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 <math>_{16} C_2</math>; but on permuting them, we know that the sock appears first in the list, which implies that only one permutation exists.
+=== Example 5 ===
+''[[2004 AIME I Problems/Problem 6 | 2004 AIME I Problem 6]]: An integer is called snakelike if its decimal representation <math> a_1a_2a_3\cdots a_k </math> satisfies <math> a_i<a_{i+1} </math> if <math> i </math> is [[odd integer | odd]] and <math> a_i>a_{i+1} </math> if <math> i </math> is [[even integer | 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 [[casework | cases]], based on whether we allow zeroes
+'''Case 1''': Snakelike integers with no zero. First, we choose the four integers. They must be between <math>1</math> and <math>9</math> inclusive, and no digit can be repeated, so the combination that describes this is <math>_9 C_4 = 126</math>. Next, we find out how many permutations of these digits keep the number snakelike. For simplicity, consider the case of <math>1</math>, <math>3</math>, <math>5</math>, and <math>7</math>. The total possibilities are <cmath>1537, 1735, 3517, 3715, \textrm{ and } 5713.</cmath> This applies to all snakelike integers with no zero, which means there <math>5</math> arrangements that keep the number snakelike. Thus we have <math>126 \cdot 5 = 630</math> 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 <math>_9 C_3 = 84</math>. Next, we permute these digits. Without loss of generality, let our other three digits be <math>1</math>, <math>3</math>, and <math>5</math>. The total possibilities are <cmath>1305, 1503, \textrm{ and } 3501.</cmath> Hence, there are <math>84 \cdot 3 = 252</math> 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 <math>1000</math> and <math>9999</math>, so there are no four-digit snakelike integers with two or more zeroes. Thus, our total is <math>630 + 252 = 882</math> snakelike integers with four distinct digits, as desired. <math>\square</math>.
+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.
+== Intermediate Examples ==
+These problems are more advanced than the introductory examples, requiring greater creativity to solve.
+=== Example 1 ===
+''Russia 1998: A 10-digit number is said to be interesting if its digits are all distinct and it is a multiple of 11111. How many interesting numbers are there?''
+'''Solution''': There doesn't seem to be a useful pattern in multiples of 11111 And even if there was one, it's not clear how to mediate it with the distinct digits condition. Thus, we look for additional restrictions that will help us count.
+Let <math>n</math> be any interesting number. Because <math>n</math> has ten distinct digits, its digits must be an ordered arrangement of <math>0</math> to <math>9</math> used exactly once. From here, note that the sum of its digits, <math>1 + 2 + \cdots + 9 = 45</math>, is divisible by <math>9</math>. This implies through [[divisibility rules]] that <math>n</math> is a multiple of <math>9</math>; therefore, <math>n</math> is a multiple of <math>11111 \cdot 9 = 99999</math>.
+An idea from here is to utilize the special properties of <math>99999</math> — namely, that <math>99999 = 10^5 - 1</math>. The <math>10^5</math> compells us to express <math>n</math> as <math>\overline{uv}</math> for some five-digit numbers <math>u</math> and <math>v</math>; doing so gives that <cmath>n = 10^5 u + v = 99999u + (u + v).</cmath> Both sides of this equation must be divisible by <math>99999</math>, which implies that <math>u+v</math> is divisible by <math>99999</math>. It's easy to verify that even without this condition, the maximum of <math>u+v</math> is <math>97531 + 86420</math>, which is less than <math>2 \cdot 99999</math>. Therefore, <math>u + v</math> must be equal to <math>99999</math>.
+This also interacts with the distinct digits property; namely, that the corresponding digits of <math>u</math> and <math>v</math> add to <math>9</math>. For example <math>67915 + 32084 = 99999</math>, where <math>6+3 = 7+2 = 9+0 = 1+8 = 5+4 = 9</math>. Thus, corresponding digits must come in pairs — which now enables us to construct <math>u</math> and <math>v</math>. We first place these pairs in <math>u</math> (which places it in <math>v</math>), of which they can be in any order. There are then <math>5!</math> options for the pairs' positions. The only thing left is which number in each pair goes to <math>u</math> and which to <math>v</math>; there are <math>2</math> ways we can divvy a pair up, which means there are <math>2^5</math> total possibilities.
+But wait! This construction counts numbers that start with zero — something that violates the 10-digit condition — as being interesting numbers. Note that in our count, each digit is equally likely to be first; thus, <math>1/10</math> of our numbers start with <math>0</math>, and only <math>9/10</math> of our count keeps the number ten-digit. Putting this all together, there are <math>(9/10)(5!)(2^5) = 3456</math> interesting numbers. <math>\square</math>
+== More Problems ==
+* [[2005 AIME I Problems/Problem 5]]
+== Resources ==
+* [https://artofproblemsolving.com/videos/counting/chapter2/190 AoPS Constructive Counting Part 1]
+* [https://artofproblemsolving.com/videos/counting/chapter2/186 AoPS Casework Counting Part 1]
+== See also ==
+* [[Casework]]
+* [[Complementary counting]]
+* [[Overcounting]]
+[[Category:Combinatorics]]
+[[Category:Definition]]

Page

Toolbox

Search

Difference between revisions of "Constructive counting"

Latest revision as of 07:42, 19 August 2024

Contents

Introductory Examples

Example 1

Example 2

Example 3

Example 4

Example 5

Intermediate Examples

Example 1

More Problems

Resources

See also