January 2009 - mathfun@mailman.xmission.com

Re: [math-fun] English sequence
by Dan Asimov 16 Jan '09

16 Jan '09

Some may recall a scene from the movie Rain Man when Dustin Hoffman instantly counts how many toothpicks spilled on the floor: 214 (or so). In reality, how well can humans do in tasks like this? Given, let's say, five seconds to look at a collection of well-separated white ping-pong balls on a black rug, how many can the best-in-the-world-at-this count reliably? --Dan << At this juncture I can't resist observing that "bijective enumeration" is a very primitive counting technique. People well-practised in counting sets of cardinal up to (say) a few tens simply glance once at the whole assemblage, enumerating it instantaneously. Such a facility is necessary in order for example to count sheep in a field, or ducks on a pond --- neither of which are in the habit of waiting around obligingly for any such pedestrian procedure as bijection! >> _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

3 2

Re: [math-fun] muffin problem
by Michael Reid 16 Jan '09

16 Jan '09

several more values, to cover your table: T(7, 8) = 5/112 ; 4 * 5/112 + 2 * 3/56 + 4 * 1/16 + 2 * 1/14 + 4 * 9/112 T(7, 9) = 5/125 ; 6 * 5/126 + 3 * 1/21 + 3 * 4/63 + 6 * 1/14 T(8, 9) = 1/24 ; 6 * 1/24 + 6 * 1/18 + 6 * 5/72 the latter two agree with your table; but the first gives an improvement. (no contradiction, since you only gave a lower bound.) mike > > > Here are my lower bounds for U(m, n): > > > > 1 2 3 4 5 6 7 8 9 > > 1 1 > > 2 1 2 > > 3 1 1 3 > > 4 1 2 1 4 > > 5 1 1 5/4 3/2 5 > > 6 1 2 3 2 2 6 > > 7 1 1 5/4 5/3 5/3 2 7 > > 8 1 2 4/3 4 2 2 9/4 8 > > 9 1 1 3 7/4 2 3 5/2 3 9 > > > > The entry in column 4 row 7 is the bound on U(4, 7), which in fact > > equals the > > optimum value that was the subject of previous posts ( U(m, n) = m n T > > (m, n) ). > > I suspect several of my bounds are optimal values. I'm happy to > > supply the > > partitions to anyone interested. > > > i've also "calculated" some values. recall that my T(m, n) is the > maximum c such that there exists a partition of 1 with each part > >= c , and which is a simultaneous refinement of 1/m + 1/m + ... + 1/m = 1 > and of 1/n + 1/n + ... = 1/n = 1 . > > i believe i have a valid proof for each of the values below. i also give > one such partition for each; showing that it's a refinement is easy. > > T(m, n) = 1/n if m divides n ; n * 1/n > > T(2, 2n+1) = 1/(2(2n+1)) ; (4n+2) * 1/(2(2n+1)) > > T(3, 4) = 1/12 ; 12 * 1/12 > T(3, 5) = 1/12 ; 4 * 1/12 + 2 * 1/10 + 4 * 7/60 > T(3, 7) = 5/84 ; 4 * 5/84 + 6 * 1/14 + 4 * 1/12 > T(3, 8) = 1/18 ; 6 * 1/18 + 6 * 5/72 + 2 * 1/8 > T(3, 10) = 2/45 ; 6 * 2/45 + 6 * 1/18 + 2 * 1/10 > T(3, 11) = 1/24 ; 8 * 1/24 + 2 * 1/22 + 8 * 13/264 + 2 * 1/11 > T(3, 13) = 11/312 ; 8 * 11/312 + 2 * 1/26 + 8 * 1/24 + 4 * 1/13 > > T(4, 5) = 3/40 ; 4 * 3/40 + 2 * 1/10 + 4 * 1/8 > T(4, 6) = 1/12 ; 12 * 1/12 > T(4, 7) = 5/84 ; 6 * 5/84 + 2 * 1/14 + 6 * 1/12 > T(4, 9) = 7/144 ; 8 * 7/144 + 2 * 1/18 + 8 * 1/16 > T(4, 10) = 1/20 ; 20 * 1/20 > T(4, 11) = 9/220 ; 10 * 9/220 + 2 * 1/22 + 10 * 1/20 > T(4, 4n+2) = 1/(2(4n+2)) ; (8n+4) * 1/(2(4n+2)) > > T(5, 6) = 1/15 ; 6 * 1/15 + 6 * 1/10 > T(5, 7) = 1/21 ; 3 * 1/21 + 6 * 1/15 + 6 * 8/105 > T(5, 8) = 1/20 ; 4 * 1/20 + 4 * 3/40 + 4 * 1/8 > T(5, 9) = 2/45 ; 6 * 2/45 + 6 * 1/15 + 3 * 1/9 > > T(6, 7) = 1/21 ; 12 * 1/21 + 6 * 1/14 > T(6, 8) = 1/24 ; 24 * 1/24 > T(6, 9) = 1/18 ; 18 * 1/18 > > these appear to agree with your lower bounds on the overlap. > > mike >

