User blueraja - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T16:59:31Z http://mathoverflow.net/feeds/user/2883 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/34790#34790 Answer by BlueRaja for Math puzzles for dinner BlueRaja 2010-08-06T17:53:33Z 2010-08-06T17:53:33Z <p>You have a large pile of ropes and some matches. All you know about the ropes:</p> <ul> <li>Each rope has a different length</li> <li>Each rope burns completely (starting from one end) in exactly 64 minutes</li> <li>Each rope has non-uniform density, meaning it is thicker at some points than others. Consequently, burning half a rope cannot be guaranteed to take 32 minutes.</li> </ul> <p>The goal is to identify when exactly 63 minutes have passed.</p> http://mathoverflow.net/questions/33304/mareys-problem-generating-all-prime-numbers-in-n-1-n-2/33310#33310 Answer by BlueRaja for Marey's problem: Generating all prime numbers in $[n_1,n_2]$ BlueRaja 2010-07-25T18:35:53Z 2010-07-25T18:35:53Z <p>I'm assuming you're asking if we can generate primes in [n<sub>1</sub>, n<sub>2</sub>] without generating the primes before that (using a sieve), to which the answer is, no, nothing aside from testing every number between n<sub>1</sub> and n<sub>2</sub> for primality using something like <a href="http://en.wikipedia.org/wiki/Rabin-Miller" rel="nofollow">Rabin-Miller</a>.</p> <p>Note that this will be significantly slower than sieving unless the numbers are extremely large and the range [n<sub>1</sub>, n<sub>2</sub>] is comparatively small.</p> http://mathoverflow.net/questions/33046/arent-oracle-machines-unsound-concepts/33050#33050 Answer by BlueRaja for Aren't "oracle machines" unsound concepts? BlueRaja 2010-07-23T05:34:49Z 2010-07-23T05:34:49Z <p>I'm not sure about complexity, but they're used all the time in security. You make the oracle able to compute whatever it is you want it to compute in one operation, then show that <em>even if</em> such an oracle existed, your system would still be secure.</p> <p>For example, if I give you an encryption <strong>E<sub>k</sub></strong> <em>(k is the key)</em>, an encrypted message <strong>E<sub>k</sub>(M)</strong> and an oracle who can decrypt any message encrypted with k <em>except</em> for <strong>M</strong>, then, for an ideal encryption, you should be no better off at figuring out what <strong>M</strong> is than if I hadn't even given you an oracle!</p> <p>So basically we get around the problems you mentioned by ignoring them :)</p> http://mathoverflow.net/questions/31448/lower-bounds-in-theoretical-computer-science/31459#31459 Answer by BlueRaja for Lower Bounds in Theoretical Computer Science BlueRaja 2010-07-11T20:43:04Z 2010-07-11T20:43:04Z <p>Many <strong>O(n)</strong> algorithms <em>(sorting array with values in fixed range; searching in unsorted array; MST; finding largest binary-search subtree of a tree)</em> are asymptotically optimal simply by virtue of the fact that every element must be looked at at least once.</p> <p>Also, comparison-search (of a sorted array) is bounded by $\Omega(\log{n})$ for the same reason that comparison-sort is bounded by $\Omega(\log{n!})$</p> <p>For completeness, <strong>O(1)</strong> algorithms are also trivially asymptotically-optimal.</p> http://mathoverflow.net/questions/24913/quick-proofs-of-hard-theorems/31388#31388 Answer by BlueRaja for Quick proofs of hard theorems BlueRaja 2010-07-11T09:59:55Z 2010-07-11T09:59:55Z <p>Most of the problems tackled in introductory calculus courses (tangent lines of and areas under basic curves, volumes and areas of solids of revolution, etc) had to be solved on a case-by-case basis, with some pretty complicated and ingenious proofs; now any undergraduate can solve them in a few lines by rote methodology.</p> http://mathoverflow.net/questions/761/undergraduate-level-math-books/30855#30855 Answer by BlueRaja for Undergraduate Level Math Books BlueRaja 2010-07-07T04:41:29Z 2010-07-07T04:41:29Z <p><a href="http://www.amazon.com/Concrete-Approach-Abstract-advanced-mathematics/dp/048663647X/ref=sr_1_3?ie=UTF8&amp;s=books&amp;qid=1278477374&amp;sr=8-3" rel="nofollow">A Concrete Approach to Abstract Algebra</a> by W. W. Sawyer ($6 on Amazon!)</p> <p>Though it goes a bit slow at times, it is by far the simplest, most intuitive book on Abstract Algebra in existence. Written for the non-mathematician, it does a great job of teaching the subject in simple, easy-to-understand prose. I couldn't put it down!</p> <p>There are also two chapters on linear algebra, leading up to the final chapters, <em>"vectors over fields"</em> and <em>"fields regarded as vector-spaces"</em>.</p> http://mathoverflow.net/questions/9037/how-is-it-that-you-can-guess-if-one-of-a-pair-of-random-numbers-is-larger-with-p/30551#30551 Answer by BlueRaja for How is it that you can guess if one of a pair of random numbers is larger with probability > 1/2? BlueRaja 2010-07-04T20:30:40Z 2010-07-05T04:48:04Z <p>The problem is that there's no way to define a random sample over all the real numbers, where every real number has equal probability of being chosen.</p> <p>See <a href="http://blog.xkcd.com/2010/02/09/math-puzzle/comment-page-1/#comment-17804" rel="nofollow">this related problem and solution</a> by Randall Munroe, the creator of <a href="http://xkcd.com/" rel="nofollow">XKCD</a>.</p> http://mathoverflow.net/questions/29494/pseudo-random-number-generation-algorithms/29548#29548 Answer by BlueRaja for Pseudo-random number generation algorithms BlueRaja 2010-06-25T21:29:40Z 2010-06-27T01:13:08Z <p><a href="http://en.wikipedia.org/wiki/Blum-blum-shub" rel="nofollow">Blum-Blum-Shub</a> was the first (and still most popular) <strong>provably-secure</strong> PRNG (assuming only <a href="http://en.wikipedia.org/wiki/Quadratic_residuosity_problem" rel="nofollow">QRP</a>), despite being <em>incredibly</em> simple. It's very slow compared to non-secure PRNGs, though.</p> http://mathoverflow.net/questions/29545/whitening-a-random-bit-sequence/29558#29558 Answer by BlueRaja for whitening a random bit sequence BlueRaja 2010-06-25T23:04:21Z 2010-06-25T23:04:21Z <p>If your goal is to create an unbiased <em>truly</em> random stream, <a href="http://www.ciphergoth.org/crypto/unbiasing/" rel="nofollow">this page</a> has an algorithm which produces results much faster than the usual technique <em>(the one mentioned by qwerty1793 in the comments above)</em>.</p> <p>However, if your concern is simply real-world cryptographic security, since random generators like the one you describe usually produce unbiased streams <em>very</em> slowly, you are better off whitening your stream once using the usual method and using that to seed a <a href="http://en.wikipedia.org/wiki/Blum_Blum_Shub" rel="nofollow">provably-secure cryptographic PRNG</a>.</p> <p><em>In fact,</em> if you are able to produce your truly-random biased bits as quickly as your PRNG, you could even introduce true randomness to the result by XOR'ing the biased stream with the PRNG output. This works regardless of the stream's bias <em>(due to the fact that random data XOR'ed with non-random data produces random data)</em>.</p> http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29519#29519 Answer by BlueRaja for Math puzzles for dinner BlueRaja 2010-06-25T15:10:01Z 2010-06-25T15:10:01Z <p>Most of us know that, being deterministic, computers cannot generate true <a href="http://en.wikipedia.org/wiki/Pseudorandom_number_generator" rel="nofollow">random numbers</a>.</p> <p>However, let's say you have a box which generates truly random binary numbers, but is biased: it's more likely to generate either a <code>1</code> or a <code>0</code>, but you don't know the exact probabilities, or even which is more likely <em>(both probabilities are > 0 and sum to 1, obviously)</em></p> <p>Can you use this box to create a unbiased random generator of binary numbers?</p> http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29454#29454 Answer by BlueRaja for Math puzzles for dinner BlueRaja 2010-06-25T01:19:04Z 2010-06-25T04:27:44Z <p><strong>Fork in the road 1</strong></p> <p>You're on a path on an island, come to a fork in the road. Both paths lead to villages of natives; the entire village either always tells the truth or always lies <em>(both villages could be truth-telling or lying villages, or one of each)</em>. There are two natives at the fork - they could both be from the same village, or from different villages <em>(so both could be truth-tellers, both liars, or one of each)</em>.</p> <p>One path leads to safety, the other to doom. You're allowed to ask only one question to each native to figure out which path is which.</p> <p>What do you ask?</p> http://mathoverflow.net/questions/8846/proofs-without-words/29459#29459 Answer by BlueRaja for Proofs without words BlueRaja 2010-06-25T02:45:08Z 2010-06-25T02:45:08Z <p>Conway and Soifer tried to set a record for least number of words in a mathematical paper. I've reproduced it here in its entirety.</p> <p><strong>Can n<sup>2</sup> + 1 unit equilateral triangles cover an equilateral triangle of side > n, say n + ε?</strong><br> <sup><em>John H. Conway &amp; Alexander Soifer<br> Princeton University, Mathematics<br> Fine Hall, Princeton, NJ 08544, USA<br> conway@math.princeton.edu asoifer@princeton.edu</em></sup></p> <p>n<sup>2</sup> + 2 can:</p> <p><img src="http://img231.imageshack.us/img231/9329/figure1x.png" alt="alt text"></p> <p><img src="http://img138.imageshack.us/img138/1122/figure2.png" alt="alt text"></p> http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29456#29456 Answer by BlueRaja for Math puzzles for dinner BlueRaja 2010-06-25T01:26:44Z 2010-06-25T01:26:44Z <p><em>Cryptography riddle - that's a branch of mathematics, right? :)</em></p> <p>Jan and Maria have fallen in love (via the internet) and Jan wishes to mail her a ring. Unfortunately, they live in the country of Kleptopia, where anything sent through the mail will be stolen unless it is enclosed in a padlocked box. Jan and Maria each have plenty of padlocks, but none to which the other has a key. How can Jan get the ring safely into Maria’s hands?</p> http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29455#29455 Answer by BlueRaja for Math puzzles for dinner BlueRaja 2010-06-25T01:23:48Z 2010-06-25T01:23:48Z <p><strong>Fork in the road 2</strong></p> <p>You're once again at a fork in the road, and again, one path leads to safety, the other to doom.</p> <p>There are three natives at the fork. One is from a village of truth-tellers, one from a village of liars, one from a village of random answerers. Of course you don't know which is which.</p> <p>Moreover, the natives answer "pish" and "posh" for yes and no, but you don't know which means "yes" and which means "no."</p> <p>You're allowed to ask only two yes-or-no questions, each question being directed at one native.</p> <p>What do you ask?</p> http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29449#29449 Answer by BlueRaja for Math puzzles for dinner BlueRaja 2010-06-25T00:28:52Z 2010-06-25T00:28:52Z <p>Oldie but a goodie (Monty-hall problem): </p> <p>You are on a game show with three doors, behind one of which is a car and behind the other two are goats. You pick door #1. Monty, who knows what’s behind all three doors, reveals that behind door #2 is a goat. Before showing you what you won, Monty asks if you want to switch doors. Should you switch?</p> http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29447#29447 Answer by BlueRaja for Math puzzles for dinner BlueRaja 2010-06-25T00:19:49Z 2010-06-25T00:19:49Z <p>Alice secretly picks two different real numbers by an unknown process and puts them in two (abstract) envelopes. Bob chooses one of the two envelopes randomly (with a fair coin toss), and shows you the number in that envelope. You must now guess whether the number in the other, closed envelope is larger or smaller than the one you’ve seen.</p> <p>Is there a strategy which gives you a better than 50% chance of guessing correctly, no matter what procedure Alice used to pick her numbers?</p> http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29446#29446 Answer by BlueRaja for Math puzzles for dinner BlueRaja 2010-06-25T00:17:41Z 2010-06-25T00:17:41Z <p>Assuming you have unlimited time and cash, is there a strategy that's guaranteed to win at roulette?</p> http://mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics/29444#29444 Answer by BlueRaja for What are the most attractive Turing undecidable problems in mathematics? BlueRaja 2010-06-25T00:12:04Z 2010-06-25T00:12:04Z <p>As a computer scientist, it would be nice to know if a program contains <a href="http://en.wikipedia.org/wiki/Buffer_overflow" rel="nofollow">buffer overflows</a> or <a href="http://en.wikipedia.org/wiki/Deadlock" rel="nofollow">deadlocks</a>.</p> http://mathoverflow.net/questions/12828/inverse-gamma-function/28977#28977 Answer by BlueRaja for Inverse gamma function? BlueRaja 2010-06-21T18:56:27Z 2010-06-21T19:34:19Z <p>David Cantrell gives a good approximation of$\Gamma^{-1}(n)$on <a href="http://mathforum.org/kb/message.jspa?messageID=342551&amp;tstart=0" rel="nofollow">this page</a>.</p> <p>I'll copy the result here in case that page ever goes down:</p> <p><code> k = the positive zero of the digamma function, approximately 1.461632<br> c =$\sqrt{2\pi}/e - \Gamma(k)$, approximately 0.036534<br> L(x) =$\ln((x+c)/\sqrt{2\pi})$<br> W(x) = <a href="http://en.wikipedia.org/wiki/Lambert_W_function" rel="nofollow">Lambert W function</a><br> ApproxInvGamma(x) = L(x) / W(L(x) / e) + 1/2 </code></p> http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/34820#34820 Comment by BlueRaja BlueRaja 2010-08-10T17:32:26Z 2010-08-10T17:32:26Z Jryy whfg gur beqre jr fubj obo gur pneqf nybar tvirf hf 4! = 24 cbffvovyvgvrf. Fvapr gurer ner bayl 48 cbffvovyvgvrf sbe gur svsgu pneq, vs jr pbhyq guebj va nabgure snpgbe bs 2 fbzrubj (cerfhznoyl ol bhe pubvpr bs juvpu bs gur svir pneqf abg gb fubj Obo), jr'q unir n fbyhgvba. http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/29360#29360 Comment by BlueRaja BlueRaja 2010-08-06T21:19:52Z 2010-08-06T21:19:52Z Regardless of hardware, I'd be interested in @Pietro's solution to solving it with four bulbs (assuming it's not just qvssrerapr va urng orgjrra gur guerr 'bss' ohyof, juvpu jbhyq nyybj hf gurbergvpnyyl hayvzvgrq ahzore bs ohyof...) http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/34794#34794 Comment by BlueRaja BlueRaja 2010-08-06T21:14:07Z 2010-08-06T21:14:07Z If 50 have one apple and 49 and one orange, then you can only select 25 bags with apples and 25 bags with oranges, which is not more than half the apples. Are you sure you didn't mean <i>at least half</i> the total number of apples/oranges? http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/33993#33993 Comment by BlueRaja BlueRaja 2010-08-06T21:09:36Z 2010-08-06T21:09:36Z Since the prisoner has infinite tries, he is guaranteed to win <i>eventually</i> by flipping random coins... unless the guard is allowed to be malicious (ie. he doesn't just turn the table randomly)? http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/34790#34790 Comment by BlueRaja BlueRaja 2010-08-06T17:58:48Z 2010-08-06T17:58:48Z Hint: lbh arrq gb ohea frira ebcrf http://mathoverflow.net/questions/33426/string-of-integers-puzzle Comment by BlueRaja BlueRaja 2010-07-26T19:16:30Z 2010-07-26T19:16:30Z SO page: <a href="http://stackoverflow.com/questions/3337620/string-of-integers-puzzle" rel="nofollow" title="string of integers puzzle">stackoverflow.com/questions/3337620/&hellip;</a> http://mathoverflow.net/questions/33304/mareys-problem-generating-all-prime-numbers-in-n-1-n-2/33311#33311 Comment by BlueRaja BlueRaja 2010-07-26T16:29:41Z 2010-07-26T16:29:41Z @Mohammed: The distance between primes is ~ ln(n), so even if you are only looking for the primes between [$2^{50}$,$2^{51}$) ($2^{50}$numbers), you are still looking at many terabytes of space to store all those primes. http://mathoverflow.net/questions/33304/mareys-problem-generating-all-prime-numbers-in-n-1-n-2/33310#33310 Comment by BlueRaja BlueRaja 2010-07-25T23:39:07Z 2010-07-25T23:39:07Z Yes, Rabin-Miller is used in practice in cryptography, usually 100 times to give a probability of failure of$1−1/2^{100}$, which is close enough to certain for practical purposes. However, if this worries you too much, you can of course use something like AKS, which is deterministic. http://mathoverflow.net/questions/33304/mareys-problem-generating-all-prime-numbers-in-n-1-n-2/33308#33308 Comment by BlueRaja BlueRaja 2010-07-25T18:29:05Z 2010-07-25T18:29:05Z That gives you <i>a</i> prime; he is looking for <i>all</i> the primes http://mathoverflow.net/questions/32892/does-anyone-know-a-polynomial-whose-lack-of-roots-cant-be-proved Comment by BlueRaja BlueRaja 2010-07-22T16:51:34Z 2010-07-22T16:51:34Z For those unaware: The site is <a href="http://math.stackexchange.com" rel="nofollow">math.stackexchange.com</a>, and is meant for the kind of questions that would get closed on MO. It is in closed beta, but will be open to the public in 5 or 6 days. http://mathoverflow.net/questions/32730/does-an-efficient-random-number-generator-exist Comment by BlueRaja BlueRaja 2010-07-21T06:36:56Z 2010-07-21T06:36:56Z What you are looking for is not a PRNG but a random permutation (&quot;shuffle&quot;) of the integers. This is actually covered in introductory algorithms classes - the usually solution is a LFSR, as mentioned by Yuval. You may also be interested to know that you solution is very close to the popular Knuth Shuffle (<a href="http://en.wikipedia.org/wiki/Knuth_shuffle" rel="nofollow">en.wikipedia.org/wiki/Knuth_shuffle</a>) http://mathoverflow.net/questions/32479/what-are-some-mathematical-sculptures/32557#32557 Comment by BlueRaja BlueRaja 2010-07-20T06:04:17Z 2010-07-20T06:04:17Z +1 for George Hart; I had the pleasure of taking a few of his classes at Stony Brook. He's a great teacher, and a great person. Also, mathematical sculptures are his life. http://mathoverflow.net/questions/29323/math-puzzles-for-dinner/32445#32445 Comment by BlueRaja BlueRaja 2010-07-19T22:35:20Z 2010-07-19T22:35:20Z <code>1.</code> Cvpx gur fznyyrfg cevzr &gt; a, fvapr guvf vf gur fznyyrfg ahzore ≡ 0 zbq 2, zbq 3, ..., zbq a. <code>2.</code> Nffhzvat rirelbar cvpxf enaqbzyl, cvpx gur ynetrfg cevzr c ≤ a, fvapr gur bayl jnl lbh jvyy trg cvpxrq vf vs lbh orybat gb n plpyr bs rknpgyl gung nzbhag. <code>3.</code> Vs lbh hfr gur orfg fgengrtl (naq gurl xabj vg), frggvat hc n plpyr bs rknpgyl c jvyy trg lbh nal gvzr lbh cvpx nalbar va gung plpyr; naq vs (gurl xabj) lbh cvpx enaqbzyl, rirelbar cbvagvat ng lbh jvyy trg lbh sybbe(a/2) bhg bs (a-1) gvzrf (vr. 1/2 vs a vf bqq, bire 1/2 vs a vf rira) - qba'g xabj vs V pna cebir gung'f bcgvzny gubhtu. http://mathoverflow.net/questions/32269/guess-a-number-with-at-most-one-wrong-answer Comment by BlueRaja BlueRaja 2010-07-18T07:22:36Z 2010-07-18T07:22:36Z This is a standard ECC (<a href="http://en.wikipedia.org/wiki/Error-correcting_code" rel="nofollow">en.wikipedia.org/wiki/Error-correcting_code</a>) problem. http://mathoverflow.net/questions/32174/infinite-games-are-they-well-defined Comment by BlueRaja BlueRaja 2010-07-17T02:50:50Z 2010-07-17T02:50:50Z I don't see how they could both have winning strategies, infinite or not: if they both use their winning strategy, the sequence of points is well-defined, and either it converges in$D^{2}\$ or it doesn't.