I believe this is correct. Knuth goes into this at length in the first volume of The Art of Computer Programming, when he discusses the bijection between permutations and pairs of Young tableaux. On Tue, Feb 16, 2010 at 11:37 AM, Dave Blackston <hyperdex@gmail.com> wrote:
On Tue, Feb 16, 2010 at 11:26 AM, Andy Latto <andy.latto@pobox.com> wrote:
So apparently I dream math problems now.
Let f(n) be the smallest number such that what ever order you arrange the numbers from 1 to f(n) in, there is either an increasing subsequence or a decreasing subsequence of length n.
What is f(n)?
(JB, it seems unlikely that you care about this in real life, but in my dream, it was very important to you, for some practical application, to know that f(n) < n^2. You couldn't prove it though, and I said I would help.)
f(1) = 1 f(2) = 2 f(3) = 4
Andy
What is the increasing/decreasing subsequence of length 3 in 3, 1, 4, 2?
Off the top of my head, I would guess that f(n) = (n-1)^2 + 1. A pigeonhole argument shows that f(n)<=(n-1)^2+1. To show that f(n)>(n-1)^2, arrange the numbers from 1 to (n-1)^2 in an n-1 x n-1 matrix starting at the lower left corner and moving to the right and up and then read the columns in order in a top-down fashion... For example...
7 8 9 4 5 6 1 2 3
7 4 1 8 5 2 9 6 3
This should produce a permutation of 1 - (n-1)^2 with no increasing.decreasing subsequences of length n.
Dave
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/