Sets of Consecutive Positive Integers With Sum k (2006 AMC 12A #8)

2006 AMC 12A #8

Problem: How many sets of two or more consecutive positive integers have a sum of 15?

Solution: It is simple to see there are 3 total ways: {1, 2, 3, 4, 5} | {4, 5, 6} | {7, 8}.

But why? Is there a way to generalize this?

Yes! The number of sets of two or more positive integers that have a sum of k is equal to the number of positive odd divisors of k excluding 1.

Let's break this down with an example. Take 369 = 3^2 * 41. From above, we have 5 ways.

To find such sets, we take the factors of 369 and let them be our median of the set. Then, (regardless if any of the integers in the set are negative) we have a feasible set.

First, 123 will be our median. Our set is: {122, 123, 124}. This set has 3 numbers and needs no manipulation.

Next, our median equals 41. Our set becomes longer: {37, 38, 39, 40, 41, 42, 43, 44, 45}. This also doesn't require manipulation.

Now, we have 9 as our median. Our set is then: {-11, -10 , -9, ... 9, 10, 11, ... 29}. However, this set has negative numbers which we don't want. So after canceling the positive and negative numbers, we get: {12, 13, 14, ..., 27, 28, 29} which has 18 = 2*9 values.

Let's take 3 as the median. Our set is: {-58, ..., 3, ..., 64}. But as we can see, the negative numbers cancel out the positive ones to leave us with the set: {59, 60, 61, 62, 63, 64}, which add up to 369. Note that this set has 6 = 2*3 numbers.

Lastly, we have 1 to be a median. This is the set: {-183, ..., 1, ... 185} --> {184, 185} which has 2 = 2*1 numbers.

Now we see that there are indeed 5 ways to express 369 as the sum of 2 or more consecutive positive integers. (369 cannot be a median or else there will only be 1 integer in the set.) But how can we be sure?

Well, we first let's look at how we chose our medians. Our medians are all the factors of 369, or x, such that 369/x is an odd integer. This ensures that the sequence of 369/x integers with a median of x will indeed sum to 369 and that all numbers in the sequence are integers. So the x we chose were: 1, 3, 9, 41, 123, (no 369).

When x = 1, 3, 9 (or when 369/(2x) > x), our sequence went into the negatives. This cancelled out the positives to give us 2x numbers in all. But why 2x? Suppose 369/x = y. Then our sequence went from x - (y-1)/2 to x + (y-1)/2 for a total of x + (y-1)/2 - (-(x - (y-1)/2)) = 2x.

On the other hand, when x = 41, 123 (or when 369/2x < x), our sequence did not go into the negatives. This resulted in 369/x numbers with x as the median.

But how do we know we didn't lose any possibilities?

The only other ways to get a possible set is 369/(2n), which gives us n/2 as the median. However, our  369/(2x) > x cases covered those possibilities with 2x numbers total with n = x.

Comments

Post a Comment

Popular posts from this blog

Math Formulas + Facts

Sum of cubes and Difference of Cubes a 3  + b 3  = (a + b) (a 2  − a b + b 2  ) a 3  - b 3  = (a - b) (a 2  + a b + b 2  ) Powers to know 5 7  = 78125 5 6  = 15625 5 5  = 3125 Compound Interest A = P(1+r/n) nt Harmonic Series 1+1/2+1/3+1/4+1/5+1/6...+1/n To estimate sum, take the 2 0  term for 1, then take the next 2 1  terms for 2, then take the next  2 2  terms for 3.... Sums: 2 - up to 1/4 2.5 - up to 1/7 3 - up to 1/11 3.5 - up to 1/19 4 - up to 1/31 4.5 - up to 1/51 5 - up to 1/83 Area of Octogon A = 2(1+√2) a 2 Finding the number sides of a regular polygon when you know the interior angle in degrees 180-x° = 360/n Finding total number of diagonals in a polygon n(n-3)/2
Read more

Discovered New Theorem while solving Chinese Remainder Theorem

I was working through some Chinese Remainder Theorem (CRT) problems today (9/24/22), using a new technique introduced in the UKMT Introduction to Number Theory Book. And I noticed a pattern: 9a \equiv 1 \pmod 7 \rightarrow a = 4 7b \equiv 1 \pmod 9 \rightarrow b = 4 Which is cool. But it continues: 7c \equiv 1 \pmod 5 \rightarrow c = 3 5d \equiv 1 \pmod 7 \rightarrow d = 3 And: 35e \equiv 1 \pmod 33 \rightarrow e = 17 33f \equiv 1 \pmod 35 \rightarrow f = 17 Each modular inverse for these pairs were the same! I formed a conjecture, and proved it as a new theorem: Theorem : The solutions a, b to the modular equivalences (n-1)a \equiv 1 \pmod {n+1} (n+1)b \equiv 1 \pmod {n-1} for positive even integers n satisfy a = b = \frac{n}{2}. Update  (12/25/23): More intuitive understanding of Chinese Remainder Theorem (CRT) process. I was looking back at this post, and realized that I had forgotten how the Chinese Remainder Theorem process ...
Read more

Cyclic Quattrocento (Fall 2021 AMC 12B #24)

Image
Fall 2021 AMC 12B #24 Problem:  Triangle ABC has side lengths AB = 11, BC=24, and CA = 20. The bisector of \angle{BAC} intersects \overline{BC} in point D, and intersects the circumcircle of \triangle{ABC} in point E \ne A. The circumcircle of \triangle{BED} intersects the line AB in points B and F \ne B. What is CF? Solution:  We can create a diagram to try to find unique relationships in this problem. By angle chasing in the cyclic quadrilateral ABEC given that AE is the angle bisector of \angle{BAC} we can find that \angle{BAE} = \angle{CAE} = \angle{BCE} = \angle{CBE}. This means that triangle BCE is isosceles and BE = CE, which may be useful later on. Now, we can focus on CF , which is the length we want to find. We can see that ACF has a cevian CB, so we can use Stewart's Theorem (we will "derive" it with the law of cosines here) to solve for CF in terms of other side lengths. We can let \angle{ABC} = \theta which means...
Read more