From: mathwft@math.canterbury.ac.nz (Bill Taylor) Subject: Sylver Coinage - a constructivist conundrum? Date: 29 Feb 2000 04:10:20 GMT Newsgroups: sci.math,sci.logic,rec.games.abstract Summary: [missing] 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) Subject: Re: Sylver Coinage - a constructivist conundrum? Date: 29 Feb 2000 18:40:23 GMT Newsgroups: sci.math,sci.logic,rec.games.abstract In article <89fgrc$lar$1@cantuc.canterbury.ac.nz>, Bill Taylor 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: sicherman@lucent.com (The Pied Typer) Subject: Re: Linear Combination of Non-negative integers. Date: 26 Aug 2000 15:24:48 GMT Newsgroups: sci.math.research In <2000Aug22.204644.13135@leeds.ac.uk>, eclrh@sun.leeds.ac.uk wrote: > In <39A24296.52BC@club-internet.fr>, pbornszt@club-internet.fr writes: > > > according to Guy's "unsolved problems in number theory" Springer p.113 > > (C7), this result is due to Sylvester (1884), who also proved that the > > number of non-representable numbers is (a-1)(b-1)/2. In fact, of any two numbers that add up to the highest non-representable number, exactly one is representable. (This property characterizes what Sylver Coinage Theory calls a "quiet ender.") > > The general problem with n > 1 numbers is known as the coin exchange > > problem of Frobenius. This was a natural sidetrack to Frobenius's interest in linear forms. > > The case n = 3 has been solved by Selmer and Beyer, then simplified by > > Rödseth and later by Greenberg. But there is no formula as simple as > > above. > > For n > 3, only bounds are known. > > This is the basis of Conway's game of "Sylver Coinage", named in honour > of Sylvester (see Berlekamp, Conway and Guy, "Winning Ways", vol. 2). > The basic results for n=2 numbers are so easy (for example, I was able > to independently rediscover and prove them, and I'm pretty dim) that I > wonder if somebody knew them before Sylvester (whose contribution was > not limited to the case n=2). Maybe an earlier publication has been > overlooked, or somebody knew the stuff but didn't trouble to publish it. A scholar of Indian or Chinese mathematics might be able to find something. By the way, Guy points out that J. L. Roberts solved the coin problem for a set of values in arithmetic progression. His formula has implications for Sylver Coinage. -:- 'PATAGEOMETRY: The study of those mathematical properties which remain invariant under brain transplants. -- G. L. Sicherman work: sicherman@lucent.com home: colonel@mail.monmouth.com