If you have never seen ProfessorBenjamin's magic trick, wander down to his office in the MathDepartment and ask him to show it to you. He'll happily oblige. Oh yeah, and if you can figure out how it works... Well, don't tell me 'cause that'd ruin it. But congratulations, you're smarter than most people.
Ok...ProfessorSu knows how he does it, and his comments lead me to believe that what I present here may not, in fact, be the way in which Benjamin accomplishes his amazing invisible deck trick. However, it is interesting...don't click the link unless you really mean it [
Has been known to teach single-v, discrete, probability, algebra I, combinatorics, and number theory.
You say ‘God, I don’t want to integrate along that path’. So you decide, ‘I’m gonna change that path.’
So, by all that is sensible...
(While integrating e^(-r^2/2) r dr) And even I can do that integral. <Pause> So what's that integral? (Later, while integrating 1) Even I can do that integral. Really.
Let's all make this mistake together, so we do it right.
Maybe you did induction with k. Ks are for sissies. Real mathematicians use n.
Oh, we're in luck today. We have exactly n students....
Therefore this algorithm is k^(1/4), which is better than the naive algorithm's k^(1/2). But what happens if we want to compute it for all pairs? Then we have another factor of k choose 2, which is like k^2, so we've just blown our wad and are back to where we started.
…and then ed – this sounds like a Viagra ad – and we know what ed is by this formula in a box… (regarding RSA encryption)