Difference between revisions of "Casework"
Etmetalakret (talk | contribs) |
Etmetalakret (talk | contribs) |
||
| Line 2: | Line 2: | ||
== Examples == | == Examples == | ||
| − | Here are some examples of problems that | + | Here are some examples of problems with solutions that utilize casework. While the selection in this article can be completely solved by splitting it into several cases, most problems in the wild cannot. However, in a sizeable amount of math problems, casework is a crucial intermediate step. |
While there are problems where casework produces the most elegant solution, in those where a shorter answer exists, casework may be considered [[brute force]]. This is especially true if that alternative solution uses [[complementary counting]]. | While there are problems where casework produces the most elegant solution, in those where a shorter answer exists, casework may be considered [[brute force]]. This is especially true if that alternative solution uses [[complementary counting]]. | ||
Revision as of 09:41, 7 November 2021
In combinatorics, casework is a counting method where one splits a problem into several parts, counts these cases individually, then adds together each part's total. Casework is a very general problem-solving approach, and as such has wide applicability.
Contents
Examples
Here are some examples of problems with solutions that utilize casework. While the selection in this article can be completely solved by splitting it into several cases, most problems in the wild cannot. However, in a sizeable amount of math problems, casework is a crucial intermediate step.
While there are problems where casework produces the most elegant solution, in those where a shorter answer exists, casework may be considered brute force. This is especially true if that alternative solution uses complementary counting.
Example 1
How many words are less than four letters long and contain only the letters A, B, C, D, and E? Here, 'word' refers to any string of letters.
Solution: We divide the problem into cases, based on how long the word is.
Case 1: The word is one letter long. Clearly, there are 
of these words.
Case 2: The word is two letters long. Constructing the set of these words, there are options for the first letter and options for the second letter, so there are 
of these words.
Case 3: The word is three letters long. By similar logic as above, we have options for the first letter, options for the second, and options for the third. Then there are 
of these letters.
Adding all our cases up, there are 
words that are less than four letters long and contain only the letters A, B, C, D, and E. 
Example 2
How many positive integers satisfy the equation 
?
Solution: We use casework, based on the value of x.
Case 1: 
. Then this problem becomes 
, so there are 
possible values for 
, and thus solutions when 
is one.
Case 2: 
. Then this problem becomes 
, so there are 
possible values for , and thus solutions when is two.
If 
, the problem becomes 
. But the question mandates that is positive, so there are no solutions when 
. Thus, there are 
positive integer solutions to the equation.
Example 3
2004 AIME II Problem 4: How many positive integers less than 10,000 have at most two different digits?
Solution: Let 
and 
be the two digits of the number. Use casework, based on how many digits the number has.
Case 1: The number is one digit. All numbers in this category satisfy the given condition, so there are 
of these.
Case 2: The number is two-digit. Again, all numbers in this category have two different digits, so there are 
of these.
Case 3: The number is three-digit. The possible cases in this category are 
and 
Using a constructive approach, there are digits for what the first number can be, zero excluded to keep the number three-digit. The second digit can be digits, with zero included and the first digit's number removed. Then there are 
of these numbers.
Case 4: The number is four-digit. The possible cases in this category are 
and 
Using the same logic as before, the first digit has options, as does the second. Then there are 
of these numbers.
Thus, there are 
integers less than 
that have at most two different digits.
