June 2012 - mathfun@mailman.xmission.com

[math-fun] The competition (was Re: Wiki article on Circumscribed_circle)
by Robert Munafo 03 Jun '12

03 Jun '12

I read messages in order, so I sent an answer before reading other people's answers. There is some pretty good organized competition for Wikipedia. Everything2 ( http://everything2.com/ ) was established quite a while before Wikipedia, and roughly at the same time Google's search was beginning to compete with Alta Vista. Their philosophy is that everyone can write their own article on each topic, and no-one can edit anyone else's writings. (But you can send messages to other users and hope they like your suggestions.) Since you mention normal journal publishing, I suppose you are familiar with peer review… so I suppose I should mention Scholarpedia ( http://www.scholarpedia.org/ ), and Citizendium ( http://en.citizendium.org/ ) which appears to be similar. These have less content, so there's a good chance they're actually harder to contribute to, but maybe they're just growing slowly. There have been others I've run across in the past 15 years, but my memory's not so good… On 6/3/12, Henry Baker <hbaker1(a)pipeline.com> wrote: > Well, the guys/gals I ran into certainly did a pretty mean goose-step. Life's too short [...] > [...] > I suspect that the Brits will then develop YAWP (Yet Another WikiPedia) for > academics that will have different rules -- rules more akin to normal > journal publishing rules. -- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com

2 1

[math-fun] Maximum number of queens simultaneously on a chessboard from a legal game
by Dan Asimov 03 Jun '12

03 Jun '12

In a casual conversation last night, some friends and I were wondering what is the maximum number of queens that can on the board simultaneously in a legal chessgame. (Assuming of course that both players are cooperating to achieve this result.) There is an obvious upper bound of 18. Is this achievable? --Dan ________________________________________________________________________________________ It goes without saying that .

3 3

[math-fun] The reverse of the bits of a negative integer?
by Henry Baker 03 Jun '12

03 Jun '12

