RE: Math Challenge

You are viewing a single comment's thread from:

Math Challenge

in math •  7 years ago  (edited)

I solved it!

The answer is: No, the sub-sequence 13579 cannot occur anywhere in this sequence.

Proof:
13579 are odd numbers.

Claim:
There can be no five subsequent odd numbers in the sequence.

Proof:
Suppose there were 5 subsequent odd numbers in the sequence. Consider the sequence modulo 2.
So then there would be a subsequence of the form
abcdef11111

The last digit of a number is odd iff the number itself is odd.

Thus it must hold that

1)a+b+c+d+e+f mod 2 = 1
2)b+c+d+e+f+1 mod 2 = 1
3)c+d+e+f+1+1 mod 2 = 1
4)d+e+f+1+1+1 mod 2 = 1
5)e+f+1+1+1+1 mod 2 = 1

From 1) and 2) follows
(a+b+c+d+e+f)+(b+c+d+e+f+1 )=1+1
=>
a+1=0
=>
a=1

From 2) and 3) follows
(b+c+d+e+f+1)+(c+d+e+f+1+1)=1+1
=>
b=1

And analogously from 3),4) and 4),5) it follows
c=1 and d=1

Plugging a=b=c=d=1 into equation 1) gives:
1+1+1+1+e+f=1
<=>
e+f=1

So either e=1 and f=0
or e=0 and f=1

Now let i be the FIRST index so that a_i a_(i+1) a_(i+2) a_(i+3) a_(i+4)
is a subsequence of 5 odd numbers.
Then 6 numbers abcdef with above properties occur in front of it, i.e
abcdef a_i a_(i+1) a_(i+2) a_(i+3) a_(i+4)
which is
1111ef a_i a_(i+1) a_(i+2) a_(i+3) a_(i+4)
modulo 2

Since i is the FIRST index so that a subsequence of 5 odd numbers start there
f cannot be odd itself, otherwise
f a_i a_(i+1) a_(i+2) a_(i+3) would already be a subsequence of 5 odd numbers starting at the lower index i-1.
And also e cannot be odd, since otherwise
abcde would already be a subsequence of 5 odd numbers starting at a lower index than i.

Therefore there cannot be any subsequence of 5 odd numbers in the sequence at all.

qed

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!