sequence (.) eventually becomes constant.

The post below has been deleted. Click to close.

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

N.T.TUAN

3595 posts

N.T.TUAN

#1 h Apr 26, 2007, 5:54 AM • 13 Y

Y by itslumi, Karangy, Adventure10, HWenslawski, megarnie, Mango247, Mango247, and 6 other users

Let $n$ be a positive integer. Define a sequence by setting $a_{1}= n$ and, for each $k > 1$ , letting $a_{k}$ be the unique integer in the range $0\leq a_{k}\leq k-1$ for which $a_{1}+a_{2}+...+a_{k}$ is divisible by $k$ . For instance, when $n = 9$ the obtained sequence is $9,1,2,0,3,3,3,...$ . Prove that for any $n$ the sequence $a_{1},a_{2},...$ eventually becomes constant.

Z K Y

The post below has been deleted. Click to close.

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

t0rajir0u

12167 posts

t0rajir0u

#2 h Apr 26, 2007, 6:01 AM • 4 Y

Y by Adventure10, HWenslawski, rayfish, KhongMinh

$m_{k}= \frac{a_{1}+...+a_{k}}{k}\le \frac{n}{k}+\frac{k-1}{2}$

For sufficiently large $k$ (say, $k = n$ ) we have

$m_{n}= \frac{n+1}{2}\le n$

And

$a_{1}+...+a_{n}+im_{n}= (n+i) m_{n}$

Hence $a_{n+i}= m_{n}, i = 1, 2, ...$ .

Z K Y

The post below has been deleted. Click to close.

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

Rust

5049 posts

Rust

#3 h Apr 26, 2007, 6:13 AM • 2 Y

Y by Adventure10, Mango247

Exactly for $k\ge \sqrt{2n}$ we get $a_{k}=a_{k+1}=...$

Z K Y

The post below has been deleted. Click to close.

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

yankeesrule007

123 posts

yankeesrule007

#4 h Mar 23, 2011, 9:43 PM • 2 Y

Y by Adventure10, Mango247

Not sure if revival of these topics is allowed or not, but I've come up with a solution and wouldn't mind having it evaluated.
Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

phiReKaLk6781

2074 posts

phiReKaLk6781

#5 h Apr 10, 2011, 9:35 PM • 2 Y

Y by Adventure10, Mango247

yankeesrule007 wrote:

By the properties of this sequence, we know that $b_n = n d_n$ for some positive integers $b_n$ and $d_$ for all $k \in \mathbb{N}$ .

Specifically what properties of the sequence did you use to determine that?

Z K Y

The post below has been deleted. Click to close.

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

anchenyao

292 posts

anchenyao

#6 h Sep 25, 2011, 3:38 AM • 1 Y

Y by Adventure10

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

ThinkFlow

1415 posts

ThinkFlow

#7 h Dec 31, 2011, 11:42 PM • 7 Y

Y by v_Enhance, mad, Chandrachur, nmd27082001, guptaamitu1, Adventure10, aidan0626

Even simpler?

Z K Y

The post below has been deleted. Click to close.

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

quantumbyte

547 posts

quantumbyte

#8 h Mar 18, 2012, 4:08 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

In ThinkFlow's solution, why does $b_i$ have to become constant? I am sorry if this is a dumb question.

Z K Y

The post below has been deleted. Click to close.

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

mavropnevma

15142 posts

mavropnevma

#9 h Mar 18, 2012, 7:14 AM • 2 Y

Y by Adventure10 and 1 other user

ThinkFlow wrote:

Let $b_i = \frac{a_1+\cdots +a_i}{i}$ . Because $b_{i+1} = \frac{a_1+\cdots +a_{i}+a_{i+1}}{i+1}< \frac{a_1+\cdots +a_i+i}{i} = b_i+1$ , the sequence $\{b_i\} _{i=1}^\infty$ is nonincreasing.

Because the $b_i$ are positive integers, $b_i$ eventually becomes constant, so $\{a_1+\cdots +a_i\}_{i=1}^\infty$ eventually becomes arithmetic, so $a_i$ becomes constant, as desired.

