## Representations of Number as Sum of Consecutive Integers

October 2nd, 2009

How many ways are there of writing XXXX as a sum of positive consecutive integers?

Interesting Yahoo! Answers thread.

I found this discussion very interesting (after coming upon it after a search due to encountering one of these problems on FTW and failing horribly).

Basically, the result is that the number of ways of writing a number as a sum of consecutive integers is the number of odd divisors of that number, minus one. This is an awesome conclusion.

How many ways are there of writing 123123 as a sum of positive consecutive integers?

$123123 = 3 \cdot 7 \cdot 11 \cdot 13 \cdot 41$

Therefore, the number of factors (all of which must be odd, because there is no factor of $2$ in $123123$) are:

$2^5 = 32 \text{ factors}$

Since there are 32 odd factors of 123123, the number 123123 can be written as a sum of positive consecutive integers in 31 ways.

Each of these ways is one of the odd divisors of 123123 (we subtract 1 because we can’t count the divisor 1 as that would yield only 1 integer, 123123 itself, and we need plural integers anyways).

If we count the even divisors, that will result in some of the divisors being negative. (See thread.)

Ok, lame post, sorry. Guys, do some of the earlier problems, like that staircase one ^_^

## Limits

September 26th, 2009

Question from the tryout:

Find:

$\dfrac{\displaystyle\lim_{x \to 0} \dfrac{\sin \dfrac{x}{5}}{\sin 2x} \cdot \lim_{x \to 3^{-}} \lfloor x \rfloor}{\displaystyle\lim_{x \to 3} \dfrac{x^2 - 9}{x - 3} + \lim_{x \to\infty} \dfrac{3 - 4x^2}{2x^2 + 7}}$

This problem just looks scary, doesn’t it? Well, let’s split up the four limits.

First limit, the top left.

$\displaystyle\lim_{x \to 0} \dfrac{\sin \dfrac{x}{5}}{\sin 2x}$

l’Hôpital it! Bwahaha.

$\displaystyle\lim_{x \to 0} \dfrac{\dfrac{1}{5}\cos \dfrac{x}{5}}{2 \cos 2x} = \dfrac{\dfrac{1}{5}}{2} = \boxed{\dfrac{1}{10}}$

Now for the top right:

$\displaystyle\lim_{x \to 3^{-}} \lfloor x \rfloor$

The limit of the floor function approaching from the negative side is the lower number, so this equals $\boxed{2}$.

Bottom left:

$\displaystyle\lim_{x \to 3} \dfrac{x^2 - 9}{x - 3}$

Indeterminate form (zero over zero), so once again we can use l’Hôpital’s rule on it.

$\displaystyle\lim_{x \to 3} \dfrac{2x}{1} = \boxed{6}$

Last limit is the bottom right one.

$\displaystyle\lim_{x \to\infty} \dfrac{3 - 4x^2}{2x^2 + 7}$

This one is $\frac{\infty}{\infty}$, so once again we must use l’Hôpital’s rule. This time we apply it twice in succession (because I’m not sure whether or not you can just cancel out the $x$s or not since it’s technically dividing by infinity; ask your local calculus teacher).

$\displaystyle\lim_{x \to \infty} \dfrac{-8x}{4x} = - \dfrac{8}{4} = \boxed{-2}$

Now, we put these solved limits back into the original problem:

$\dfrac{\dfrac{1}{10} \cdot 2}{6 + (-2)} = \dfrac{\dfrac{1}{5}}{4} = \boxed{\dfrac{1}{20}}$

Andy? We both fail. XD;

## Exercises

September 24th, 2009

Find the number of ways you can ascend 10 stair steps, if you can make any length step you want except zero.

Simplified version of that problem on the tryout. After this is found, try the actual problem again.

Find the number of ways you can ascend 10 stair steps, if you can only make steps of one or two.

If you want to get more hardcore:

