K-pop sequences

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

K-pop sequences

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: India EGMO TST 2023/5

The post below has been deleted. Click to close.

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

1184 posts

L567

#1 h Dec 10, 2022, 4:32 PM

Y by

Let $k$ be a positive integer. A sequence of integers $a_1, a_2, \cdots$ is called $k$ -pop if the following holds: for every $n \in \mathbb{N}$ , $a_n$ is equal to the number of distinct elements in the set $\{a_1, \cdots , a_{n+k} \}$ . Determine, as a function of $k$ , how many $k$ -pop sequences there are.

Proposed by Sutanay Bhattacharya

This post has been edited 1 time. Last edited by L567, Dec 10, 2022, 7:00 PM

Z K Y

The post below has been deleted. Click to close.

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

1184 posts

L567

#2 h Dec 10, 2022, 4:37 PM • 1 Y

Y by VicKmath7

First, note that the sequence is non-decreasing. Also, $a_{i+1} - a_i$ must be either $0$ or $1$ , and it depends on whether $a_{i+1+k} - a_{i+k} = 0$ or $1$ .

Define $b_i = a_{i+1} - a_i$ , then the condition means that $b_{i+k} = b_i$ , and so each residue class mod $k$ has a constant value of $b_i$ . Since this is the only constraint, there are $2^k$ ways to choose this.

