March 2014 - mathfun@mailman.xmission.com

Re: [math-fun] Stop signs
by Dan Asimov 28 Mar '14

28 Mar '14

I seem to recall that the octagon is the regular polygon with the lowest optimal packing density (sup of the density over all its planar packings where density is defined). I'm not sure whether the actual density is known, or whether there is a packing realizing the sup over all density-defined packing. I also seem to recall that there were some adjustments to the octagon that give a convex shape with an even lower packing density than the octagon. I don't know if the inf over all convex shapes S of the sup over all density-defined packings' densities is realizable by a specific shape (though I would expect so) or by a specific packing of that shape (no idea). Does anyone out there know more about this? --Dan Gene wrote: ----- I thought red octagonal stop signs are an international standard, except for "STOP" being in the local language. But, this being posted to math-fun, I would think the intended interpretation is how to fabricate stop signs while minimizing the usage of sheet metal. -----

2 1

[math-fun] Stop signs
by Bill Gosper 28 Mar '14

28 Mar '14

JPropp> What is the officially approved way to manufacture a stop sign? Is a perfectly made stop sign really a regular octagon, or is it something slightly different? (My hope is that the answer varies from state to state.) <Jim Propp If your hope is right, this urgently requires new Federal regulations! Someone connected with the MIT Model Railroad Club collected photos of stopsigns. They had a green one. From Maine, I think. Conjecturally, a chemical changeling. --rwg OMG, https://www.google.com/search?q=green+stop+sign&client=firefox-a&hs=99u&rls…

2 1

[math-fun] Chess underpromotions etc
by Guy Haworth 28 Mar '14

28 Mar '14

The P=B game examples are new to me and v welcome: I had thought there were none over the board that were 'essential'. P=N is not strictly an underpromotion but an 'underpromotion' - as the Knight can do things the Queen cannot do. The maxDTM[ate] KRPPKRP btm loss requires White to genuinely underpromote to a Rook in a 'Saavedra'-like position ... in order to win in 217 moves, q.v., http://centaur.reading.ac.uk/34268/ The maxDTM KRNPKPP loss, also at http://centaur.reading.ac.uk/34268/ , has Black making two P=N promotions to maximise the depth of mate: dtm = 182m. FIDE briefly varied the 50-move rule with a 100-move rule in various circumstances - but realised, with the 6-man results (maxDTC[onversion] = 243m) that this was not a finite game. Now all is back to a 50-move rule ... except there is a 75-move rule (that the game will end as a draw without need of a claim) coming in at the end of June 2014. Tournament arbiters can waive a rule if they wish, provided they are happy for the games not to be FIDE rated ... which doesn't apply to Computer-Computer games. The Lomonosov 'MVL' team in Moscow completed 7m DTM EGTs in 2012 for all except 6-1m endgames and positions with non-null casting rights. Interestingly, the new World Champion, Carlsen, said (only a few weeks ago) that 7m EGTs would never be done in his lifetime. Guy

1 0

[math-fun] underpromotions in real chess games, 50 move rule, etc
by Warren D Smith 28 Mar '14

28 Mar '14

