Monday, April 11, 2016

Searching For Simplicity

"Simplify, simplify, simplify."  -- Thoreau  ;-)

I'll start with an old puzzle many or most will know:
25 basketball teams compete in a single-elimination tournament -- as soon as you lose one game you're out of the tournament, and with 25 teams one team will get a bye in the first round. How many games total will be played by the end in order to crown the champion?
Clearly you can reach the correct answer by patiently working out all possible pairings or games and counting up their number; that will take some time... BUT there's a much easier way that gives the answer literally in seconds. It requires a simple insight that cuts through the process and in 'Aha!' fashion let's you see the answer in a moment.  For any who don't know it, I give the answer at the bottom of this post.**

I mention this puzzle as an intro to the post from "Gödel's Last Letter..." that I'm linking to, to launch the week. It starts with chess, then moves to the Reimann Hypothesis and then P vs. NP, while generally wondering out loud about the "easiest possible kinds" of proof or solutions: 

An interesting read. The gist of it is pondering whether there could be simpler, overlooked solutions to some of the exceedingly difficult problems that appear in mathematics... it's like wondering, as folks did for many years, if Fermat could have actually had a simple proof for his "Last Theorem." In most cases, the answer is likely 'no,' but somewhere out there, who knows? What might our human logic be overlooking, or our limited, biased minds be completely missing? The post includes links to a couple of recent "proofs" offered for the Riemann Hypothesis, one of which is relatively simple (or short) -- though a further commenter, "Gentzen," IDs it is a "fake proof," for reasons that exceed my pay grade :-(

 And as long as we're talking about the difficulty of proofs, I'll also point you to this nice, succinct exposition on the Continuum Hypothesis, re-published in Nautilus this weekend (a case where, to this point at least, the only "proof" has been to show that there are no proofs, under current set theory):


** the answer is 24, because in a single elimination tournament of 25 teams there must, by the end, be 24 LOSERS (and one champion) -- and if there are 24 losers, there must be 24 games played. 

No comments: