Archive:
Subtopics:
Comments disabled |
Wed, 01 Sep 2021 A recent Math StackExchange question asks “Prove every permutation of the alphabet contains a subset of six letters in order”. That is, you take a string of length 26 that contains each letter once; you can find a subsequence of six letters that is either increasing or decreasing. Choosing a permutation at random, suppose we have:
Then the sequence
This contains the ascending sequence I thought about this for a while but couldn't make any progress. But OP had said “I know I have to construct a partially ordered set and possibly use Dilworth's Theorem…” so I looked up Dilworth's theorem. It turns out I did actually know Dilworth's theorem. It is about partially-ordered sets. Dilworth's theorem says that if you partition a partially-ordered set into totally-ordered subsets, called ‘chains’, then the number of such chains is at least as big as the size of the largest “antichain”. An antichain is a subset in which no two elements are comparable. This was enough of a hint, and I found the solution pretty quickly after that. Say that S[i] is the position of letter i in the string S. Define the partial order ≺: i≺j≡i<j and S[i]<S[j] That is, i≺j means that i is alphabetically earlier than j and its position in S is to the left of j. This is obviously a partial ordering of the letters of the alphabet. Chains under ≺ are, by definition, ascending sequences of letters from S. It's easy to show that antichains are descending sequences. Partition S into chains. If any chain has length 6 or more, that is an ascending sequence of letters and we win. If not, then no chain has more than 5 letters, and so there must be at least 6 chains, because 5·5=25 and there are 26 letters. Since there are at least 6 chains, Dilworth's theorem tells us there is an antichain of at least 6 letters, and hence a descending sequence of that length, and we win. Once you have the idea to use Dilworth's theorem, the problem collapses. (You also have to invent the right ≺ relation, but there's really only one possible choice.) Maybe I'll write a followup article about how just having a theorem doesn't necessarily mean you have an algorithm. Mathematicians will say “partition S into chains,” but actually programming something like that might be nontrivial. Then finding the antichain among the chains might also be nontrivial. [Other articles in category /math] permanent link |