User - MathOverflow

Answer by shreevatsa for Guess a number with at most one wrong answer

2010-07-17T09:16:07Z

BTW, this problem is known as the Ulam(-Renyi) liar problem or Ulam's searching game (or just "playing Twenty Questions with a liar"), and has an extensive literature. The following is a survey as of 2002:

Andrzej Pelc, Searching games with errors--fifty years of coping with liars, Theoretical Computer Science, Volume 270 (2002), pp. 71-109

In particular, with 1 lie allowed, to guess a number in {1…n} where n is even, the number of queries needed is the smallest integer q which satisfies n ≤ 2^q/(q+1), which for n=1000 is indeed 14. There are alternative solutions to the one-lie game in more recent papers like this and this. As observed by Peter Shor in a comment above, the general adaptive strategy when multiple lies are allowed does not look like Hamming codes.

Edit: Since this has been bumped up, I may as well mention a nice result in the more general setting, proved by Joel Spencer and Peter Winkler in their paper Three Thresholds for a Liar.

It is traditional to name the two players Paul and Carole, where Paul (named after Paul Erdős) is the one who asks the questions, and Carole (an anagram of oracle) is the one who answers them. Paul asks $q$ questions in all, and Carole is allowed to lie a fraction $r$ of the time. We will consider three progressively harder (for Paul) versions of what this means. In Version A, Carole is allowed to lie at most $\lfloor ri\rfloor$ times to the first $i$ questions, for all $i$. In Version B, Carole is only required to lie at most $\lfloor rq \rfloor$ times in total — she can choose to exhaust all her lies at the beginning, for instance. In Version C (nonadaptive), Paul must ask all his questions in one batch, and Carole can choose up to $\lfloor rq \rfloor$ ones to lie to.

Note that if no lies are allowed ($r = 0$), the number of questions needed is exactly $\lceil \log_2 n\rceil$, and that, intuitively, if $r$ is too large, Paul cannot guess correctly at all. Specifically, they show that:

In version A, Paul wins with $\Theta(\log n)$ questions if $r < 1/2$, but Carole wins if $r \ge 1/2$.
In version B, Paul wins with $\Theta(\log n)$ questions if $r < 1/3$, but Carole wins if $r \ge 1/3$.
In version C, Paul wins with $\Theta(\log n)$ questions if $r < 1/4$, Carole wins if $r > 1/4$, and if $r = 1/4$, Paul wins but needs $\Theta(n)$ questions.

Answer by shreevatsa for Decision problem restricted to inputs that satisfy some necessary condition.

2010-07-12T17:57:13Z

Your Problem 2 is indeed a promise problem. By definition, it is not in NP, because NP is a class of decision problems, not promise problems. But if you like, you can say that it's in a class Promise-NP. See Wikipedia or Oded Goldreich's survey On Promise Problems.

For a decision problem, all strings are either YES instances or NO instances. For a promise problem, some strings are allowed to be "invalid": neither YES nor NO.

In general, if you have a nondeterministic algorithm for a promise problem, then when you feed it inputs that don't satisfy the promise, it will either accept or not — so the the sets of strings accepted and not accepted by your predicate will be supersets of the actual YES and NO instances respectively (and have intersection with the "invalid" instances). In this particular problem, because your condition is a necessary one for 3-colorability, the set of accepted strings will be exactly the set of 3-colorable graphs, but its complement will include graphs that don't satisfy the condition. (If you like, you can artificially change the problem to a decision problem with the same set of YES instances, but then your Problem 2 becomes the same as Problem 1 and therefore in NP.)

Answer by shreevatsa for 100 Prisoners, 100 Boxes: Proof of Optimality

2010-07-12T04:26:26Z

I'm not sure this is at an appropriate level for Math Overflow, but while the question is open... Yes, there is a proof that the strategy is optimal, and it's in this paper:

Eugene Curtin and Max Warshauer, The locker puzzle, The Mathematical Intelligencer, Volume 28, Number 1 (March 2006), pages 28–31.

If you can't access the paper, you can see it explained (along with the original puzzle and strategy) in detailed here (or a sketch here).

Answer by shreevatsa for Implementation of the Robinson-Schensted Correspondence

2010-07-07T16:44:17Z

It doesn't require linked lists, just arrays that can grow.

There's a Java applet online that implements it.

I'm sure there are other implementations online, but since I couldn't find any, as a start, here's a simple Python implementation. [Though it feels odd giving a programming answer here, and I'm sure several people here can write it much better!]

from bisect import bisect
def RSK(p):
    '''Given a permutation p, spit out a pair of Young tableaux'''
    P = []; Q = []
    def insert(m, n=0):
        '''Insert m into P, then place n in Q at the same place'''
        for r in range(len(P)):
            if m > P[r][-1]:
                P[r].append(m); Q[r].append(n)
                return
            c = bisect(P[r], m)
            P[r][c],m = m,P[r][c]
        P.append([m])
        Q.append([n])

    for i in range(len(p)):
        insert(int(p[i]), i+1)
    return (P,Q)

print RSK('1364752')

Edit: Used binary search to improve from O(n³) to O(n²log n), which should matter only for very large permutations.

Answer by shreevatsa for Older editions of which books were better than the new ones?

2010-06-27T16:59:50Z

Usually a newer edition is something that at least the author and publisher considered an improvement, so any answers are rather subjective. That said,

Ian Stewart's Galois Theory, 3rd edition, is sometimes harshly criticized for ruining a great book, by (1) doing everything over the complex numbers first (leading to some long-winded proofs), and (2) being full of typos. The former is a conscious choice of the author, so its merits are debatable, but at any rate it's a substantially different book from the 2nd edition.
Calculus Made Easy, by Silvanus P. Thompson. This 1910 classic was updated in 1998 by Martin Gardner, but because both the authors are "men of strong individuality", the difference in styles can be somewhat jarring. Also, John Baez complains that:

Alas, the new edition has been puffed up to 336 pages by Martin Gardener. People must want calculus to seem hard.

Answer by shreevatsa for Proofs without words

2010-03-06T23:18:28Z

This other answer shows that an 8x8 board with opposite squares removed cannot be tiled with dominoes, as they are of the same "colour". But what if two squares of opposite colours are removed? Ralph E. Gomory showed that it is always possible, no matter where the two removed squares are, and this is his proof.

(Imagine A and B are the squares removed.) The image is from Honsberger's Mathematical Gems I.

Answer by shreevatsa for A single paper everyone should read?

2009-10-26T23:21:49Z

William Thurston's On Proof and Progress in Mathematics is a wonderful read, enlightening many aspects of the practice of mathematics.

Comment by

2013-04-19T05:01:44Z

For what it's worth: I've checked that there are no other solutions for n up to 35 billion or so.

Comment by

2012-10-23T09:27:19Z

Could someone explain this? I can see with calculus that the optimum value of $(100/x)^x$ is at $x=100/e$ (corresponding to something like 100/e copies of e), but (1) how would a 10-year-old arrive close to this without calculus?, and (2) even if she sees (by trying out everything with a calculator, say) that the answer for 100 is $(100/37)^{37}$, how to get from there to an understanding of $e$ in general?

Comment by

2012-10-22T04:41:20Z

I remember trying to track this down; this is what I found. Although WZ quote it as being from Concrete Mathematics by Graham, Knuth and Patashnik and attribute it to the authors, in the book it is just a margin comment left by one of the students of the Stanford class. (The book is full of those.) It follows Whitehead's quote ("It is a profoundly erroneous truism [...] Civilization advances by extending the number of important operations which we can perform without thinking about them": www-history.mcs.st-and.ac.uk/Quotations/…) and some student must have "extended" it.

Comment by

2012-08-06T14:08:37Z

This is the most delightful biography I have read, of anyone in any field.

Comment by

2012-01-07T19:22:45Z

@Tobias: The "complete trivialities" in Section 1 are not obvious to all mathematicians. (I have certainly seen people whose personal definitions of "good mathematics" wouldn't include some qualities in the list—which is fine—and who seemed unaware that others could value those qualities.) Even these insights, "trivial" to you, may be encouraging and illuminating to a young person somewhere. There are people who find Section 1&3 even more valuable than the case study. If mathematicians kept all their trivial thoughts to themselves, everyone to whom those were not trivial would be much poorer.

Comment by

2011-12-23T04:48:18Z

What Douglas Zare said is nicely explained in the 1999 paper Recounting the Rationals (math.upenn.edu/~wilf/website/recounting.pdf) by Calkin and Wilf. Some people have felt (blog.plover.com/math/recounting.html) that it's a good "first math paper" to read.

Comment by

2011-12-23T04:42:12Z

To complete Michael Hardy's comment, Euclid's original proof proves the following statement: given any finite list of primes, we can extend the list by finding a prime not in the list. (Proof: multiply the primes in the list and add one; any prime factor of this new number is a prime not in the original list.) So it's a constructive way of taking a list of primes and producing another prime; we don't have to assume that the original list was "all the primes" (as in the contradiction proof) or that they were the first n primes.

Comment by

2011-06-28T04:43:08Z

[The following is probably obvious stuff, but since this page doesn't yet mention the word "polynomial"…] One standard way to generate n pairwise independent random variables is to take some prime p greater than n, independently generate two values a and b modulo p (a≠0), and take values of the polynomial (ax+b) mod p for different x (say X_i=(ai+b) mod p, for i=0 to i=n). This is pairwise independent but not 3-wise independent. In general, to get random variables that are k-wise independent but not (k+1)-wise, take a polynomial of degree k-1.

Comment by

2011-06-05T18:09:40Z

Is the minus sign in Lewis's equation intentional?

Comment by

2010-10-28T06:51:00Z

The problem with 1_{X}, as you observed, is that it pushes the main stuff to the small font of the subscript. I don't understand the advantage you wrote of: what's wrong with (2+[X])²? IIRC, expressions of this sort are used without hesitation in Graham-Knuth-Patashnik (Concrete Mathematics).

Comment by

2010-08-14T05:12:08Z

@Kaveh: No, the question is "Which conjectures in complexity theory are widely believed because they are so so so obvious, yet have not been proved?"

Comment by

2010-08-14T05:09:54Z

The word is "renown", not "reknown", BTW. (Sorry for this trivial comment.)

Comment by

2010-08-03T23:23:07Z

Wrt Zeilberger and tongue-in-cheekness, see the interview here: math.rutgers.edu/~zeilberg/… (search for 'evangelical'). Also, whenever mention of "ultrafinitism" comes up it's irresistible to mention the anecdote involving Yessenin-Volpin, mentioned at scottaaronson.com/blog/?p=103 and dialinf.wordpress.com/2009/02/16/… :-)

Comment by

2010-08-02T03:27:07Z

BTW, the idea of a Galois theory course leading up to insolubility of the quintic using everything that came before is somewhat a myth, since most of Galois theory is unnecessary for it (though worthwhile for other reasons). See John Stillwell's "Galois Theory for Beginners" (jstor.org/stable/2325119): "most of the equipment supplied—in particular normal extensions, irreducible polynomials, splitting fields and a lot of group theory—is unnecessary. The biggest encumbrance is the so-called fundamental theorem of Galois theory." ☺ He proves it 5 pages using only the relevant parts.

Comment by

2010-08-01T11:56:59Z

I think this is an answer to "What is the use of moment-generating functions", and not to "Where does the definition of moment-generating functions come from?"