Knowing to count is an integral part of having a good grasp of probability. And being comfortable in probability is a sine qua non for understanding cryptography. Aside from making sense of cryptography, learning to count is really fun 😃.
In this primer we will learn to count starting from “scratch” i.e., we will start from a very basic counting problem and then reduce other problems to resemble this. Mathematics is all about making the leap from the realm of the known to the unknown. The power to reduce the unknown to the known is a very powerful technique that will be repeatedly encountered during the study of various branches of mathematics. Even security proofs in cryptography are based on reduction.
So lets start with a very trivial counting problem.
Counting Lists of Numbers
Lets count the number of elements in this list
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
It doesn’t take much to figure out that there are 11 numbers in this list. Now lets try counting other lists of numbers by reducing to this kind of list.
How would we go about counting the following list of numbers?
7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
We know to count a list of the form 1, 2, \cdots, n, where n is some positive natural number greater than or equal to n. Can we reduce this list to this form?
Indeed we can! Subtracting 6 from every element of the list while not changing the count of the list, reduces this list to the form we already know how to count. This is illustrated below.
\begin{align*}
7 && 8 && 9 && \cdots && 17 \\
-6 && -6 && -6 && \cdots && -6 \\
\hline
1 && 2 && 3 && \cdots && 11
\end{align*}We see that this list also consists of 11 numbers.
The important takeaway from this problem is the power of reduction. Always try to reduce something you don’t yet know how to do into something you already know how to do. It’s a mouthful, but it works like a charm in mathematics.
Okay. The next powerful concept in mathematics is abstraction. How do we abstract this counting into a more generic way such that it works for any range of positive numbers a \text{ and } b with b > a and inclusive of a \text{ and } b?
We can follow the same method we followed while counting our previous list. This is shown below:
\begin{align*}
a && a+1 && a+2 && \cdots && b \\
-(a-1) && -(a-1) && -(a-1) && \cdots && -(a-1) \\
\hline
1 && 2 && 3 && \cdots && b-a+1
\end{align*}This is a list of numbers we already know how to count. So there are b-a+1 numbers between the positive natural numbers a \text{ and } b (including a \text{ and } b).
How many multiples of 7 are between 15 \textit{ and } 235 ?
The first multiple of 7 in the list is given by \Biggl\lceil \dfrac{15}{7} \Biggr\rceil \times 7 = 3 \times 7 = 21 .
Alternatively, since \dfrac{15}{7} = 2\dfrac{1}{7}, the smallest multiple of 7 in our list is 3 \times 7 = 21.
By similar reasoning, the last multiple of 7 in our list is \Biggl\lfloor \dfrac{235}{7} \Biggr\rfloor \times 7 = 33 \times 7 = 231.
Alternatively, since \dfrac{235}{7} = 33\dfrac{4}{7}, the largest multiple of 7 in the given list is 33 \times 7 = 231.
Therefore, finding the number of multiples of 7 between 15 \textit{ and } 235 is equivalent to finding the number of multiples of 7 between 21 \textit{ and } 231.
So we have to count the numbers in the following list:
21, 28, 35, \cdots, 231
We can rewrite this list as
7 \times 3, 7 \times 4, 7 \times 5, \cdots, 7 \times 33
We can divide each number in the list by 7 since it does not alter the count of the list. Hence,
3, 4, 5, \cdots, 33
This is a list we know how to handle. We can subtract 2 from each number in the list as shown below.
\begin{align*}
3 && 4 && 5 && \cdots && 33 \\
-2 && -2 && -2 && \cdots && -2 \\
\hline
1 && 2 && 3 && \cdots && 31
\end{align*}We see that there are 31 elements in the list.
Alternatively, we could have also used the formula we just derived i.e., b - a + 1. Here a = 3 \text{ and } b = 33. Hence b - a + 1 = 33 - 3 +1 = 31.
Hence there are 31 multiples of 7 between 15 \text{ and } 235.
Next lets do something a bit fancy.
How many five digit numbers are perfect cubes?
Lets first find the smallest five digit number that is a perfect cube. We will do this by trial and error. We know that 20^3 = 8000. So lets try numbers greater than 20.
\begin{align*}
21^3 &= 9261 \\
22^3 &= 10648 \\
\end{align*}Hence 22^3 is the smallest five digit number that is a perfect cube.
Next lets find the largest five digit number that is a perfect cube. We know that 50^3 = 125000. So clearly it is some number smaller than 50. Hence,
\begin{align*}
45^3 &= 91125 \\
46^3 &= 97336 \\
47^3 &= 103823 \\
\end{align*}So the largest five digit number that is a perfect cube is 46^3.
Hence the list of five digit perfect cubes are:
22^3, 23^3, \cdots, 46^3
The number of numbers in the above list is same as
22, 23, \cdots, 46
This is a list we know how to count. Either we subtract 21 from every number in the list or we use the formula we have derived.Hence,
\begin{align*}
22 && 23 && 24 && \cdots && 46 \\
-21 && -21 && -21 && \cdots && -21 \\
\hline
1 && 2 && 3 && \cdots && 25
\end{align*}So there are 25 numbers in the list. Using the formula, we get 46 - 22 + 1 = 25.
Hence there are 25 five digit cubes.
Lets do something weirder. Lets count the numbers in the following list.
-34, -27, -20, -13, -6, 1, 8, 15, 22, \cdots, 190
I have listed more numbers than usual so that its easier to see the pattern.
We can see that each successive number in the list is greater than the one preceding it by 7. However these are not multiples of 7. For us to count, we need to transform this list into a list of contiguous numbers. Since each number differs from the next one in the list by 7, if we can transform this list into one of contiguous multiples of 7, then we can count as usual.
Subtracting 1 from each number in the list will make it one of contiguous multiples of 7. So the list becomes,
-35, -28, -21, -14, -7, 0, 7, 14, 21, \cdots, 189
Now dividing each number in the list by 7 gives,
-5, -4, -3, -2, -1, 0, 1, 2, 3, \cdots, 27
Adding 6 to each number in the list gives us
\begin{align*}
-5 && -4 && -3 && \cdots && 27 \\
+6 && +6 && +6 && \cdots && +6 \\
\hline
1 && 2 && 3 && \cdots && 33
\end{align*}So there are 33 elements in the list. Alternatively, by using the formula we get 27 - (-5) +1 = 27 + 5 + 1 = 33.
How many numbers are in the following list?
3\frac{2}{3}, 4\frac{1}{3}, 5, 5\frac{2}{3}, \cdots, 26\frac{1}{3}, 27Converting the mixed fractions into proper fractions, we get the following list.
\frac{11}{3}, \frac{13}{3}, \frac{15}{3}, \frac{17}{3}, \cdots, \frac{79}{3}, \frac{81}{3}We can divide all the numbers in the list by 3 to get,
11, 13, 15, 17, \cdots, 79, 81
We can see that every number in the list is 2 more than the previous number in the list. Also adding 1 to every number in the list makes all the numbers divisible by 2. Doing these two operations we get the following lists:
12, 14, 16, 18, \cdots, 80, 82
6, 7, 8, 9, \cdots, 40, 41
We count the number of numbers in the list by subtracting 5 from every number in the list as shown below.
\begin{align*}
6 && 7 && 8 && 9 && \cdots && 40 && 41 \\
-5 && -5 && -5 && -5 && \cdots && -5 && -5 \\
\hline
1 && 2 && 3 && 4 && \cdots && 35 && 36
\end{align*}Alternatively, by using the formula we get 41 - 6 +1 = 36, which agrees with our previous calculation.
Hence there are 36 elements in the list.
How many sets of four consecutive positive integers are there such that the product of the four integers is less than 200000 ?
We know that 22^4 = 234256. Hence we can try to see what the product of 19 \times 20 \times 21 \times 22 equals. The product equals 175560 which is less than 200000. And 20 \times 21 \times 22 \times 23 = 212520 . Hence 19 \times 20 \times 21 \times 22 is the largest product of four consecutive positive integers that is less than 200000.
So we need to count the number of sets in the following list:
\big\{1, 2, 3, 4\big\}, \big\{2, 3, 4, 5\big\}, \big\{3, 4, 5,6\big\}, \cdots, \big\{19, 20, 21, 22\big\}This list is equivalent to the following list since it does not change the number of sets in the list:
1, 2, \cdots, 19
Hence there are 19 sets of four consecutive positive integers whose product is less than 200000.