 |
 |
Problem Posts |  |
 |
 |
| Who knew power series multiplication could help you at the grocer? (see Question 2) |
Just a quick post for younger readers. Often one will find oneself using `brute force' approaches when obvious tricks and shortcuts exist. Most of the time, this is justified -- many tricks are usually too arcane to remember, or too impracticable to execute realistically. This is neither. It's fast, simple, and it could save you in a Do-Or-Die (I've used it before; our team won!)
What is a factor?
First things first, right? Not everybody defines the word “factor” the same way. I will be using the convention used in most local contests: A factor of an integer $n$ is a positive integer $a$ for which there exists an integer $b$ such that $n=ab$. So by our convention $4$ and $-4$ both have exactly three factors: 1, 2, and 4. We do not consider $-2$ as a factor, even if it divides both $4$ and $-4$. On the other hand, a factor of a number is a proper factor iff it is not the number itself. Often 1 is also not considered a proper factor. With this ambiguity, however, the term is not used too often in contests.The Technique
QUESTION 1
Find the sum of the factors of $2^{2013}\times3^{3015}\times5^{23}$.
Find the sum of the factors of $2^{2013}\times3^{3015}\times5^{23}$.
I intentionally picked a huge number so it's impossible to solve this by brute force. First, let's solve a simpler problem.
HELPER QUESTION 1.1
Find the number of factors of $n=2^{2013}\times3^{3015}\times5^{23}$.
Find the number of factors of $n=2^{2013}\times3^{3015}\times5^{23}$.
A question like this could easily come up in a grade school contest, and here's how we are commonly taught to solve it.
SOLUTION, HELPER QUESTION 1.1
Get the prime factorization, add 1 to each exponent, then multiply: we have $$(2013+1)\times(3015+1)\times(23+1)=\boxed{145781376}$$
Get the prime factorization, add 1 to each exponent, then multiply: we have $$(2013+1)\times(3015+1)\times(23+1)=\boxed{145781376}$$
This is a very easy formula to find the answer. Grade schoolers who have grown to prefer idea-picking over nose-picking would already have asked the important question: Why/how does this formula work?
Usually the explanation offered is a combinatorial one. We start out with the important idea that every factor of $n$ has different amounts of the prime factors of $n$, but no new prime factors. In our example, that means 17 will never divide a factor. All factors are of the form $2^{a}\times3^{b}\times5^{c}$, where $0\le a\le2013$, $0\le b\le3015$, and $0\le c\le23$. So you have 2014 choices for $a$, 3016 choices for $b$, and 24 choices for $c$. Then by something we call the Fundamental Principle of Counting, we can just multiply these three numbers to get the answer.
Now, can we take a closer look at what's happening when we're multiplying? Well, yes: \[2014\times3016\times24=\underbrace{\left(1+1+\cdots+1\right)}_{2014\text{ ones}}\times\underbrace{\left(1+1+\cdots+1\right)}_{3015\text{ ones}}\times\underbrace{\left(1+1+\cdots+1\right)}_{24\text{ ones}}= \underbrace{1\times1\times1+1\times1\times1+\cdots+1\times1\times1}_{145781376\text{ ones}} \]You're probably asking: what's the point? Well, if we look at the fully expanded form, we note that there's one term of $1\times1\times1$ for each and every factor of $n$, and the first 1 comes from 2014, the second 1 comes from 3015, and the third 1 comes from 24. So now there arises a natural way of attacking our original problem: why don't we replace the ones by the actual powers themselves (see note):
SOLUTION, QUESTION 1
Each factor is the product of a pure power of 2 with exponent from 0 to 2013, a pure power of 3 with exponent from 0 to 3015, and a pure power of 5 with exponent from 0 to 23. So the sum of these factors must be\[\left(2^{0}+2^{1}+\cdots+2^{2013}\right)\times\left(3^{0}+3^{1}+\cdots+3^{3015}\right)\times\left(5^{0}+5^{1}+\cdots5^{23}\right) \]
Each factor is the product of a pure power of 2 with exponent from 0 to 2013, a pure power of 3 with exponent from 0 to 3015, and a pure power of 5 with exponent from 0 to 23. So the sum of these factors must be\[\left(2^{0}+2^{1}+\cdots+2^{2013}\right)\times\left(3^{0}+3^{1}+\cdots+3^{3015}\right)\times\left(5^{0}+5^{1}+\cdots5^{23}\right) \]
If we fully expand this out, we'll again have 145781376 terms, and each term is precisely one of the 145781376 factors of $n$. So we simply evaluate this. It should be apparent by now that it's pointless to give the full version of the final answer.
NOTE: CARTESIAN PRODUCTS
In the language of higher math, this is intimately connected to the Cartesian product. Essentially, given the the three sets $A=\left\{ 2^{a}|0\le a\le2013\right\}$, $B=\left\{ 3^{b}|0\le b\le3015\right\}$, $C=\left\{ 5^{c}|0\le c\le23\right\}$, the former expression has one $1\times1\times1$ for each element of $A\times B\times C$. The latter expression will have the products of the entries of each element of $A\times B\times C$.
In the language of higher math, this is intimately connected to the Cartesian product. Essentially, given the the three sets $A=\left\{ 2^{a}|0\le a\le2013\right\}$, $B=\left\{ 3^{b}|0\le b\le3015\right\}$, $C=\left\{ 5^{c}|0\le c\le23\right\}$, the former expression has one $1\times1\times1$ for each element of $A\times B\times C$. The latter expression will have the products of the entries of each element of $A\times B\times C$.
Now, I pose the question: Can we make it better? Well, let's recall the formula of the sum of a finite geometric series: \begin{eqnarray*}\sum_{i=0}^{n}ar^{i} & = & a+ar+\cdots+ar^{n}\\ & = & a\frac{r^{n+1}-1}{r-1}\end{eqnarray*}
We simply apply this to each of the factors and we get \[\frac{2^{2014}-1}{1}\times\frac{3^{3016}-1}{2}\times\frac{5^{24}-1}{4}\approx1.394\times10^{2061}\]
Extensions
Okay, this part approaches [Difficulty 4]. Our leveraging of the distributive property of multiplication here is echoed in a more advanced technique called generating functions (the most famous class of generating function, and arguably the one closest to real-life application, is the moment generating function $M_X\left(t\right)$ of a random variable.) Here's a very fundamental example:
QUESTION 2
Suppose you can choose up to five apples, six oranges, and four pears in our basket. How many ways are there to pick eleven fruits?
Suppose you can choose up to five apples, six oranges, and four pears in our basket. How many ways are there to pick eleven fruits?
Of course you would do the standard combinatorial strategy of breaking into cases: so if you get $a$ apples, you can get any number$r$ of oranges from 0 to $11-a$, and then any number $p$ of pears from 0 to $11-a-r$. Eventually one will end up with something like:
BORING SOLUTION, QUESTION 2
\[\sum_{a=0}^{5}\,\sum_{r=0}^{11-a}\,\sum_{p=0}^{11-a-r}1=\boxed{18}\]
\[\sum_{a=0}^{5}\,\sum_{r=0}^{11-a}\,\sum_{p=0}^{11-a-r}1=\boxed{18}\]
which is perfectly fine.
But notice that in some ways, what we're doing is similar to the previous problem. A while ago, we picked what exponent 2 has, then what exponent 3 has, then what exponent 5 has. These choices are independent. Then by choosing a way to represent these choices, we make the factor expansion work for us.
So now we're worried about the number of fruits in our cart. We deal with it like this: the apples can be represented with the generating function \[1+x+x^{2}+\cdots+x^{5}\] where the exponent of $x$ is the number of apples added to your cart. Then the oranges can be represented with \(1+x+x^{2}+\cdots+x^{6}\), and the pears with \(1+x+x^{2}+\cdots+x^{4}\). Then when they multiply out, the exponents add, so each term in the product (before combining like terms) represents a decision (of how many of each fruit to buy), and the exponent of $x$ in that term is the number of fruits in your cart.
But that means that after combining like terms, the coefficient of $x^1$ would be the number of ways to buy one fruit, the coefficient of $x^2$ would be the number of ways to buy two fruits, and so on.
COOL SOLUTION, QUESTION 2
Multiply the above generating functions and obtain the coefficient of $x^{11}$:\begin{eqnarray*}\left(1+x+x^{2}+\cdots+x^{5}\right)\left(1+x+x^{2}+\cdots+x^{6}\right)\left(1+x+x^{2}+\cdots+x^{4}\right) & =\\x^{15}+\cdots+18x^{11}+24x^{10}+27x^{9}+\cdots+6x^{2}+1\end{eqnarray*}The coefficient of $x^{11}$ is $\boxed{18}$.
Multiply the above generating functions and obtain the coefficient of $x^{11}$:\begin{eqnarray*}\left(1+x+x^{2}+\cdots+x^{5}\right)\left(1+x+x^{2}+\cdots+x^{6}\right)\left(1+x+x^{2}+\cdots+x^{4}\right) & =\\x^{15}+\cdots+18x^{11}+24x^{10}+27x^{9}+\cdots+6x^{2}+1\end{eqnarray*}The coefficient of $x^{11}$ is $\boxed{18}$.
Note that this isn't really good as a computational aid, as to get 18, we essentially have to do a glorified kind of listing. The generating function is much more impressive in proving problems involving partitions, where it may be difficult to obtain a closed-form expression, and also in problems like the one below (which admittedly are pretty contrived).
QUESTION 3
Apples come in packs of three, oranges come in packs of two. You can buy as many packs of these as you want. Moreover, you can choose to get one watermelon or not, and you can buy up to two coconuts. How many ways can you buy $n$ fruits?
Apples come in packs of three, oranges come in packs of two. You can buy as many packs of these as you want. Moreover, you can choose to get one watermelon or not, and you can buy up to two coconuts. How many ways can you buy $n$ fruits?
SOLUTION, QUESTION 3
Okay, so the generating function for the apples is $1+x^{3}+x^{6}+\cdots$, the one for the oranges is $1+x^{2}+x^{4}+\cdots$, the one for the watermelon is $1+x$ , and the one for the coconuts is $1+x+x^{2}$. So the complete generating function is \begin{eqnarray*}\left(1+x^{3}+x^{6}+\cdots\right)\left(1+x^{2}+x^{4}+\cdots\right)\left(1+x\right)\left(1+x+x^{2}\right) & = &\\ \frac{1}{1-x^{3}}\frac{1}{1-x^{2}}\left(1+x\right)\left(1+x+x^{2}\right)& = & \frac{1}{\left(1+x\right)^{2}}\\& = & 1+x+2x^{2}+3x^{3}+\cdots\end{eqnarray*} which means there are exactly $n$ ways to buy $n$ fruits.
Okay, so the generating function for the apples is $1+x^{3}+x^{6}+\cdots$, the one for the oranges is $1+x^{2}+x^{4}+\cdots$, the one for the watermelon is $1+x$ , and the one for the coconuts is $1+x+x^{2}$. So the complete generating function is \begin{eqnarray*}\left(1+x^{3}+x^{6}+\cdots\right)\left(1+x^{2}+x^{4}+\cdots\right)\left(1+x\right)\left(1+x+x^{2}\right) & = &\\ \frac{1}{1-x^{3}}\frac{1}{1-x^{2}}\left(1+x\right)\left(1+x+x^{2}\right)& = & \frac{1}{\left(1+x\right)^{2}}\\& = & 1+x+2x^{2}+3x^{3}+\cdots\end{eqnarray*} which means there are exactly $n$ ways to buy $n$ fruits.
Note how we have no qualms about the generating function having an infinite amount of terms. This is okay; generating functions are formal power series, meaning they are like polynomials but they can continue forever. Also, we can convert them to closed form without worrying about convergence.
There are some very clever ways we can leverage the generating function, but I'll leave that for when I can make a full post on them. For now, I've got eleven fruits to eat.
Image Credits
"Fruits" by Maciej Lewandowski. Licensed under CC BY-SA 2.0.
No comments:
Post a Comment