Olympiad problem
Is it possible to choose 1983 distinct positive integers, all less than or equal to 1 0 5 , no three of which are consecutive terms of an arithmetic progression ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
Moderator note:
Great question. We can generalize the lemma, where for any prime p , an AP with p terms written in base ≤ p will consist of all of the digits.
The proof of the lemma seems rigorous to me. What are your concerns?
Log in to reply
The part whose proof I skipped, of course.
Log in to reply
Eh, I think it's self-evident.
I know I'm like 2.5 years late, but for anyone wondering;
Let the arithmetic progression be a , a + d ⋅ p n , a + 2 d ⋅ p n , … , a + ( p − 1 ) ⋅ d ⋅ p n , where p ∤ d .
With this notation, the rightmost digit that changes is the n + 1 st from the right. Assuming any two of the numbers, say a k = a + k ⋅ d ⋅ p n and a l = a + l ⋅ d ⋅ p n , k > l , share said digit; then p n + 1 ∣ ( a k − a l ) ⟹ p n + 1 ∣ ( k − l ) ⋅ p n , contradiction.
Take the first ,second,fourth and fifth of every 9 consecutive integers ,it satisfies the condition.
The easiest way to do this is to notice that prime numbers cannot belong to a single arithmetic progression and to calculate the number of prime numbers not greater than 100000, which is 100000/ln(100000) ≈ 8686 > 1981
This solution is wrong. For example, 3 , 5 , 7 are three terms forming an arithmetic progression, and so as 5 , 1 1 , 1 7 .
What you are telling is not correct as it is clearly mentioned that no three consecutive terms must form an AP while 3,5,7 does form . You are considering the whole sequence as not an AP....hope u got it
The answer is yes . To do this, we first need a lemma:
Lemma 1 : Suppose three natural numbers form an arithmetic progression. Then, in base three , at least one of the numbers have the digit 2. For example, 1 3 , 2 8 , 4 3 forms an arithmetic progression, and they are 1 1 1 3 , 1 0 0 1 3 , 1 1 2 1 3 in ternary; there's that digit 2.
Proof : It's not fully rigorous yet, but the idea is to notice the rightmost digit that changes. For example, in the above, the rightmost digit that changes is the second digit. You can prove that said digit will be different in all three numbers, which means, because there are only three digits in ternary, one of them must be a 2.
Now, we use the contraposition of the above lemma. If three numbers form an arithmetic progression, one of them has a 2 in ternary. Thus if none of our numbers has a 2 in ternary, no three of them would form an arithmetic progression.
How many such numbers are there? Natural numbers in ternary that don't contain a 2 are simply 1 3 , 1 0 3 , 1 1 3 , 1 0 0 3 , 1 0 1 3 , 1 1 0 3 , 1 1 1 3 , … ; for a given n , there are 2 n − 1 natural numbers of at most n ternary digits that don't have a 2. The largest of these is 1 1 1 … 1 3 with n ones, which is equal to 2 3 n − 1 . We plug in n = 1 1 and find that we have 2047 such natural numbers, the largest of them being 88573. (We choose n = 1 1 because that's when 2 n − 1 ≥ 1 9 8 1 .) Thus not only we have enough; we have a few more.