June 2012 - mathfun@mailman.xmission.com

[math-fun] solving linear equations made difficult
by James Propp 22 Jun '12

22 Jun '12

I saw this amusing derivation on the blackboard at MSRI a couple of months ago (I'm paraphrasing and reformatting slightly): "Problem: Solve x = ax + b for x. Solution: x = a(ax+b) + b = a^2 x + ab + b = a(a(ax+b)+b)+b= a^3 x + a^2 b + ab + b ... = (assuming |a| < 1) lim_{n \rightarrow \infty} a^n x + b sum_{i=0}^{\infty} a^i = 0 + b/(1-a). This also holds by analytic continuation for all a neq 1." Has anyone seen this before? I took a photograph of the blackboard, and I am inclined to submit it to Mathematics Magazine, but first I want to know the provenance. Curt McMullen was in residence at MSRI at the time, and he seemed a likely culprit, but when I pointed it out to him he seemed amused, and he denied authorship, so I don't have any suspects at present. Jim Propp

3 2

Re: [math-fun] solving linear equations made difficult
by Henry Baker 21 Jun '12

21 Jun '12

While this method might look strange for regular numbers, I believe that there are some algorithms for _matrices_ that work pretty much like this. At 06:09 PM 6/20/2012, James Propp wrote: >I saw this amusing derivation on the blackboard at MSRI a couple of months >ago (I'm paraphrasing and reformatting slightly): > >"Problem: Solve x = ax + b for x. > Solution: >x = a(ax+b) + b = a^2 x + ab + b > = a(a(ax+b)+b)+b= a^3 x + a^2 b + ab + b > ... > = (assuming |a| < 1) lim_{n \rightarrow \infty} a^n x + b >sum_{i=0}^{\infty} a^i > = 0 + b/(1-a). >This also holds by analytic continuation for all a neq 1." > >Has anyone seen this before? I took a photograph of the blackboard, and I >am inclined to submit it to Mathematics Magazine, but first I want to know >the provenance. > >Curt McMullen was in residence at MSRI at the time, and he seemed a likely >culprit, but when I pointed it out to him he seemed amused, and he denied >authorship, so I don't have any suspects at present. > >Jim Propp

2 1

[math-fun] Clock of Generic Digits
by rtwainwright＠optonline.net 20 Jun '12

20 Jun '12

In response to Stuart Anderson's question regarding subject: 1 = (n + n) / (n + n) 2 = (n / n) + (n / n) 3 = (n + n + n) / n 4 = (n - .nr) / (.nr + .nr) 5 = (n + .nr) / (.nr + .nr) 6 = (n + n) / SQRT ((.nr) (n)) 7 = (n - .nr - .nr) / .nr 8 = (n - .n - .n) / n 9 = (n + .nr - .nr) / .nr 10 = (n + .n - .n) / .n 11 = (n + .nr + .nr) / .nr 12 = (n + .n + .n) .n Where .nr = repeating decimal. R. Wainwright

2 1

[math-fun] Names of coefficients?
by Henry Baker 20 Jun '12

20 Jun '12

Consider the polynomial p(x)=(x-1)^6. For the coefficient of x^3, Macsyma/Maxima returns coeff(p(x),x,3)=-20 (at least after expanding p(x). I would rather have coefficients that are divided by the appropriate binomial coefficient, and whose sign is multiplied by (-1)^(n-i) for the coeff(p(x),x,i), where p(x) is a monic polynomial of degree n. Is there a standard name for these coefficients? Some of the 19th century texts tend to use this type of notation, but I don't know what the modern name for these coefficients is.

1 0

Re: [math-fun] reverse-engineering biased Galton boards
by Dan Asimov 20 Jun '12

20 Jun '12

The difference is that I'm starting out by assuming that *all* the probabilities T(i,j) of arriving at the point (i,j) are given for i,j >= 0, in advance. I'm now seeing that the intended problem was evidently to provide in advance only the probabilities along a fixed NW-SE diagonal D_n = {(i,j) | i+j = n}. (I made my hypotheses clearer in my post following the quoted one.) Apologies for misunderstanding the problem. --Dan Jim wrote: << I still assert that the probabilities are underdetermined, even in the case n=3. Consider a situation board in which balls get routed from (0,0) to (1,0) w.p. (with probability) 2/3, from (1,0) to (2,0) w.p. 1/2, and from (0,1) to (1,1) w.p. 0. In the Galton board picture, that's 2/3:1/3 1/2:1/2 0:1 The output distribution is 1/3:1/3:1/3. On the other hand, the biased Galton board 1/3:2/3 1:0 1/2:1/2 also gives output distribution 1/3:1/3:1/3. So the n output probabilities do NOT uniquely determine the n(n-1)/2 biases. My guess is that Dan is solving a different problem. Can anyone reconcile his analysis with mine and explain why we came to such different conclusions? >> ________________________________________________________________________________________ It goes without saying that .

1 0

Re: [math-fun] reverse-engineering biased Galton boards
by Dan Asimov 20 Jun '12

20 Jun '12

Very interesting problem. Of course as was mentioned in a later post, all the target probabilities on each SE-NW diagonal must sum to 1. But I'm not sure if this is massively underdetermined. It's easy to check that all transition probabilities are uniquely determined through the NW-SE diagonal i+j = 3. (In fact this imposes some minor constraints on the target probabilities). And it looks as though things may continue that way. (Or do things suddenly start loosening up after this?) --Dan Jim wrote: << Here's a (hopefully clearer) statement of the question. Consider a random walk on ZxZ that starts at (0,0) and progresses n-1 steps upward and rightward, ending at some vertex (i,j) with i,j non-negative integers summing to n-1, such that p_{i,j} is the probability that a walker at (i,j) will go to (i+1,j) (and 1-p_{i,j} is the probability that a walker at (i,j) will go to (i,j+1)). Thus the path taken in the first n-1 steps is determined by all the p_{i,j}'s with i,j non-negative integers with sum no greater than n-2. Suppose we want to choose those n(n-1)/2 probabilities p_{i,j} so that the probability of the walker being at (n-k,k-1) is some specified number p_k (1 leq k leq n). This is a massively underdetermined problem; there are lots of ways to choose biases at the n(n-1)/2 junctions so as to generate this distribution after n steps. But suppose we have the additional goal of minimizing the effect that slight perturbations of the biases will have. Is there a unique best choice of biases, and if so, what is it? . . . >> ________________________________________________________________________________________ It goes without saying that .

2 1

Re: [math-fun] reverse-engineering biased Galton boards
by Dan Asimov 19 Jun '12

19 Jun '12

Notational confusion: At the end of my last post on this subject, I wrote: << The TP's are clearly *not* UD if the Q(i,j) have enough 0's among them. But I think in that case all the TP's going to point (i,j) with Q(i,j) > 0 *are* UD, so the TP's that are non-UD would seem to be irrelevant. >> but forgot to change the expression Q(i,j) to T(i,j). So it should read: << The TP's are clearly *not* UD if the T(i,j) have enough 0's among them. But I think in that case all the TP's going to point (i,j) with T(i,j) > 0 *are* UD, so the TP's that are non-UD would seem to be irrelevant. >> Hope that makes more sense. --Dan ________________________________________________________________________________________ It goes without saying that .

1 0

Re: [math-fun] "C^1" isometric deformations of S^2 in R^3
by Dan Asimov 19 Jun '12

19 Jun '12

The phrase "deformation (through isometric embeddings)" includes the word "through". But to expand on that definition: Given any eps > 0, there is a family of isometric embeddings H_t : S^2 -> R^3 given by H_t(x) := H(x,t), where H: S^2 x [0,1] -> R^3 is a continuous mapping, and such that a) H_0 is the standard inclusion of the unit sphere S^2 into R^3 and b) H_1(S^2) lies inside an open ball in R^3 of radius eps. --Dan << I think I can guess what deformation of a surface "through" a set of surfaces might mean; but can you give a pointer to where these matters are defined in more detail? In particular, why is there no mention of "through" in your and Gerver's result? [I] wrote: << Joe Gerver and I have found a way to perform a C^0-isometric deformation (through isometric embeddings) of the round S^2 in R^3 that reduces it to fitting into a small ball of radius eps for arbitrarily small eps > 0. >> >> ________________________________________________________________________________________ It goes without saying that .

2 1

Re: [math-fun] "C^1" isometric deformations of S^2 in R^3
by Dan Asimov 19 Jun '12

19 Jun '12

Joe Gerver and I have found a way to perform a C^0-isometric deformation (through isometric embeddings) of the round S^2 in R^3 that reduces it to fitting into a small ball of radius eps for arbitrarily small eps > 0. --Dan On 13/11/2009 09:32, Gerard Westendorp wrote: << . . . Daniel Asimov wrote: << It's known that the standard sphere S^2 in R^3 is rigid with respect to C^2 deformations through C^2 surfaces. (See, e.g., Edgar Kann, "A new method for infinitesimal rigidity of surfaces with K > 0," J. Diff. Geom., 1970 pp. 5-12.) But have there been results about isometric deformation of the standard S^2 in R^3, through surfaces that need be only C^1 embeddings? The deformation itself need be only C^0. And what about the same question but with C^0 replacing C^1 ? >> . . . >> ________________________________________________________________________________________ It goes without saying that .

2 1

[math-fun] Proof(?) that black can always win 19x19 go with 25 handicap stones (at least, with the right rule set)
by Warren Smith 19 Jun '12

19 Jun '12

Proof(?) that black can always win 19x19 go with 25 handicap stones (at least, with the right rule set) ==================Warren D. Smith======19 June 2012================ INTRODUCTION: It is an interesting question: what is the smallest number H of handicap stones such that black can always win (and we can prove this) an NxN go game? Janice Kim (I think she was 1 pro dan at the time) in a famous game beat the computer "Handtalk" (author: ZhiXing Chen) by "a few points" despite giving it 25 handicap stones. Didier Garcia (1 amateur dan, 3 kyu on IGS) also beat handtalk with 25 handicap stones (playing at "best" level, supposedly 4 kyu Japanese) by a winning margin of 88 in a game posted on Jean-Loup Gailly's go page http://gailly.net/go.html . Gailly says he could defeat Handtalk and Go++ at far larger handicaps than their and his strengths would predict, presumably because he understood the weaknesses of those programs. It has been remarked that many go programs seem strong on your first encounter but when the human gets used to them, they look weaker. Martin Mueller (amateur 6 dan) in a famous 1998 game beat the computer "ManyFaces" (author: David Fotland) by a 6-point margin despite giving it 29 handicap stones. Ingo Althofer on 26 January 2012 http://www.althofer.de/handicap-29-prize.html offered a 1000-Euro prize for the first program able to give the 1998 version of Many Faces 29 stones handicap and beat it >=3 times in a 5-game match. Offer ends 31 December 2020. I here describe a strategy by which I claim/hope, black can win NxN go versus any opponent, provided he starts the game with N+6 handicap stones (free placement); the margin of victory (Chinese scoring) should be >=N+8. So with N=19, it should suffice to have 25 handicap stones to win by margin>=27. If so, this means it was inexcusable for Handtalk and ManyFaces to lose those games. It also would mean Althofer would never need to pay, provided ManyFaces knew this strategy, which it didn't in 1998. Maybe Althofer should send me 1000 Euro, donations happily accepted. :) However, with my strategy the game can also end with "no result" in Japanese rules. THE STRATEGY: My strategy is simple. Black begins with this unconditionally-alive (N+6)-stone pattern: xx...............xx .xxxxxxxxxxxxxxxxx. xx...............xx (Please view in constant-width font.) The long line of stones is on the board's centerline. This is shown for N=19 but works for any odd value of N>=3. If N is even then we can instead begin with this alternate (N+6)-stone pattern: ............xx xxxxxxx.....x. .x.....xxxxxxx xx............ >From then onward, anytime white plays a move (x,y), black responds with the "mirror move" (N+1-x, N+1-y). (I assume the rules are that "suicide is illegal" and x=1,2,3...,N coordinate system.) If white plays a move which would be illegal for black to mirror -- this can happen if, say, white basically suicides (i.e. makes black capture) a white group above and touching the centerline (the corresponding black below+touching group is not captured) then white moves into his killed area (black cannot because the corresponding area is filled with black stones) -- then black simply passes. DISCUSSION: It is well known that "mirror go" is not a good strategy in go without any handicap stones, see http://senseis.xmp.net/?Manego and http://senseis.xmp.net/?CounteringMirrorGo . If black tried first moving to the centerpoint then mirroring from then onward, he loses either because of (i) a shortage of liberties allowing white to capture his central group [but this cannot happen in my handicap scenario, central group is unconditionally alive], (ii) or a situation with two converging "ladders" yields the same thing [also cannot happen in my handicap scenario] (iii) or one can set up a situation with two "ko"s A and B with mirror images A' and B'. White captures in A, and Black mimics by capturing in A'. Then White captures in B, and Black captures in B'. Then White recaptures in A', and Black recaptures in A. Finally White recaptures in B'. The "superko rule" (repeating position is illegal) forbids Black from recapturing in B, so he has to stop mimicking. [However, in Japanese go rules, there is no superko rule; instead if a position is repeated that is not merely a simple ko, then if at least one of the players desires, the game is declared "no result" and is to be re-played or perhaps (if there is not time for replay) regarded as a tie ("jigo") or adjudicated. So I am trying to argue that our handicap strategy yields either a black victory or "no result"/jigo.] Incidentally, this is a STRONG ARGUMENT FOR ADOPTING A FORM OF THE SUPERKO RULE in go -- otherwise it would be too easy for a moron to win or draw at handicap go. (iv) If black in a 10-stone handicap game on an NxN board with N=even were to begin by placing the unconditionally alive handicap-stone group xx.. x.xx xx.x ..xx at board center, or in an NxN (N=odd) 11-stone handicap game ..xx. .x.x. .xxx. .x.x. .xx.. then mirroring from then onward, that would not work because white could contrive to get an annular situation near the rim of the board like xxxxxx. xooooox xo...ox xo...xo ox...xo oxxxxxo .oooooo in this situation, o makes a large capture by playing in the upper right corner, then x would not capture anything playing in bottom left, in fact it would be an illegal suicide. [However, again, this "annular" anti-mirror ploy again cannot be used in my N+6 handicap stone scenario.] (v) in a no-handicap game with N=odd if white just tried mirroring black, then black at some well-chosen moment could move to the centerpoint which is a move that cannot be mirrored and which also can be made decisive. [Can't do that here since centerpoint already occupied.] SUMMARY: So does this really constitute a proof? I've just argued that all the usual standard ideas in go for stopping mirror-go from working, do not work against my handicap-go strategy, at least provided we adopt the right rule-set (suicide-illegal, Japanese no-superko rules, and Chinese scoring). It is a much stronger claim than any previous I've seen (all the previous proof-strategy-attempts needed H to be of order N*N, not order N). But it seems to me that more generally, we can argue that with this strategy there will be exactly the same stone formation above & below (mirrored & color-reversed) the original eternal handicap stones, except that there can be white groups captured by black, for which the corresponding black groups stay uncaptured. Hence it really is a proof, i.e. each point of the board has a mate such that the sum of the two is a nonnegative Chinese score for black, so in view of that plus the original N+8 advantage, black must win. --end.

2 1