Find the number of ways you can ascend 10 stair steps, if you can climb as many steps at a time as you want, but you can’t climb the same number of steps twice.

(Example allowed sequence: 1, 2, 3, 4. Example not allowed sequence: 2, 2, 4, 4.)

## Recurrences

September 23rd, 2009
In the sequence $2001, 2002, 2003, \ldots$, each term after the third is found by subtracting the previous term from the sum of the two terms that precede that term. For example, the fourth term is $2001 + 2002 - 2003 = 2000$. What is the $2004$th term in this sequence?

I know that nobody cares, but here’s my solution anyways.

This problem defines a linear recurrence $x_n$ such that:

$x_n = x_{n-3} + x_{n-2} - x_{n-1}$

Replacing $x_n$ with a constant in order to find the characteristic polynomial, $\lambda^n = x_n$:

$\lambda^n = \lambda^{n-3} +\lambda^{n-2} - \lambda^{n-1}$

Thus the characteristic polynomial of this linear recurrence is:

$\lambda^n - \lambda^{n-3} -\lambda^{n-2} + \lambda^{n-1} = 0$

Rearrange, and divide by $\lambda^{n-3}$.

$\lambda^3 + \lambda^{2} -\lambda - 1 = 0$

This is our characteristic polynomial. Factoring it:

$(\lambda^3 - 1) + \lambda(\lambda - 1) = 0$

Difference of cubes.

$(\lambda - 1)(\lambda^2 + \lambda + 1) + \lambda(\lambda - 1) = 0$

Combine like terms and factor $\lambda^2 + 2\lambda + 1$.

$(\lambda - 1)(\lambda + 1)^2 = 0$

The roots of the characteristic polynomial are $\{1, -1, -1\}$. The root $-1$ has a multiplicity of two, so the general solution to the recurrence $x_n$ is given by:

$x_n = c_1 \cdot 1^n + \left( d_0 + d_1 n \right) (-1)^n$

We can plug in the initial values given in the problem, $x_1$, $x_2$, $x_3$, and $x_4$ to find the constants.

$2001 = c_1 \cdot 1^1 + \left( d_0 + d_1 \cdot 1 \right) (-1)^1$ $2001 = c_1 - d_0 - d_1$ $2002 = c_1 + d_0 + 2d_1$ $2003 = c_1 - d_0 - 3d_1$

Solving this system of three linear equations gives the following values for $c_1$, $d_0$, and $d_1$:

$c_1 = 2002$ $d_0 = 2$ $d_1 = -1$

Therefore, the formula for the $n$th term of this sequence is given by:

$\boxed{ x_n = 2002 + ( 2 - n ) (-1)^n }$

And, finally, $x_{2004}$ is:

$x_{2004} = 2002 + (-2002)(1)$
$x_{2004} = 2002 - 2002$
$x_{2004} = \boxed{0}$

Hey, Andy, you must have solved it intuitively (instead of actually solving the recurrence and finding the general formula), could ya tell me/us how? =D

## Variation of a previous number theory problem

September 19th, 2009

Lol, just saw this on the math team forum, was posted by like last last year, but anyways…

In the prime factorization of the expression $100! \cdot 99! \cdot 98! \cdot \ldots \cdot 3! \cdot 2! \cdot 1!$ there is a $7^x$ term. Find x.

## K’s Semi-solution to “Hard Problem”

September 19th, 2009

I can’t think well after lunch, so I don’t have the solution. But I know you have to have the travelling times of each individual equal each other. And they have to share the bike. x=distance girl rides on bike, y=distance of boy on bike, z=distance of dog on bike.

$x+y+z = 38$ $16(38-x) + 6x = 15(38-y) + 5y = 10 (38-x) +4z$

I think I’m on the right track ,but if not, well, there’s a reason I’m not trying out for math team. Ok, people are coming over to work on the English project now.

