Choosing signs for sum of squares

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Choosing signs for sum of squares

G H J

Reveal topic tags

number theory proposed

L

G H BBookmark kLocked kLocked NReply

Source: Baltic Way 2009

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1343 posts

jgnr

#1 h Dec 4, 2009, 6:31 AM • 2 Y

Y by Adventure10, Mango247

Let $n$ be a given positive integer. Show that we can choose numbers $c_k\in\{-1,1\}$ ( $i\le k\le n$ ) such that $0\le\sum_{k=1}^nc_k\cdot k^2\le4.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7579 posts

ZetaX

#2 h Dec 4, 2009, 10:31 AM • 2 Y

Y by Adventure10, Mango247

For a polynomial $f$ define $\Delta_c f$ by $(\Delta_c f)(x) : = f(x + c) - f(x)$ . This is a polynomial of degree one less than $f$ (or the $0$ polynomial if $f$ was constant).
Then consider $\Delta_4 \Delta_2 \Delta_1 f$ , it is $0$ . Expanding it gives that it is $(x + 7)^2 - (x + 6)^2 - (x + 5)^2 + (x + 4)^2 - (x + 3)^2 + (x + 2)^2 + (x + 1)^2 - x^2 = 0$ . This reduces the original problem to checking those cases with $n \leq 7$ , which can easily be done.
One couls also use $\Delta_2 \Delta_1 f$ to be $4$ , easily reducing the problem to $n \leq 3$ , making the checking easier.
This also shows that one can replace the square by arbitrary powers $k^n$ if one just changes $4$ into a big enough number (the biggest value occuring in the first $2^{n + 1}$ numbers is the best possible bound, a more general bound is $n! \cdot 2^{\frac {n(n - 1)}{2}}$ or $2^{n^2}$ ).

See also http://www.mathlinks.ro/viewtopic.php?t=30998 for a related problem.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a