Sequence of integers where no $3$ are in arithmetic progression

Question

I'm having some trouble understanding some parts of this proof. Specifically

1. Why does missing the number $2$ in the ternary system avoid $3$ terms from being in arithmetic progression? I read elsewhere that it was because if you did have $3$ numbers in arithmetic progression then writing those numbers in ternary would give a constant difference, $c$ with the last term being $1$, and this only occurs when the three terms each have last terms $0$, $1$ and $2$. But I was a bit confused with that explanation. Could you explain why a term with $2$ in the ternary representation of a number in the sequence is a sufficient condition for the existence of an arithmetic progression?
2. Where specifically is the "greedy algorithm" applied?
3. And just general clarification on what's going on in this proof would be helpful.

Thanks!

Answer 1

Partial answer to "Why does missing the number 2 in the ternary system avoid 3 terms from being in arithmetic progression? " in detail.

Let $a, a + k, a + 2k$ be three terms in arithmetic sequence.

Let $k_i$ be the first non-zero ternary digit have $k$. Let $a_i$ the corresponding digit of $a$. Then corresponding $i$th digit of $a + k$ and $a + 2k$ are equivalent to $a_i + k_i \mod 3$ and $a_i + 2k_i \mod 3$.

If $k_i = 1$ then $a_i\mod 3, a_i + 1\mod 3, a_i + 2\mod 3$ are three different residues $\mod 3$ so one of them is $2$ (and one of them is $0$ and one of them is $1$.

Likewise if $k_i = 2$ then $a_i \mod 3, a_i + 2\mod 3$, and $a_i + 2*k\equiv a_i + 1 \mod 3$ are also so that one of them is $2$.

So if any three have terms are in arithmetic progression there will be a digit $2$.

Could you explain why a term with 2 in the ternary representation of a number in the sequence is a sufficient condition for the existence of an arithmetic progression?

It is not a sufficient condition for an arithmetic progression; it is a necessary condition. So a lack of a $2$ is a sufficient condition to there not being any arithmetic progressions.

....

So if we list all the numbers that avoid any $2$s in their ternary representation we will get in ternary, the sequence $0, 1, 10,11, 100, 101......$ (which, irrelevantly in decimal, are: $0, 1,3,4,9,10,......$).

No in ternary $100,000_{10} = 12002011201_3$ so we can make this sequence go up to $11111111111_3=88573_{10}$ which has $11111111111_2 = 2047$ terms.

So we can easily make a sequence have $1983$ terms. i.e. then $1983$th term would be $a_{1983_{10}} = a_{11110111111_2} = 11110111111_3=87844$.

So the answer is: Yes, we can do it. $0,1,3,4,9,10,12,13,27,......, 87844$ is such a sequence.

"Where specifically is the "greedy algorithm" applied?"

I'm not entirely sure. But I think the strategy of trying to find the "tightest" sequence is the general idea.