10
$\begingroup$

Here's a fun math thing:

Imagine building a set of non-negative integers, starting with zero. As you check increasing numbers, you add it to the set if doing so does NOT create a subset of three items in your set that form an equally-spaced series. For example:

0,1,2 is not okay, since 2-1 = 1 and 1-0=1.
0,1,3 is okay since 3-1=2 and 1-0=1.
0,1,3,4 is okay.
0,1,3,4,5 is NOT okay, since 1-3-5 is a 2-step series, and 3,4,5 is a 1-step series (2 fouls).
And so on.

Numbers in between elements in this test don't interfere with it. Imagine the flawed set of:

0,5,6,8,10 (this fails by 0-5-10, even though 6 and 8 are in the way).

So you should not be able to pick ANY three numbers from ANYWHERE in the set that create an illegal triad.

QUESTION 1: Which of the following numbers, if any, would be in the final set?
100?
200?
1,234,887,985,556?
1,024?
2,135?

BIGGER QUESTION: There's a relatively simple way to identify the numbers that would end up in your final set. Can you identify the property/properties they all share, and find a simple way to express them?

$\endgroup$
12
$\begingroup$

A number will be in the set if and only if

its ternary representation consists only of 0s and 1s.

Proof:

We prove by induction on n that n is in the set if and only if n has no twos in its ternary expansion, the base case n = 0 being obvious.

If n has some 2s when written in ternary, then n will be ruled out by the two smaller numbers formed by replacing all these 2s with zeroes and ones, which are in the set by induction. For example, 12023 is ruled by 10003 and 11013.

If n has no 2s, then n will be in the set as long as there do not exist two smaller numbers, a and b, in the set for which (a,b,n) is an equally spaced sequence. This happens only if n = 2b – a. However, the number 2b – a will have a 2 in the first position where a and b have different ternary digits, so this cannot be the case.

How I came up with the rule:

I just started building up the set, marking down the new numbers that were eliminated every time I added a new number. I noticed that the set was made of consecutive blocks of adjacent numbers (0,1), (3,4), (9,10), etc, so I examined every other element of the list. What remained were all multiples of 3, again coming in pairs of adjacent multiples of 3. After eliminating every other number again, it was multiples of 9, and I saw a 27, so that I noticed it has something to do with powers of three. A little more fiddling led to the ternary interpretation.

For the requested cases:

None of the listed numbers are in the set:
100 = 102013
200 = 211023
1,234,887,985,556 = 111010011101101211012221223
1024 = 11012213
2135 = 22210023

$\endgroup$
  • $\begingroup$ For the last paragraph of your proof, 2b-a will always have a 2, but it will not always be in the first position. Ex: 2000-100=1200. As for why 2b-a will always have a 2, it's because it's impossible to add two different 01-only ternary numbers together to get a 02-only ternary number (the only way to get 2000 is 1000+1000, which doesn't work). $\endgroup$ – Geoffrey Nov 3 '17 at 0:16
  • $\begingroup$ @Geoffrey I see, when I said “first,” I should have said “least significant”. For example, the least significant place where b = 1100100 and a = 10100 differ is the fourth digit from the right, and 2b - a = 2120100 has a 2 as it’s fourth digit from the right. $\endgroup$ – Mike Earnest Nov 3 '17 at 4:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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