Counting
7 Problems • 4 sub-topics
Isaac Cho • 6/28/2026
Introduction
Counting is a staple of number theory and combinatorics on the AMC 10. It's an odd concept to turn something as simple as counting, something we learn as school children, and make it into an immensely complicated and confusing endevour, but counting is a perfect example of how the AMC 10 takes simple topics and twists it into something difficult that engages logic. Counting, in its nature, is a sort of brute force, but proficiency in counting allows you to do so in an effective way that can save you time and energy.
Casework
Casework the practice of splitting a large quantity into cases so that you can count it systematically and in an organized manner.
When to use Casework
I like to say that casework can be applied to anything in combinatorics, because when it comes down to it casework is just a type of counting, and combinatorics is fundamentally counting. That being said, casework is technically brute forcing, which we want to avoid unless it is nescessary or optimal. There will sometimes be better solutions to casework, or combinations of when to use casework, etc.
Casework is best used when there are distinct and manageable cases (small case sizes, not many). Of course, this hardly simplifies it, so we'll go into a few cases where casework tends to be likely:
- In number theory/combinatorics questions where one digit is set, either by divisibility or by a clear constraint (e.g. "divisible by 5" would indicate what the last digit is, and you can solve for the remaining digits by cases for if it is \(0\) or \(5\))
- When there are boundaries ("at least", "at most"), where you can solve for all cases that are under or over the constraint
- When there are already clearly defined cases and they are easy to solve (e.g. how many combinations are there of 3 items taken 2 at a time?)
- When finding the opposite would take too long. If finding the "complement" or opposite would be easier, that is indicative of complementary counting.
Casework will work in a lot of situations, if not all, but it helps to know when it is best.
How to Divide Into Cases
Cases must fit two situations: they must be mutually exlcusive and collectively exhaustive. In a more simple vernacular, they must not overlap, and alltogether they must cover the entire data set. For instance, if we said that we had knights that were either red or blue and then were also either magic or non-magic, we can't say our cases are red and magic, because that could overlap and would discount blue-non-magics. We can't do red-blue-magic-non-magic because those would overlap. Thus, we would have to do red-blue or magic-non-magic.
AMC 10B 2021 Spring Problem 16 star star star star
Call a positive integer an uphill integer if every digit is strictly greater than the previous digit. For example, \(1357\), \(89\) and \(5\) are all uphill integers, but \(32\), \(1240\) and \(466\), are not. How many uphill integers are divisble by \(15\)?
Complementary Counting
Complementary counting is the idea that you can count something by counting everything that is not that something. Effectively, you calculate the total number of outcomes, and then you count anything that is not your expected/preferred outcome. When you subtract the latter from the former, of course, you will get the expected outcome. This is especially helpful when you have a very complex, nuanced, or faceted goal or expected outcome that you are trying to count. If the alternate is easier, go for the alternate. Consider the following problem:
- Una rolls \(6\) standard \(6\)-sided dice simultaneously and calculates the product of the \(6\) numbers obtained. What is the probability that the product is divisible by \(4\)?
There are a lot of ways to be divisible by \(4\). You could roll a \(4\), or two \(2\)s, or a \(2\) and a \(6\), and so on and so on. But if we consider the alternate, that is much simpler. We just need it to be entirely odd or be even and not divisible by \(4\). All odds is just \(\frac{1}{2}^6=\frac{1}{64}\). For evens, we have \((\binom{6}{1})=6\) ways to pick exactly ONE to be even, and that can be \(2\) or \(6\). Thus, there's a \(\frac{1}{3} \times \frac{1}{2}^5 \times 6 = \frac{1}{16}\). The combined probability is \(\frac{1}{64}+\frac{1}{16}=\frac{5}{64}\). The opposite, or the complement, is thus \(1-\frac{5}{64}=\frac{59}{64}\).
Stars and Bars
One of the most essential tricks to know in counting is what we call Stars and Bars. Written as \(\binom{n+k-1}{k-1}\), it describes \(n\) stars split by into \(k\) bins by \(k-1\) bars. Note that this allows bins to be empty. This is a very technical definition, of course, so I'll introduce you to one of the main ways stars and bars is used: sum of digits. Let's say you know that the sum of digits of some \(3\) digit number is \(20\). We have \(20\) stars spit into \(3\) bins by \(2\) bars. The number of stars on each side of a bar is the digit, and of course we account for overcounting with the digits or the cases where a bin is empty, but the idea still follows.
Conclusion
Counting is an essential tool on the AMC 10 for being efficient about large scale problems and solving combinatorics or number theory questions. It allows you to systematically organize how you solve, even if you are using brute force. Common tricks in counting involve casework, complementary counting, or stars and bars.
Question 1:
Loading question...
Privacy Policy
Data Collection
How we use your data
Children's Privacy
Terms and Conditions
Welcome Back!
Access your progress across all your devices
Need Some Help?
Contact us through our form