In Lisp, there are a number of operations on the bit representation of 2's complement arbitrary-precision integers. One function missing is that of "reverse" -- probably because no one came up with a good suggestion about what it should mean. If I have a bit _vector_ (finite ordered sequence of bits) in Lisp, the length is well-defined, so the reverse of this bit vector is also well-defined; Lisp therefore does define the reverse of a bit _vector_. For all finite bit-vectors x, we have the nice properties that reverse(reverse(x))=x; for the zero-length bit-vector x, reverse(x)=x. What now should be the definition for the reverse of the bits of an integer? If the integer is non-negative, then the function "integer-length(n)" returns the number of bits necessary to hold the integer n; if we take integer-length(n) as the length of the appropriate bit-sequence, then we get a well-defined result. In particular, for n>0, reverse(n) is always odd, because the high-order bit has become the low order bit; for n=0, where integer-length(0)=0, so we have a zero-length sequence which is an identity for reverse -- i.e., reverse(0)=0. So at least for odd n, n>0, reverse(reverse(n))=n, which is comforting. Unfortunately, for even n, this definition of reverse(n) loses all the information about the number of low order 0's in the number, and so reverse(reverse(n))/=n for all n. In order to get reverse(reverse(n))=n for all n>=0, reverse(n) needs to be 1-1 -- i.e., an injection -- i.e., it doesn't lose any information. If we consider the the bits of the bignum n>=0 to be a polynomial p(x) with coefficients in GF(2), then there _are_ no negative elements, and the above definition works when p(0)=1. After all, we reverse the list of polynomial coefficients all the time -- e.g., reversing a polynomial inverts all the roots: r->1/r; this requires r/=0 <=> p(0)=1. So this representation gains us no new insight. But what should the reverse(n) for the 2's complement integer n<0 be? I think we still need reverse(reverse(n))=n, so we obviously need to have reverse(x)<0 for some x's. Since the positive integers are already accounted for, such x's must be <0. So reverse(n)<0 for n<0. It would be nice if integer-length(reverse(n)) is O(integer-length(n)). If we consider n<0 as simply an infinite bit string, perhaps reverse(n)=reverse(n')', i.e., we first complement n = n' = lognot(n), compute reverse(n'), and then lognot again to produce reverse(n')'. This definition gets us reverse(-1)=reverse((-1)')'=reverse(0)'=0'=-1. But what other properties do we want reverse(x) to have/preserve? I haven't looked at 2-adic numbers; perhaps there is an insight there? Does anyone here have any thoughts?

4 5

Re: [math-fun] Wiki article on Circumscribed_circle
by Steve Witham 03 Jun '12

03 Jun '12

>From: Henry Baker <hbaker1(a)pipeline.com> > >Let me get this straight: Wikipedia is the one place in the world >where plagiarism is not only ok, but required! Like other encyclopedias, it's a place for review articles about other people's work. I suppose if you quote someone directly you're supposed to use quotation marks. >I try not to waste my time & my readers' time by repeating stuff >other people have already said much better than I could. You might preface this, "As a content creator,..." To use a term of the derivative metapeople. It seems to me an encyclopedia is mainly for people who don't know the literature on the subject they want to read about. >Perhaps Wikipedia isn't the place for me? Not for when you want to contribute original work. Wikipedia is for people taking the role of encyclopedia review article writers. >From: Dave Dyer <ddyer(a)real-me.net> > >One of the things "the rules" try hardest to prevent is anything >that could be construed as self promotion. Unfortunately that rules >out a lot of useful content along with the meaningless drivel that >is it's target. Yes. Looking at this tradeoff two ways, 1) Wikipedia doesn't aim to be a repository of useful content, it aims to be an encyclopedia. 2) by using a rule like this, they definitely filter out a *quantity* of useful information but probably improve the ratio of useful to useless. Another cost of a rule is the work required to make the call, counting hours spent by anyone disputing it. If the filtering weren't simple, filtering wouldn't get done. Also, if it weren't simple, readers wouldn't have a reliable way to know what to expect about the quality. Impartiality per se isn't what I want as a reader, but simply-enforced "impartiality" is a lot easier for me to base my expectations on. It's more informative *about* the quality. If Wikipedia were interesting to a lot fewer readers, then it would also be interesting to a lot fewer writers, and the quantity would *also* go down, regardless of the rules. Interesting having the flip of the conversation about whether Wikipedia must suck because they let anyone come and write whatever they want. --Steve

2 1

Re: [math-fun] The reverse of the bits of a negative integer?
by Steve Witham 03 Jun '12

03 Jun '12

>From: Gareth McCaughan <gareth.mccaughan(a)pobox.com> > >In general, perhaps we "should" adopt the convention that a positive >number ends with an infinite string of 0s, and a negative number ends >with an infinite string of 1s; then negation is just bitwise complement, >and reversal commutes with negation. Well, it's the "true meaning of two's complement." +1 = ...001.000... = ...000.111... +0 = ...000.000... = ...111.111... = -0 -1 = ...111.000... = ...110.111... In each case, the representation the left is just the "rounding up" of the representation on the right. So two's-complement notation just means choosing the rounded-up representation. But, I agree with Gareth that when reversing negative number, we "should" work in the form on the right. But we can express the inputs and outputs in the form on the left. >From: Eugene Salamin <gene_salamin(a)yahoo.com> > >The proper definition of bit-reversal depends on the application for >which it is needed.? In the case of Fast Fourier Transform, the >index is an N-bit integer that may be regarded as a modulo 2^N >pointer into the numeric array of length 2^N.? It is automatically >twos-complement.? Here the proper bit reversal consists of reversing >all N bits, including leading zeros. You could reflect around the binary point, then multiply by 2^N. We "should" say these are the "correct" way. Or, you could divide by 2^(N/2), reflect, and multiply by 2^(N/2), by analogy with reflecting space around a point other than the origin...if only you knew N was even... Gee, what's the value of the polynomial made out of the reversed bits of the square root of two? --Steve

1 0

[math-fun] Another sequence: reverse(n)
by Henry Baker 03 Jun '12

03 Jun '12

;;; Common Lisp definition for reverse(n), which permutes the integers, but integer_length(reverse(n))=integer_length(n). (defun myreverse (n) ;;; This definition makes no pretense at efficiency. ;;; I just wanted to get the values correct. ;;; Compute a character string of bits; reverse that; & convert back to a number. (cond ((minusp n) (- (myreverse (- n)))) ((zerop n) 0) ((evenp n) (* 2 (myreverse (/ n 2)))) (t (values (read-from-string (concatenate 'string "#b" ; interpret number as binary (reverse (format nil "~b" n)))))))) (defun test-myreverse (n) (dotimes (i n) (let* ((ri (myreverse i))) (unless (= i ri) (print `(,i ,ri)))))) ;;; In the range 0-63, these are the entries that are _not_ fixed points for reverse(n): (11 13) (13 11) (19 25) (22 26) (23 29) (25 19) (26 22) (29 23) (35 49) (37 41) (38 50) (39 57) (41 37) (43 53) (44 52) (46 58) (47 61) (49 35) (50 38) (52 44) (53 43) (55 59) (57 39) (58 46) (59 55) (61 47)

1 0

Re: [math-fun] Checkers "solved"?
by Guy Haworth 03 Jun '12

03 Jun '12

Interesting positions, Warren! http://library.msri.org/books/Book29/files/schaeffer.pdf quotes Allis' 1994 definition of three levels of solving the game: 1) 'Ultra-weakly solved': the game-theoretic value of the opening position has been determined 2) 'Weakly solved': the game is ultra-weakly solved and a a strategy exists for achieving the game-theoretic value from the opening position, assuming reasonable computing resources 3) 'Strongly solved': For all possible positions, a strategy is known for determining the game-theoretic value, assuming reasonable computing resources One might criticise the definitions for including the word 'reasonable' but I don't really see any alternative. Allis cited the game of Hex as ultra-weakly solved but not weakly-solved. Nim and Tic-tac-toe are strongly solved. http://en.wikipedia.org/wiki/Solved_game gives other examples. Jonathan claimed on 2007-04-29 to have weakly solved Checkers, finding the opening position to be drawn and determining a strategy for both players to do so. For a game to be 'weakly solved' but not 'strongly solved', the proof must rely on the fact that some positions cannot be reached by 'minimaxing' play from the opening position. It would be interesting to hear Jonathan's own response to your position ... but I think he will say that - backing up your position to previous positions ... White would have easily won from those positions (by what is today a not very deep computer-search of the options). That is to say, if White is playing for the win, White would not have got itself into your position from a previous position. Nice try though! Guy Message: 1 Date: Sat, 2 Jun 2012 11:38:13 -0400 From: Warren Smith <warren.wds(a)gmail.com> To: math-fun <math-fun(a)mailman.xmission.com> Subject: [math-fun] Checkers "solved"? Think so. Message-ID: <CAAJP7Y29d9C-EBivmmc+zPDFd46BqvfQSqymwT02EpwO=KJthQ(a)mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1 Perhaps this has some amusement value. Can these examples be made even more dramatic than they are? ---- Here is a checkers position I created to annoy Jonathan Schaefer, leader of the "chinook" project which solved the game of checkers (forced draw). View in constant-width font. .W.W.W.W W.W.W.w. .w.w.w.. ........ ...b.... ........ ...W.... ........ W=white king, w=white checker, white is moving North. White to move. ?In this position, white has 8 kings plus 4 checkers, while black has only a single checker. Nevertheless, black soon wins the game. Here's basically the same thing backed up a little to make it a bit more amusing, black to move and win: .W.W.W.W W.W.W.w. .w.w.... ..b...B. .......B ........ ...W.w.. ........ In view of this, should the Chinook team still contend they solved checkers? I took a look at their paper in Science and it looks to me like they really did solve checkers. Their strategy was to use chinook search + heuristic evaluator + perfect endgame tables. ? They assumed (perhaps falsely) that a heuristic eval > X was a "win" and a heuristic eval < -X was a "loss." They then pseudo-solved the game. ?Then they increased the value of X and did it again. ?They only claimed a full proof once X had increased all the way to a genuine win. ? So this kind of counterexample shows you need to go a pretty long way and cannot cheat by using too-small X... but the chinook team claims not to have cheated (although I think their initial efforts had cheated in this way). Warren D. Smith http://RangeVoting.org

1 0

Re: [math-fun] Wiki article on Circumscribed_circle
by Henry Baker 02 Jun '12

02 Jun '12

Let me get this straight: Wikipedia is the one place in the world where plagiarism is not only ok, but required! So if I lie, and say that I learned it from Zeus/Apollo/Apocrypha/John Doe, then it's ok? BTW, I did get one snippy remark: "We get a lot of academics here. Alas, some of them are completely ineducable. If you take the time to learn how Wikipedia works, it will be a big help to you." I guess the reason my previous edits to other articles got through is that I didn't explicitly claim anything novel, even though there was some novelty there. I try not to waste my time & my readers' time by repeating stuff other people have already said much better than I could. Perhaps Wikipedia isn't the place for me? At 02:57 PM 6/2/2012, Mike Stay wrote: >Until it's been published in a journal somewhere, you can't. >Otherwise it's excluded as "original research". > >On Sat, Jun 2, 2012 at 2:07 PM, Henry Baker <hbaker1(a)pipeline.com> wrote: >> Does anyone know how to deal with Wikipedia? >> >> I tried this morning to make a very modest edit to the Circumscribed_circle article, >> and someone else keeps reverting it back. >> >> All I'm trying to do is to add an external link to my article about >> computing the circumcenter coordinates using complex numbers: >> >> http://home.pipeline.com/~hbaker1/FAQ-circumcircle.txt >> >> My result is a generalization of the classic formula: >> >> R=abc/(4 A), where R is the radius of the circumcircle, a,b,c are the side-lengths, and A is the area. >> >> Now consider R,a,b,c to be "vectors" in the complex plane -- i.e., complex numbers. >> >> Then the previous formula is |R|=|a||b||c|/(4 A) >> >> My formula is: >> >> R = -ia'bc/(4 A) >> >> where i=sqrt(-1), and a' is conjugate(a). >> >> Note that the multiplications in my formula are now _complex_ multiplies. >> >> I think that this is a cool formula, and I believe that Gosper thought so, too. >> >> Can someone here please help me make this change? >> >> Thanks. >-- >Mike Stay - metaweta(a)gmail.com >http://www.cs.auckland.ac.nz/~mike >http://reperiendi.wordpress.com

3 2

Re: [math-fun] math-fun Digest, Vol 112, Issue 5
by Steve Witham 02 Jun '12

02 Jun '12

>From: Dave Dyer <ddyer(a)real-me.net> > >Wiki is infested with content nazis who are intent on enforcing "the rules". You don't need to put quotes around it, there really are a few rules of Wikipedia, and no-original-research is one of them. I think it's a little rude that nobody told Henry why they were reverting his edit, but that's the attitude a lot of open-source projects have: we'd love you to contribute, but take it on yourself to learn the rules first. >Overall, it's probably a necessary affliction to prevent it from becoming >just another platform for spam. Not only that, it's to keep it an encyclopedia, and to improve the quality. --Steve

1 0

Re: [math-fun] The reverse of the bits of a negative integer?
by Henry Baker 02 Jun '12

02 Jun '12

Perhaps we should count the low order zero bits, remove them, reverse the rest of the number as below, and then put them back, i.e., For even n>0, reverse(n)=2*reverse(n/2). This works for polynomials over GF(2), as well. For n<0, we can still define reverse(n)=reverse(n')', where n'=lognot(n). At 11:32 AM 6/2/2012, Henry Baker wrote: >In Lisp, there are a number of operations on the bit representation of 2's complement arbitrary-precision integers. > >One function missing is that of "reverse" -- probably because no one came up with a good suggestion about what it should mean. > >If I have a bit _vector_ (finite ordered sequence of bits) in Lisp, the length is well-defined, so the reverse of this bit vector is also well-defined; Lisp therefore does define the reverse of a bit _vector_. For all finite bit-vectors x, we have the nice properties that reverse(reverse(x))=x; for the zero-length bit-vector x, reverse(x)=x. > >What now should be the definition for the reverse of the bits of an integer? > >If the integer is non-negative, then the function "integer-length(n)" returns the number of bits necessary to hold the integer n; if we take integer-length(n) as the length of the appropriate bit-sequence, then we get a well-defined result. In particular, for n>0, reverse(n) is always odd, because the high-order bit has become the low order bit; for n=0, where integer-length(0)=0, so we have a zero-length sequence which is an identity for reverse -- i.e., reverse(0)=0. > >So at least for odd n, n>0, reverse(reverse(n))=n, which is comforting. > >Unfortunately, for even n, this definition of reverse(n) loses all the information about the number of low order 0's in the number, and so reverse(reverse(n))/=n for all n. > >In order to get reverse(reverse(n))=n for all n>=0, reverse(n) needs to be 1-1 -- i.e., an injection -- i.e., it doesn't lose any information. > >If we consider the the bits of the bignum n>=0 to be a polynomial p(x) with coefficients in GF(2), then there _are_ no negative elements, and the above definition works when p(0)=1. After all, we reverse the list of polynomial coefficients all the time -- e.g., reversing a polynomial inverts all the roots: r->1/r; this requires r/=0 <=> p(0)=1. So this representation gains us no new insight. > >But what should the reverse(n) for the 2's complement integer n<0 be? > >I think we still need reverse(reverse(n))=n, so we obviously need to have reverse(x)<0 for some x's. Since the positive integers are already accounted for, such x's must be <0. So reverse(n)<0 for n<0. > >It would be nice if integer-length(reverse(n)) is O(integer-length(n)). > >If we consider n<0 as simply an infinite bit string, perhaps reverse(n)=reverse(n')', i.e., we first complement n = n' = lognot(n), compute reverse(n'), and then lognot again to produce reverse(n')'. > >This definition gets us reverse(-1)=reverse((-1)')'=reverse(0)'=0'=-1. > >But what other properties do we want reverse(x) to have/preserve? > >I haven't looked at 2-adic numbers; perhaps there is an insight there? > >Does anyone here have any thoughts?

3 2