I am aware that there are other posts discussing the same proposition. However, I would like to get feedback on my particular solution, which I have not been able to find on the forum. Thank you :)
We can construct a monotone subsequence given any sequence.
We will try to construct two monotone subsequences simultaneously, one increasing and one decreasing. One will be completed, the other will not.
Consider any sequence $(x_n).$
Start the following process with $n = 1$ (the first element in the sequence).
PROCESS: Look at $x_n.$ Either there exists an element $x_{n'}$ later in the sequence that satisfies $x_n \leq x_{n'},$ or there does not.
If there does not exist such an element after $x_n,$ then all elements $x_{n'}$ after $x_n$ satisfy $x_{n'} < x_n.$ Add $x_n$ as the next element in the monotone decreasing sequence. Wipe clean the monotone increasing sequence under construction, and look at $x_{n+1}$ and start over.
If there does exist such an element $x_{n'}$ after $x_n,$ then add the element as the next element in the monotone increasing subsequence. Now, consider $x_{n'},$ and start over.
Notice that if there is a monotone increasing subsequence, then eventually Condition 2 will eventually be everlastingly satisfied and will sequentially construct a monotone increasing subsequence.
If there is no monotone increasing subsequence, every attempt at sequentially constructing a monotone increasing sequence will eventually fail, arriving at an peak element $x_p,$ after which there is no element greater or equal to it (that is, there is no element that appears after it in the sequence that satisfies the monotone increasing condition), and Condition 1 will be satisfied infinitely many times, therein sequentially constructing a monotone decreasing subsequence.
Answer
There's a flaw at this part of the argument:
Notice that if there is a monotone increasing subsequence, then eventually Condition 2 will eventually be everlastingly satisfied and will sequentially construct a monotone increasing subsequence.
Consider this sequence for $n\geq2$:
$$\frac{(-1)^n}{n}=\frac12,-\frac13,\frac14,-\frac15,\frac16,-\frac17,\frac18,-\frac19,\ldots$$
There is a monotonically increasing subsequence: $-\frac13,-\frac15,-\frac17,\ldots$. However, your algorithm fails to find it. Instead, it steps through each value of $n$, wiping clean the increasing sequence under construction at every other step.
I'm not sure whether or not this sort of counterexample completely dooms your "greedy" algorithm, but it's false as stated.
No comments:
Post a Comment