Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Casework"

(added example problem)
m (→‎Example 3)
 
(18 intermediate revisions by 8 users not shown)
Line 1: Line 1:
−
'''Casework''' is solving [[counting]] or [[probability]] problems by considering the different cases and adding them together. While casework is sometimes the most elegant method of solution, it may be considered [[brute force]] when a more elegant solution exists.
+
In [[combinatorics]], '''casework''' is a [[counting]] method that involves splitting a problem into several parts, counting these parts individually, then adding together the totals of each part. Casework is a very general problem-solving approach, and as such has wide applicability.
  
 +
== Examples ==
 +
Here are some examples that demonstrate casework in action. Unlike the selections in this article, most problems cannot be completely solved through casework. However, it is crucial as an intermediate step across all of mathematics, not just in competitions.
  
−
== Example Problems and Solutions ==
+
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]].
−
=== Introductory ===
 
−
* [[2006_AMC_12A_Problems/Problem_20 | 2006 AMC 12A Problem 20]]
 
  
−
* [[2005_AMC_10A_Problems/Problem_14 | 2005 AMC 10A Problem 14]]
+
=== Example 1 ===
−
=== Intermediate ===
+
''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.''
−
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2004&p=371262 AIME 2004II/2]
 
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=371220#p371220 AIME 2004II/4]
 
−
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2005&p=365518 AIME 2005I/5]
 
−
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2000&p=385886 AIME 2000II/3]
 
  
 +