1. $b_i = \frac{a_1+\cdots +a_i}{i}$ is a positive integer, precisely by the way $a_i$ is chosen;
2. $a_{i+1} \leq (i+1) - 1 = i$ , so $b_{i+1} = \frac{a_1+\cdots +a_i + a_{i+1}}{i+1} \leq$ $\frac{a_1+\cdots +a_i + i}{i+1} <$ $\frac{a_1+\cdots +a_i + i}{i} =$ $\frac{a_1+\cdots +a_i}{i} + 1 = b_i + 1$ ;
3. Since the sequence $(b_i)_{i\geq 1}$ is made of positive integers, from $b_{i+1} < b_i +1$ follows $b_{i+1} \leq b_i$ , hence the sequence is non-increasing;
4. Therefore the sequence $(b_i)_{i\geq 1}$ must become eventually constant, since there are only a finite number of times (namely $b_1=a_1=n$ times) when it may strictly decrease (by at least $1$ at each step).

Z K Y

The post below has been deleted. Click to close.

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

distortedwalrus

193 posts

distortedwalrus

#10 h Feb 9, 2013, 3:50 AM • 1 Y

Y by Adventure10

A little different

Z K Y

The post below has been deleted. Click to close.

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

MMEEvN

252 posts

MMEEvN

#11 h Feb 14, 2013, 9:37 AM • 1 Y

Y by Adventure10

Let us define $S_i= \Sigma a_i$
Consider the number ${D_x= \frac {S_x + \frac{S_x}{x}}{x+1} =\frac{S_x}{x}}$
Since ${\frac{S_x}{x}}$ is an integer $D_x$ is an integer .But since $a_{x+1}$ is the unique integer such that $0 \le a_{x+1} \le x$ and $S_{x+1}$ is divisible by $x+1$
if ${a_{x+1}\not= \frac{S_x}{x}}$ for all x we would have ${{\frac{S_{x+1}}{x+1}}=\frac{S_x+a_{x+1}}{x+1}} >D_x$ .Therefore ${\frac{S_x}{x}} > x (\frac{S_x}{x} also satisfies \frac{S_x+r}{x+1} is an integer)$ for all $x$ . But we can choose sufficiently large $x$ such that ${\frac{S_x}{x}} \le x(since a_x <x)$ Hence for a sufficiently large $x$ we would have ${a_{x+1}= \frac{S_x}{x}}$ Hence ${{\frac{S_x}{x}}=\frac{S_{x+1}}{x+1}} =a_{x+1}$
Now if we proceed by induction we would get ${{\frac{S_{x+i}}{x+i}}=\frac{S_x}{x}}$ for all $i \ge 0((x+i)^2 \ge S_{x+i})$ and this gives the desired result $a_{x+i}= a_{x+1}$ for all $i \ge 0$

Z K Y

The post below has been deleted. Click to close.

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

viperstrike

1198 posts

viperstrike

#12 h Nov 2, 2013, 7:09 PM • 2 Y

Y by Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

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

thecmd999

2860 posts

thecmd999

#13 h Jan 8, 2014, 4:52 AM • 2 Y

Y by Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

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

AnonymousBunny

339 posts

AnonymousBunny

#14 h Nov 21, 2014, 4:04 PM • 4 Y

Y by Delray, Chokechoke, Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

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

bobthesmartypants

4337 posts

bobthesmartypants

#15 h Apr 7, 2016, 1:42 AM • 2 Y

Y by Adventure10, Mango247

my solution

Z K Y

The post below has been deleted. Click to close.

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

chenghaohu

68 posts

chenghaohu

#49 h Jul 8, 2023, 8:56 PM

Y by

I claim that there must exist some k such that a(1) + .... + a(k) is less than k^2 regardless of what you start with. To prove this, assume for the maximization that for each a(i) = i-1 for i≥2. Then this becomes a(1) + (1+...+(k-1)) = k(k-1)/2 + a(1). If you increase k enough then this will be true.

Now define the first k for which this value is true has a(1) + .... + a(k) = ck, for c some positive integer. Then we show that all a(i) afterwards must have a(i) = c. This now becomes an induction problem. For the inductive step, we assume that a(1) + ..... + a(n) = cn for n ≥ k. Then by taking mod n+1, this becomes -c mod n+1. c<n+1< n+1+c, so a(n+1) must be c.

Thus after this k the sequence becomes constant with all terms = c.

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8853 posts

HamstPan38825

#50 h Nov 27, 2023, 5:36 AM

Y by

Pretty funny problem.

