Competition problem — Algebra — Maths Olympiad Prep

Library / /219 of 377

Algebra Difficulty 5.2 AIME, harder Prove it United States

Problem:
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$ ?

Solution

Solution:
Answer: 1092

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}$
$N$		0
$N+1$	1	$N+1$
$N+2$	1	$2N+3$
$N+3$	-1	$N$
$N+4$	1	$2N+4$
$N+5$	-1	$N-1$
$N+6$	1	$2N+5$
$N+7$	-1	$N-2$

We see inductively that, for every

i \geq 1

S_{N+2i} = 2N + 2 + i

and

S_{N+1+2i} = N + 1 - i

thus

S_{3N+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}=3p_{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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.