Xvii cono sur [argentina 2006] q3.

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

Xvii cono sur [argentina 2006] q3.

G H J

Reveal topic tags

number theory proposed

L

G H BBookmark kLocked kLocked NReply

Source: Spanish Communities

The post below has been deleted. Click to close.

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

500 posts

#1 h May 11, 2006, 5:08 AM • 2 Y

Y by Adventure10, Mango247

Let $n$ be a natural number. The finite sequence $\alpha$ of positive integer terms, there are $n$ different numbers ( $\alpha$ can have repeated terms). Moreover, if from one from its terms any we subtract 1, we obtain a sequence which has, between its terms, at least $n$ different positive numbers. What's the minimum value of the sum of all the terms of $\alpha$ ?

Z K Y

The post below has been deleted. Click to close.

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

578 posts

#2 h May 11, 2006, 3:35 PM • 2 Y

Y by Adventure10, Mango247

EDIT: misunderstood question.

This post has been edited 1 time. Last edited by Andreas, May 15, 2006, 2:22 PM

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 May 15, 2006, 2:06 PM • 1 Y

Y by Adventure10

Before a solution, I think we can explain better the condition of the problem because it is not very clear...

The idea is: We are given a finite sequence of positive integers. The sequence contains in total $n$ different integers appearing on it, also, if we substract 1 from any of its terms, we get a new sequence which has at least $n$ different integers on it. Whats the minimun sum of the elements of this sequence?

The answer is $n=2k$ , then $f(n)=3k^2+2k-1$ , $n=2k+1$ , then $f(n)=3k^2+5k+1$ . Suppose we have an arbitrary sequence that does the job, and suppose an integer appears more than 2 times on it, clearly, leaving just 2 appearences of this integer, we get a new sequence which does the job, but with smaller sum. Hence in an optimal sequence we have every integer appearing at most 2 times.

Now, if an integer $m$ appears 2 times in the sequence, but $m-1$ doesnt appears, then, removing one $m$ we decrease our sum, and get a sequence that also works (this is trivial

) .

So, suppose we have a working sequence with all transformations we described, and let $a_j$ be the number of $j$ in the sequence.

we get $S=1a_1+2a_2+3a_3...+ma_m$ , now, this sequence will look like subsequences of consecutive terms appearing each two times, conected by sequences of terms with difference 2 among one and the next.
(the smallest term claerly appears only once)

for example, for $n=6$ one possible sequence is:

$1,2,2,4,5,5,7,9$ with sum $35$ .

$1,3,5,7,9,11$ with sum $36$ .

Now, consider the sequence $(a_1,a_2...,a_m)$ , it is build up of blocks that can be like: $1,2,2...,2$ and $0,1,0,1,0...,1,0$ that alternate. Call them $A$ and $B$ blocks. Let $A(x,y)$ and $B(x,y)$ be respectively the sum that $A$ and $B$ sequences give, starting in $x$ and finishing in $y-1$ . We then have:

$S=A(1,n_1)+B(n_1,n_2)+A(n_2,n_3)...$

But we also have that the number of terms in an $A$ sequence starting in $x$ and finishing in $y-1$ is $y-x$ , and similary, in a $B$ sequence we have $\frac{y-x-1}{2}$ integers. The idea is: find expresions for $A(x,y)$ and $B(x,y)$ , and finish with an inequality, I will finish it later

I will finish it in a moment, gotta go to college

Z K Y

The post below has been deleted. Click to close.

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

1160 posts

#4 h May 15, 2006, 3:57 PM • 1 Y

Y by Adventure10

mmmm, new idea, same escenario....

Suppose we have an integer $m$ appearing once, and such that it is less than the middle of $n$ . Then change it for $m-1,m-1$ , and substract one form every term bigger than $m$ , we get a new sequence and the sum decreases, so its not minimal. So in the minimal sum, all terms smaller than or equal to $\frac{n}{2}$ appear exactly 2 times (but 1 only once). Now, let $k$ be the biggest number, which is bigger than the half of $n$ and appears twice, changing it to $m+1$ , and adding $1$ to every bigger term, we get a new sequence with smaller sum. So the sequence with smallest sum must be: $1,2,2,3,3...,k,k,k+2,k+4...,3k-2,3k$ for $n=2k$ and $1,2,2,3,3...,k,k,k+2,k+4...,3k,3k,3k+2$ for $n=2k+1$ .

Z K Y

The post below has been deleted. Click to close.

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

150 posts

#5 h Nov 17, 2020, 4:56 PM

Y by

$1,2,2,4,5,5,7,9$ with sum $35$ .

$1,3,5,7,9,11$ with sum $36$

Make 1 become 0 and it doens't work

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a