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.

Problem: Is it possible to choose $1983$ distinct positive integers, all less than or equal to $100,000$, no three of which are consecutive terms of an arithmetic progression? (Source: IMO 1983 Q5)

Solution: We construct a set $T$ containing even more than 1983 integers, all less than $10^5$ such that no three are in arithmetic progression, that is, no three satisfy $x+z=2y$. The set $T$ consists of all positive integers whose base $3$ representations have at most $11$ digits, each of which is either $0$ or $1$ (i.e., no $2$'s). There are $2^{11} -1 > 1983$ of them, and the largest is

$$ 11111111111_3=1+3^2+3^3+\cdots+3^{10}=88573<10^5 $$

Now suppose $x+z=2y$ for some $x,y,z\in T$. The number $2y$, for any $y\in T$, consists only of the digits $0$ and $2$. Hence $x$ and $z$ must match digit for digit, and it follows that $x=z=y$. Hence the set $T$ contains no arithmetic progression of length 3, and the desired selection is possible.

My question now is, how do I gain the thinking process to come up with the idea for tacking the problem that yielded the solution above? How can I deduce or intuitively know to use this particular approach of using base $3$ representations come up with a solution to the problem? It seems to me that it requires a great amount of creativity to end up with a method of approach to tackle the problem like that. Would someone be able to explain the motivation behind the solution?

Any thoughts and insights are greatly appreciated.

share|improve this question
4  
You are quit right that «it requires a great amount of creativity to end up with a method of approach to tackle the problem like that». You gain the ability to do that with practice, exposition to similar/connected ideas, more practice, more exposition to similar/connected ideas, and then more practice, and more exposition to similar/connected ideas. In isolation, most ideas appear to require genius—in reality, very few do. –  Mariano Suárez-Alvarez Jan 10 '12 at 3:50
    
When I see any problem containing a number that could represent a year in the late 20th century, I think: "Contest math." Then I think: "The thought process comes from having solved a lot of other contest math problems." I am being slightly facetious here, but my point is that unless you want to compete in the IMO, it is OK if you can't easily do IMO problems. (Many mathematicians can't.) If you do want to compete, then: practice! and don't feel bad about learning from solutions to old problems that you don't quite "get." Study them and you will acquire the techniques by osmosis. –  leslie townes Jan 10 '12 at 4:46
add comment

3 Answers 3

up vote 12 down vote accepted

Suppose you have come to the point where you know that you are looking for a set of numbers which does not contain a triplet $x$, $y$, $z$ such that $x+z=2y$.

If I give you three numbers, how do you check if they do or do not satisfy that equality? Well, the stupidest way is to simply see if $x$ and $z$ add up to $2y$, of course!

Now, if we pick two numbers and actually try to add them, we immediately notice that there is something screwing with us: all the carrying over from one column to the other. So, to avoid that, we only consider numbers $x$ and $z$ such that when we add them there is no carrying, crossing our fingers so that this condition is not too draconian to leave us with too few candidates... (And hey, we got the opportunity to use the word draconian!)

We also need to compute $2y$, so we may just as well —keeping our fingers crossed— assume that when we compute it there is also no carrying over.

If the digits of $x$ are $x_nx_{n-1}\cdots x_0$, and similarly for $y$ and $z$, at this point, the condition that $x+z=2y$ translates into

$x_i+z_i=2y_i$ for all $i\in\{0,\dots,n\}$.

So, what we want is that if the digits of $x$, $y$ and $z$ satisfy this condition, then in fact $x$, $y$ and $z$ cannot be all different. So, if we only allow the digits of out numbers to come from a set $S\subseteq\{0,1,\dots,9\}$, we want that

for all $a$, $b\in S$, then $a+b<10$

so that there is no carrying over when we compute $x+z$, nor when we compute $2y$, and that

if $a$, $b$, $c\in S$ are such that $a+b=2c$, then in fact $a=b=c$.

