[math-fun] I dream in math now.
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
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
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/
It's probably in volume 2, actually. On Tue, Feb 16, 2010 at 11:43 AM, Tom Rokicki <rokicki@gmail.com> wrote:
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 2:37 PM, 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.
Just to fill in the details here, since it didn't seem obvious to me at first: Given a sequence x1,x2,..,x_N, consider the sequence of ordered pairs (I_j, D_j), where I_j and D_j are the lengths of the longest Increasing/Decreasing subsequences of x1,x2,...,x_j ending with x_j. Then the (I_j,D_j) cannot be equal to (I_k, D_k) for j<k, because x_k is either >= or <= x_j, and so can be appended to either an increasing or a decreasing sequence ending with x_j. Now the pigeonhole argument on those pairs says that once you have (n-1)^2+1 terms, you must have some I or D that's n or larger. Dave gave the construction for a seq of length (n-1)^2 that doesn't, so this is done, right? --Michael
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
-- Forewarned is worth an octopus in the bush.
participants (4)
-
Andy Latto -
Dave Blackston -
Michael Kleber -
Tom Rokicki