From: gls@odyssey.ATT.COM (Col. G. L. Sicherman) Subject: Re: sylver coinage Date: 1 Jun 89 18:51:28 GMT
Update to Sylver Coinage: I just stumbled over Guy's "Unsolved Problems" column for December 1987. A researcher named Francis Voelkle has been coming down hard on the problem with a VAX 8600. He found (as I did) that {10,12,18}, {10,16,24}, and {12,15,18} are all "P." So there are fewer gaps to fill in the table....
From: gls@odyssey.att.com (Col. G. L. Sicherman) Subject: monsters in sylver coinage Date: 5 Mar 90 15:18:53 GMT Organization: Jack of Clubs Precision Instruments Co.
I've been doing some Sylver Coinage computations -- on slow micros and an even slower mini. I've been getting nowhere with certain non-ender generators. If anybody has some reasonably fast hardware, I'd appreciate knowing about these positions: {6,22,38} - 4 is obviously a good reply; does there exist a good _odd_ reply? If so, it's greater than 446. {8,30,34,52} - if there's a good reply, it's greater than 214. {14,18,26,38} - if there's a good reply, it's greater than 222. It's known that {8,34,36} is P (in Guy's terminology), but I have not yet found answers to {8,34,36,54} or {8,34,36,62}. Can anybody help? Explanation: In Sylver Coinage, two players take turns picking a number. The loser is the first to pick 1 or a number expressible as a sum of some previously picked numbers, with repetitions. The game was invented by J. H. Conway and named after J. J. Sylvester. -:- "Never invite a Warpsmith to dinner."
From: gls@odyssey.att.com (Col. G. L. Sicherman) Newsgroups: sci.math Subject: postscript to monsters Date: 9 Mar 90 14:31:55 GMT
Since my previous posting, I have found that 469 is a winning move in {6,22,38}. There may be others. Anyway, {6,22,38,469} certainly qualifies as a monster, overshadowing even {10,14,26,293}. -:- "And a forest grows up From the dirt on the floor..." --F. Zappa, "It Just Might Be a One-Shot Deal"
Newsgroups: sci.math,rec.puzzles From: gls@hrcms.ATT.COM (Col. G. L. Sicherman) Subject: Sylver Coinage news Organization: F. K. Dingy & Son Date: Tue, 8 Feb 1994 02:16:07 GMT
It has occurred to me that I shall never get around to publishing my 1991 paper on Sylver Coinage, so I may as well offer it to the Net. If you'd like a copy, drop me a line at gls@hrcms.ATT.COM, specifying LaTeX or PostScript. What is Sylver Coinage? It's a two-player game of coining money. On your turn you must coin a denomination that cannot be expressed as a sum (with repetitions) of previous denominations. For instance, if nickels and dimes have already been coined, you may not coin quarters, since nickels and dimes suffice to make up 25 cents. The players who coins "1" loses. (Otherwise the first player would say "1" and win at once.) Of course all denominations must be positive integers. The game was invented by J. H. Conway, so naturally you'll find a chapter on it in _Winning Ways._ Every game of Sylver Coinage must end, because ... well, I'll let you figure out why. The body of knowledge about Sylver Coinage consists of a few remarkable general theorems, some empirical results for certain game positions, a lot of plausible conjectures (most of them disproven), and some simple positions that have not been solved but would very much like to be! My paper provides a couple of new (and minor) general results, and plenty of new empirical results. -:- "'PATAGEOMETRY: The study of those mathematical properties that remain invariant under brain transplants." -- Col. G. L. Sicherman gls@hrcms.ATT.COM
Newsgroups: sci.math From: gls@hrcms.att.com (The Pied Typer) Subject: news of Sylver Coinage? Organization: Save the Monopoles Foundation Date: Thu, 19 Oct 1995 14:25:37 GMT
Has anybody turned up new results in Sylver Coinage since my 1991 paper? I recently searched up to 4,000 without finding an odd win in {8,26,30}, and have confirmed most of my old results, but that's about it. It would be nice to hear of a solution to {8,30,34}.... -:- 'PATAGEOMETRY: The study of those mathematical properties that remain invariant under brain transplants. -- Col. G. L. Sicherman gls@hrcms.ATT.COM
Newsgroups: sci.math From: gls@hrcms.att.com (The Dangling Conversationalist) Subject: Re: Sylver Coinage - {10,26,44} is N Organization: The Ned Stokes Cabal Date: Thu, 26 Oct 1995 04:49:03 GMT
I have a new result in Sylver Coinage: {10,26,44} [2383] So far as I know, this is the highest known winning move in a small position. The previous record was {14,26,32} [1513]. I would appreciate hearing from anybody who can confirm or contradict the new result. -:- She was now working with fourteen pairs at once, and Alice couldn't help looking at her in great astonishment. "How _can_ she knit with so many?" the puzzled child thought to herself. "She gets more and more like a porcupine every minute!" "Can you row?" the Sheep asked, handing her a pair of knitting needles as she spoke. --Lewis Carroll, _Through the Looking-Glass_ -- Col. G. L. Sicherman gls@hrcms.ATT.COM
Newsgroups: sci.math From: gls@hrcms.att.com (A deaf heart, a loose liver) Subject: Sylver Coinage - {8,26,30} has an odd winning move Organization: Kentucky Fried Fox Date: Tue, 5 Dec 1995 02:57:14 GMT
I've just pulled another thorn in the analysis of {8}: {8,26,30} [12,4363] This increases our hope of solving {8,30,34}. It would be a comfort if some bright mathematics programmer set about to confirm these results (or add to them!). So far as Richard Nowakowski (the Keeper of the Sylver) knows, nobody is working on Sylver Coinage but me. You can still get my 1991 paper, in TeX, PostScript, or paper, by writing me. It has not appeared in print and probably never will. -:- K Cobalt's metal, hard and shining, Cobol's wordy and confining. KOBOLDS topple when you strike them-- Don't feel bad, it's hard to like them. --The Roguelet's ABC -- Col. G. L. Sicherman gls@hrcms.ATT.COM
From: gls@hrcms.att.com (World's Largest Leprechaun) Newsgroups: sci.math Subject: Sylver Coinage: {8,30,34} is N Date: 19 Feb 1996 00:41:45 GMT Organization: Save the Monopoles Foundation
In J. H. Conway's game of Sylver Coinage, the position {8, 30, 34} is "N"; that is, the next player can obtain a winning position. The unique winning move is 49337. This completes the open second-order analysis of {8}. -:- `Where be the Parable you normally 'ave on your shoulder, Large John?' Asks Blind Jew looking up. `Never ye mind' reponds Large John `And anyways where be your white stick?' `'Ow the 'ell should I know when oi can't see?' --John Lennon In His Own Write -- Col. G. L. Sicherman gls@hrcms.ATT.COM
From: sicherman@lucent.com (The Hobgoblin of the Net) Newsgroups: sci.math Subject: Late News of Sylver Coinage Date: 19 Jun 1996 20:00:16 GMT Organization: Save the Dodoes Foundation
I have written a sequel to my 1991 paper about Sylver Coinage. It contains results since 1991, mostly from 1995 and 1996, and is probably the last paper I will write on the subject. If you'd like a copy, write for one, specifying LaTeX, PostScript, or paper. -:- 'PATAGEOMETRY: The study of those mathematical properties that remain invariant under brain transplants. -- Col. G. L. Sicherman sicherman@lucent.com
From: mathwft@math.canterbury.ac.nz (Bill Taylor) Date: 29 Feb 2000 04:10:20 GMT Newsgroups: sci.math,sci.logic,rec.games.abstract Subject: Sylver Coinage - a constructivist conundrum?
This essay is really to ask a certain question about constructivism, and constructive proofs. But it also provides a handy place to mention the game "Sylver Coinage". My musing began when Keith Ramsay made a nice distinction between *construcive* solutions to math questions, and *explicit* solutions. For the most part, the latter are special cases of the former, whereby you actually *produce* a "closed formula" (whatever that may be in context). Whereas a constructive solution need only be a recipe whereby you can show that you could *get* an explicit solution if you wanted to. It seems to me that the distinction between explicit and constructive is a good one. And in fact, as we've discussed before, constructive but non-explicit solutions can often arise in some contexts, particularly finite games, which most mathematicians would call NON-constructive solutions, even though they are automatically constructive solutions via finiteness, just not very very helpful ones! Classic cases are Hex, where the usual strategy-stealing method proves First has a winning strategy; and Chomp on a finite rectangle, where the corner-stealing argument does likewise. These proofs are constructive (in the technical logic sense), while being totally non-explicit. Now I want to ask about unbounded-length games. Not *too* infinite, or we'll get into far too much of a mess, but not too *finite* either, or the usual constructive-by-finiteness proof will be easily extendible to the full game. For example; consider Nim, but where First picks a bunch of pile numbers, and then Second gets to decide who makes the first play in the nimming part of the game. Though this "you cut I'll choose" starting mechanic is often a good way to nullify first-move advantage, it doesn't here, obviously. One can easily prove (in the usual way) that Second has a winning strategy; and this proof is constructive, even though the length of the game is unbounded. Because the game is bounded after the first choice is made, it's just a one-quantifier extension of the standard finite game, and so easily constructivised. So that's not nearly unbounded enough. Now we come to "Sylver Coinage", a fascinating game discussed at great length in the bible - "Winning Ways", by Berlekamp, Conway and Guy. In turn, each player picks a natural number, which must not be a sum of (any positive number of) previous picks. And it is illegal to pick 1; plural numbers only. You lose if you can't make any pick. So if First picks 2, or 3, then Second can pick the other, and now as all plurals are a sum of 2's and 3's, First can't move, and thus loses. So First might pick 4, then second better not pick 2 or 3, just as before; but neither should he pick 5, or First will pick 11, cutting out all numbers except 2,3 and 6,7, and whatever Second does now First can match with its mate. In general, we can play the game with any finite combination of starting numbers already "picked" on the table. The bible notes that the game is unsolved in general, even though some starting positions are known to be losers, and some winners. The bible also notes that a solution can be proven to exist, even though it may not be "writable down" in some sense. One of the nice things about this game, is that it is not only unbounded, but the first moves can be played such that it is *still* unbounded. It is unboundedly unbounded, as they put it. Not only that, but also the first *unboundedly many* moves can be played so that it is *still* unbounded, so it is unboundedly unboundedly unbounded; and it's unboundedly that as well, and unboundedly *that*, and so on unboundedly... in very ordinal-like fashion. Nonetheless there *are* starting move sequences which *do* lead to bounded length tail games, such as the {4,5,11} above, and it was shown by Sylvester that eventually any choice sequence *must* lead to this situation, and that any actual play of the game *must* end. It's in honor of Sylvester that they give it the name, and "coinage" because it is very neatly presented as a coinage denomination problem. SYLver Coinage is a neat witty mis-spelling of the type so common in the bible; though I think they missed a trick by not calling it "Sylver COYnage", on the grounds that the players very commonly start by coyly dancing around picking very factorful numbers, before slowly getting to grips with more nearly co-prime ones, whence it soon ends. So the game is a play-finite one; just incredibly well unbounded. Now, we come to my constructivist query. I'll put on the same simple "you cut I'll choose" starting condition, and see what we get. Let First choose any finite starting set of picks, for the start position; then let Second choose who will be the first player to start the adding of new numbers alternately one at a time. Then they play out the game in the standard manner. This new game has an OBVIOUS stratgey-stealing proof that it is a win to player Second! And yet, I believe this is a non-constructive proof, and one that cannot be simply made constructive, (unlike the unbounded Nim above). Not yet, anyway. Note that this "cut-&-choose" version is not constructively unsolved merely because of the unboundedness, nor even subsequently because of the unexplicitness of the standard game - for just consider "cut-&-choose" 2-dimensional Chomp, which is also largely lacking explicit solutions:- (A) In this, the first player chooses a finite jagged rectangle as the starting position, and Second chooses who'll be starter. I think that this is easily constructively proved winnable by Second. (B) But "cut-&-choose" Sylver Coinage is NOT constructively thus proved to be a win to Second, I suspect. Just classically so. Am I right in these last two comments? Would some constructivist expert please tell me? If so, it is intriguing that essentially the same proof can be regarded constructively in one case but not in the other, even though both games are finite but unbounded! ------------------------------------------------------------------------------- Bill Taylor W.Taylor@math.canterbury.ac.nz ------------------------------------------------------------------------------- MATH:- The discovery, clarification and rigorous study of precise relationships in number, pattern, and structure. -------------------------------------------------------------------------------
From: ikastan@uranus.uucp (Ilias Kastanas) Date: 29 Feb 2000 18:40:23 GMT Newsgroups: sci.math,sci.logic,rec.games.abstract Subject: Re: Sylver Coinage - a constructivist conundrum?
In article <89fgrc$lar$1@cantuc.canterbury.ac.nz>, Bill Taylor <mathwft@math.canterbury.ac.nz> wrote: @This essay is really to ask a certain question about constructivism, @and constructive proofs. But it also provides a handy place to mention @the game "Sylver Coinage". What?? You are not interested in bending Time to get an excluded-middle proof that Space does not exist, Bill? @My musing began when Keith Ramsay made a nice distinction between @*construcive* solutions to math questions, and *explicit* solutions. @For the most part, the latter are special cases of the former, whereby you @actually *produce* a "closed formula" (whatever that may be in context). @Whereas a constructive solution need only be a recipe whereby you can @show that you could *get* an explicit solution if you wanted to. It seems @to me that the distinction between explicit and constructive is a good one. @ @And in fact, as we've discussed before, constructive but non-explicit @solutions can often arise in some contexts, particularly finite games, @which most mathematicians would call NON-constructive solutions, even though @they are automatically constructive solutions via finiteness, just not very @very helpful ones! Classic cases are Hex, where the usual strategy-stealing @method proves First has a winning strategy; and Chomp on a finite @rectangle, where the corner-stealing argument does likewise. @These proofs are constructive (in the technical logic sense), @while being totally non-explicit. @ @Now I want to ask about unbounded-length games. Not *too* infinite, @or we'll get into far too much of a mess, but not too *finite* either, @or the usual constructive-by-finiteness proof will be easily extendible @to the full game. For example; consider Nim, but where First picks a bunch @of pile numbers, and then Second gets to decide who makes the first play @in the nimming part of the game. Though this "you cut I'll choose" @starting mechanic is often a good way to nullify first-move advantage, @it doesn't here, obviously. One can easily prove (in the usual way) that @Second has a winning strategy; and this proof is constructive, even though @the length of the game is unbounded. Because the game is bounded after @the first choice is made, it's just a one-quantifier extension of @the standard finite game, and so easily constructivised. Seems to be the same situation as Chomp (choose-a-rectangle), or nxn Hex. Or checkers... Go... You know. Trivial games. @So that's not nearly unbounded enough. @ @ @Now we come to "Sylver Coinage", a fascinating game discussed at great @length in the bible - "Winning Ways", by Berlekamp, Conway and Guy. @ @In turn, each player picks a natural number, which must not be a sum of @(any positive number of) previous picks. And it is illegal to pick 1; @plural numbers only. You lose if you can't make any pick. @ @So if First picks 2, or 3, then Second can pick the other, and now as @all plurals are a sum of 2's and 3's, First can't move, and thus loses. @So First might pick 4, then second better not pick 2 or 3, just as @before; but neither should he pick 5, or First will pick 11, cutting @out all numbers except 2,3 and 6,7, and whatever Second does now First @can match with its mate. @ @In general, we can play the game with any finite combination of starting @numbers already "picked" on the table. The bible notes that the game is @unsolved in general, even though some starting positions are known to be @losers, and some winners. The bible also notes that a solution can be @proven to exist, even though it may not be "writable down" in some sense. Yes. Think of the reals, w^w, as runs of Sylver Coinage. If a finite integer sequence s is a win for player I, put the basic open neighborhood U_s ={reals extending s} into A; likewise if s breaks the rules and it was II who first broke them. So A is an open set, and the game an open game. (Indeed, by Sylvester, the corresponding set B for II is A's complement, i.e. the game is clopen). Now we appeal to the theorem "for any set X, open games on X^w are deter- mined". So a solution (winning strategy) exists... but that's that. Recall the well-known proof: if I does not have a winning strategy then for any move x1 II has a reply y1 such that from there on, I doesn't have a w.s. So for any x2 there is a y2 that does likewise... and so on. This strategy for II is a winning one: if x1,y1,x2,y2,... were in A some initial segment would be an s, and from there on I would have had a w.s. -- namely, any strategy. The non-constructiveness of this is clear. (Indeed, the theorem is equivalent to the full Axiom of Choice). @One of the nice things about this game, is that it is not only unbounded, @but the first moves can be played such that it is *still* unbounded. @It is unboundedly unbounded, as they put it. Not only that, but also @the first *unboundedly many* moves can be played so that it is *still* @unbounded, so it is unboundedly unboundedly unbounded; and it's unboundedly @that as well, and unboundedly *that*, and so on unboundedly... @in very ordinal-like fashion. @ @Nonetheless there *are* starting move sequences which *do* lead to @bounded length tail games, such as the {4,5,11} above, and it was @shown by Sylvester that eventually any choice sequence *must* lead @to this situation, and that any actual play of the game *must* end. @It's in honor of Sylvester that they give it the name, and "coinage" @because it is very neatly presented as a coinage denomination problem. @SYLver Coinage is a neat witty mis-spelling of the type so common in @the bible; though I think they missed a trick by not calling it @"Sylver COYnage", on the grounds that the players very commonly start @by coyly dancing around picking very factorful numbers, before slowly @getting to grips with more nearly co-prime ones, whence it soon ends. @ @So the game is a play-finite one; just incredibly well unbounded. @ @ @Now, we come to my constructivist query. I'll put on the same simple @"you cut I'll choose" starting condition, and see what we get. @ @Let First choose any finite starting set of picks, for the start position; @then let Second choose who will be the first player to start the adding @of new numbers alternately one at a time. Then they play out the game @in the standard manner. @ @This new game has an OBVIOUS stratgey-stealing proof that it is a win @to player Second! And yet, I believe this is a non-constructive proof, @and one that cannot be simply made constructive, (unlike the unbounded @Nim above). Not yet, anyway. Well, in the cut-and-choose version of any game G, I never has a winning strategy (no starting position of G has w.s.'s for both sides!)... so cut-and-choose is determined IFF II has a w.s. for it IFF G is determined for every starting position. If our proof of the latter was non-constructive, then no wonder!... @Note that this "cut-&-choose" version is not constructively unsolved @merely because of the unboundedness, nor even subsequently because of @the unexplicitness of the standard game - for just consider "cut-&-choose" @2-dimensional Chomp, which is also largely lacking explicit solutions:- @ @(A) In this, the first player chooses a finite jagged rectangle as @ the starting position, and Second chooses who'll be starter. I think @ that this is easily constructively proved winnable by Second. @ @(B) But "cut-&-choose" Sylver Coinage is NOT constructively thus proved @ to be a win to Second, I suspect. Just classically so. @ @Am I right in these last two comments? @Would some constructivist expert please tell me? @ @ @If so, it is intriguing that essentially the same proof can be regarded @constructively in one case but not in the other, even though both games @are finite but unbounded! (A) is clopen (boldface Delta-0-1), like before. Actually, it is just Delta-0-1 (recursive); that's easy. (B) seems to need "for all m, m is a sum of elements from s"... but no, no quantifier is needed; it is enough that s contain 2 and 3 (and that no member of s is a sum of prior ones). So (B) is recursive too. Now general theory says that there exists a hyperarithmetical (Delta-1-1) w.s. ... to do better it takes specifics. E.g. (A) does have a recursive w.s., due to the simple structure of its Delta-0-1 set. Establishing a recursive w.s. for (B) would need, I imagine, some breakthrough -- something particular about the problem. Ilias
From: ah170@FreeNet.Carleton.CA (David Libert) Date: 1 Mar 2000 08:33:24 GMT Newsgroups: sci.math Subject: Re: Sylver Coinage - a constructivist conundrum?
Ilias Kastanas (ikastan@uranus.uucp) writes: > In article <89fgrc$lar$1@cantuc.canterbury.ac.nz>, > Bill Taylor <mathwft@math.canterbury.ac.nz> wrote: > @This essay is really to ask a certain question about constructivism, > @and constructive proofs. But it also provides a handy place to mention > @the game "Sylver Coinage". > > > What?? You are not interested in bending Time to get an > excluded-middle proof that Space does not exist, Bill? > > > @My musing began when Keith Ramsay made a nice distinction between > @*construcive* solutions to math questions, and *explicit* solutions. > @For the most part, the latter are special cases of the former, whereby you > @actually *produce* a "closed formula" (whatever that may be in context). > @Whereas a constructive solution need only be a recipe whereby you can > @show that you could *get* an explicit solution if you wanted to. It seems > @to me that the distinction between explicit and constructive is a good one. > @ > @And in fact, as we've discussed before, constructive but non-explicit > @solutions can often arise in some contexts, particularly finite games, > @which most mathematicians would call NON-constructive solutions, even though > @they are automatically constructive solutions via finiteness, just not very > @very helpful ones! Classic cases are Hex, where the usual strategy-stealing > @method proves First has a winning strategy; and Chomp on a finite > @rectangle, where the corner-stealing argument does likewise. > @These proofs are constructive (in the technical logic sense), > @while being totally non-explicit. Yes, but even these easy starting cases contain some interesting subtle points. HA is Heyting arithmetic, the usual axioms of PA but formulated over intuitionistic logic. HA does not prove all instances of Law of the Excluded Middle but it does prove the following universally quantified instance of LEM: (*) (for all x)(for all y) [ x=y or ~x=y]. The HA proof of (*) is by a double induction on x and y: prove (*) by induction on x, where the inductive claims proved along the way are themselves proved by induction on y. I recall I once convinced myself that I could use Kripke models to show that if we drop induction from HA, having just a theory of the definitions of + and *, and probably even add axioms saying we have a commutative ring, over intuitionistic logic (*) is not provable. Indeed the x=0 specialization of (*) is not provable. The proof Bill mentions of determinacy would have a base case of terminal positions. I think over full HA considerations like (*) above give a version of LEM for classifications of who won, but without induction I expect there could be difficulties about LEM failing about who wins. Ie loosely speaking the previous corresponds to "ambigous numbers" that can't be recognized as =0 or ~=0, and similarly there could be "ambiguous terminal positions" about recognizing who has won. Of course this isn't disagreeing with anyting Bill wrote, because constructivism would normally be taken to include induction. But if my suggestion is correct, it is interesting that even at this early stage we require some strength of induction. (Ie, as opposed to the classical version, were (*) and related are trivial without induction). > @Now I want to ask about unbounded-length games. Not *too* infinite, > @or we'll get into far too much of a mess, but not too *finite* either, > @or the usual constructive-by-finiteness proof will be easily extendible > @to the full game. For example; consider Nim, but where First picks a bunch > @of pile numbers, and then Second gets to decide who makes the first play > @in the nimming part of the game. Though this "you cut I'll choose" > @starting mechanic is often a good way to nullify first-move advantage, > @it doesn't here, obviously. One can easily prove (in the usual way) that > @Second has a winning strategy; and this proof is constructive, even though > @the length of the game is unbounded. Because the game is bounded after > @the first choice is made, it's just a one-quantifier extension of > @the standard finite game, and so easily constructivised. Yes, again even the constructive proof is able to "cheat" and get limited cases of LEM, ie each terminal postion is determined. > Seems to be the same situation as Chomp (choose-a-rectangle), > or nxn Hex. > > Or checkers... Go... You know. Trivial games. > > > @So that's not nearly unbounded enough. > @ > @ > @Now we come to "Sylver Coinage", a fascinating game discussed at great > @length in the bible - "Winning Ways", by Berlekamp, Conway and Guy. > @ > @In turn, each player picks a natural number, which must not be a sum of > @(any positive number of) previous picks. And it is illegal to pick 1; > @plural numbers only. You lose if you can't make any pick. > @ > @So if First picks 2, or 3, then Second can pick the other, and now as > @all plurals are a sum of 2's and 3's, First can't move, and thus loses. > @So First might pick 4, then second better not pick 2 or 3, just as > @before; but neither should he pick 5, or First will pick 11, cutting > @out all numbers except 2,3 and 6,7, and whatever Second does now First > @can match with its mate. > @ > @In general, we can play the game with any finite combination of starting > @numbers already "picked" on the table. The bible notes that the game is > @unsolved in general, even though some starting positions are known to be > @losers, and some winners. The bible also notes that a solution can be > @proven to exist, even though it may not be "writable down" in some sense. > > > > Yes. Think of the reals, w^w, as runs of Sylver Coinage. If > a finite integer sequence s is a win for player I, put the basic open > neighborhood U_s ={reals extending s} into A; likewise if s breaks > the rules and it was II who first broke them. So A is an open set, > and the game an open game. (Indeed, by Sylvester, the corresponding > set B for II is A's complement, i.e. the game is clopen). Now we > appeal to the theorem "for any set X, open games on X^w are deter- > mined". > > So a solution (winning strategy) exists... but that's that. > Recall the well-known proof: if I does not have a winning strategy > then for any move x1 II has a reply y1 such that from there on, > I doesn't have a w.s. So for any x2 there is a y2 that does > likewise... and so on. This strategy for II is a winning one: if > x1,y1,x2,y2,... were in A some initial segment would be an s, > and from there on I would have had a w.s. -- namely, any strategy. > > The non-constructiveness of this is clear. (Indeed, the > theorem is equivalent to the full Axiom of Choice). Do you mean use AC to pick the y1, y2 ... for II ? I agree that if we are playing over some complex index set of moves choice may be needed to pick the yi's. The discussion just now was stated for games over w (omega), and this is the correct index set of plays for Bill's game. Use the natural well-ordering on w to pick the yi's. Everything else in the proof seems definable also. So I don't see why, for example this isn't a theorem over classical logic of ZF. On the other hand, there is an LEM issue about this proof that affects an intuitionistic attempt. Namely the division into cases about whether or not I has a winning strategy: ie if I wins, we are done, else construct a w.s. for II. The statement being LEM'd here has a real existential quantifier (there exists a w.s. for I), so LEM can't be readily recovered as it can be for low complexity statements like (*). So as I see it, there is a non-constructive aspect to this proof, but I don't think it is related to AC. > @One of the nice things about this game, is that it is not only unbounded, > @but the first moves can be played such that it is *still* unbounded. > @It is unboundedly unbounded, as they put it. Not only that, but also > @the first *unboundedly many* moves can be played so that it is *still* > @unbounded, so it is unboundedly unboundedly unbounded; and it's unboundedly > @that as well, and unboundedly *that*, and so on unboundedly... > @in very ordinal-like fashion. I haven't read Winning Ways, so I don't know if this is discussed, but Bill's "ordinal" comment can be made very precise. Below Bill mentions that Sylvester proved that each play of the game is finite. So consider the tree of plays of the game (positions of the game being nodes of the tree), and impose a partial ordering on this corresponding to "growing down": later positions of play are deemed "smaller". Sylvester's finite play claim is equivalent to the claim this tree is well-founded. For such trees we can assign an ordinal rank to all nodes: terminal positions are 0, and non-terminal postions are the proper sup of their immediate successor position ranks (successors in play: predecessors in the tree ordering). (Proper sup: the least ordinal strictly greater than the successor ranks). Then among such well-founded games, bounded games where the longest play has exactly n moves (for n finite) are exactly those with opening position having rank n. Games are unbounded iff opeing rank is infinite. Unbounded games where each first move produces a bounded position are exactly those with opening rank omega. Games having a maximum play of length n leading to an unbounded position are rank w+n. "Unboundedly unbounded" corresponds to rank >= w*2. In general any countable ordinal can be realized as the rank of the top of a well-founded tree. From Bill's comments above, I would guess Sylver coinage has been claimed to be of at least rank w^w. It would be interesting to know the exact ordinal. > @Nonetheless there *are* starting move sequences which *do* lead to > @bounded length tail games, such as the {4,5,11} above, and it was > @shown by Sylvester that eventually any choice sequence *must* lead > @to this situation, and that any actual play of the game *must* end. > @It's in honor of Sylvester that they give it the name, and "coinage" > @because it is very neatly presented as a coinage denomination problem. > @SYLver Coinage is a neat witty mis-spelling of the type so common in > @the bible; though I think they missed a trick by not calling it > @"Sylver COYnage", on the grounds that the players very commonly start > @by coyly dancing around picking very factorful numbers, before slowly > @getting to grips with more nearly co-prime ones, whence it soon ends. > @ > @So the game is a play-finite one; just incredibly well unbounded. > @ > @ > @Now, we come to my constructivist query. I'll put on the same simple > @"you cut I'll choose" starting condition, and see what we get. > @ > @Let First choose any finite starting set of picks, for the start position; > @then let Second choose who will be the first player to start the adding > @of new numbers alternately one at a time. Then they play out the game > @in the standard manner. > @ > @This new game has an OBVIOUS stratgey-stealing proof that it is a win > @to player Second! And yet, I believe this is a non-constructive proof, > @and one that cannot be simply made constructive, (unlike the unbounded > @Nim above). Not yet, anyway. Yes I agree with this. Proving the strategy-stealing proof works seems to need LEM over whether the base games wins for I. This is a complex enough statement that we don't seem to get LEM for free. Of course, this LEM instance is just the statement of determinacy for the base game. But as discussed earlier that claim itself has LEM difficulties. > Well, in the cut-and-choose version of any game G, I never > has a winning strategy (no starting position of G has w.s.'s for > both sides!)... so cut-and-choose is determined IFF II has a w.s. > for it IFF G is determined for every starting position. If our proof > of the latter was non-constructive, then no wonder!... Yes, Illias is making the same point. > @Note that this "cut-&-choose" version is not constructively unsolved > @merely because of the unboundedness, nor even subsequently because of > @the unexplicitness of the standard game - for just consider "cut-&-choose" > @2-dimensional Chomp, which is also largely lacking explicit solutions:- > @ > @(A) In this, the first player chooses a finite jagged rectangle as > @ the starting position, and Second chooses who'll be starter. I think > @ that this is easily constructively proved winnable by Second. Yes, even though these solutions are intractible to write out, intuitionism can handle them with inductions over base cases of provable LEM. In these easy cases intuitionism can fake classical well enough, and the harder case of Sylver coinage it seems it can't. > @(B) But "cut-&-choose" Sylver Coinage is NOT constructively thus proved > @ to be a win to Second, I suspect. Just classically so. I would suspect so too. Unfortunately I can only conjecture this, not prove it. > @Am I right in these last two comments? > @Would some constructivist expert please tell me? I am no expert though. For the first claim about Chomp I am more confident, ie the intuitionism can do it. For the second claim about what intuitionism can't do, I am just agreeing that it sure looks that way, but to really say I better call in those experts too. > @If so, it is intriguing that essentially the same proof can be regarded > @constructively in one case but not in the other, even though both games > @are finite but unbounded! Yes. I guess one difference is Chomp is easily provable to have rank w, so handling it only involves inductions up to omega. Sylver coinage has rank well beyond omega, which contributes to the difficulties. It forces us to consider LEM for more complicated statements where we don't get LEM for free. > (A) is clopen (boldface Delta-0-1), like before. Actually, > it is just Delta-0-1 (recursive); that's easy. (B) seems to need > "for all m, m is a sum of elements from s"... but no, no quantifier > is needed; it is enough that s contain 2 and 3 (and that no member > of s is a sum of prior ones). So (B) is recursive too. > > Now general theory says that there exists a hyperarithmetical > (Delta-1-1) w.s. ... to do better it takes specifics. E.g. (A) > does have a recursive w.s., due to the simple structure of its > Delta-0-1 set. Establishing a recursive w.s. for (B) would need, > I imagine, some breakthrough -- something particular about the > > > Ilias Yes. If the result is as we all seem to be conjecturing, we are asking for an independence result, what intuitionism can't prove. I would guess this would be difficult, needing to combine the strangeness of intuitionistic counterexamples to clasical theorems with the technicalities of Sylver coinage. What sort of thing would be such a solution? There are Kripke models, and some other methods I think Kleene gave, using recursion theory? Another question is should an independence proof like this over classical logic be acceptable, or must we have intuitionism in the meta-language also? I never pay much attention to this because I like classical logic and intuitionism is just a side topic for me, so if classical logic says so that's good enough for me. But constructivist purists might not agree. Come to think of it, for simple independence results is there a conservative extension result saying it doesn't matter? Anyway, this whole question of independence results and intuitionistic counterexamples raises another pet peeve of mine. Independence results have a different meta-mathematical flavour from simple straightforward mathematical results. And sure enough, in classical logic the effort to formalize solutions along these lines have uncovered a technical difference reflecting this intuitive difference: the independence results must be proven from a higher consistency strength theory, or must explictly include a consistency premise. I think this technical version in classical logic has brought a lot of clarity to such areas. Now consider how similar issues are dealt with in the intuitionistic literature. So called intuitionistic counterexamples, which seem to be waffling about what is being assumed and what level of machinery is being used. "If we could do this we could decide whether pi has 7 9's, so we can't do this...". So when did you prove we can't decide pi has 7 9's? Ahh we can't do this intuitionistcally? So intuitionism is consistent? How did you prove that, and in what level of language, since you never bothered to specify where you were working? Note that Godel's theorem applies to HA. Are they really trying to tell us intuitionism is inconsistent? Anyway for me a good solution would be Kripke models or something like that (not Brouwer's creative subject etc). But I would be surprised if such a solution were easy. -- David Libert (ah170@freenet.carleton.ca) 1. I used to be conceited but now I am perfect. 2. "So self-quoting doesn't seem so bad." -- David Libert 3. "So don't be a morron." -- Marek Drobnik bd308 rhetorical salvo IRC sig
From: dmoews@xraysgi.ims.uconn.edu (David Moews) Date: 2 Mar 2000 19:03:52 -0800 Newsgroups: sci.math Subject: Re: Sylver Coinage - a constructivist conundrum?
In article <89ikkk$f1u$1@freenet9.carleton.ca>, David Libert <ah170@FreeNet.Carleton.CA> wrote: | I haven't read Winning Ways, so I don't know if this is discussed, but |Bill's "ordinal" comment can be made very precise. Below Bill mentions |that Sylvester proved that each play of the game is finite. So |consider the tree of plays of the game (positions of the game being |nodes of the tree), and impose a partial ordering on this corresponding |to "growing down": later positions of play are deemed "smaller". |Sylvester's finite play claim is equivalent to the claim this tree is |well-founded. For such trees we can assign an ordinal rank to all nodes: |terminal positions are 0, and non-terminal postions are the proper sup of |their immediate successor position ranks (successors in play: predecessors |in the tree ordering). (Proper sup: the least ordinal strictly greater |than the successor ranks). ... | | From Bill's comments above, I would guess Sylver coinage has been |claimed to be of at least rank w^w. It would be interesting to know the |exact ordinal. This ordinal is w^2. For any non-starting position of Sylver Coinage, let g be the gcd of the numbers played. Then there is some N such that all multiples of g bigger than Ng are sums of numbers already played, and you can induce to prove that the ordinal of the position is <= w.(g-1)+N. So the ordinal of the starting position is <= w^2, and the following example play shows it is >= w^2: 2^m(2n+1), 2^m(2n-1), ..., 2^m.3, 2^m, 2^(m-1)(2p+1), 2^(m-1)(2p-1), ..., 2^(m-1).3, 2^(m-1), ... 2(2x+1), 2(2x-1), ..., 6, 2, 2q+3, 2q+1, ..., 5, 3. -- David Moews dmoews@xraysgi.ims.uconn.edu
From: kramsay@aol.commangled (Keith Ramsay) Date: 06 Mar 2000 02:56:49 GMT Newsgroups: sci.math Subject: Re: Sylver Coinage - a constructivist conundrum?
|In turn, each player picks a natural number, which must not be a sum of |(any positive number of) previous picks. And it is illegal to pick 1; |plural numbers only. You lose if you can't make any pick. I like to think of it a little more simply as a misere form of the game where picking 1 is allowed. In the misere form, whoever cannot play wins, so whoever is forced to play 1 loses. In article <89shua$mr5$1@cantuc.canterbury.ac.nz>, mathwft@math.canterbury.ac.nz (Bill Taylor) writes: ||> Sylver coinage has ||> rank well beyond omega, which contributes to the difficulties. It forces ||> us to consider LEM for more complicated statements where we don't get LEM ||> for free. | |Yes, it seems so. It's odd, though. I'd have though induction over smallish |ordinals was fairly constructive, yet it seems not. I guess you see "induction over ordinals" as the primary working ingredient here. Look more carefully. |Indeed, one *can* see |that there might well be trouble even with a simple double induction, |(i.e. over w^2). If, to verify A(n, x), you may go down to the A(n-1, )'s |but may have to go enormously far, to A(n-1, huge), well, one can see why |a constructivist may have a problem with that. I guess. Maybe. Don't think in terms of loose "trouble". Think of the specific steps involved. We can call a position in the game "decided" if one player or the other has a winning strategy in that position. We deduce for a given position P that if all the "lesser" positions Q<P are decided then P is also decided. How do we do that? Well, there is a set of allowed moves for the player whose turn it is, each leading to one of the lesser positions. If one of those positions Q is a winner for that player, then of course P is as well, because the player can take that move. On the other hand, if all of those positions are winners for the other player, then the other player has a winning strategy (apply a winning strategy at whichever position comes next). Then (nonconstructively) we say, always either there exists a winning play from P or there doesn't (and since each position which can be moved to is decided, in that case the other player has a winning strategy in each). Of course if there are finitely many allowed moves, each which leads to a decided position, then P is also decided. Clear enough? It's like the proof that all horses have the same color; the whole problem lies with (certain cases of) the single inductive step. The original Sylver Coinage game is nevertheless decided; we have a winning strategy, just not a very illuminating one. For the first player, picking 5 is a winning move. Then when the second player picks a number, the game is reduced to one with finitely many remaining numbers. By a strategy-stealing argument, we know that player 1 has a winning strategy, and needs only to do a finite search to implement it. ... ||> So called intuitionistic counterexamples, which seem to be ... ||> "If we could do this we could decide whether pi has 7 9's, so we ||> can't do this...". So when did you prove we can't decide pi has 7 9's? | |The pi things are traditional Heyting, but not of the essence, I suspect. |The study of these counterexamples ("fickle" I think they're called) is |fairly unimpeachable, I imagine. A better scenario would be perhaps to say. |"If we could do this we could decide | whether an arbitrary TM will halt, so we can't do this..." |That would make it much more gritty. Even granitey. Finding a proof that the conjecture in question implies one of the standard assumptions known to be outside of your "modus operandi" is more to my taste than are the examples involving pi and so on. It's what mathematicians working nonconstructively often do when confronted with statements which require this or that set-theoretical principle, after all. On the other hand, part of the point of the prosaic "counterexamples" seems to be to make the argument more concrete, which is typically perceived as making it "grittier". Your metaphor (the argument becoming grittier as it becomes less concrete) seems a bit odd even to me. I think Brouwer would have objected to the idea that we need somehow to do more than what is required to convey the intuition, in order to make it a more serious proof. ||> So intuitionism is consistent? | |I'm sure that there are more technical approaches now, but in Heyting's |popularising book, intuitionism was more or less declared "obviously |consistent", because of its model in N, which was taken to be a "mental |given". |That's how I dimly recall it, though no doubt I'll get a rocket from Keith |for having completely misunderstood the whole point. Anyway, OK, I don't |*disagree* with them; the same reasoning tells us that PA is *obviously* |consistent, which I'm quite happy with, on its somewhat informal level. There are some cute remarks in Feferman's _In the Light of Logic_ about how Goedel skewered various of Hilbert's intuitions about how these principles would relate to each other. One of Hilbert's guesses was that the consistency of the law of excluded middle would be a much bigger deal than it was. The fact that HA is consistent and PA can be proven to be equiconsistent with HA has been used as a proof of the consistency of PA. Going the other direction is nothing, however. If you *drop* an assumption, *obviously* you are not going to introduce a contradiction where none existed before. No, if you're going to worry about the consistency of intuitionism, you are doing one of two things: either worry also about the consistency of classical mathematics (and there's only so much to be done to help you there), or be concerned because of the extensions to classical mathematics which were made by intuitionists that contradict classical mathematics. Brouwer had his free-choice sequences, for example. That's a whole different story. The logicians have cooked up "interpretations" which show those are consistent if some more familiar theoriest are consistent, although I have never been keenly interested in this bit of tidying up. ||> Anyway for me a good solution would be Kripke models or something like |that | |I keep hearing about these. But there doesn't seem to be any reasonably |simple intro anywhere. Like, I mean, something along the lines of a |Schaum series book! I'd really like to learn about Kripke models - can |you make any likely suggestions? I haven't found much use for them. It's one of those things which one might think would help you figure out intuitionism by leveraging off one's prior familiarity with classical mathematics, but really doesn't seem to help much. It's more of a technical tool. The definition should not be hard to find, and it's reasonably simple, although I'm not sure I remember the rules correctly. You have a partially ordered set F, and define a relationship |= between elements of F and statements in the first-order language of some structure. You define f|= p&q when f|= p and f|= q. You define f|= p or q when f|= p or f|= q. You define f|= false never to hold. You define f|= p->q to hold if for every f'>=f for which f'|=p, also f'|=q. Then you need to have a domain of elements at each element of F in order to specify the interpretation of the atomic statements and to define the meaning of f|=(Ax)P(x) and of f|=(Ex)P(x). Keith Ramsay
From: mathwft@math.canterbury.ac.nz (Bill Taylor) Date: 6 Mar 2000 06:11:05 GMT Newsgroups: sci.math Subject: Re: Sylver Coinage - a constructivist conundrum?
OK then, time for me to show off my ignorance again. Got to keep the pitbull fed, after all. ;-) dmoews@xraysgi.ims.uconn.edu (David Moews) writes: |> This ordinal is w^2. I didn't really follow your induction argument, and this still seems too small to me. Let me adjust your own example somewhat... |> the following example play shows it is >= w^2: |> |> 2^m(2n+1), 2^m(2n-1), ..., 2^m.3, 2^m, |> 2^(m-1)(2p+1), 2^(m-1)(2p-1), ..., 2^(m-1).3, 2^(m-1), |> ... |> 2(2x+1), 2(2x-1), ..., 6, 2, |> 2q+3, 2q+1, ..., 5, 3. OK then, let me do the following: 2^m(2n+1), 2^m(2n-1), ..., 2^m.7, 2^m.5, \ 2^(m-1)(2p+1), 2^(m-1)(2p-1), ..., 2^(m-1).7, 2^(m-1).5 \ ... > all times 3^n 2(2x+1), 2(2x-1), ...,14, 10, / 2q+3, 2q+1, ..., 7, 5. / ... ... 2^m(2n+1), 2^m(2n-1), ..., 2^m.7, 2^m.5, \ 2^(m-1)(2p+1), 2^(m-1)(2p-1), ..., 2^(m-1).5, 2^(m-1).5 \ ... > all times 3^(n-1) 2(2x+1), 2(2x-1), ...,14, 10, / 2q+3, 2q+1, ..., 7, 5. / ... ... 2^m(2n+1), 2^m(2n-1), ..., 2^m.7, 2^m.5 \ 2^(m-1)(2p+1), 2^(m-1)(2p-1), ..., 2^(m-1).7, 2^(m-1).5 \ ... > all times 3 2(2x+1), 2(2x-1), ...,14, 10, / 2q+3, 2q+1, ..., 7, 5. / Wouldn't this give order type w^3 ? I'm prepared to believe this example fails in some way, but I can't see why it would be so different from your simpler one. Please help me out. ------------------------------------------------------------------------------- Bill Taylor W.Taylor@math.canterbury.ac.nz ------------------------------------------------------------------------------- Dr Frankenstein - the world's first body-builder. -------------------------------------------------------------------------------
From: dmoews@xraysgi.ims.uconn.edu (David Moews) Date: 6 Mar 2000 14:45:39 -0800 Newsgroups: sci.math Subject: Re: Sylver Coinage - a constructivist conundrum?
In article <89vi5p$lgp$1@cantuc.canterbury.ac.nz>, Bill Taylor <mathwft@math.canterbury.ac.nz> wrote: |OK then, let me do the following: [I have added some labels & changed letters] | | 2^m(2n+1), 2^m(2n-1), ..., 2^m.7, 2^m.5, \ | 2^(m-1)(2p+1), 2^(m-1)(2p-1), ..., 2^(m-1).7, 2^(m-1).5 \ | ... > all times 3^N | 2(2x+1), 2(2x-1), ...,14, 10, / | 2q+3, 2q+1, ..., 7, 5. / (first group) | |... ... | | 2^m(2n+1), 2^m(2n-1), ..., 2^m.7, 2^m.5, \ | 2^(m-1)(2p+1), 2^(m-1)(2p-1), ..., 2^(m-1).5, 2^(m-1).5 \ | ... >all times 3^(N-1) | 2(2x+1), 2(2x-1), ...,14, 10, / | 2q+3, 2q+1, ..., 7, 5. / (second group) | |... ... | | 2^m(2n+1), 2^m(2n-1), ..., 2^m.7, 2^m.5 \ | 2^(m-1)(2p+1), 2^(m-1)(2p-1), ..., 2^(m-1).7, 2^(m-1).5 \ | ... > all times 3 | 2(2x+1), 2(2x-1), ...,14, 10, / | 2q+3, 2q+1, ..., 7, 5. / (last group) | | |Wouldn't this give order type w^3 ? This example is not, in general, a play of Sylver Coinage. After playing 5.3^N and 7.3^N, you will be able to exclude every multiple of 3^N that is >23.3^N; but either 2^m.3^(N-1).(2n+1) or 2^m.3^(N-1).(2n-1) will be congruent to +3^(N-1) or -3^(N-1) mod 3^N, so by taking sums of these with 5.3^N and 7.3^N, you will be able to exclude all sufficiently large multiples of 3^(N-1), where `sufficiently large' depends only on m, n, and N. So the p, ..., x, q that occur in the second group will be limited in size, and similar problems will occur in succeeding groups. The Bible says (abridged): ``Let g be the g.c.d. of the moves made. Then it's not hard to see that only finitely many multiples of g are not expressible as sums of numbers already played. So after at most this known number of moves the g.c.d. must be reduced.'' So we may associate with each position of Sylver Coinage an ordered pair (g, N), where g is the g.c.d. of the moves made, and N is the number of inexpressible multiples of g. Any move from this position must either be an inexpressible multiple of g, taking us to (g, M), where M < N or an x not a multiple of g, taking us to (g', P), for some P, where g'=gcd(g,x) is a proper divisor of g. In either case, the ordered pair strictly decreases (in lexicographic order). This gives the bound of w^2. In your example, the sequence of g.c.d.s is 2^m.3^N.(2n+1), 2^m.3^N, 2^(m-1).3^N, ..., 2.3^N, 3^N in the first group, but when you start the second group the g.c.d. will drop almost immediately to 3^(N-1), causing trouble. -- David Moews dmoews@xraysgi.ims.uconn.edu
From: colonel@monmouth.com (He Comes As No Surprise) Date: 8 Mar 2000 17:14:28 -0500 Newsgroups: sci.math Subject: Re: Sylver Coinage - a constructivist conundrum?
In <20000305215649.05178.00000487@nso-cv.aol.com>, kramsay@aol.mangled wrote: > > |In turn, each player picks a natural number, which must not be a sum of > |(any positive number of) previous picks. And it is illegal to pick 1; > |plural numbers only. You lose if you can't make any pick. > > I like to think of it a little more simply as a misere form of the > game where picking 1 is allowed. In the misere form, whoever cannot > play wins, so whoever is forced to play 1 loses. This simplifies some of the theory. For example, W.W. defines an end-position as a position with g=1 in which every legal move u less than t excludes t, and a quiet end-position as the same except that u excludes t using just one instance of u. An equivalent (and neater) characterization of a quiet end-position is that t is not the sum of any two legal moves--but this holds only if 1 is legal. I have not thought about independence proofs in Sylver Coinage, but the material in W.W. raises a possibility of applying superdomino theory. In a position with g=2, the pattern of P's and N's in the positions obtained by making an odd move must eventually cycle. The proof is inductive but easy to follow from the text; basically each value can be shown to depend on a fixed number of previous values, so the computation can be performed by a finite automaton. For g=3 the computation is not bounded, mainly because it inducts over modular classes 1 and 2 simultaneously. This suggests a parallel with one- and two-dimensional dominoes that I have no idea what to do with. -:- 'PATAGEOMETRY, n. The study of those mathematical properties which remain invariant under brain transplants. -- Col. G. L. Sicherman home: colonel@mail.monmouth.com work: sicherman@lucent.com web: <http://www.monmouth.com/~colonel/>
From: sicherman@lucent.com (The Dangling Conversationalist) Date: 27 Apr 2000 19:09:26 GMT Newsgroups: sci.math Subject: numerical results in Sylver Coinage?
Is anybody out there doing research in Sylver Coinage? I ask partly because I'd like confirmation of my computed results, and partly because there's one position {10,36,52,68} that I've computed beyond 15 million without finding a winning move or a pattern. If this position is "N", the winning move is higher than any yet discovered in positions with G.C.D. greater than one. (The highest is 58905 in {6,34,62}.) -:- One measures a circle, beginning anywhere. --Charles Fort -- Col. G. L. Sicherman work: sicherman@lucent.com home: colonel@mail.monmouth.com
From: sicherman@lucent.com (The Pied Typer) Date: 29 Apr 2000 22:59:03 GMT Newsgroups: sci.math Subject: Re: numerical results in Sylver Coinage?
In <8ea396$3ae@nntpa.cb.lucent.com>, I wrote: > > there's one position {10,36,52,68} that I've computed beyond 15 million > without finding a winning move or a pattern. I just noticed that this position is short, which means that I could compute it to a googolplex without finding a winning move. Well, it was good exercise for the computer. -- G. L. Sicherman work: sicherman@lucent.com home: colonel@mail.monmouth.com
From: colonel@monmouth.com (The Pied Typer) Date: 15 Jun 2000 22:47:25 -0400 Newsgroups: sci.math Subject: Sylver Coinage - can you prove them?
I recently stumbled over two elegant results in the theory of Sylver Coinage (see _Winning Ways,_ ch. 18). Unfortunately they are empirical results; I have not found even an ugly proof of either. Maybe you on the Net can do better! Notation: g(x,y,...) is the greatest common divisor of its arguments. t(x,y,...) is the highest legal move in {x,y,...}; that is, the greatest number not expressible as a sum with multiples of elements of {x,y,...}. t is defined only if g=1. Other terminology is as in _Winning Ways._ The earliest general results in Sylver Coinage are Sylvester's Theorem : If g(m,n)=1, then t(m,n) = mn - (m+n). (This does not actually involve the game of Sylver Coinage; it is only important in characterizing it.) Hutchings's Theorem: If g(m,n)=1 and t(m,n)>1, then {m,n} is an ender (and therefore "N"). Now here are the unproved results: Proposition X: Let S and T be initial segments of the same ascending arithmetic progression with g=1. Then t(S) and t(T) differ by a multiple of the first element of the progression. (Like Sylvester's Theorem, this does not actually involve the game.) Proposition Y: Let S be a finite arithmetic progression of numbers greater than 3. If S is an ender, then S is a quiet ender. From Hutchings's Theorem and Proposition Y follows the known result that if g(m,n)=1 and m and n are greater than 3, then {m,n} is a quiet ender. It is easy to replace the condition that m and n are greater than 3 with the weaker condition of Hutchings's Theorem. Technically even {2,3} (where t=1) is a quiet ender--the only ender that is "P". -:- "'PATAGEOMETRY: The study of those mathematical properties that remain invariant under brain transplants." -- Col. G. L. Sicherman home: colonel@mail.monmouth.com work: sicherman@lucent.com web: <http://www.monmouth.com/~colonel/>
From: colonel@shell.monmouth.com (Col. G. L. Sicherman) Date: 22 Jun 2000 17:30:50 -0400 Newsgroups: sci.math Subject: Re: Sylver Coinage - somebody proved it!
In <8im0ug$8pj$1@shell.monmouth.com>, I wrote: > In <8ic4ft$es2$1@shell.monmouth.com>, I wrote: > > > > Proposition X: Let S and T be initial segments of the same ascending > > arithmetic progression with g=1. Then t(S) and t(T) differ by a > > multiple of the first element of the progression. (Like Sylvester's > > Theorem, this does not actually involve the game.) > > I just ran across a reference to a 1956 paper by J. B. Roberts that > may have a proof of this. More later! And so it does. Taking the arithmetic progression to be a0, a1, ..., as with successive difference d, Roberts gives: t(a0, a1, ..., as) + 1 = ([{a0-2}/s] + 1)a0 + (d - 1)(a0 - 1). where [...] indicates the integer part. Since the second term does not depend on s, Proposition X follows immediately. Roberts's proof, while efficient, runs to 5 pages--I'm glad I don't need to discover it myself! (Mathematics can be a good livelihood but it makes a poor hobby.) > > Proposition Y: Let S be a finite arithmetic progression of numbers > > greater than 3. If S is an ender, then S is a quiet ender. > > No progress yet. But I'll try to adapt Roberts's ideas. -:- "This rock, for instance, has an I.Q. of zero. Ouch!" "What's the matter, Professor?" "It bit me!" -- Col. G. L. Sicherman home: colonel@mail.monmouth.com work: sicherman@lucent.com web: <http://www.monmouth.com/~colonel/>
From: colonel@shell.monmouth.com (Col. G. L. Sicherman) Date: 26 Jun 2000 12:09:13 -0400 Newsgroups: sci.math Subject: Re: Sylver Coinage - building on Roberts
In <8iu0ia$8pj$1@shell.monmouth.com>, I wrote: > > > Proposition Y: Let S be a finite arithmetic progression of numbers > > > greater than 3. If S is an ender, then S is a quiet ender. > > > > No progress yet. > > But I'll try to adapt Roberts's ideas. Roberts's formula has inspired me to reformulate Proposition Y: Proposition Y: Let S = {a[0], a[1], ... , a[s]} be an increasing arithmetic progression of numbers greater than 3. If s divides a[0]-2, then S is a quiet ender; otherwise S is not an ender. This is more specific and should be easier to prove. -:- When by judgement one means knowing how something comes to be what it is, the judgement must appear as re-constructing the identical universe of the difference. Then every model includes the measure of its own difference. No state of equilibrium is empowered to remain identical, or to compel the individual to alter (and integrate with it). The identical is equal to itself, since it is different. --Franco Spisani (1975) -- Col. G. L. Sicherman home: colonel@mail.monmouth.com work: sicherman@lucent.com web: <http://www.monmouth.com/~colonel/>
From: gls@simba.cvu.lucent.com (G. L. Sicherman) Date: 3 Aug 2000 19:09:16 GMT Newsgroups: sci.math Subject: Sylver Coinage: {14,26} is P
I've bagged another one: In Sylver Coinage, {14,26} is P. Details are at my Sylver Coinage page: <http://www.monmouth.com/~colonel/sylver/> This forms a triad of mutually responsive moves in {}: {10, 14, 26} Against any opening move from this set, any other move from this set will win. A unique situation--so far! By the way, the winning move in {10, 14, 26} is 293--a result that Voelkle found long ago. We now know all winning moves in {14}: [7, 8, 10, 26]. -:- "Hey, Rocky! Watch me pull a UNIX program out of my source directory!" "AGAIN?" "Nothin' up my sleeve ... PRESTO!" IDENTIFICATION DIVISION. AUTHOR-NAME. B. J. MOOSE, FROSTBYTE DATA SYS. SOURCE-COMPUTER. IBM-7044. OBJECT-COMPUTER. IBM-7044. . . . "No doubt about it--I gotta get a new source directory!" -- G. L. Sicherman work: sicherman@lucent.com home: colonel@mail.monmouth.com