> From: Bill Gosper <billgosper(a)gmail.com> > To: math-fun(a)mailman.xmission.com > Subject: [math-fun] how many chess positions? > WDS>Ignore the 3-time repetition and 50-move rules. > rwg> Note that someone has found a 517 move forced mate: > http://timkr.home.xs4all.nl/chess2/diary_16.htm > See also http://en.wikipedia.org/wiki/Fifty-move_rule --yes, FIDE after the discovery some endings took longer than 50 reversible moves to make progress, changed "fifty" to higher numbers in specific endings. But eventually it got ridiculous with several "mate in >500" positions being proven and no end in sight to the horror. So then they just said "to hell with them" and changed it to 50 moves, period, to the great relief of all top human players. ........ r......n ........ ........ black (lowercase) to move but then will be mated in 545 moves. .....k.. ...K.... .......N ...b...Q http://chessok.com/?page_id=27966 describes the latest progress in perfect-solve endgame databases. They are trying to solve all 7-man positions, ignoring stupid stuff like 6 men versus bare king or multiple same-square-color bishops, and their answers have consumed 140 TeraBytes so far. > WDS> What is the number P of chess positions reachable via a legal game? > Finding the exact answer is too hard, but finding good upper & lower bounds > Note that pawns can only be located on ranks 2-6, not 1,8; > rwg> Why not 2-7? --WDS: sorry for this typo. > Tom asked if one should ever promote to a bishop. Can someone > construct a case where queening would stalemate? --yes, there are many chess problemists who have made positions where, e.g. the unique best move is underpromotion to anything they wanted. However, in real games it is rare that underpromotion is best, and knight underpromos are way less rare than bishop and rook. Real games involving underpromotions were found by a game database search and collected here: http://www.chessgames.com/perl/chesscollection?cid=1000028 Apparently this search found only 4 games involving bishop underpromos. Of those, only 1 was real, 2 were stupid jokes or hoaxes, and the remaining 1 was not really played in the game but should have been. http://www.chessgames.com/perl/chessgame?gid=1253800 In this 1972 game Reshko (white) should have played 61. a8=B! If he'd played a8=Q or R then 61... Qf7+! 62.Qxf7 stalemate). Wikipedia claims that the above URL game record is wrong and really Reshko played 61. a8=N? which should have drawn according to analysis by Soltis, but won due to an error by his opponent Kaminsky, whereas 61. a8=B! really was a forced win. In this 1993 game http://www.chessgames.com/perl/chessgame?gid=1287069 Tomic (white) played 44. cxd8=B. If he had played cxd8=Q or R, then immediate stalemate. But the B threatened immediate unstoppable mate. If he'd promoted to an N, this would probably also win, but much slower. In this 1932 game http://www.chessgames.com/perl/chessgame?gid=1094403 Vidmar (white) gets into an opposite-Bs ending 2 pawns up. I suspect this game is fake because Maroczy could & should have called a 50-move draw on him (moves 61-106). Anyhow it has 124. h8=B+ which was just a stupid joke, he should have played h8=Q+ but it made no difference due to immediate 124... Kxh8. Furthermore, the game continued past the point where it automatically would have ended (at least in today's rules) due to insufficient mating material. In this 1978 game http://www.chessgames.com/perl/chessgame?gid=1042976 Meyer's bishop underpromo is another stupid joke. Then he lost. chessgames.com says it has "over 711000 games" so it would appear real bishop underpromos happen about 1 game per million. Same search found about 40 knight underpromo games, of which maybe half of them were jokes. Wikipedia discusses examples of R and B underpromotions, http://en.wikipedia.org/wiki/Promotion_(chess)#Promotion_to_rook_or_bishop but both their B-examples are constructed, not real. Tim Krabbe also did game database searches for underpromo games (as well as discussing constructed positions) http://timkr.home.xs4all.nl/chess2/minor.htm noting that R or B underpromo that win are rare compared to those that salvage draws. He found Grishchuk-Hua 1994 in which 68. axb8=B won, although axb8=N also would win. chessgames.com N-underpromo games: http://www.chessgames.com/perl/chessgame?gid=1037562 white played 71.b8=N+ getting a draw, because 71.b8=other? 72. Ra1 checkmate. Same thing happened in http://www.chessgames.com/perl/chessgame?gid=1400994 In this 1994 game http://www.chessgames.com/perl/chessgame?gid=1046960 Cramling played 39. c8=N+ which is not bad, but she could have done c8=Q and also won. In 1956 Zurakhov played 57.g8=N! http://www.chessgames.com/perl/chessgame?gid=1156733 since 57.g8=other loses it to the knight fork-check. Later in the same game, 79.c8=N+! for the same reason and if 79.c8=other? Nd6+ 80. K moves, Nxc8 then black presumably eventually would draw by playing ..NxP or by sacrificing his N to reach a known fortress position in which the a-pawn cannot promote. So... TWO N-underpromos in the same game, which is amazing and surely qualifies this as "the immortal underpromotion game." In 1948 http://www.chessgames.com/perl/chessgame?gid=1072256 44. f8=N+ looks to be the only winning move. If 44.f8=Q? Qc2+ 45. Ke3 or Kf3, Qe2+ 46. Kf4 Qe4 mate In 1993 http://www.chessgames.com/perl/chessgame?gid=1014437 Adams played b8=N since anything else loses to Ra6 (checkmate or wins both pawns). 45. Kf3 > HAKMEM Item 70 misprints a vaguely related subtle chess > problem (bishop at KB7 should be KB8). > > --rwg > > wds> and that if M pieces and P pawns have been captured, then > at most 2*M+3*P promotions could have happened. > And many pawn configurations are impossible unless enough captures > happened... > > John Tromp claimed > P<=7728772977965919677164873487685453137329736522=2^152.437 > as the result of a computer program he has not described, but this is > unlikely to > be optimal (assuming it is correct). > > For somebody determined enough: > I think it should be possible to determine the answer accurate to 5% > by first creating a good encoding scheme, say which proves P<2^155, > and then sampling random positions for each deciding if it really would > be reachable. Assuming deciding reachability is actually feasible > 99.999% of the time, and assuming P>2^144, we would after 2 million > random samples find at least about 1000 reachable positions and at most > about 20 whose reachability was unknown. This would be good enough > for a 5% accurate (Monte Carlo) estimate. > > If P<2^150, then the proof tree of chess (at least ignoring > 50-move rule) would presumably be about 2^75 positions, > suggesting chess might actually be feasibly solvable (?!). > -- > Warren D. Smith > > > ------------------------------ > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > End of math-fun Digest, Vol 133, Issue 35 > ***************************************** > -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 2