5 6

Re: [math-fun] English sequence
by Dan Asimov 16 Jan '09

16 Jan '09

Gareth wrote: << On Thursday 15 January 2009, Veit Elser wrote: > This type of question reminds me of my son's first experience > learning to count: he got caught in an infinite loop! ... > EIGHT > NINE > TEN > ELEVEN > EIGHT > NINE ... My daughter recently went 1,2,3,...,13,14,16,16,16,16,16,... . I assume some 4-bit counter overflowed and scrobbled a linked-list pointer, or something. >> There's a vignette of a small child counting birds on a wire: "1, 4, 3, 9, 12, 11, 2. That's funny, it looks like more than 2." --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

4 3

[math-fun] English sequence
by Eric Angelini 15 Jan '09

15 Jan '09

Hello Math-Fun, a(n) is the letter-length of a(n+1), written in English: S = 3, 6, 11, 23, 323, ... Could someone check and extend S (strictly monotonically increasing)? Always use the smallest necessary integer to extend S. Best, É.

5 4

[math-fun] Overhang
by victor miller 15 Jan '09

15 Jan '09

Tim Chow (tchow(a)alum.mit.edu) asked me to post this to math-fun. I should also mention that this was the subject of a very nice talk by Peter Winkler at the Joint Math Meetings a few weeks ago ("Stacking Bricks and Stoning Crows") and the paper "Maximum Overhang" http://arxiv.org/abs/0707.0093 Victor Here's Tim's post: Mike Paterson and Uri Zwick have a very nice article in the current issue of the American Mathematical Monthly entitled "Overhang." Earlier versions of this work may be found, for example, on Zwick's homepage. http://www.cs.tau.ac.il/~zwick/ The topic is the old problem of stacking bricks on a table so that they hang over the edge by an arbitrarily large amount. The standard solution involves a harmonic series, but the authors show that one can do much better if one allows more than one brick at each level. One thing that I mentioned to Paterson and Zwick (though apparently too late for them to include it in their Monthly article) is that there is, in fact, at least one place in the literature where the possibility of more than one brick on each level is explicitly considered. I refer to the book "Ingenious Mathematical Problems and Methods" by L. A. Graham (Dover 1959), specifically the problem about the "Bridal Arch." In Graham's version of the problem, there are 86 bricks (smooth, uniform, etc.) with dimensions 2x4x8, and they are to be stacked to form a (symmetrical) 7'-high, 34"-wide arch. In the solutions section, Graham reproduces three proposed solutions to the problem sent in by his readers, all of which have more than one brick per level. See http://thelastdanishpastry.blogspot.com/2009/01/bridal-arch.html However, Graham dismisses all three solutions as incorrect "models of graceful instability" without any analysis! I asked Paterson and he said that at least some of these solutions might be correct, but he did not actually check them in detail. Presumably, Graham simply assumed that those other solutions could not be correct. Can anyone here either vindicate them, or show that they are wrong? Tim

2 2

Re: [math-fun] Passing thought for a textbook
by Steve Witham 15 Jan '09

15 Jan '09