Claim. If $a_k = rk \leq k^2$ , then $a_{k+1} = a_{k+2} = \cdots = r$ .

Proof. Note that $r \leq k$ , and $r$ also creates multiples of $i > k$ at every juncture. $\blacksquare$

On the other hand, we must have $a_k < k^2$ at some point, because $a_k < n + 1 + 2 + \cdots + (k-2) = n+\frac{k(k-1)}2.$

Z K Y

The post below has been deleted. Click to close.

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

AlanLG

241 posts

AlanLG

#51 h Jan 24, 2024, 7:38 PM

Y by

nice

Let $S_i=a_1+a_2+\cdots a_n$
Claim. if $m\mid S_m=m\cdot k$ and $0\leq k\leq m$ for some $k$ we are done
Proof:
This is true since in the following steps we may choose $k$ as $m+i\mid S_{m+i}=S_m+ik=mk+ik=k(m+i)$

So note that this would be impossible only if $S_m=mk>m\cdot m=m^2$ for every $m$ . Now
$S_m=a_1+a_2+a_3+\cdots a_m\leq n+1+2+\cdots (m-1)=n+\frac{m(m-1)}{2}$ But $S_m\leq n+\frac{m(m-1)}{2}\leq m^2$ for enough large $m$

Z K Y

The post below has been deleted. Click to close.

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

thdnder

194 posts

thdnder

#52 h Feb 6, 2024, 6:24 AM

Y by

Note that for large $k$ , we have $a_1 + a_2 + \dots + a_k \le a_1 + 1 + 2 + \dots + (k-1) \le a_1 + \frac{k(k-1)}{2} \le k^2$ . Let $s = \frac{a_1 + a_2 + \dots + a_k}{k}$ , then $s \le k$ . Then we get $a_{k+1} = a_{k+2} = \dots = s$ , so we're done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

ihatemath123

3430 posts

ihatemath123

#53 h Jun 29, 2024, 4:01 AM

Y by

If $b_k = \tfrac{a_1 + a_2 + \dots + a_k}{k}$ , then the recurrence for $a_n$ translates to $b_n$ as
$b_k = \left \lceil b_{k-1} \cdot \frac{k-1}{k} \right \rceil,$ so $b_i$ is nonincreasing. It is also bounded below by $0$ , so $b_k$ is eventually constant. When this happens, $a_k$ is also constant, so we are done.

oops my writeup is word for word identical to #45 :skull:

This post has been edited 1 time. Last edited by ihatemath123, Jun 29, 2024, 4:02 AM

Z K Y

The post below has been deleted. Click to close.

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

Bigtaitus

72 posts

Bigtaitus

#54 h Jul 30, 2024, 1:32 AM • 1 Y

Y by Vahe_Arsenyan

Clearly the idea is to define the new sequence $b_k = (a_1 + a_2 + \cdots + a_k)/k$ . Now one can proceed in two diferent ways

Approach 1. Be optimistic and try to show $(b_k)$ is non-increasing.

One can show that $(b_k)$ is not increasing. To do this, notice how $b_{k+1} = \frac{k}{k+1}b_k + \frac{a_k}{k+1} \leq \frac{k}{k+1}(b_k+1) < b_k+1.$ As $b_{k+1}$ is a positive integer this implies that $b_{k+1} \leq b_k$ , implying that $(b_k)$ is eventually constant

Approach 2 Look at differences.

We will look at the values of $b_{k+1} - b_k$ . We will show this is eventually always $0$ . To do this notice that $b_{k+1}-b_{k} = (a_1 + a_2 + \cdots a_k - ka_{k+1})/k(k+1) < (n + 1 + 2 + \cdots + (k-1))/k(k+1) = 1/2 + o(1).$ So for $k$ big enough this must be $0$ , as it is an integer smaller than $1$ . So from a point on $a_1 + a_2 + \cdots + a_k - ka_{k+1} = 0$ , so $a_{k+1}$ must be the average of the $a_i's$ before him, and applying this law from a point on gives us that the $a_i's$ are eventually constant.

Remark It is almost too good to be true that one can show so easily that $(b_k)$ is non-increasing, as it destroys the problem immediately. That is why maybe one overlooks this idea and thinks of Approach 2. In my eyes the problem almost guarantees you that Approach 2 works, as it is telling you that $(b_{k+1} - b_{k})$ is eventually $0$ , so it will take finitely many values before reaching this point, which motivates you to look at its growth.

