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