Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Just wondering what this imo problem is asking(it looks simple but i don't understand what's important in the question) and how to solve:

Suppose that $s_1,s_2,s_3,\ldots$ is a strictly increasing sequence of positive integers such that the subsequences $$s_{s_1}, s_{s_2}, s_{s_3},\ldots\qquad\text{and}\qquad s_{s_1+1}, s_{s_2+1}, s_{s_3+1},\ldots$$ are both arithmetic progressions. Prove that the sequences $s_1,s_2,s_3,\ldots$ is itself an arithmetic progression.

  • Author: Gabriel Carroll, USA
share|improve this question
5  
The problem statement seems clear to me. What precisely do you not understand? –  Chris Eagle Jul 19 '11 at 18:37
1  
And, of course, bothering to write out the problem so people don't have to go hunting for it is not something one should wonder about.... –  Arturo Magidin Jul 19 '11 at 18:38
    
@ chris- i don't really know how to start a induction basis by the given information –  Victor Jul 19 '11 at 18:43
4  
@Victor: If you understand the question, then why does your title and your first sentence claim that you do not understand it? Why invite people to waste their time explaining to you something you understand already by making a false statement about yourself? –  Arturo Magidin Jul 19 '11 at 19:11
4  
@Victor: This is an IMO problem. They are meant to be tricky. Sometimes very tricky. More often than not there is no textbook approach, and some very clever observations need to be made. Nothing too deep though (deep as in requiring university level theory). It is pointless to ask 'which information I need toprove the statement'. The point of the exercise is to figure that out. –  Jyrki Lahtonen Jul 19 '11 at 20:11

1 Answer 1

up vote 1 down vote accepted

Here's one strategy for understanding what the problem is asking. We're supposed to show that a sequence $S_1, S_2, S_3, ...$ is an arithmetic sequence (i.e. $S_2-S_1 = S_3-S_2=S_4-S_3= \;...$) if the sequence satisfies a couple of properties. Given the abstract nature of the properties, let's pick a specific arithmetic sequence and see what these properties are for that sequence. Thus, let's consider the positive integer multiples of 5. That is, let $S_1 = 5$, $S_2 = 10$, $S_3 = 15$, ..., $S_n = 5n$, ... The first property is that $S_{S_1}, \; S_{S_2}, \; S_{S_3}, \; ...$ is an arithmetic sequence. Is this true in our case? Yes, since $S_{S_1} = S_{5} = 25,\;$ $S_{S_2} = S_{10} = 50,\;$ $S_{S_3} = S_{15} = 75,\;$ ..., $S_{S_n} = S_{5n} = 25n,\;$ ..., and clearly the consecutive differences are constant (all equal to 25). The second property is that $S_{S_{1}+1}, \; S_{S_{2}+1}, \; S_{S_{3}+1}, \; ...$ is an arithmetic sequence. Is this also true in our case? Yes, since $S_{S_{1}+1} = S_{5+1} = S_{6} = 30,\;$ $S_{S_{2}+1} = S_{10+1} = S_{11} = 55,\;$ $S_{S_{3}+1} = S_{15+1} = S_{16} = 80,\;$ ..., $S_{S_{n}+1} = S_{5n+1} = 5(5n+1)=25n+5,\;$ ..., and clearly the consecutive differences are constant (also all equal to 25).

At this point you might want to see if you can prove that, for every arithmetic sequence $S_1, S_2, S_3, ...$, both of these properties hold. Basically, what will happen is that if the terms of the sequence $S_1, S_2, S_3, ...$ have a common consecutive difference equal to $d$, then the two properties ask you to investigate subsequences of $S_1, S_2, S_3, ...$ in which you pick every $d$th term, starting with $S_{S_1}$ (first property) and starting with $S_{S_{1}+1}$ (second property). You should be able to see that if the terms of $S_1, S_2, S_3, ...$ are spaced $d$ units apart, then the terms you get by picking every $d$th term of $S_1, S_2, S_3, ...$ will be spaced $d^2$ units apart.

More generally, if you start with an arithmetic sequence and then select terms from this sequence in an "arithmetic sequence" manner (i.e. beginning at some point in the sequence, you select every 3rd term from that point on, or you select every 5th term from that point on, or you select every 12th term from that point on, etc.), the result will be an arithmetic sequence. Note that this can be done in infinitely many ways.

The problem asks us to show that if we only know that each of a certain two of these infinitely many ways of selecting terms in an "arithmetic sequence" manner results in an arithmetic sequence, then the original sequence we started with had to have been an arithmetic sequence.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.