This post has been edited 3 times. Last edited by Bigtaitus, Jul 30, 2024, 1:39 AM

Z K Y

The post below has been deleted. Click to close.

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

cappucher

88 posts

cappucher

#55 h Aug 14, 2024, 9:37 PM

Y by

Denote $S_{n, k}$ as the $k$ th partial sum for the sequence where $a_1 = n$ ; i.e., $S_{n, k} = a_1 + a_2 + \dots + a_k$ , $a_1 = n$ . From the problem statement, we know that $\forall k$ , $k \mid S_{n, k}$ . This means that for all values of $k$ and $n$ , $S_{n, k}$ can be written as $km$ . We will now show that if there exists $S_{n, k}$ such that $m \leq k$ , the sequence becomes constant.

First, we will demonstrate that $\forall c \in \mathbb{Z}^{+}$ , $a_{k + c} = m$ via induction.

Base Case

In order to find $a_{k + 1}$ such that $k + 1 \mid km + a_{k + 1}$ , we can simply choose $a_{k + 1} = m$ ; this is valid because we are given that $m \leq k$ and $a_{k + 1} \leq k$ . Obviously, $k + 1 \mid m(k + 1)$ .

Inductive Step

We assume that $a_{k + i} = m$ for $i \leq c$ . We can also write $S_{n, k + c}$ as $S_{n, k} + mc$ . Since $S_{n, k} = km$ , we have $S_{n, k + c} = km + mc = m(k + c)$ . Similar to before, in order to find $a_{k + c + 1}$ such that $k + c + 1 \mid m(k + c) + a_{k + c + 1}$ , we have $a_{k + c + 1} = m$ , as desired.

We will now show that $\forall n$ , $\exists k \text{ s.t. } S_{n, k} = km$ for $m \leq k$ . Assume for the sake of contradiction that $\forall k$ , $S_{n, k} = mk$ where $m > k$ . Since $a_{k} \leq k - 1$ , we have a bound of $S_{n, k}$ .

$S_{n, k} \leq n + 1 + 2 + \dots + (k - 1)$ $S_{n, k} \leq n + \frac{k(k - 1)}{2}$ $2S_{n, k} \leq 2n + k(k - 1)$
We now write $S_{n, k} = mk$ (where $m > k$ ):

$2mk \leq 2n + k(k - 1)$ $k(2m - k + 1) \leq 2n$
Since $m > k$ , we know $b \geq k + 1$ ; we are then allowed to plug in $b = k + 1$ into the LHS (as it will simply decrease the value of it).

$k(2(k + 1) - k + 1) \leq 2n$ $k(k + 3) \leq 2n$
But $2n$ is constant, so we just need to find $k$ (which clearly always exists) such that $k(k + 3) > 2n$ . This contradicts our initial assumption that $\exists n \text{ s.t. } \forall k$ , $S_{n, k} = mk$ where $m > k$ .

We can then conclude that $\forall n$ , $\exists k \text{ s.t. } S_{n, k} = km$ for $m \leq k$ , as desired. Since we showed earlier that all $S_{n, k}$ that satisfy the form stated earlier, $a_k$ will eventually become constant $\forall n$ , as desired.

Z K Y

The post below has been deleted. Click to close.

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

SomeonesPenguin

123 posts

SomeonesPenguin

#56 h Aug 15, 2024, 4:49 PM

Y by

Pick a $k>n$ and denote $S=a_1+a_2+\ldots+a_{k-1}$ . Note that $S\le n+\frac{(k-2)(k-1)}{2}$ and $S=(k-1)p$ where $p$ is a natural number. We also have $S+a_k=kq$ where $q$ is a natural number. So we have $kq=S+a_k\le S+k-1=(k-1)p+k-1\iff k(p-q+1)\ge 1+p>0$
So we have $p-q \ge 0$ . On the other hand, we have $kq=S+a_k\ge S=(k-1)p\iff k(p-q)\le p$
Now notice that $p\le \frac{n}{k-1}+\frac{k-2}{2}$ so for $k>n$ we have $p<k$ so we must have $p-q=0$ . So we get $p=q$ for all $k>n$ hence $\frac{a_1+a_2+\ldots+a_k}{k}$ is eventually constant and equal to $p$ from where we easily get that $a_k=p$ for all $k>n$ . $\square$

