Rainman

That's the solution I had in mind for the problem, well done. I also enjoyed your javascript implementation of the problem.

I agree, just because you make a false statement you are not necessarily lying. You could just be mistaken. But whether you are lying or mistaken about a statement, it is still false. So consider the statement "this statement is false". This paradox can't be so easily sidestepped.

Good and quick solve, it's not possible to evacuate the area.

An amoeba is sitting on the bottom left square (A1) of a chessboard which extends infinitely upwards and to the right. You can make an amoeba split into two. If an amoeba is split into two, its offspring will take the square directly above and the square directly to the right of the parent amoeba. This vacates the square of the parent amoeba. So your first move, splitting the amoeba on A1, will put one amoeba on A2 and one amoeba on B1. An amoeba can only split if both spaces for its offspring are unoccupied. Your objective is for all the amoebas to evacuate the area A1, A2, A3, B1, B2, B3, C1, and C2. (Squares marked with x in drawing below) ........... oooooooo... oooooooo... xxoooooo... xxxooooo... xxxooooo...

And that's the maximum, well done!

Nice improvement, keep going Edit: scratch that, looks like you found the minimum

That's a good start, but it's not the minimum.

What is the maximum number of knights you can place on a regular chess board, so that each square has at most one knight threatening or occupying it? What is the minimum number of knights you can place on a regular chess board, so that each square has at least one knight threatening or occupying it?

Yes, that proves it nicely done! On a side note, I said in an earlier reply that the set of monotone subsequences has Aleph null cardinality. Then I thought about it and realized I spoke to soon. It contains every element in the power set of an infinite subsequence, and so it must have greater than Aleph null cardinality. So there is an uncountably infinite number of monotone subsequences.

Rephrasing it would not be enough, IIRC the lemma was proven using some kind of pigeon hole principle - there are more pairs of indices than there are numbers in the sequence - and the lemma is true for natural numbers. But in the infinite case we can't apply that principle.

Good work so far though I don't want to come off as being rude, and I would love to give credit for a problem solved. It just isn't quite solved yet.

The problem is to show that there is an individual monotone subsequence that is not finite. To show that the set of monotone subsequence is different from the set of natural numbers in that respect. You are right in (almost) every aspect, bonanova. The primes are not bounded, but each individual prime is still finite. The natural numbers are not bounded, but each individual natural number is still finite. The set of monotone subsequences is not bounded, and there is an individual monotone subsequence that is infinite. That last part is what remains to be proven. It is proven that there is no longest finite monotone subsequence, but that doesn't imply that there is an infinitely long monotone subsequence. If it did, that same reasoning would imply that there are infinitely large natural numbers.

The set of natural numbers has Aleph null cardinality, yes. The set of monotone subsequences also has Aleph null cardinality. Which means that there are infinitely many such subsequences. But that's not what I asked you to prove. I asked you to prove that there is a monotone subsequence that is infinitely long, i.e. it does not have a finite length. So far you have only proven that there is a subsequence of any given finite length.

That proves that there are infinitely many primes, not that there is an infinitely large prime. Every prime is of course finite. In the same way, Bushindo has proven that there are infinitely many monotone subsequences, not that there is an infinitely long one.

Maybe my name is Dead Lying Liar. Then if someone asks me, "are you Dead?" or "are you Lying?" or "are you a Liar?", I would have to say yes.

Let me provide a definition for infinite sequence as well, to clear up the countability issue. Infinite sequence: a sequence S satisfying the following conditions. 1) S has a first element P. 2) For each element E, there is a next element E+. 3) Every element in S, except P itself, is a descendant of P. That is, it can be reached by starting at P and going to the next element a certain number of times.

Sorry, you still can't justify that conclusion based on those premises. Let me put it this way. 1) There is a natural number 1. 2) For every natural number K, there is a natural number K+1. Conclusion: there is an infinite natural number. The premises 1 and 2 are correct, but I think we both know there is no infinite natural number. So the conclusion can't be made. Arbitrarily long: for any given natural number K, there is a monotone sub-sequence of length L>K. Proven. Infinitely long: there is a monotone sub-sequence S such that for any given natural number K, S is more than K units long. Not proven. bonanova, regarding countable vs uncountable infinity, my OP is unclear. I am only considering countable infinity.

Sorry, but there is an error in that proof. Assumption ~A does not imply that there is a monotone subsequence with maximum finite length M. Suppose you are standing at a crossroads, with an infinite number of roads leading away from it. Each road is numbered with a unique natural number, and each road is n miles long where n is the number of the road. Whichever of these roads you choose (say road number p), it will eventually end (after p miles), so no road has infinite length. But you could always have chosen another road that is longer (road number p+1 for example). The same thing could be true for these subsequences. You have proven that there is no longest monotone subsequence, but that doesn't imply that there is an infinite monotone subsequence.