Re: [math-fun] a strange class of algebraic numbers
by Adam P. Goucher 27 Mar '14

27 Mar '14

Bill Gosper mentioned: "The 549 move forced mate http://timkr.home.xs4all.nl/chess2/diary.htm" Wow, this is truly remarkable. I wouldn't have imagined the possibility of chess endgames taking that long to reach a conclusion (assuming perfect play). Apparently all 7-piece endgames have now been catalogued. Eugene Salamin wrote: "The series sum(x^k/2^k, k=0..inf) = 1/(1 - (x/2)) satisfies Julian's requirement." That's a rational function/number, though, so it's not as interesting as an irrational example (since the binary expansion must be periodic). A slightly less trivial rational number is this binary counter: Image[Partition[RealDigits[1/(1 - ((1/2)^20))^2 - 1/2, 2, 10000][[1]], 20]] And a one-digit modification to display the triangular numbers in binary: Image[Partition[RealDigits[1/(1 - ((1/2)^20))^3 - 1/2, 2, 10000][[1]], 20]] Simon Plouffe wrote: "a very good question now : can this be generated with a cellular automata ?" No, it cannot be generated in the obvious way as the Wolfram-style output of a one-dimensional cellular automaton. If it could, then the bitstring would become eventually periodic (when the CA is restricted to a finite world, as is the case for your algebraic constant). But sqrt(sqrt(2^(2^n) + 1)) is irrational, so the bitstring is aperiodic. #Contradiction Sincerely, Adam P. Goucher > ----- Original Message ----- > From: Eugene Salamin > Sent: 03/27/14 07:47 PM > To: math-fun > Subject: Re: [math-fun] a strange class of algebraic numbers > > >________________________________ > > From: Julian Ziegler Hunts <julianj.zh(a)gmail.com> > >To: Simon Plouffe <simon.plouffe(a)gmail.com> > >Cc: math-fun <math-fun(a)mailman.xmission.com> > >Sent: Thursday, March 27, 2014 11:40 AM > >Subject: Re: [math-fun] a strange class of algebraic numbers > > > > > >The two functions are the same, after replacing k by 2s+1. Even > >k/half-integral s only produce a little bit of regularity, namely the first > >few bits because it's very close to 1, but odd k/integral s produce the > >longer (length quadratic in k) patterns. > > > >> do you see any way to lengthen the nonrandomness? > > > >Find some other algebraic function whose Taylor series' coefficients have > >power-of-two denominators and numerators that grow more slowly > >(sub-exponentially, if possible)? The actual size of the denominators > >doesn't matter too much, unless they grow really quickly, since only the > >ratio of two consecutive denominators contributes (currently, the > >denominators grow exponentially, hence contribute only a constant (because > >the numerators are also exponential) amount to the non-randomness). I > >don't know how you would go about constructing such a function, though. > > > >Julian > >--------------------------------------------- > >The series sum(x^k/2^k, k=0..inf) = 1/(1 - (x/2)) satisfies Julian's requirement. > > > > -- Gene > > > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

