Competition problem — Algebra — Maths Olympiad Prep

Library / /617 of 860

Algebra Difficulty 5.3 AIME, harder Find the answer

Let $S_{0}=0$ and let $S_{k}$ equal $a_{1}+2 a_{2}+\ldots+k a_{k}$ for $k \geq 1$ . Define $a_{i}$ to be 1 if $S_{i-1}<i$ and -1 if $S_{i-1} \geq i$ . What is the largest $k \leq 2010$ such that $S_{k}=0$ ?

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

Suppose that $S_{N}=0$ for some $N \geq 0$ . Then $a_{N+1}=1$ because $N+1 \geq S_{N}$ . The following table lists the values of $a_{k}$ and $S_{k}$ for a few $k \geq N$ : $k$ & $a_{k}$ & $S_{k}$ \hline $N$ & & 0 \ $N+1$ & 1 & $N+1$ \ $N+2$ & 1 & $2 N+3$ \ $N+3$ & -1 & $N$ \ $N+4$ & 1 & $2 N+4$ \ $N+5$ & -1 & $N-1$ \ $N+6$ & 1 & $2 N+5$ \ $N+7$ & -1 & $N-2$ . We see inductively that, for every $i \geq 1$ , $S_{N+2 i}=2 N+2+i$ and $S_{N+1+2 i}=N+1-i$ thus $S_{3 N+3}=0$ is the next $k$ for which $S_{k}=0$ . The values of $k$ for which $S_{k}=0$ satisfy the recurrence relation $p_{n+1}=3 p_{n}+3$ , and we compute that the first terms of the sequence are $0,3,12,39,120,363,1092$ ; hence 1092 is our answer.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.