integer sequence, 2 strictly increasing 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

integer sequence, 2 strictly increasing sequences

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2021 Ukraine NMO 10.7

The post below has been deleted. Click to close.

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

30628 posts

#1 h Apr 4, 2021, 5:08 PM

Y by

The sequence $a_1,a_2, ..., a_{2n}$ of integers is such that each number occurs in no more than $n$ times. Prove that there are two strictly increasing sequences of indices $b_1,b_2, ..., b_{n}$ and $c_1,c_2, ..., c_{n}$ are such that every positive integer from the set $\{1,2,...,2n\}$ occurs exactly in one of these two sequences, and for each $1\le i \le n$ is true the condition $a_{b_i} \ne a_{c_i}$
.
(Anton Trygub)

Z K Y

The post below has been deleted. Click to close.

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

239 posts

#2 h Jun 7, 2021, 3:05 PM

Y by

We induct on $n$ . Clearly, $n = 1$ works. So assume that the statement holds for $n = m$ . Let $a_1,a_2,\ldots, a_{2m+2}$ be a sequence of integers.
Suppose some number appears $m + 1$ times. Then we let all $b_i$ 's be the indices corresponding to those numbers and let the $c_i$ 's be all the other indices. This construction clearly works.
Now, suppose each number in $\{a_i\}$ only appear at most $m$ times. Then let $k$ be the smallest index such that $a_k \neq a_1$ . So $a_1 = a_2 = \ldots = a_{k - 1}$ .
Consider the sequence $a_2, a_3,\ldots, a_{k-1}, a_{k+1}, a_{k+2}, \ldots a_{2m + 2}$ with $2m$ terms. By induction, there exist $b_2, b_3, ..., b_{m+1}$ and $c_2, c_3, ..., c_{m+1}$ that satisfy the condition.
Let $b_1 = 1$ and $c_1 = k$ . Since $a_{b_1} \neq a_{c_1}$ , this satisfies the condition. So the statement holds for $n = m + 1$ , and the induction is complete.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a