Re: [math-fun] a strange class of algebraic numbers
by Bill Gosper 27 Mar '14

27 Mar '14

Julian, do you see any way to lengthen the nonrandomness? --Bill On Wed, Mar 19, 2014 at 5:12 PM, Julian Ziegler Hunts <julianj.zh(a)gmail.com>wrote: > What's strange about this? Other than the long runs of identical bits, > which are easily explained by rewriting it as > 1+Sqrt[1+(Sqrt[1+4^(1-k)]-1)/2]/2^(k/2+1/2) (which accurately predicts a > lack of structure for k even), and noting that the series coefficients for > sqrt(1+x) have power-of-two denominators (and therefore so do the > coefficients of sqrt(1+(sqrt(1+x)-1)/2)). > > Julian > > > On Tue, Mar 18, 2014 at 4:52 PM, Bill Gosper <billgosper(a)gmail.com> wrote: > >> Nice. But your plots are line-wrapped. >> Out[698]= 1 + 2^(-1 - k) Sqrt[2^k + 2 Sqrt[1 + 2^(2 (-1 + k))]] >> >> You have, e.g. >> In[700]:= ArrayPlot[ >> Partition[RealDigits[%698 /. k -> 63, 2, 63^2][[1]], 63]] >> >> Try >> In[705]:= ArrayPlot[ >> Partition[ >> Join[ConstantArray[0, 32], >> RealDigits[%698 /. k -> 63, 2, 2*63^2][[1]]], 2*63]] >> --rwg >> Violating two embargoes at once: >> Climate change makes planes disappear. >> >

4 3

[math-fun] underpromotions in real chess games, 50 move rule, etc
by Bill Gosper 27 Mar '14

27 Mar '14

