An important problem-solving skill - especially for math contests - is figuring out how to frame (or reframe) a situation to make it easier to solve. This course will guide you through the thought processes needed to excel at this problem-solving art.
Consider the problem of finding the sum of all positive factors of Typically, factors are found by creating pairs (or using a factor tree). An inefficient method for summing all the factors would involve finding all these pairs, and then summing them together:
However, there is a more efficient way of finding the factors by using the prime factorization There are only two prime factors, so we can list all of the factors with a multiplication grid:
The sum of all the factors of is just the sum of all the numbers in this grid, and there happens to be a quick way to add all these numbers together. Using this, what is the sum of all of the positive factors of
To find the sum of the factors of a number with more than two prime factors, we can't make a grid of factors, but we can extend the same idea to more dimensions.
What is the sum of the positive factors of
The art of reframing a problem is present across all topics. In the next few problems, we'll look at an application in Combinatorics: the branch of Discrete Math concerned with counting.
How many ways are there to divide indistinguishable candies among distinguishable friends?
Note that all candies must be distributed, and people can receive candies.
In combinatorics problems, a re-framing can reveal an equivalent set of possibilities that is easier to count.
Consider the previous problem of distributing indistinguishable candies among distinguishable people. This was relatively tedious to count, especially because the people were distinguishable. For example, there are ways to distribute all candies to person, but there are ways to distribute candies to person and candy to a different person.
However, we can re-frame this problem: We put the candies in a line, and separate them into groups with two indistinguishable dividers.
Each different way of placing the dividers gives a different way to distribute the candy. The above example corresponds to the distribution of candies to the first person, candy to the second person, and candies to the third person. Thus, we now have a different, equivalent problem: How many ways are there to place the candies and dividers into a line? It turns out, there is a very simple way to compute this without resorting to casework or tedious counting.
In a fish tank, there are distinct fish. You spread identical food pellets into the tank.
How many different distributions of food pellets among the fish are possible, given that fish can receive pellets and every pellet goes to some fish?
We can generalize the answer from the previous problems. When distributing identical objects to distinguishable bins, it's equivalent to arranging identical objects and identical dividers, so it can be done in ways. However, in problem-solving, it's important to understand the method rather than to memorize the formula.
By doing so, you'll be able to tackle problems that you encounter that you haven't seen before by relating them to what you already know, and making the necessary modifications.
In the next problem, we'll see a slight modification on the previous fish feeding problem.
In a fish tank, there are distinct fish. You spread identical food pellets into the tank. However, you don't want any fish to go hungry, so each fish must receive at least pellet.
How many different distributions of food pellets among the fish are possible?