Classic algebra problem

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

Classic algebra problem

G H J

Reveal topic tags

number theory unsolved

L

G H BBookmark kLocked kLocked NReply

Source: USAMO1994

The post below has been deleted. Click to close.

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

194 posts

#1 h Aug 22, 2005, 10:22 AM • 1 Y

Y by Adventure10

Let $\, k_1 < k_2 < k_3 < \cdots \,$ be positive integers, no two consecutive, and let $\, s_m = k_1 + k_2 + \cdots + k_m \,$ for $\, m = 1,2,3, \ldots \; \;$ . Prove that, for each positive integer $\, n, \,$ the interval $\, [s_n, s_{n+1}) \,$ contains at least one perfect square.

Z K Y

The post below has been deleted. Click to close.

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

203 posts

dblues

#2 h Aug 22, 2005, 1:54 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

We notice that $s_n = k_1 + k_2 + \ldots + k_n \geq 1 + 3 + \ldots + (2n-1) = n^2$ . If $s_n = m^2$ for some $m \in \mathbb{Z}^+$ , then we are done. If not, then letting $r$ be the largest non-negative integer such that ${(n+r)}^2 < s_n$ , we note that the next perfect square ${(n+r+1)}^2$ , which is $2n+2r+1$ greater than ${(n+r)}^2$ . We now claim that this difference $2n+2r+1$ is $\leq k_{n+1}$ . To see this, we suppose not, then we have $2n+2r+1 > k_{n+1} \Rightarrow 2n+2r \geq k_{n+1} \Rightarrow 2n+2r-2 \geq k_n$
$\Rightarrow k_n+k_{n-1} + \ldots + k_1 \leq (2n+2r-2) + (2n+2r-4) + \ldots + 2r = n^2 + 2nr -n$ , which is less than $n^2 + 2nr + r^2 = {(n+r)}^2$ . (Contradiction, since we have assumed that $s_n = k_1 + k_2 + \ldots + k_n > {(n+r)}^2$ .)

Thus ${(n+r+1)}^2 \in [s_n, s_{n+1})$ and we are done.

Z K Y

The post below has been deleted. Click to close.

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

1160 posts

#3 h Aug 23, 2005, 3:54 PM • 2 Y

Y by Adventure10, Mango247

$n(x_{n+1}-1)>=s_n+n^2>=2n\sqrt{s_n}$ so $x_{n+1}>=2\sqrt{s_n}+1$ and $s_{n+1}>=(\sqrt{s_n}+1)^2$ so we get $\sqrt{s_{n+1}}-\sqrt{s_n}>=1$ so the interval contains a square.

Z K Y

The post below has been deleted. Click to close.

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

194 posts

#4 h Sep 1, 2005, 8:59 AM • 2 Y

Y by Adventure10, Mango247

dblues wrote:

Erm... I believe you mean the interval $[sn, s(n+1) )$ , or rather $[s_n, s_{n+1})$ .

The second one

Z K Y

The post below has been deleted. Click to close.

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

203 posts

dblues

#5 h Sep 2, 2005, 4:19 PM • 1 Y

Y by Adventure10

Makaveli wrote:

dblues wrote:

Erm... I believe you mean the interval $[sn, s(n+1) )$ , or rather $[s_n, s_{n+1})$ .

The second one

Well... if i've already solved the problem, it just means i definitely know it's the second one.

You originally wrote $[sn, sn+1)$ without latex, which is not what you mean. I'm just trying to say that even without latex, u should write $[sn, s(n+1) )$ instead, so that we can interpret it as $[s_n, s_{n+1})$ . Best thing is to go latex of course.

Z K Y

The post below has been deleted. Click to close.

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

524 posts

#6 h Apr 13, 2009, 10:12 PM • 2 Y

Y by Adventure10, Mango247

Can't we prove this using the argument that perfect squares have differences of consecutive odds, and the interval with width $s_m$ are larger than these odd numbers (because the base case of the sequence is 1,3,5,7,..., and every other sequence either has the same interval width or a larger one), i.e. proving the base case and then proving that it would work for any case greater than the base case?

Z K Y

The post below has been deleted. Click to close.

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

4854 posts

#7 h Apr 13, 2009, 10:28 PM • 1 Y

Y by Adventure10

that is essentially what dblues did.

Z K Y

The post below has been deleted. Click to close.

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

524 posts

#8 h Apr 13, 2009, 11:19 PM • 2 Y

Y by Adventure10, Mango247