If the sequence of $b_i$ is determined, $a_1$ is also uniquely determined (it is the number of $1$ 's among the first $k$ $b_i$ + 1), so there are overall exactly $2^k$ sequences. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

1069 posts

gghx

#4 h Mar 5, 2023, 1:53 PM

Y by

Rewrite as $f$ . Obviously $f(n)\le f(n+1)\le f(n)+1$ . Note that if $f(n+1)=f(n)$ then $f(n+1+k)=f(n+k)$ , while if $f(n+1)=f(n)+1$ then $f(n+1+k)=f(n+k)$ . Hence the function is determined by $f(1),f(2),\cdots f(k+1)$ alone. Conversely, if there are $f(1)$ distinct elements amongst them, and $f(i)\le f(i+1)\le f(i)+1$ for all $1\le i\le k$ , then we can construct such a function. Suppose $f(1)=t$ , then we need $t$ "+1"s between adjacent numbers in $f(1)$ to $f(k+1)$ . There are $\binom{k}{t}$ ways to do this. Summing over all $t$ , this gives $2^k$ .

This post has been edited 1 time. Last edited by gghx, Mar 5, 2023, 1:57 PM

Z K Y

The post below has been deleted. Click to close.

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

466 posts

#5 h Jul 22, 2023, 1:38 PM • 2 Y

Y by HoripodoKrishno, whencence

Here is a solution written with every possible motivation I had.

Also, I just totally loved this problem!

The answer if $f(k)=2^k$ .

Note that $a_n\le a_{n+1}\le a_n+1$ as we are just adding one more term into the previous set which is either a new term, or one of the pre-existing ones.

Now note that $a_i$ is the number of distinct elements in $a_1,a_2,\ldots,a_{k+i}$ and that $a_{i+1}$ is the number of distinct elements in $a_1,a_2,\ldots,a_{k+i},a_{k+i+1}.$ So if $a_{i+1}=a_i$ , then both the sequences have the same number of distinct elements, which means $a_{k+i+1}\in\left\{a_1,a_2,\ldots,a_{k+i}\right\}$ . Now using the fact that $a_{k+i+1}in{a_{k+i},a_{k+i}+1}$ we get that this forces $a_{k+i+1}=a_{k+i}$ . Similarly, if $a_{i+1}=a_i+1$ , then we can get $a_{k+i+1}=a_{k+i}+1$ .

Now let $+$ denote the operation $a_i\rightarrow a_{i+1}$ when $a_{i+1}=a_i+1$ and $\square$ denote the operation $a_i\rightarrow a_{i+1}$ when $a_{i+1}=a_i$ . Due to what we derived above, we get that the operation of $a_{k+i}\rightarrow a_{k+i+1}$ is same as that of the operation $a_i\rightarrow a_{i+1}$ . This gives us that if we determine the order of operations on the sequence $\left\{a_1,a_2,\ldots, a_{k+1}\right\}$ , then we automatically get the order of operations on the entire sequence which is described as below.
$\begin{align*} a_1&\rightarrow a_2\rightarrow\cdots\rightarrow a_{k+1}\\ a_{k+1}&\rightarrow a_{k+2}\rightarrow\cdots\rightarrow a_{2k+1} .\end{align*}$

So we just need to determine the sequence $\left\{a_1,a_2,\ldots, a_{k+1}\right\}$ . Let there be $m$ many $+$ operations, and thus $k-m$ many $\square$ operations in the sequence of first $k+1$ numbers; where $0\le m\le k$ . So we get that there are $m+1$ distinct elements in the sequence. But we also had that this value equals $a_1$ , and so $a_1=m+1$ . Thus after picking the ordering of the $+$ and the $\square$ operations, we get the sequence from $a_1$ to $a_{k+1}$ , which on extending further gives us our entire sequence.

Now to finish, we have can select a value for $m$ from $0\le m\le k$ , and then, we will have $\binom{k}{m}$ ways to choose the positions of the $+$ , which sets the position for the rest of the $\square$ operations too. So we get that our final answer is $f(k)=\displaystyle\sum_{m=0}^k \binom{k}{m}=2^k$ and we are done. :stretcher:

:stretcher:

This post has been edited 1 time. Last edited by kamatadu, Jul 22, 2023, 1:39 PM

Z K Y

The post below has been deleted. Click to close.

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

587 posts

#7 h Sep 9, 2023, 6:23 AM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

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

800 posts

#8 h Oct 8, 2023, 8:39 AM

Y by

Wow! Neat bijection. I guess Im getting good C practice before RMO

The answer is $2^k$ . First note that $a_i$ is a non-decreasing sequence due to it's definition. So, $a_{i+1}-a_i=0,1$ if $a_{k+i+1}-a_{k+i}=0,1$ and so if we define $d_i=a_{i+1}-a_i$ , then $d_i$ is periodic with period $k$ . Now what matters is the choice of $d_1,\hdots , d_k$ , which can be chosen in $2^k$ ways, so we are done.

Remark. Many times, what is important with such problems which create strong 'dependencies' is to utilize those 'dependencies' and identify uniquely determined objects. The problem then would be very easy.

Z K Y

The post below has been deleted. Click to close.

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

419 posts

#9 h Apr 10, 2024, 5:33 PM

Y by

We claim that there are exactly $2^k$ such sequences for any $k$ .

Claim: For any positive integer $n$ , we have $a_{n+k+1}-a_{n+k}=a_{n+1}-a_n$ .
Proof. By definition, we have $0\leq a_{n+1}-a_n\leq 1$ . Note that if $a_{n+k+1}=a_{n+k}$ then $a_{n+1}=a_n$ , and if $a_{n+k+1}\ne a_{n+k}$ , then their difference is 1, but then $a_{n+1}-a_n=1$ . So, $a_{n+k+1}-a_{n+k}=a_{n+1}-a_n$ . $\blacksquare$
A simple induction gives $a_{n+tk+1}-a_{n+tk}=a_{n+1}-a_n$ for any $t$ . So, we really just need to ensure that $a_1$ is the number of distinct elements in the set $\{a_1,a_2,\ldots,a_{1+k}\}$ . In this set, call a number $1\leq i\leq k$ good if $a_{i+1}=a_i+1$ and bad otherwise. We have that $a_1=1+\#(\text{good numbers between }1\text{ and }k\text{ inclusive})$ .
This can be done very easily, let there be $g$ good numbers from $1,2,\ldots,k$ . Then, $a_1=1+g$ and choose $g$ good numbers in $\binom{n}{g}$ ways. Hence,
$\#(k-\text{pop sequences})=\sum_{g=0}^{k}\binom kg=2^k,$ as claimed.

Z K Y

The post below has been deleted. Click to close.

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

934 posts

#10 h Dec 17, 2024, 2:22 PM

Y by

Note that $a_{i+1} - a_i \in \{0, 1 \} \forall i$ .
Further, any $k$ -pop sequence must satisfy $a_{i+1} = a_i \iff a_{i+k+1} = a_{i+k}$ . And conversely, all sequences satisfying this and the fact that $a_1 = |\{a_1, \dots, a_{k+1}\}|$ work.
So now we choose $a_{i+1} - a_i$ for $i = 1, 2, \dots, k$ out of $\{0, 1\}$ to get a working $k$ -pop sequence. Since there are $2^k$ ways to do this, the final answer is in fact $\boxed{2^k}$ .

EDIT: WAIT POST #700 LESGOOOOOOOO

This post has been edited 1 time. Last edited by AshAuktober, Dec 17, 2024, 3:11 PM

Z K Y

The post below has been deleted. Click to close.

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

alexanderhamilton124

378 posts

alexanderhamilton124

#11 h Dec 21, 2024, 11:03 AM • 1 Y

Y by L13832

This is a really nice problem

Claim 1: $a_i \leq a_{i + 1} \leq a_i + 1$
Observe that $a_i$ is the number of distinct elements in $\{a_1, \dots, a_{k + i}\}$ , while $a_{i + 1}$ is the number of distinct elements in $\{a_1, \dots, a_{k + i}, a_{k + i + 1}\}$ . Note that $a_{k + i + 1}$ can either add one distinct element or the number of distinct elements remain the same, so our claim is proved.

Claim 2: The sequence is dependent on the selection of $\{a_1, \dots, a_{k + 1}\}$ .
Again, $a_i$ is the number of distinct elements in $\{a_1, \dots, a_{k + i}\}$ , while $a_{i + 1}$ is the number of distinct elements in $\{a_1, \dots, a_{k + i}, a_{k + i + 1}$ . If $a_{i + 1} = a_i$ , then $a_{k + i + 1}$ must not add any distinct element, or $a_{k + i + 1} = a_{k + i}$ . If $a_{i + 1} = a_i + 1$ , then $a_{k + i + 1}$ must add a distinct element, or $a_{k + i + 1} = a_{k + i} + 1$ .

This proves our claim. To finish, note that for each $a_j$ where $j \leq k$ , we can either choose $a_{j + 1} = a_j$ or $a_{j + 1} = a_j + 1$ , and $a_1$ is merely the number of pairs $(a_i, a_{i + 1}) + 1$ , where $a_{i + 1} = a_i + 1$ . So there will be $2^k$ selections (dependent on $a_1$ ) for $(a_1, a_2, \dots, a_{k + 1}$ , which means there are $2^k$ sequences.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a