[math-fun] Games of no strategy
What are fun examples of combinatorial games that (like Conway and Paterson's game of Brussels Sprouts) appear to be games of strategy but whose outcome doesn't depend on what either player does? One of my favorites is Impartial Cutcake, aka the Candy Bar Game. The initial state is a chocolate rectangle, scored into unit squares. On any given turn, a player may take any rectangular piece bigger than a 1-by-1 square and divide it along a horizontal or vertical scoring-line into two smaller rectangular pieces. The two players alternate. When no further divisions are possible, the game ends, and the player who made the last move wins (and, if you like, gets to eat all the pieces). Jim Propp
These are examples of She-Loves-Me-She-Loves-Me-Not. If you can get access to Een Pak Met Een Korte Broek, Papers presented to H.W.Lenstra, you'll find one with subtitle Relatives of two game of Lenstra, which lists Sympler, Fitted Carpets, The octal games .3 (take a bean from a heap), .5 (take a bean if it's isolated or one from a larger heap which must be left as two non-empty heaps), .7 (take a bean for a heap, possibly splitting the remainder into 2 heaps) (or 3 heaps, 4 heaps, ...), 4.0 (split a heap into 2 non-empty heaps), 4.2 (split a heap into 2 non-empty heaps, or take a bean fro a larger heap), 3030303... (take any odd number of beans), 4.01, 4.04, 4.05, 4.21, 4.24, 4.25, .30X, .50X, .70X, where 0<X<8, Brussels Sprouts, Jocasta, Impartial Childish Hackenbush, ... (most of these are in Winning Ways). R. From: math-fun [math-fun-bounces@mailman.xmission.com] on behalf of James Propp [jamespropp@gmail.com] Sent: Thursday, November 13, 2014 9:00 AM To: math-fun Subject: [math-fun] Games of no strategy What are fun examples of combinatorial games that (like Conway and Paterson's game of Brussels Sprouts) appear to be games of strategy but whose outcome doesn't depend on what either player does? One of my favorites is Impartial Cutcake, aka the Candy Bar Game. The initial state is a chocolate rectangle, scored into unit squares. On any given turn, a player may take any rectangular piece bigger than a 1-by-1 square and divide it along a horizontal or vertical scoring-line into two smaller rectangular pieces. The two players alternate. When no further divisions are possible, the game ends, and the player who made the last move wins (and, if you like, gets to eat all the pieces). Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Since the paper Richard mentions contains A006016, and Een Pak Met Een Korte Broek is very rare, and privately printed, I think we would be justified in adding a scanned copy of his paper as an attachment to A006016. That would be OK with you, Richard, I assume, since you've generally given the OEIS permission to do this sort of thing? Richard, what about other sequences that arise from the paper? The octal games you mention, for instance - can you tell me the A-numbers, or the first few terms, of any of them? (I have a copy of the book, since Andrew Odlyzko and I wrote something in it) Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Thu, Nov 13, 2014 at 11:50 AM, Richard Guy <rkg@ucalgary.ca> wrote:
These are examples of She-Loves-Me-She-Loves-Me-Not. If you can get access to Een Pak Met Een Korte Broek, Papers presented to H.W.Lenstra, you'll find one with subtitle Relatives of two game of Lenstra, which lists Sympler, Fitted Carpets, The octal games .3 (take a bean from a heap), .5 (take a bean if it's isolated or one from a larger heap which must be left as two non-empty heaps), .7 (take a bean for a heap, possibly splitting the remainder into 2 heaps) (or 3 heaps, 4 heaps, ...), 4.0 (split a heap into 2 non-empty heaps), 4.2 (split a heap into 2 non-empty heaps, or take a bean fro a larger heap), 3030303... (take any odd number of beans), 4.01, 4.04, 4.05, 4.21, 4.24, 4.25, .30X, .50X, .70X, where 0<X<8, Brussels Sprouts, Jocasta, Impartial Childish Hackenbush, ... (most of these are in Winning Ways). R.
From: math-fun [math-fun-bounces@mailman.xmission.com] on behalf of James Propp [jamespropp@gmail.com] Sent: Thursday, November 13, 2014 9:00 AM To: math-fun Subject: [math-fun] Games of no strategy
What are fun examples of combinatorial games that (like Conway and Paterson's game of Brussels Sprouts) appear to be games of strategy but whose outcome doesn't depend on what either player does?
One of my favorites is Impartial Cutcake, aka the Candy Bar Game. The initial state is a chocolate rectangle, scored into unit squares. On any given turn, a player may take any rectangular piece bigger than a 1-by-1 square and divide it along a horizontal or vertical scoring-line into two smaller rectangular pieces. The two players alternate. When no further divisions are possible, the game ends, and the player who made the last move wins (and, if you like, gets to eat all the pieces).
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Mainly to Neil, My email system has been changed, so apologies for any inadequacies. Can do as you wish with the paper. The only nim-sequence that arises is 010101010101010101010.... R. ________________________________________ From: math-fun [math-fun-bounces@mailman.xmission.com] on behalf of Neil Sloane [njasloane@gmail.com] Sent: Thursday, November 13, 2014 12:52 PM To: math-fun Subject: Re: [math-fun] Games of no strategy Since the paper Richard mentions contains A006016, and Een Pak Met Een Korte Broek is very rare, and privately printed, I think we would be justified in adding a scanned copy of his paper as an attachment to A006016. That would be OK with you, Richard, I assume, since you've generally given the OEIS permission to do this sort of thing? Richard, what about other sequences that arise from the paper? The octal games you mention, for instance - can you tell me the A-numbers, or the first few terms, of any of them? (I have a copy of the book, since Andrew Odlyzko and I wrote something in it) Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Thu, Nov 13, 2014 at 11:50 AM, Richard Guy <rkg@ucalgary.ca> wrote:
These are examples of She-Loves-Me-She-Loves-Me-Not. If you can get access to Een Pak Met Een Korte Broek, Papers presented to H.W.Lenstra, you'll find one with subtitle Relatives of two game of Lenstra, which lists Sympler, Fitted Carpets, The octal games .3 (take a bean from a heap), .5 (take a bean if it's isolated or one from a larger heap which must be left as two non-empty heaps), .7 (take a bean for a heap, possibly splitting the remainder into 2 heaps) (or 3 heaps, 4 heaps, ...), 4.0 (split a heap into 2 non-empty heaps), 4.2 (split a heap into 2 non-empty heaps, or take a bean fro a larger heap), 3030303... (take any odd number of beans), 4.01, 4.04, 4.05, 4.21, 4.24, 4.25, .30X, .50X, .70X, where 0<X<8, Brussels Sprouts, Jocasta, Impartial Childish Hackenbush, ... (most of these are in Winning Ways). R.
From: math-fun [math-fun-bounces@mailman.xmission.com] on behalf of James Propp [jamespropp@gmail.com] Sent: Thursday, November 13, 2014 9:00 AM To: math-fun Subject: [math-fun] Games of no strategy
What are fun examples of combinatorial games that (like Conway and Paterson's game of Brussels Sprouts) appear to be games of strategy but whose outcome doesn't depend on what either player does?
One of my favorites is Impartial Cutcake, aka the Candy Bar Game. The initial state is a chocolate rectangle, scored into unit squares. On any given turn, a player may take any rectangular piece bigger than a 1-by-1 square and divide it along a horizontal or vertical scoring-line into two smaller rectangular pieces. The two players alternate. When no further divisions are possible, the game ends, and the player who made the last move wins (and, if you like, gets to eat all the pieces).
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Assuming randomly-sized candy bars, the guys who insisted on going first now find it three times more difficult to climb into their pants than their opponents. And serve them right. Isn't mathematics wonderful ... WFL On 11/13/14, James Propp <jamespropp@gmail.com> wrote:
What are fun examples of combinatorial games that (like Conway and Paterson's game of Brussels Sprouts) appear to be games of strategy but whose outcome doesn't depend on what either player does?
One of my favorites is Impartial Cutcake, aka the Candy Bar Game. The initial state is a chocolate rectangle, scored into unit squares. On any given turn, a player may take any rectangular piece bigger than a 1-by-1 square and divide it along a horizontal or vertical scoring-line into two smaller rectangular pieces. The two players alternate. When no further divisions are possible, the game ends, and the player who made the last move wins (and, if you like, gets to eat all the pieces).
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Although I doubt this is what Jim had in mind . . . . . . It is well known that for countable games where each of two players A, B alternates in creating a binary string of order-type omega (== {0, 1, 2, 3, ...}) with a subset W(A) in {0,1}^omega and its complement W(B) determining who won according as which of W(A) or W(B) the string ended up in . . . . . . then the statement: "There is always a strategy for A or B regardless of the dichomy W(A)+ W(B)" (aka "the Axiom of Determinacy") is not consistent with the Axiom of Choice. So according to AC, there is some W(A) + W(B) for which there exists no strategy for either player. I suspect this means that the outcome does not depend on what either player does. But I'm not absolutely sure of that. --Dan
On Nov 13, 2014, at 8:00 AM, James Propp <jamespropp@gmail.com> wrote:
What are fun examples of combinatorial games that (like Conway and Paterson's game of Brussels Sprouts) appear to be games of strategy but whose outcome doesn't depend on what either player does? . . .
Dear all, It's not exactly a game, but funsters may be interested in (or already know about) the following: Start with a pile (tower) of n building blocks (cubes). Dismantle the tower by splitting into two towers of heights a and n-a, giving yourself a score of a(n-a). Continue with one of the resulting towers, and repeat until there are n towers of height 1. How to maximize your score ? E.g., 7 --> 4,3 --> 1,3,3 --> 1,1,2,3 --> 1,1,2,2,1 --> 1,1,2,1,1,1 --> 1,1,1,1,1,1,1 gives a score of 12+3+2+2+1+1 = 21. Can you do better? R. ________________________________________ From: math-fun [math-fun-bounces@mailman.xmission.com] on behalf of Dan Asimov [dasimov@earthlink.net] Sent: Thursday, November 13, 2014 1:51 PM To: math-fun Subject: Re: [math-fun] Games of no strategy Although I doubt this is what Jim had in mind . . . . . . It is well known that for countable games where each of two players A, B alternates in creating a binary string of order-type omega (== {0, 1, 2, 3, ...}) with a subset W(A) in {0,1}^omega and its complement W(B) determining who won according as which of W(A) or W(B) the string ended up in . . . . . . then the statement: "There is always a strategy for A or B regardless of the dichomy W(A)+ W(B)" (aka "the Axiom of Determinacy") is not consistent with the Axiom of Choice. So according to AC, there is some W(A) + W(B) for which there exists no strategy for either player. I suspect this means that the outcome does not depend on what either player does. But I'm not absolutely sure of that. --Dan
On Nov 13, 2014, at 8:00 AM, James Propp <jamespropp@gmail.com> wrote:
What are fun examples of combinatorial games that (like Conway and Paterson's game of Brussels Sprouts) appear to be games of strategy but whose outcome doesn't depend on what either player does? . . .
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
You could play this using some of Jim's candy bars instead, if there are any left. (But you only get to eat them if you beat Richard's score ...) WFL On 11/13/14, Richard Guy <rkg@ucalgary.ca> wrote:
Dear all, It's not exactly a game, but funsters may be interested in (or already know about) the following: Start with a pile (tower) of n building blocks (cubes). Dismantle the tower by splitting into two towers of heights a and n-a, giving yourself a score of a(n-a). Continue with one of the resulting towers, and repeat until there are n towers of height 1. How to maximize your score ? E.g., 7 --> 4,3 --> 1,3,3 --> 1,1,2,3 --> 1,1,2,2,1 --> 1,1,2,1,1,1 --> 1,1,1,1,1,1,1 gives a score of 12+3+2+2+1+1 = 21. Can you do better? R.
________________________________________ From: math-fun [math-fun-bounces@mailman.xmission.com] on behalf of Dan Asimov [dasimov@earthlink.net] Sent: Thursday, November 13, 2014 1:51 PM To: math-fun Subject: Re: [math-fun] Games of no strategy
Although I doubt this is what Jim had in mind . . .
. . . It is well known that for countable games where each of two players A, B alternates in creating a binary string of order-type omega (== {0, 1, 2, 3, ...}) with a subset W(A) in {0,1}^omega and its complement W(B) determining who won according as which of W(A) or W(B) the string ended up in . . .
. . . then the statement:
"There is always a strategy for A or B regardless of the dichomy W(A)+ W(B)"
(aka "the Axiom of Determinacy") is not consistent with the Axiom of Choice.
So according to AC, there is some W(A) + W(B) for which there exists no strategy for either player.
I suspect this means that the outcome does not depend on what either player does. But I'm not absolutely sure of that.
--Dan
On Nov 13, 2014, at 8:00 AM, James Propp <jamespropp@gmail.com> wrote:
What are fun examples of combinatorial games that (like Conway and Paterson's game of Brussels Sprouts) appear to be games of strategy but whose outcome doesn't depend on what either player does? . . .
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The spoiler, though I doubt anyone needs one, is to ask how much potential energy is lost in the process. Alternatively, how much work needs to be done to reassemble the tower. R. ________________________________________ From: math-fun [math-fun-bounces@mailman.xmission.com] on behalf of Richard Guy [rkg@ucalgary.ca] Sent: Thursday, November 13, 2014 2:17 PM To: math-fun Subject: Re: [math-fun] Games of no strategy Dear all, It's not exactly a game, but funsters may be interested in (or already know about) the following: Start with a pile (tower) of n building blocks (cubes). Dismantle the tower by splitting into two towers of heights a and n-a, giving yourself a score of a(n-a). Continue with one of the resulting towers, and repeat until there are n towers of height 1. How to maximize your score ? E.g., 7 --> 4,3 --> 1,3,3 --> 1,1,2,3 --> 1,1,2,2,1 --> 1,1,2,1,1,1 --> 1,1,1,1,1,1,1 gives a score of 12+3+2+2+1+1 = 21. Can you do better? R. ________________________________________ From: math-fun [math-fun-bounces@mailman.xmission.com] on behalf of Dan Asimov [dasimov@earthlink.net] Sent: Thursday, November 13, 2014 1:51 PM To: math-fun Subject: Re: [math-fun] Games of no strategy Although I doubt this is what Jim had in mind . . . . . . It is well known that for countable games where each of two players A, B alternates in creating a binary string of order-type omega (== {0, 1, 2, 3, ...}) with a subset W(A) in {0,1}^omega and its complement W(B) determining who won according as which of W(A) or W(B) the string ended up in . . . . . . then the statement: "There is always a strategy for A or B regardless of the dichomy W(A)+ W(B)" (aka "the Axiom of Determinacy") is not consistent with the Axiom of Choice. So according to AC, there is some W(A) + W(B) for which there exists no strategy for either player. I suspect this means that the outcome does not depend on what either player does. But I'm not absolutely sure of that. --Dan
On Nov 13, 2014, at 8:00 AM, James Propp <jamespropp@gmail.com> wrote:
What are fun examples of combinatorial games that (like Conway and Paterson's game of Brussels Sprouts) appear to be games of strategy but whose outcome doesn't depend on what either player does? . . .
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Although I doubt this is what Jim had in mind . . .
[...]
So according to AC, there is some W(A) + W(B) for which there exists no strategy for either player.
I suspect this means that the outcome does not depend on what either player does. But I'm not absolutely sure of that.
No, it just means that neither player can force a win, even though the game cannot end in a draw. The way to `construct' such a game is by (uncountable transfinite) induction: 1. Well-order the set of all player-1-strategies and player-2-strategies by the initial ordinal of cardinality 2^aleph_null. 2. For each strategy in a list, insist that a particular sequence of moves `beats' it. Since at any stage we have fixed < 2^aleph_null outcomes, we can always do this. By the end of all time, we have a game where for any strategy that player n makes, player 3-n can make a sequence of moves to win. Sincerely, Adam P. Goucher
--Dan
On Nov 13, 2014, at 8:00 AM, James Propp <jamespropp@gmail.com> wrote:
What are fun examples of combinatorial games that (like Conway and Paterson's game of Brussels Sprouts) appear to be games of strategy but whose outcome doesn't depend on what either player does? . . .
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes. I realized as soon as I posted that that may statement that "the outcome does not depend on what either player does" couldn't be right. Adam's proof is very nice. I love transfinite induction. It's elegant that you don't need to say something alternately about A's and B's strategies, but can pool them together. Conway and Croft (1964) used a similar argument to prove that R^3 can be partitioned into congruent planar unit circles.) I've been totally down with AC ever since learning it was equivalent to "The cartesian product of a nonempty collection of nonempty sets is nonempty." (Proof: immediate.) By the way, I claim that assuming AC one can pick a random integer. From which some interesting consequences follow. --Dan
On Nov 14, 2014, at 7:19 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Although I doubt this is what Jim had in mind . . .
[...]
So according to AC, there is some W(A) + W(B) for which there exists no strategy for either player.
I suspect this means that the outcome does not depend on what either player does. But I'm not absolutely sure of that.
No, it just means that neither player can force a win, even though the game cannot end in a draw.
The way to `construct' such a game is by (uncountable transfinite) induction:
1. Well-order the set of all player-1-strategies and player-2-strategies by the initial ordinal of cardinality 2^aleph_null.
2. For each strategy in a list, insist that a particular sequence of moves `beats' it. Since at any stage we have fixed < 2^aleph_null outcomes, we can always do this.
By the end of all time, we have a game where for any strategy that player n makes, player 3-n can make a sequence of moves to win.
Sincerely,
Adam P. Goucher
Dan, I'll bite: What do you mean when you claim that "assuming AC one can pick a random integer.
From which some interesting consequences follow"?
Jim Propp On Friday, November 14, 2014, Dan Asimov <dasimov@earthlink.net> wrote:
Yes. I realized as soon as I posted that that may statement that
"the outcome does not depend on what either player does"
couldn't be right.
Adam's proof is very nice. I love transfinite induction. It's elegant that you don't need to say something alternately about A's and B's strategies, but can pool them together.
Conway and Croft (1964) used a similar argument to prove that R^3 can be partitioned into congruent planar unit circles.)
I've been totally down with AC ever since learning it was equivalent to
"The cartesian product of a nonempty collection of nonempty sets is nonempty."
(Proof: immediate.)
By the way, I claim that assuming AC one can pick a random integer. From which some interesting consequences follow.
--Dan
On Nov 14, 2014, at 7:19 AM, Adam P. Goucher <apgoucher@gmx.com <javascript:;>> wrote:
Although I doubt this is what Jim had in mind . . .
[...]
So according to AC, there is some W(A) + W(B) for which there exists no strategy for either player.
I suspect this means that the outcome does not depend on what either player does. But I'm not absolutely sure of that.
No, it just means that neither player can force a win, even though the game cannot end in a draw.
The way to `construct' such a game is by (uncountable transfinite) induction:
1. Well-order the set of all player-1-strategies and player-2-strategies by the initial ordinal of cardinality 2^aleph_null.
2. For each strategy in a list, insist that a particular sequence of moves `beats' it. Since at any stage we have fixed < 2^aleph_null outcomes, we can always do this.
By the end of all time, we have a game where for any strategy that player n makes, player 3-n can make a sequence of moves to win.
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (6)
-
Adam P. Goucher -
Dan Asimov -
Fred Lunnon -
James Propp -
Neil Sloane -
Richard Guy