Difference between revisions of "Constructive counting"
Etmetalakret (talk | contribs) |
Etmetalakret (talk | contribs) |
||
Line 26: | Line 26: | ||
'''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 | '''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 <math>1</math> and <math>9</math> inclusive, 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. Without loss of generally, let our digits be <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> 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 <math>126</math> digits, there are <math>5</math> arrangements of them that keep the number snakelike, and thus we have <math>126 \ | + | '''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, 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. Without loss of generally, let our digits be <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> 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 <math>126</math> digits, there are <math>5</math> arrangements of them that keep the number snakelike, and 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. | '''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. |
Revision as of 19:46, 21 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.
Contents
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 to
(it cannot be zero, or else it ceases to be four-digit). As for the other three digits, they can be any number from
to
. From the multiplication principle, our answer is thus
.
Example 2
How many permutations of are there?
Solution: We construct the set of the permutations of . We can imagine this as a row of seven boxes, like
The total number of ways to place three
s in these boxes is
, where
is a combination. Here's one possibility:
From here, we let the four remaining boxes contain the
s, which completes the construction. Thus, there are
different permutations.
.
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 , the second is
, and so on. Thus, the total orders of sock-shoe pairs
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
.
Example 4
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, so the combination that describes this is
. Next, we find out how many permutations of these digits keep the number snakelike. Without loss of generally, let our digits be
,
,
, and
. The total possibilities are
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
digits, there are
arrangements of them that keep the number snakelike, and 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
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.
.