(This does look like more than what we really need, but I can't think of what we really need... if it does not work, this is were we need to think more...)

So... a little work will show that we can pick $S=\{0, 1, 3, 4\}$. and then it works. Cool!

So we only have to consider all numbers whose digits are drawn from ${0,1,3,4}$ and which are less than $100,000$. Hmm. We think a bit and see that there are too few of these! Damn. In fact, there are 1025 of them.

Start over.

Well... now we have a little idea: what is this obsession with the number $10$. Really. I never wrapped my head with using $A$ and $B$ and so on as digits, so well, I'll try to use another base, but smaller than $10$.

(Hmm, base $2$, the usual suspect, is not going to help here...)

Random pick: let's do base $6$. Our set $S$ of digits will have to be drawn from ${0,1,2}$, because for $3$ already we have carry over when doubling. Hm. The sets $S$ we can construct have at most $2$ elements; for example, $\{0,2\}$ or $\{1,2\}$. Hmm. Thinking a bit shows there are too few numbers smaller than $100000$ using those $6$adic numbers (we of course prefer $\{0,2\}$ to $\{1,2\}$, because it allows us to write smaller numbers, so more numbers). Damn again.

So... Think a bit more... Using base $5$ is not going to help, because the maximal digit is also $2$... Base $4$... Ok. We can take $S=\{0,1\}$, and work, work, work, there are only 512 numbers below $100000$ using only them. Ok, but base $3$ allows us to use the same digits, and obviously there will be more numbers with only those digits. Hmm. Ooooo. $2048$ of them!

We did it :)

share|improve this answer
1  
Why would one think of changing the base? Well, experience. –  Mariano Suárez-Alvarez Jan 10 '12 at 4:40
1  
Draconian is so pedestrian: you could have used Procrustean! (Really nice answer.) –  Brian M. Scott Jan 10 '12 at 5:15
    
@Brian, (I had to check, but those two do not mean quite the same :) ) –  Mariano Suárez-Alvarez Jan 10 '12 at 8:10
    
Going just on the title (i.e. before I saw the limit to numbers less than 100.000) my immediate reaction was that powers of two would work, so there must be some constraint preventing them from being valid. That's another prompt to think of changing the base. –  Peter Taylor Jan 10 '12 at 12:35
    
Sorry, Mariano, I didn’t mean to suggest that they did, just that either would be appropriate (and that one has perhaps even fewer opportunities to use Procrustean). –  Brian M. Scott Jan 11 '12 at 2:12
show 5 more comments

if this is the number line:

ooooooooooooooooooooooooooooooooo...

the first dot represents 1, the next 2, ...

notice there's an arithmetic progression here:

ooooooooooooooooooooooooooooooooo...
^^^

we can initially remove all arithmetic progressions of step 1 by removing every third

oo oo oo oo oo oo oo oo oo oo oo ...
^^^

notice that it doesn't contain any arithmetic progressions of step 2 either! but it does contain an arithmetic progression of size 3:

oo oo oo oo oo oo oo oo oo oo oo ...
^  ^  ^
 ^  ^  ^

so let's remove the third from each of those

oo oo    oo oo    oo oo    oo oo ...

notice that the arithmetic progressions of size 4, 5, 6, 7 and 8 are missing too! The next one we have is:

oo oo    oo oo    oo oo    oo oo ...
^        ^        ^

so we can remove those..

oo oo    oo oo             oo oo ...

I think that was a natural way to approach the problem and after actually doing it for a little while the pattern and connection with base 3 numbers is clear. So the next step is to write it out in mathematical symbols and remove all the scaffolding, that's how you end up back at the proof you posted.

share|improve this answer
1  
This is how I would have done it if I had started from zero, modulo variation, I think. The equation $x+z=2y$ says exactly that for each pair $x$, $z$ we need to remove the middle point, and after turning around the idea this has to bring up the Cantor set and so on. (There is a difference between the continuous case and the discrete case, which makes it interesting) –  Mariano Suárez-Alvarez Jan 10 '12 at 7:43
add comment

Maybe it can be motivated by imagining objects other than integers, and wondering for which kinds of objects and for which rules of addition you can construct such a set. Then once you figure this out, you can devise a scheme to map the solution to integers. That said, I probably wouldn't have been able to figure out the answer.

share|improve this answer
add comment

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.