Edit/Ben: You’re thinking on the right track with systems of linear equations, with three variables. However, I don’t see why you set $x+y+z = 38$, because $x+y+z$ is the sum of the time the girl, boy, and dog ride the bike, and that shouldn’t have anything to do with the distance they travel. As for the second equation, why are the three equal?

Continue >.< or leave it to Hanchan when you guys finish with your projects.

Edit/2: On second thought I shouldn’t really barge into your post, I should write a comment ^_^

## Hard Problem

September 19th, 2009

A boy, a girl and a dog go for a 38 mile journey. The girl takes 16 minutes to walk a mile. The boy takes 15 minutes to walk a mile and the dog can trot a mile in 10 minutes. They also have a bicycle which only one of them (including the dog!) can use at a time. When riding, the girl can travel a mile in 6 minutes, the boy can travel a mile in 5 minutes and the dog can pedal a mile in 4 minutes (what a marvelous dog!). What is the shortest time in which all three can complete the trip?

Credit for problem goes to Dr. Kevin Wang (not sure if it’s by him or not).

Good luck. Post solutions as blog post or comment.

## The Racist Coin Problem

September 19th, 2009

Hank has 744 black coins and 527 white coins. He wants to arrange them in stacks of the same kind of coins (since if differently-colored coins are placed together in the same stack, discrimination will eventually result in hate crimes and lynchings). In other words, all coins in a stack are all black or all white. If each stack has the same number of coins, what is the minimum number of stacks needed?

## Number Theory – Solutions

September 18th, 2009

1) Written out in base 10, the number $345!$ ends in how many zeroes?

Each zero in a number represents a factor of 10, or a factor each of five and two.

Therefore, to find the number of zeros after a number, we need to find the number of factors of five and the number of factors of two in $345!$.

How many factors of five are in $345!$?

Simply divide 345 by five.

$\dfrac{345}{5} = 69$

However, we need to count the factors of five squared (25) twice, so we divide again by 25.

$\dfrac{345}{25} = 13$

And finally, let’s not forget the factors of five cubed which need to be counted three times.

$\dfrac{345}{125} = 2$

Summing these together:

$69 + 13 + 2 = \boxed{84}$

Thus there are 84 zeroes after the number $345!$.

2) The product of the 12-digit number $493,\!224,\!762,\!945$ and the 12-digit number $471,\!910,\!894,\!925$ is the 24-digit number $232,\!758,\!139,\!280,\!5A5,\!928,\!554,\!125$. Find the digit $A$.

Did you try to find the digits that affected the value of A and try multiplying things out?

A smarter solution, do this calculation mod 9. It’s called “casting out nines”. Cross out all the nines and all the numbers that add up to nine, etc, and add up the remaining numbers, subtracting nine when needed.

$493,\!224,\!762,\!945 \equiv 3 \mod 9$ $471,\!910,\!894,\!925 \equiv 5 \mod 9$

Therefore,

$493,\!224,\!762,\!945 \cdot 471,\!910,\!894,\!925 \equiv 15 \mod 9$

And

$15 \equiv 6 \mod 9$

The product mod 9 is:

$232,\!758,\!139,\!280,\!5A5,\!928,\!554,\!125 \equiv 2 + A \mod 9$

And since the products are supposed to be equal, they will also be equal mod 9.

$2 + A \equiv 6 \mod 9$ $\boxed{A \equiv 4 \mod 9}$

It’s as simple as that!

## Number Theory

September 18th, 2009

Exercises for Hanchan:
(note to self, move this to private/password protected tomorrow)

1) Written out in base 10, the number $345!$ ends in how many zeroes?

2) The product of the 12-digit number $493,\!224,\!762,\!945$ and the 12-digit number $471,\!910,\!894,\!925$ is the 24-digit number $232,\!758,\!139,\!280,\!5A5,\!928,\!554,\!125$. Find the digit $A$.

Hey, Ben, this is K. Apparently I can edit this. I can also see all your private posts. You should probably fix this.

Fixed. Thanks.