gauss202 wrote:

that is essentially what dblues did.

thanks, i read through his proof once more, and i see it now.

Z K Y

The post below has been deleted. Click to close.

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

1896 posts

#9 h Feb 27, 2010, 11:16 PM • 2 Y

Y by Adventure10, Mango247

Note that $s_{n + 1} - s_n = k_{n + 1} \ge k_{n} + 2$ . Also, $s_n \le k_n + (k_n - 2) + (k_n - 4) + ......$ ( $2$ or $1$ ) $= (\frac {k_n + 1}{2})^2$ if $k_n$ is odd and $\frac {k_n^2 + 2k_n}{4}$ if $k_n$ is even. In either case,
$s_n \le (\frac {k_n + 1}{2})^2$ . But then the greatest possible difference between $s_n$ and the next square number after $s_n$ must be $(\frac {k_n + 3}{2})^2 - (\frac {k_n + 1}{2})^2 = k_n + 2$ , and since the difference between $s_{n + 1}$ and $s_n$ is at least this, there must be a square on the interval $[s_n,s_{n + 1})$ .

Z K Y

The post below has been deleted. Click to close.

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

315 posts

MBGO

#10 h Apr 5, 2012, 8:21 PM • 2 Y

Y by Adventure10, Mango247

Dear Friends

I solved it by Apriority( if I used the right word!)

1.it's also clear that between $K$ and $K'$ which $K\leq K+2$ there is a square.by using what dear dgreenb801 said.

2.we assumed that for integer $m$ , between $s_{m}$ and $s_{m+1}$ there is atleast one square.

3.we'll prove that between $s_{m+1}$ and $s_{m+2}$ there is atleast one square.

4.and it's Done.

also the third step proved by what dear dgreenb801 said.

With Regards.

Z K Y

The post below has been deleted. Click to close.

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

1900 posts

#11 h Dec 30, 2018, 7:19 PM • 1 Y

Y by Adventure10

dgreenb801 wrote:

Note that $s_{n + 1} - s_n = k_{n + 1} \ge k_{n} + 2$ . Also, $s_n \le k_n + (k_n - 2) + (k_n - 4) + ......$ ( $2$ or $1$ ) $= (\frac {k_n + 1}{2})^2$ if $k_n$ is odd and $\frac {k_n^2 + 2k_n}{4}$ if $k_n$ is even. In either case,
$s_n \le (\frac {k_n + 1}{2})^2$ . But then the greatest possible difference between $s_n$ and the next square number after $s_n$ must be $(\frac {k_n + 3}{2})^2 - (\frac {k_n + 1}{2})^2 = k_n + 2$ , and since the difference between $s_{n + 1}$ and $s_n$ is at least this, there must be a square on the interval $[s_n,s_{n + 1})$ .

If $s_{n+1}\le (\frac {k_n + 1}{2})^2$ then your conclusion is incorrect.

Z K Y

The post below has been deleted. Click to close.

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

GeronimoStilton

1521 posts

GeronimoStilton

#12 h Nov 5, 2020, 2:32 PM

Y by

Consider a particular $n$ . Say that $k^2< s_n\le (k+1)^2$ for some integer $k$ . Suppose for contradiction that $[s_n,s_{n+1})$ does not contain at least one perfect square, then $s_{n+1}\le (k+1)^2$ , so $s_{n+1}-s_n=k_{n+1}\le 2k$ . This implies that $s_n$ is at most
$(2k-2)+(2k-4)+\cdots+2 = 2\cdot \frac{k(k-1)}{2} = k(k-1),$ contradiction.

Z K Y

The post below has been deleted. Click to close.

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

4219 posts

#13 h Tuesday at 9:02 PM

Y by

We will do a proof by contradiction, and assume that $[s_n, s_{n+1})$ contains no perfect squares.

Let $s_n=k_1+\dots+k_n=a^2+b$ for some $0<b<2a+1$ .

Then, $s_{n+1}=s_n+k_{n+1}\le (a+1)^2$ , so $k_{n+1}\le 2a+1-b$ .

This means that $s_n=k_1+\dots+k_n\le \sum_{i=1}^{n} (2a+1-b-2i)=n(2a-n-b)$ .

Therefore, $a^2+b\le 2an-n^2-bn$ so $(a-n)^2+b(n+1)\le 0$ .

Since $(a-n)^2\ge 0$ , $b\le 0$ , contradicting our assumption that $0<b<2a+1$ , as desired.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a