Order from Chaos (the math bit) - Numberphile

More links & stuff in full description below ↓↓↓

NUMBERPHILE

Videos by Brady Haran

[AlanColon]

Oh Brady, I'm so glad you posted this part.. The first part was so "matter of fact".. Now I feel like I learned something :)

[TheGamer]

This is actually a very, very smart application of the Dirichlet (pigeonhole) principle. By rephrasing the question in terms of the quantities a and d it becomes how that happens, but it takes only a genius like Erdös to think of something like this.

[Tfin]

"Proven in 1935... not that long ago" left me wondering how long it took for someone to prove it. So, the theorem is actually named for those who proved it, leading me to believe it was simply an unasked question previously.

[alexpotts]

When you think about it, it really is astonishing that this wasn't discovered sooner. By the end of the nineteenth century, very little "easy" maths (in the sense of maths that can be explained to intelligent people who are not mathematicians) was left still to be done.

[GretgorPooper]

I freaking love Erdös theorems on combinatorics <3

[horvathandras]

Very funny pronunciation of names in the end, but a great interpretation.
Actually, the theorem is more generalized. It says:
For given r, s positive integers, any sequence of distinct real numbers of length at least rs+1 contains a monotonically increasing subsequence of length r or longer, or a monotonically decreasing subsequence of length s or longer.
Greetings from Hungary.

[rakittna]

And now we need a video of Ramsey's theorem... And how these two link up.

[ericvicaria]

I nearly spit out my coffee when it turned out to be Erdos's work. He's everywhere! 

[martixy]

And while we're on the subject of combinatorics - can we get someone to do the mathematics of MASTERMIND? I bet that'd be rather interesting.

[mnkyman]

IMO this should have been part of the first video. The first video really has no substance without this part. This though - this is extremely cool! What a nice little proof of something which at first appears to be very strange.

[iammaxhailme]

I guess Szekerers has an Erdos Number 1...

[KillianDefaoite]

This is a beautiful problem with a surprisingly simple and enlightening solution.

[ajreukgjdi]

so the same can be done with 16 then. to have no greater ascending or descending sequence than 4 arrange as such:

[jamesmurphy]

When Simon draws the diagram, the result is even more intuitive if you use the digits {0, 1, 2} instead of {1, 2, 3}, since suddenly you're just counting in ternary.

[11, 12, 13, 21, 22, 23, 31, 32, 33] becomes [00, 01, 02, 10, 11, 12, 20, 21, 22]

And then the next one must obviously flip over a new digit – it *must* leave the space bounded by the box he draws later.

[Scorsoo]

Maybe a story/video about Paul Erdös, the most active mathematician ever, would be interesting? ;-)

[Makkatya]

Erdős--Szekeres Theorem... nice to see people from Hungary appear:)

[toast_recon]

Reminds me of the Pauli exclusion principle.

[Dyslexic-Artist-Theory-on-Time]

You need symmetry or a process of symmetry forming and breaking to start with to have chaos and order!

[HeraldoS]

Woo... Increadible... And I suppose it would be also a generalization that for any sequence of n^2+n+1 different real numbers there would be at least one ascending and one descending subsequence of n+1 numbers.

[largenewbragle]

You can actually prove that for n*m+1 different real numbers, you can always find either a decreasing sequence of m+1 elements or an increasing sequence of n+1 elements. The proof uses the pigeon hole-principle and is pretty neat. :)