The 549 move forced mate http://timkr.home.xs4all.nl/chess2/diary.htm has 6. g8=N+ (! cleverly saving the Q), allegedly perfect play. Wh'ouda thunk *this* is how computers would ruin chess? --rwg WDS> From: Bill Gosper <billgosper(a)gmail.com> > To: math-fun(a)mailman.xmission.com > Subject: [math-fun] how many chess positions? > WDS>Ignore the 3-time repetition and 50-move rules. > rwg> Note that someone has found a 517 move forced mate: > http://timkr.home.xs4all.nl/chess2/diary_16.htm > See also http://en.wikipedia.org/wiki/Fifty-move_rule --yes, FIDE after the discovery some endings took longer than 50 reversible moves to make progress, changed "fifty" to higher numbers in specific endings. But eventually it got ridiculous with several "mate in >500" positions being proven and no end in sight to the horror. So then they just said "to hell with them" and changed it to 50 moves, period, to the great relief of all top human players. ........ r......n ........ ........ black (lowercase) to move but then will be mated in 545 moves. .....k.. ...K.... .......N ...b...Q http://chessok.com/?page_id=27966 describes the latest progress in perfect-solve endgame databases. They are trying to solve all 7-man positions, ignoring stupid stuff like 6 men versus bare king or multiple same-square-color bishops, and their answers have consumed 140 TeraBytes so far. > WDS> What is the number P of chess positions reachable via a legal game? > Finding the exact answer is too hard, but finding good upper & lower bounds > Note that pawns can only be located on ranks 2-6, not 1,8; > rwg> Why not 2-7? --WDS: sorry for this typo. > Tom asked if one should ever promote to a bishop. Can someone > construct a case where queening would stalemate? --yes, there are many chess problemists who have made positions where, e.g. the unique best move is underpromotion to anything they wanted. However, in real games it is rare that underpromotion is best, and knight underpromos are way less rare than bishop and rook. Real games involving underpromotions were found by a game database search and collected here: http://www.chessgames.com/perl/chesscollection?cid=1000028 Apparently this search found only 4 games involving bishop underpromos. Of those, only 1 was real, 2 were stupid jokes or hoaxes, and the remaining 1 was not really played in the game but should have been. http://www.chessgames.com/perl/chessgame?gid=1253800 In this 1972 game Reshko (white) should have played 61. a8=B! If he'd played a8=Q or R then 61... Qf7+! 62.Qxf7 stalemate). Wikipedia claims that the above URL game record is wrong and really Reshko played 61. a8=N? which should have drawn according to analysis by Soltis, but won due to an error by his opponent Kaminsky, whereas 61. a8=B! really was a forced win. In this 1993 game http://www.chessgames.com/perl/chessgame?gid=1287069 Tomic (white) played 44. cxd8=B. If he had played cxd8=Q or R, then immediate stalemate. But the B threatened immediate unstoppable mate. If he'd promoted to an N, this would probably also win, but much slower. In this 1932 game http://www.chessgames.com/perl/chessgame?gid=1094403 Vidmar (white) gets into an opposite-Bs ending 2 pawns up. I suspect this game is fake because Maroczy could & should have called a 50-move draw on him (moves 61-106). Anyhow it has 124. h8=B+ which was just a stupid joke, he should have played h8=Q+ but it made no difference due to immediate 124... Kxh8. Furthermore, the game continued past the point where it automatically would have ended (at least in today's rules) due to insufficient mating material. In this 1978 game http://www.chessgames.com/perl/chessgame?gid=1042976 Meyer's bishop underpromo is another stupid joke. Then he lost. chessgames.com says it has "over 711000 games" so it would appear real bishop underpromos happen about 1 game per million. Same search found about 40 knight underpromo games, of which maybe half of them were jokes. Wikipedia discusses examples of R and B underpromotions, http://en.wikipedia.org/wiki/Promotion_(chess)#Promotion_to_rook_or_bishop but both their B-examples are constructed, not real. Tim Krabbe also did game database searches for underpromo games (as well as discussing constructed positions) http://timkr.home.xs4all.nl/chess2/minor.htm noting that R or B underpromo that win are rare compared to those that salvage draws. He found Grishchuk-Hua 1994 in which 68. axb8=B won, although axb8=N also would win. chessgames.com N-underpromo games: http://www.chessgames.com/perl/chessgame?gid=1037562 white played 71.b8=N+ getting a draw, because 71.b8=other? 72. Ra1 checkmate. Same thing happened in http://www.chessgames.com/perl/chessgame?gid=1400994 In this 1994 game http://www.chessgames.com/perl/chessgame?gid=1046960 Cramling played 39. c8=N+ which is not bad, but she could have done c8=Q and also won. In 1956 Zurakhov played 57.g8=N! http://www.chessgames.com/perl/chessgame?gid=1156733 since 57.g8=other loses it to the knight fork-check. Later in the same game, 79.c8=N+! for the same reason and if 79.c8=other? Nd6+ 80. K moves, Nxc8 then black presumably eventually would draw by playing ..NxP or by sacrificing his N to reach a known fortress position in which the a-pawn cannot promote. So... TWO N-underpromos in the same game, which is amazing and surely qualifies this as "the immortal underpromotion game." In 1948 http://www.chessgames.com/perl/chessgame?gid=1072256 44. f8=N+ looks to be the only winning move. If 44.f8=Q? Qc2+ 45. Ke3 or Kf3, Qe2+ 46. Kf4 Qe4 mate In 1993 http://www.chessgames.com/perl/chessgame?gid=1014437 Adams played b8=N since anything else loses to Ra6 (checkmate or wins both pawns). 45. Kf3 > HAKMEM Item 70 misprints a vaguely related subtle chess > problem (bishop at KB7 should be KB8). > > --rwg This is corrected in Henry's http://home.pipeline.com/~hbaker1/hakmem/hakmem.html > > wds> and that if M pieces and P pawns have been captured, then > at most 2*M+3*P promotions could have happened. > And many pawn configurations are impossible unless enough captures > happened... > > John Tromp claimed > P<=7728772977965919677164873487685453137329736522=2^152.437 > as the result of a computer program he has not described, but this is > unlikely to > be optimal (assuming it is correct). > > For somebody determined enough: > I think it should be possible to determine the answer accurate to 5% > by first creating a good encoding scheme, say which proves P<2^155, > and then sampling random positions for each deciding if it really would > be reachable. Assuming deciding reachability is actually feasible > 99.999% of the time, and assuming P>2^144, we would after 2 million > random samples find at least about 1000 reachable positions and at most > about 20 whose reachability was unknown. This would be good enough > for a 5% accurate (Monte Carlo) estimate. > > If P<2^150, then the proof tree of chess (at least ignoring > 50-move rule) would presumably be about 2^75 positions, > suggesting chess might actually be feasibly solvable (?!). > -- > Warren D. Smith >

