February 2010 - mathfun@mailman.xmission.com

[math-fun] reference for a simple algorithm
by Joerg Arndt 18 Feb '10

18 Feb '10

[a homework question] The following method is straightforward (from my thesis (and from my own brain)): --------------------- An algorithm for generating a random object $x$ where $x \in U \subset V$ ($U$ is the subset of all objects in $V$ that have a required property) is as follows. 1) Generate a random object $x \in V$. 2) If $x \in U$ then return it ($x$ is of the required type). 3) Go to step 1. --------------------- Now I have been asked (by one examiner) for a reference for this method, but surprisingly I cannot find anything. So trivial no one ever bothered to write down? Anyone? Btw. I call this thing the "rejection method". The example (square in a circle) at the bottom of the page http://en.wikipedia.org/wiki/Rejection_sampling would suggest that my algorithm is a special case of what is described on this page. However, I cannot see how it can be specialised from the Algorithm given just above it.

5 10

Re: [math-fun] I dream in math now.
by Dan Asimov 16 Feb '10

16 Feb '10

Sigh. This correction seems to have gotten lost in the ether, so here is a resend: << From: Dan Asimov <dasimov(a)earthlink.net> To: math-fun <math-fun(a)mailman.xmission.com> Subject: Re: [math-fun] I dream in math now. Date: Feb 16, 2010 3:23 PM Correction: In the last sentence, one should change one of my original increasings to decreasing. It doesn't matter which one, of course: << This question sounded familiar, and in fact it's a special case or the Erdos-Szekeres theorem (1935): < http://en.wikipedia.org/wiki/Erdős–Szekeres_theorem >, original paper at < http://archive.numdam.org/ARCHIVE/CM/CM_1935__2_/CM_1935__2__463_0/CM_1935_… >. The theorem states that any set of integers of size (r-1)(s-1) + 1 has either an increasing subsequence of length r or an decreasing subsequence of length s. >> >> ________________________________________________________________________________________ "Outside of a dog, a book is man's best friend. Inside of a dog, it's too dark to read." --Groucho Marx

1 0

Re: [math-fun] I dream in math now.
by Dan Asimov 16 Feb '10

16 Feb '10

Correction: In the last sentence, one should change one of my original increasings to decreasing. It doesn't matter which one, of course: << This question sounded familiar, and in fact it's a special case or the Erdos-Szekeres theorem (1935): < http://en.wikipedia.org/wiki/Erdős–Szekeres_theorem >, original paper at < http://archive.numdam.org/ARCHIVE/CM/CM_1935__2_/CM_1935__2__463_0/CM_1935_… >. The theorem states that any set of integers of size (r-1)(s-1) + 1 has either an increasing subsequence of length r or an decreasing subsequence of length s. >> ________________________________________________________________________________________ "Outside of a dog, a book is man's best friend. Inside of a dog, it's too dark to read." --Groucho Marx

1 0

Re: [math-fun] I dream in math now.
by Dan Asimov 16 Feb '10

16 Feb '10

This question sounded familiar, and in fact it's a special case or the Erdos-Szekeres theorem (1935): < http://en.wikipedia.org/wiki/Erdős–Szekeres_theorem >, original paper at < http://archive.numdam.org/ARCHIVE/CM/CM_1935__2_/CM_1935__2__463_0/CM_1935_… >. The theorem states that any set of integers of size (r-1)(s-1) + 1 has either an increasing subsequence of size r or an increasing subsequence of length s. --Dan ________________________________________________________________________________________ "Outside of a dog, a book is man's best friend. Inside of a dog, it's too dark to read." --Groucho Marx

1 0

[math-fun] I dream in math now.
by Andy Latto 16 Feb '10

16 Feb '10

So apparently I dream math problems now. Let f(n) be the smallest number such that what ever order you arrange the numbers from 1 to f(n) in, there is either an increasing subsequence or a decreasing subsequence of length n. What is f(n)? (JB, it seems unlikely that you care about this in real life, but in my dream, it was very important to you, for some practical application, to know that f(n) < n^2. You couldn't prove it though, and I said I would help.) f(1) = 1 f(2) = 2 f(3) = 4 Andy

4 4

[math-fun] A prime factor of the Fermat number F14
by Warut Roonguthai 16 Feb '10

16 Feb '10

Seems like noone mentions this big news (IMHO) yet. So here I go! On February 3, 2010, Tapio Rajala reported at http://mersenneforum.org/showthread.php?t=13051 that he found a prime factor of the Fermat number F14 with GIMPS' ECM. Until then, F14 = 2^2^14 + 1 had been the smallest composite Fermat number with no known prime factors. Warut

1 0

[math-fun] 2 Sudoku notes
by rcs＠xmission.com 16 Feb '10

16 Feb '10

The two messages below were trapped by the mailing list filter. As usual, I can't figure out why. I've inverted the order, since Paul Payton's message has a spoiler. --Rich -------- Date: Mon, 15 Feb 2010 15:45:11 -0800 Subject: Re: [math-fun] a difficult sudoku From: Nick Baxter <nickb(a)baxterweb.com> To: ms(a)alum.mit.edu, math-fun <math-fun(a)mailman.xmission.com> 2.1 unnamed [text/html] 2.34 KB Download This puzzle is "well known" and even has a name: AI Escargot. It was created about three years ago by Arto Inkala, and got some press for having the highest difficulty rating at some sudoku web site. Actually, the 1 in the lower-left box should not be there. Either way, it has a unique solution. Nick Mike Speciner wrote: > It has multiple solutions, so does it count? > > --ms > > On 2/15/2010 2:55 PM, Simon Plouffe wrote: > >> >> >> Hello, >> >> here is a sudoku for the amateurs, >> >> +-------+-------+-------+ >> | 1 . . | . . 7 | . 9 . | >> | . 3 . | . 2 . | . . 8 | >> | . . 9 | 6 . . | 5 . . | >> +-------+-------+-------+ >> | . . 5 | 3 . . | 9 . . | >> | . 1 . | . 8 . | . . 2 | >> | 6 . . | . . 4 | . . . | >> +-------+-------+-------+ >> | 3 . . | . . . | . 1 . | >> | . 4 1 | . . . | . . 7 | >> | . . 7 | . . . | 3 . . | >> +-------+-------+-------+ >> >> apparently the is one of the toughest there is. >> >> - can anyone do this ? >> >> Simon Plouffe >> <boilerplate trimmed -- rcs> ---------------- <spoiler space> x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x xx x x xx x x x x x x x x x x x x x x x x x x x x x x x x x Date: Mon, 15 Feb 2010 13:05:53 -0700 Subject: RE: [math-fun] a difficult sudoku From: "Payton, Paul" <paul.payton(a)lmco.com> To: "'math-fun'" <math-fun(a)mailman.xmission.com> 2 unnamed [multipart/signed] 14.93 KB Download 1 6 2 | 8 5 7 | 4 9 3 5 3 4 | 1 2 9 | 6 7 8 7 8 9 | 6 4 3 | 5 2 1 -------+-------+------ 4 7 5 | 3 1 2 | 9 8 6 9 1 3 | 5 8 6 | 7 4 2 6 2 8 | 7 9 4 | 1 3 5 -------+-------+------ 3 5 6 | 4 7 8 | 2 1 9 2 4 1 | 9 3 5 | 8 6 7 8 9 7 | 2 6 1 | 3 5 4 -----Original Message----- From: math-fun-bounces(a)mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Simon Plouffe Sent: Monday, February 15, 2010 11:56 AM To: math-fun Subject: [math-fun] a difficult sudoku Hello, here is a sudoku for the amateurs, +-------+-------+-------+ | 1 . . | . . 7 | . 9 . | | . 3 . | . 2 . | . . 8 | | . . 9 | 6 . . | 5 . . | +-------+-------+-------+ | . . 5 | 3 . . | 9 . . | | . 1 . | . 8 . | . . 2 | | 6 . . | . . 4 | . . . | +-------+-------+-------+ | 3 . . | . . . | . 1 . | | . 4 1 | . . . | . . 7 | | . . 7 | . . . | 3 . . | +-------+-------+-------+ apparently the is one of the toughest there is. - can anyone do this ? Simon Plouffe <trailer clipped --rcs>

1 0

[math-fun] The correct word for ...
by Guy Haworth 16 Feb '10

16 Feb '10

"Let F == " Guy

1 0

[math-fun] a difficult sudoku
by Simon Plouffe 16 Feb '10

16 Feb '10

Hello, here is a sudoku for the amateurs, +-------+-------+-------+ | 1 . . | . . 7 | . 9 . | | . 3 . | . 2 . | . . 8 | | . . 9 | 6 . . | 5 . . | +-------+-------+-------+ | . . 5 | 3 . . | 9 . . | | . 1 . | . 8 . | . . 2 | | 6 . . | . . 4 | . . . | +-------+-------+-------+ | 3 . . | . . . | . 1 . | | . 4 1 | . . . | . . 7 | | . . 7 | . . . | 3 . . | +-------+-------+-------+ apparently the is one of the toughest there is. - can anyone do this ? Simon Plouffe

3 2

Re: [math-fun] What is the correct word for . . .
by Henry Baker 15 Feb '10

15 Feb '10

Re countable v. uncountable models: True, but nitpicking. There are lots of models of axiom sets that are incredibly larger than the smallest ones, but one typically studies one of the smaller models. The second part is a round-about way of saying that real closed fields are decidable. Real closed fields are pretty interesting because they incorporate Sturm theory, which enables counting & locating polynomial roots. I was shocked, shocked, when I learned that you didn't need all of the baggage of "real" real numbers (including infinitesimal calculus) in order to study polynomials. I considered this to be laziness on the part of my math teachers, that they used calculus mumbo-jumbo, when algebraic mumbo-jumbo worked just fine for this case. At 02:36 PM 2/15/2010, Andy Latto wrote: >> Clearly the elements of real closed fields are a countable set. > >Not true. Any field that satisfies the axioms of a real closed field >is a real closed field. The smallest such is countable, but there are >uncountable ones too, like the reals. From a logician's point of view, >the interesting thing about the real-closed-field axioms is that they >are categorical; any statement you can make in a language which talks >about elements, +, and *, but not sets of elements, is either true of >all real closed fields or false for all of them.

1 0