Z K Y

The post below has been deleted. Click to close.

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

Ywgh1

136 posts

Ywgh1

#57 h Aug 28, 2024, 6:41 PM

Y by

Consider the sequence.

$b_i= \frac{a_1+a_2+\dots +a_i}{i}$
We get that the sequence $(b_i)$ is nonincreasing, hence it will eventually be constant. Implying that $(a_i)$ will also be constant.

This post has been edited 1 time. Last edited by Ywgh1, Aug 28, 2024, 6:43 PM

Z K Y

The post below has been deleted. Click to close.

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

N3bula

254 posts

N3bula

#58 h Sep 21, 2024, 8:36 AM

Y by

Define the sequence $b_1, b_2, \dots$ where $b_i=\frac{a_i}{i}$ , I will prove that $b_i$ is eventually constant, if $b_i\leq i$ then we have that $i+1 \mid ib_i+b_i$ and as
$b_i<i+1$ this is the unique value less than $i$ , so we have that $b_{i+1}=b_i$ and thus the sequence is constant, if $b_i>i$ , then we have that $a_{i+1}=ib_{i}+k$ where $k<b_i$
so we have that $b_{i+1}<b_i$ if $b_i>i$ which suffices.

Z K Y

The post below has been deleted. Click to close.

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

Mr.Sharkman

487 posts

Mr.Sharkman

#59 h Oct 11, 2024, 1:19 AM

Y by

Solution

This post has been edited 1 time. Last edited by Mr.Sharkman, Oct 11, 2024, 1:19 AM

Z K Y

The post below has been deleted. Click to close.

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

Saucepan_man02

1299 posts

Saucepan_man02

#60 h Oct 22, 2024, 12:35 PM

Y by

Let $b_k = \frac{a_1+a_2+\cdots+a_k}{k}$ . Then, notice that: $b_{k+1} = \frac{k b_k+a_{k+1}}{k+1} < \frac{k b_k + k}{k} = b_k+1.$ Thus, the sequence $b_i$ is a non-increasing positive integer sequence, which implies it eventually attains a constant value.

Z K Y

The post below has been deleted. Click to close.

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

Jack_w

103 posts

Jack_w

#61 h Dec 28, 2024, 11:20 PM

Y by

Let $\{b_k\} = a_1 + a_2 + \dots + a_k$ . The sequence $b_k$ jumps up to the nearest multiple of $k$ .

Claim: $\left\{\frac{b_k}{k}\right\}$ is eventually constant.
Note that this sequence starts at $n$ . Suppose $\frac{b_k}{k} > \frac{b_{k-1}}{k-1}$ . Let $b_{k-1} = a(k-1)$ so that $b_k \geq (a+1)k$ . Then $a_k = b_k - b_{k-1} \geq k + a \geq k$ , contradiction.
Therefore, $\left\{\frac{b_k}{k}\right\}$ is a nonincreasing infinite sequence of positive integers. Thus, it is eventually constant.
So, $\{b_k\}$ eventually forms an arithmetic progression, and thus $\{a_k\}$ is eventually constant.

This post has been edited 1 time. Last edited by Jack_w, Dec 28, 2024, 11:21 PM

Z K Y

The post below has been deleted. Click to close.

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

eg4334

602 posts

eg4334

#62 h Jan 18, 2025, 3:29 AM

Y by

Notice that there exists some number $k$ such that the first $k$ terms is less than or equal to $k^2$ . This is because the upper bound on the sum is $n + \frac{k(k+1)}{2}$ which when compared to $k^2$ is small. Let this sum be $s$ . Then, set every other term equal to $\frac{s}{k}$ , which works.

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

792 posts

shendrew7

#63 h Mar 17, 2025, 8:11 PM

Y by

For arbitrarily large $k$ , we have some
$a_1 + \ldots + a_k \leq n + \frac{k(k-1)}{2} < k^2.$
Let $a_1 + \ldots + a_k = nk$ , where $n \leq k$ . But then the next multiple of $k+1$ after $nk$ must be $nk+n$ , so $a_{k+1} = n$ , and analogously all $a_i$ from here equal to $n$ . $\blacksquare$

Z K Y