'''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 <math>5</math> of these words.
 +
 +
'''Case 2''': The word is two letters long. [[Constructive counting | Constructing]] the set of these words, there are <math>5</math> options for the first letter and <math>5</math> options for the second letter, so there are <math>5^2 = 25</math> of these words.
 +
 +
'''Case 3''': The word is three letters long. By similar logic as above, we have <math>5</math> options for the first letter, <math>5</math> options for the second, and <math>5</math> options for the third. Then there are <math>5^3 = 125</math> of these letters.
 +
 +
Adding all our cases up, there are <math>5 + 25 + 125 = 155</math> words that are less than four letters long and contain only the letters A, B, C, D, and E. <math>\square</math>
 +
 +
=== Example 2 ===
 +
''How many positive integers satisfy the equation <math>x^4 + y < 70</math>?''
 +
 +
'''Solution''': We use casework, based on the value of x.
 +
 +
'''Case 1''': <math>x=1</math>. Then this problem becomes <math>y<69</math>, so there are <math>68</math> possible values for <math>y</math>, and thus <math>68</math> solutions when <math>x</math> is one.
 +
 +
'''Case 2''': <math>x=2</math>. Then this problem becomes <math>y<54</math>, so there are <math>53</math> possible values for <math>y</math>, and thus <math>53</math> solutions when <math>x</math> is two.
 +
 +
If <math>x=3</math>, the problem becomes <math>y<-11</math>. But the question mandates that <math>y</math> is positive, so there are no solutions when <math>x \geq 3</math>. Thus, there are <math>68+53=121</math> positive integer solutions to the equation. <math>\square</math>
 +
 +
=== Example 3 ===
 +
''[[2004 AIME II Problems/Problem 4 | 2004 AIME II Problem 4]]: How many positive integers less than 10,000 have at most two different digits?''
 +
 +
'''Solution''': Let <math>A</math> and <math>B</math> 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 <math>9</math> of these.
 +
 +
'''Case 2''': The number is two-digit. Again, all numbers in this category have two different digits, so there are <math>90</math> of these.
 +
 +
'''Case 3''': The number is three-digit. The possible cases in this category are <math>AAA, AAB, ABA,</math> and <math>BAA.</math> Using a constructive approach, there are <math>9</math> digits for what the first number can be, zero excluded to keep the number three-digit. The second digit can be <math>9</math> digits, with zero included and the first digit's number removed. Then there are <math>9 + 3 \cdot 81 = 252</math> of these numbers.
 +
 +
'''Case 4''': The number is four-digit. The possible cases in this category are <math>AAAA, AAAB, AABA, ABAA, BAAA, AABB, ABAB,</math> and <math>ABBA.</math> Using the same logic as before, the first digit has <math>9</math> options, as does the second. Then there are <math>9 + 7 \cdot 81 = 576</math> of these numbers.
 +
 +
Thus, there are <math>9 + 90 + 252 + 576 = 927</math> integers less than <math>10,000</math> that have at most two different digits. <math>\square</math>
 +
 +
=== More examples ===
 +
* [https://artofproblemsolving.com/wiki/index.php/2005_AIME_I_Problems/Problem_5 2000 AIME 1 Problem 5]
 +
 +
== Resources ==
 +
* [https://artofproblemsolving.com/videos/counting/chapter2/186 AoPS Casework Counting Part 1]
 +
* [https://artofproblemsolving.com/videos/counting/chapter2/187 AoPS Casework Counting Part 2]
  
 
== See also ==
 
== See also ==
−
* [[Math books]]
+
* [[Complementary counting]]
 +
* [[Constructive counting]]
 +
* [[Overcounting]]
 +
 
 +
[[Category:Combinatorics]]
 +
[[Category:Definition]]

Latest revision as of 16:40, 24 September 2024

In combinatorics, casework is a counting method that involves splitting a problem into several parts, counting these parts individually, then adding together the totals of each part. Casework is a very general problem-solving approach, and as such has wide applicability.

Examples

Here are some examples that demonstrate casework in action. Unlike the selections in this article, most problems cannot be completely solved through casework. However, it is crucial as an intermediate step across all of mathematics, not just in competitions.

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 $5$ of these words.

Case 2: The word is two letters long. Constructing the set of these words, there are $5$ options for the first letter and $5$ options for the second letter, so there are $5^2 = 25$ of these words.

Case 3: The word is three letters long. By similar logic as above, we have $5$ options for the first letter, $5$ options for the second, and $5$ options for the third. Then there are $5^3 = 125$ of these letters.

Adding all our cases up, there are $5 + 25 + 125 = 155$ words that are less than four letters long and contain only the letters A, B, C, D, and E. $\square$

Example 2

How many positive integers satisfy the equation $x^4 + y < 70$?

Solution: We use casework, based on the value of x.

Case 1: $x=1$. Then this problem becomes $y<69$, so there are $68$ possible values for $y$, and thus $68$ solutions when $x$ is one.

Case 2: $x=2$. Then this problem becomes $y<54$, so there are $53$ possible values for $y$, and thus $53$ solutions when $x$ is two.

If $x=3$, the problem becomes $y<-11$. But the question mandates that $y$ is positive, so there are no solutions when $x \geq 3$. Thus, there are $68+53=121$ positive integer solutions to the equation. $\square$

Example 3

2004 AIME II Problem 4: How many positive integers less than 10,000 have at most two different digits?

Solution: Let $A$ and $B$ 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 $9$ of these.

Case 2: The number is two-digit. Again, all numbers in this category have two different digits, so there are $90$ of these.

Case 3: The number is three-digit. The possible cases in this category are $AAA, AAB, ABA,$ and $BAA.$ Using a constructive approach, there are $9$ digits for what the first number can be, zero excluded to keep the number three-digit. The second digit can be $9$ digits, with zero included and the first digit's number removed. Then there are $9 + 3 \cdot 81 = 252$ of these numbers.

Case 4: The number is four-digit. The possible cases in this category are $AAAA, AAAB, AABA, ABAA, BAAA, AABB, ABAB,$ and $ABBA.$ Using the same logic as before, the first digit has $9$ options, as does the second. Then there are $9 + 7 \cdot 81 = 576$ of these numbers.

Thus, there are $9 + 90 + 252 + 576 = 927$ integers less than $10,000$ that have at most two different digits. $\square$

More examples

Resources

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Casework&oldid=227958"