1 0

[math-fun] Missing plane discussion closed.
by rcs＠xmission.com 26 Mar '14

26 Mar '14

I'm declaring the thread about the missing plane closed. Rich

2 1

Re: [math-fun] Chess ... Various
by Guy Haworth 26 Mar '14

26 Mar '14

An update on the 517-move win: Tim Krabbe, item #393, http://timkr.home.xs4all.nl/chess2/diary.htm ... Including my own predictions to 10-man chess. Rules about 'general wins' in Pawnless chess can be checked out against data about extreme wins in my 'Chess Endgame Records', http://centaur.reading.ac.uk/34268/ . John Nunn gives a review of 'general win/draw' in a subset of 6-man endgames in 'Secrets of Pawnless Endgames'. Basically, we are seeing smaller and smaller advantages playing out in larger and larger spaces (x60, x59, x58 etc) ... The maxDTM win in KQPKRBN derives its length (1,097 plies, 549 winner's moves) from an underpromotion of P=N (which is not strictly an underpromotion as the Q cannot do a N-move) and a very long phase in KQNKRBN (1,006 plies, 503m). The main restriction on the number of positions is the constraint that the side-not-to-move should not be in check. The statistical sampling idea seems to be news and interesting. Guy

1 0

[math-fun] how many chess positions?
by Bill Gosper 26 Mar '14

26 Mar '14

WDS>Ignore the 3-time repetition and 50-move rules. rwg> Note that someone has found a 517 move forced mate: http://timkr.home.xs4all.nl/chess2/diary_16.htm See also http://en.wikipedia.org/wiki/Fifty-move_rule WDS> What is the number P of chess positions reachable via a legal game? Finding the exact answer is too hard, but finding good upper & lower bounds is doable. A "position" should know what the pieces are, where they are, who is to move, what are the castling rights, and what the available en passant captures (if any) are. Note that pawns can only be located on ranks 2-6, not 1,8; rwg> Why not 2-7? Tom asked if one should ever promote to a bishop. Can someone construct a case where queening would stalemate? HAKMEM Item 70 misprints a vaguely related subtle chess problem (bishop at KB7 should be KB8). --rwg wds> and that if M pieces and P pawns have been captured, then at most 2*M+3*P promotions could have happened. And many pawn configurations are impossible unless enough captures happened... John Tromp claimed P<=7728772977965919677164873487685453137329736522=2^152.437 as the result of a computer program he has not described, but this is unlikely to be optimal (assuming it is correct). For somebody determined enough: I think it should be possible to determine the answer accurate to 5% by first creating a good encoding scheme, say which proves P<2^155, and then sampling random positions for each deciding if it really would be reachable. Assuming deciding reachability is actually feasible 99.999% of the time, and assuming P>2^144, we would after 2 million random samples find at least about 1000 reachable positions and at most about 20 whose reachability was unknown. This would be good enough for a 5% accurate (Monte Carlo) estimate. If P<2^150, then the proof tree of chess (at least ignoring 50-move rule) would presumably be about 2^75 positions, suggesting chess might actually be feasibly solvable (?!). -- Warren D. Smith

1 0