Difference between revisions of "Constructive counting"
Etmetalakret (talk | contribs) |
Etmetalakret (talk | contribs) |
||
Line 7: | Line 7: | ||
''How many four-digit numbers are there?'' | ''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 one to nine (it cannot be zero, or else it ceases to be four-digit), so it has <math>9</math> options. As for the other three digits, they can be any number from zero to ten, so they all have <math>10</math> options. From the multiplication principle, our answer is thus <math>9 \cdot 10 \cdot 10 \cdot 10 = 9000</math>. <math>\square</math> | + | '''Solution''': We construct the set of four-digit numbers, by finding the number of possibilities each digit can be, then multiplying them all together. For the first digit, it can be any number from one to nine (it cannot be zero, or else it ceases to be four-digit), so it has <math>9</math> options. As for the other three digits, they can be any number from zero to ten, so they all have <math>10</math> options. From the multiplication principle, our answer is thus <math>9 \cdot 10 \cdot 10 \cdot 10 = 9000</math>. <math>\square</math> |
=== Example 2 === | === Example 2 === |
Revision as of 17:00, 29 August 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.
Contents
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 solved by constructive counting alone. At the same time, there are many, many more 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, by finding the number of possibilities each digit can be, then multiplying them all together. For the first digit, it can be any number from one to nine (it cannot be zero, or else it ceases to be four-digit), so it has options. As for the other three digits, they can be any number from zero to ten, so they all have
options. 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
We first "pick" the boxes that
can occupy. This is given by
, 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 located 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 further. 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.
.