>From: Steve Witham <sw(a)tiac.net> > >_The Elements of Programming Style_, by Kernighan and Plauger, famously >headed its sections with examples of bad style taken from other textbooks. > >I'm not sure whether it was that book, or maybe one of these: > _Software Tools_ by Kernighan, _Software Tools_ is actually also by Kernighan and Plauger. From the first paragraph of the Preface: "These programs are complete, not just algorithms or outlines, and they work: all have been tested directly from the text, which is in machine-readable form." The previous page says that the book was typeset by the authors on a PDP 11/45 running Unix. I found all this very bracing in 1976. From: Gareth McCaughan <gareth.mccaughan(a)pobox.com> >"The practice of programming", by Kernighan and Pike, makes >more or less that claim, but doesn't make a big fuss about it. >I think I've seen it in at least one other book, but that may >be memory error. Btw my point isn't that testing a program is the same as checking a proof, but that K&P's was a way to convey a similar attitude in a book. --Steve

3 2

Re: [math-fun] Passing thought for a textbook
by Dan Asimov 15 Jan '09

15 Jan '09

Steve Gray wrote: << Isn't Kernighan one of the designers of C? Or am I thinking of Unix? If it's C, that name probably came from the mark they got for it in compiler class. I hated programming in it, especially after using a greatly superior language back in the 1970's. >> I think Dennis Ritchie gets full credit for the (original) C language. I found it definitely harder to learn than Fortran or Pascal, but once I caught on, I loved it. (I worked for a while at AT&T Labs (just as & after AT&T spun off Lucent). An odd thing is that, even though Stroustrup had invented C++ there 18 years earlier -- and still worked in the same building -- C++ had never caught on among the hardcore programmer types there; it remained a C culture.) --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

Re: [math-fun] English sequence
by Allan Wechsler 14 Jan '09

14 Jan '09

Responses interspersed below. On Wed, Jan 14, 2009 at 4:42 PM, Steve Witham <sw(a)tiac.net> wrote: > >From: "Allan Wechsler" <acwacw(a)gmail.com> > > > >More "constructively", let a(0)=3, and then define a(n+1) as the smallest > >number whose name written out in English has a(n) letters. > > If so, shouldn't a(1) = 1? Ah, I think you have reconstructed Eric's original reason for explicitly specifying that the sequence be monotonic. If a(1)=1, the whole idea breaks down because there is no number whose English name has one letter. > 6 seems to be the smallest a(0) that works with that definition > (and I like that definition). This works too. > The prefixes on English 'illions seem to be Latin names for numbers. > If so, can we back-fit Latin transliterations of the English words > to extend things indefinitely? We trod this ground most heavily in a discussion on this list in the run-up to the publication of Conway's & Guy's *The Book of Numbers*. Coherent, consistent Latin names for numbers become hard to find somewhere around 1e6; above that point different writers used different systems. The Latin number names become inappropriate for use as prefixes long before that, unless you like names like unus-et-vigintillion. For TBoN, we presented a plausible extension (with minor corrections) of the system popularized by Chuquet; our system works up to the 999th zillion. For bigger numbers, we created a slightly-less-plausible extension of the extension; only by the tiniest margin did we avoid naming some poor number the "millivanillion". The 31-digit number I was groping for earlier fits within the Chuquet system just fine. A number whose name has that many letters is a different matter.

1 0

Re: [math-fun] English sequence
by Steve Witham 14 Jan '09

14 Jan '09

>From: "Allan Wechsler" <acwacw(a)gmail.com> > >More "constructively", let a(0)=3, and then define a(n+1) as the smallest >number whose name written out in English has a(n) letters. If so, shouldn't a(1) = 1? 6 seems to be the smallest a(0) that works with that definition (and I like that definition). The prefixes on English 'illions seem to be Latin names for numbers. If so, can we back-fit Latin transliterations of the English words to extend things indefinitely? --Steve

1 0

Re: [math-fun] English sequence
by Dan Asimov 14 Jan '09

14 Jan '09

Allan wrote: << More "constructively", let a(0)=3, and then define a(n+1) as the smallest number whose name written out in English has a(n) letters. I suspect it's easy to prove your parenthesized comment "strictly monotonically increasing". ... >> Only now do I comprehend the idea of this sequence -- Thanks! Question: Is it clear that the sequence is indefinitely extensible? I.e., couldn't there be a length for which (given a fixed universal naming system) there exists no English number name? (Or if there are some obvious small sizes missing, is it clear that each sufficiently large length has even one exemplar? --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

2 1