2
$\begingroup$

These were two of 20 problems I had to do in a test today that I didn't manage to solve.

1) Find the least $k$ such that $1^2 + 2^2 + 3^2 + 4^2 + \dots + k^2$ is a multiple of 200.

2) Find $f(97)$, where $f(n) = \lfloor 2 \sqrt{1 \cdot 2 \cdot 3 + 4 \cdot 5 \cdot 6 + \dots + n(n+1)(n+2)} \rfloor$.

For the first one, I know that:
$$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$

so we have: $\displaystyle\frac{k(k+1)(2k+1)}{6} = 200a$ for some integer $a$. So: $\displaystyle\frac{k(k+1)(2k+1)}{1200} = a$. And then I don't know how to go on...

As for the second one, I don't even know where to start...
We had to do all the problems with pen&paper only (no calculator allowed). Using Python I found that the answer to the first question is 112, but how to reach it?

Thank you,
rubik

  • 0
    For first, $200=8\cdot 25$. We will be dividing by $6$, so we need at least four $2$'s on top. Since $2n+1$ is odd, they will have to come from *one* of $n$ or $n+1$ (they have different parities). So $n$ or $n+1$ is a multiple of $16$, and we need a $25$ from somewhere. This greatly cuts down the search space.2012-01-30
  • 0
    It's probably easier to write it as $k(k+1)(2k+1)=1200a$ and note that $k$, $k+1$, and $2k+1$ are pair-wise relatively prime. Writing $1200=5^2*2^4*3$, then one of $k,k+1,2k+1$ must be divisible by $2^4$, one must be divisible by $5^2$, and one must be divisible by $3$. it could be all the same ones - if $k=1200$, for example. Also, note that since $2k+1$ is odd, it cannot be divisible by $2^4$.2012-01-30
  • 0
    for the second : $$\displaystyle\sum_{i=1}^{\frac{n+2}{3}} (3i-2)(3i-1)3i = \frac{1}{12}n^4 +\frac{5}{6}n^3+\frac{31}{12}n^2+\frac{5}{2}n$$2012-01-30
  • 0
    For the first, I can't see much more other than brute force using the conditions I stated before. You can ignore the issue of which is divisible by $3$, since one is always divisible by $3$, and you can reduce it to $6$ different Chinese remainder problems and get the smallest $n=112$.2012-01-30
  • 0
    @pedja Your formula can be factored as $\frac{n(n+2)(n+3)(n+5)}{12}$2012-01-30

1 Answers 1

1

The smallest value for which $n(n+1)(2n+1)/6$ is divisible by 200 is $n = 112$. In this case, the sum is $$ 112*113*225 = 8*14*113*9*25 = 200*14238.$$ Note that $n=200$ fails.

Now let's look at the second problem. We have $$\sum_{k=1}^n k(k+1)(k+2) = 6 \sum_{k=1}^n {k + 2\choose 3} = 6{n + 3\choose 4} = {n(n + 1)(n+2)(n+3)\over 4}.$$ Hence $f(97) = \lfloor \sqrt{97*98*99*100}\rfloor$ = 9700. This calculation is razor close; floating point error could have thrown it off.

  • 0
    I see. Using $112$, a multiple of $2^4$ but not itself a power of $2$, makes it possible to find a smaller solution than can be found if we insist that $n$ or $n+1$ be a power of $2$. I found $n=2^9=512$ works. I've deleted that answer because that's not the smallest one.2012-01-30
  • 0
    I changed your $200*14238$ to $200\cdot14238$. I've wondered sometimes whether young people are not aware that $*$ is a workaround introduced for use when one is restricted to what's on the keyboard and proper notation like "$\times$" or "$\cdot$" is not available. And before computers, the lower-case "x" was used on typewriters, but that won't do in programming languages where "x" is used for variables, so programming languages are where this substitute notation comes from.2012-01-30
  • 1
    for the second problem you cannot use that formula for sum because there are no terms such as : $2\cdot 3 \cdot 4 , 3\cdot 4 \cdot 5$ , etc.2012-01-30
  • 0
    The poster's second question is confusing because it is, technically, only defined if $n\equiv 1\pmod 3$, since the sum starts $1\cdot 2\cdot 3 + 4\cdot 5\cdot 6 + ...$. It's not clear what he would mean by $f(2)$, for example.2012-01-30
  • 0
    I got sidetracked into dealing with several student questions. I will come back after dinner and complete this.2012-01-30
  • 0
    @MichaelHardy I live in two worlds, math and programming. Hence my usage.2012-01-31
  • 0
    I chose your answer, but there's a typo: for the second problem the answer should be 9700, not 97. Here's why: $\sqrt{97 \cdot 98 \cdot 99 \cdot 100} = \sqrt{97 \cdot (97 + 1) \cdot (100 - 1) \cdot 100} = \sqrt{(97 \cdot 100)^2 - 97^2 \cdot 100 + 97 \cdot 100^2 - 97 \cdot 100} = \sqrt{9700^2 + 97 \cdot 100 (-97 + 100 -1)} = \sqrt{9700^2 + 2 \cdot 9700}$. If under the square root there was a $+1$ we would have had a perfect square ($9701$), since there isn't and we have to compute the floor of it, the answer is $9700$.2012-02-03
  • 0
    Very cool, rubik!2012-02-03