User blueraja - MathOverflow

Answer by BlueRaja for Math puzzles for dinner

2010-08-06T17:53:33Z

You have a large pile of ropes and some matches. All you know about the ropes:

Each rope has a different length
Each rope burns completely (starting from one end) in exactly 64 minutes
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.

The goal is to identify when exactly 63 minutes have passed.

Answer by BlueRaja for Marey's problem: Generating all prime numbers in $[n_1,n_2]$

2010-07-25T18:35:53Z

I'm assuming you're asking if we can generate primes in [n₁, n₂] without generating the primes before that (using a sieve), to which the answer is, no, nothing aside from testing every number between n₁ and n₂ for primality using something like Rabin-Miller.

Note that this will be significantly slower than sieving unless the numbers are extremely large and the range [n₁, n₂] is comparatively small.

Answer by BlueRaja for Aren't "oracle machines" unsound concepts?

2010-07-23T05:34:49Z

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 even if such an oracle existed, your system would still be secure.

For example, if I give you an encryption E_k (k is the key), an encrypted message E_k(M) and an oracle who can decrypt any message encrypted with k except for M, then, for an ideal encryption, you should be no better off at figuring out what M is than if I hadn't even given you an oracle!

So basically we get around the problems you mentioned by ignoring them :)

Answer by BlueRaja for Lower Bounds in Theoretical Computer Science

2010-07-11T20:43:04Z

Many O(n) algorithms (sorting array with values in fixed range; searching in unsorted array; MST; finding largest binary-search subtree of a tree) are asymptotically optimal simply by virtue of the fact that every element must be looked at at least once.

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!})$

For completeness, O(1) algorithms are also trivially asymptotically-optimal.

Answer by BlueRaja for Quick proofs of hard theorems

2010-07-11T09:59:55Z

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.

Answer by BlueRaja for Undergraduate Level Math Books

2010-07-07T04:41:29Z

A Concrete Approach to Abstract Algebra by W. W. Sawyer ($6 on Amazon!)

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!

There are also two chapters on linear algebra, leading up to the final chapters, "vectors over fields" and "fields regarded as vector-spaces".

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?

2010-07-04T20:30:40Z

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.

See this related problem and solution by Randall Munroe, the creator of XKCD.

Answer by BlueRaja for Pseudo-random number generation algorithms

2010-06-25T21:29:40Z

Blum-Blum-Shub was the first (and still most popular) provably-secure PRNG (assuming only QRP), despite being incredibly simple. It's very slow compared to non-secure PRNGs, though.

Answer by BlueRaja for whitening a random bit sequence

2010-06-25T23:04:21Z

If your goal is to create an unbiased truly random stream, this page has an algorithm which produces results much faster than the usual technique (the one mentioned by qwerty1793 in the comments above).

However, if your concern is simply real-world cryptographic security, since random generators like the one you describe usually produce unbiased streams very slowly, you are better off whitening your stream once using the usual method and using that to seed a provably-secure cryptographic PRNG.

In fact, 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 (due to the fact that random data XOR'ed with non-random data produces random data).

Answer by BlueRaja for Math puzzles for dinner

2010-06-25T15:10:01Z

Most of us know that, being deterministic, computers cannot generate true random numbers.

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 1 or a 0, but you don't know the exact probabilities, or even which is more likely (both probabilities are > 0 and sum to 1, obviously)

Can you use this box to create a unbiased random generator of binary numbers?

Answer by BlueRaja for Math puzzles for dinner

2010-06-25T01:19:04Z

Fork in the road 1

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 (both villages could be truth-telling or lying villages, or one of each). There are two natives at the fork - they could both be from the same village, or from different villages (so both could be truth-tellers, both liars, or one of each).

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.

What do you ask?

Answer by BlueRaja for Proofs without words

2010-06-25T02:45:08Z

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.

Can n² + 1 unit equilateral triangles cover an equilateral triangle of side > n, say n + ε?
^{John H. Conway & Alexander Soifer

Princeton University, Mathematics

Fine Hall, Princeton, NJ 08544, USA

conway@math.princeton.edu asoifer@princeton.edu}

n² + 2 can:

Answer by BlueRaja for Math puzzles for dinner

2010-06-25T01:26:44Z

Cryptography riddle - that's a branch of mathematics, right? :)

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?

Answer by BlueRaja for Math puzzles for dinner

2010-06-25T01:23:48Z

Fork in the road 2

You're once again at a fork in the road, and again, one path leads to safety, the other to doom.

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.

Moreover, the natives answer "pish" and "posh" for yes and no, but you don't know which means "yes" and which means "no."

You're allowed to ask only two yes-or-no questions, each question being directed at one native.

What do you ask?

Answer by BlueRaja for Math puzzles for dinner

2010-06-25T00:28:52Z

Oldie but a goodie (Monty-hall problem):

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?

Answer by BlueRaja for Math puzzles for dinner

2010-06-25T00:19:49Z

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.

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?

Answer by BlueRaja for Math puzzles for dinner

2010-06-25T00:17:41Z

Assuming you have unlimited time and cash, is there a strategy that's guaranteed to win at roulette?

Answer by BlueRaja for What are the most attractive Turing undecidable problems in mathematics?

2010-06-25T00:12:04Z

As a computer scientist, it would be nice to know if a program contains buffer overflows or deadlocks.

Answer by BlueRaja for Inverse gamma function?

2010-06-21T18:56:27Z

David Cantrell gives a good approximation of $\Gamma^{-1}(n)$ on this page.

I'll copy the result here in case that page ever goes down:

k = the positive zero of the digamma function, approximately 1.461632 c = $\sqrt{2\pi}/e - \Gamma(k)$, approximately 0.036534 L(x) = $\ln((x+c)/\sqrt{2\pi})$ W(x) = Lambert W function ApproxInvGamma(x) = L(x) / W(L(x) / e) + 1/2

Comment by BlueRaja

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.

Comment by BlueRaja

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...)

Comment by BlueRaja

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 at least half the total number of apples/oranges?

Comment by BlueRaja

2010-08-06T21:09:36Z

Since the prisoner has infinite tries, he is guaranteed to win eventually by flipping random coins... unless the guard is allowed to be malicious (ie. he doesn't just turn the table randomly)?

Comment by BlueRaja

2010-08-06T17:58:48Z

Hint: lbh arrq gb ohea frira ebcrf

Comment by BlueRaja

2010-07-26T19:16:30Z

SO page: stackoverflow.com/questions/3337620/…

Comment by BlueRaja

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.

Comment by BlueRaja

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.

Comment by BlueRaja

2010-07-25T18:29:05Z

That gives you a prime; he is looking for all the primes

Comment by BlueRaja

2010-07-22T16:51:34Z

For those unaware: The site is math.stackexchange.com, 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.

Comment by BlueRaja

2010-07-21T06:36:56Z

What you are looking for is not a PRNG but a random permutation ("shuffle") 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 (en.wikipedia.org/wiki/Knuth_shuffle)

Comment by BlueRaja

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.

Comment by BlueRaja

2010-07-19T22:35:20Z

1. Cvpx gur fznyyrfg cevzr > a, fvapr guvf vf gur fznyyrfg ahzore ≡ 0 zbq 2, zbq 3, ..., zbq a. 2. 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. 3. 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.

Comment by BlueRaja

2010-07-18T07:22:36Z

This is a standard ECC (en.wikipedia.org/wiki/Error-correcting_code) problem.

Comment by BlueRaja

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.