[math-fun] Game question
Consider a game in which two players, A and B, each choose distinct integers by turn. A's object is to maximize the length of the longest A.P. among his selected integers. B's object is to limit the length of A's longest A.P. Show that B cannot prevent A from obtaining an A.P. of length 3. Can B prevent A from obtaining an A.P. of some length N? What is the smallest such N?
David, I can't remember the last time I saw A.P. used as an abbrev. to mean arithmetic progression — quite possibly I never did. It took me maybe 3 minutes before I thought of that (which I presume is what you mean, right?). Maybe next time you can spell it out — or abbreviate it like "arith. prog." — the first time with e.g. "A.P." in parentheses, and then use A.P. after that? (At first I thought it was probably some common abbrev. in number theory, a subject I don't have a lot of knowledge about.) Thanks, Dan
On Aug 12, 2015, at 9:22 PM, David Wilson <davidwwilson@comcast.net> wrote:
Consider a game in which two players, A and B, each choose distinct integers by turn.
A's object is to maximize the length of the longest A.P. among his selected integers.
B's object is to limit the length of A's longest A.P.
Show that B cannot prevent A from obtaining an A.P. of length 3.
Can B prevent A from obtaining an A.P. of some length N?
What is the smallest such N?
You'll have to forgive me. Having encountered the abbreviation "A.P." in high school, I assumed it was on a par with "GCD" or "LCM" in terms of general familiarity, meaning I didn't need to define it in this forum. Apologies. "A.P." indeed stands for "arithmetic progression". I feel your pain. When I see something I don't understand in this forum, I usually wait for the follow-up messages to clarify the situation, or in the case of analysis geeks spouting about q-equations, Galois groups and hypergeometric functions, politely skip on to the next email. "Better to remain silent and be thought a fool than to speak out and remove all doubt." But seriously, in any mathematical discussion you must assume some background material, which implies that someone is not going to understand what you're talking about.
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Dan Asimov Sent: Thursday, August 13, 2015 1:01 AM To: math-fun Subject: Re: [math-fun] Game question
David,
I can't remember the last time I saw A.P. used as an abbrev. to mean arithmetic progression — quite possibly I never did. It took me maybe 3 minutes before I thought of that (which I presume is what you mean, right?).
Maybe next time you can spell it out — or abbreviate it like "arith. prog." — the first time with e.g. "A.P." in parentheses, and then use A.P. after that?
(At first I thought it was probably some common abbrev. in number theory, a subject I don't have a lot of knowledge about.)
Thanks,
Dan
On Aug 12, 2015, at 9:22 PM, David Wilson <davidwwilson@comcast.net> wrote:
Consider a game in which two players, A and B, each choose distinct integers by turn.
A's object is to maximize the length of the longest A.P. among his selected integers.
B's object is to limit the length of A's longest A.P.
Show that B cannot prevent A from obtaining an A.P. of length 3.
Can B prevent A from obtaining an A.P. of some length N?
What is the smallest such N?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
B cannot prevent A from owning two consecutive integers on the second move. Regardless of what B does, A can now place a "pivot" far enough away from the first pair that the reflection of the pair through the pivot is a distant pair of integers, neither of which are claimed. B cannot claim both, and A wins on the fourth move. I haven't thought much about length four goals. This is very reminiscent of the "angels and demons" problem. On Thu, Aug 13, 2015 at 8:59 AM, David Wilson <davidwwilson@comcast.net> wrote:
You'll have to forgive me. Having encountered the abbreviation "A.P." in high school, I assumed it was on a par with "GCD" or "LCM" in terms of general familiarity, meaning I didn't need to define it in this forum. Apologies. "A.P." indeed stands for "arithmetic progression".
I feel your pain. When I see something I don't understand in this forum, I usually wait for the follow-up messages to clarify the situation, or in the case of analysis geeks spouting about q-equations, Galois groups and hypergeometric functions, politely skip on to the next email. "Better to remain silent and be thought a fool than to speak out and remove all doubt."
But seriously, in any mathematical discussion you must assume some background material, which implies that someone is not going to understand what you're talking about.
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Dan Asimov Sent: Thursday, August 13, 2015 1:01 AM To: math-fun Subject: Re: [math-fun] Game question
David,
I can't remember the last time I saw A.P. used as an abbrev. to mean arithmetic progression — quite possibly I never did. It took me maybe 3 minutes before I thought of that (which I presume is what you mean, right?).
Maybe next time you can spell it out — or abbreviate it like "arith. prog." — the first time with e.g. "A.P." in parentheses, and then use A.P. after that?
(At first I thought it was probably some common abbrev. in number theory, a subject I don't have a lot of knowledge about.)
Thanks,
Dan
On Aug 12, 2015, at 9:22 PM, David Wilson <davidwwilson@comcast.net> wrote:
Consider a game in which two players, A and B, each choose distinct integers by turn.
A's object is to maximize the length of the longest A.P. among his selected integers.
B's object is to limit the length of A's longest A.P.
Show that B cannot prevent A from obtaining an A.P. of length 3.
Can B prevent A from obtaining an A.P. of some length N?
What is the smallest such N?
_______________________________________________ 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
I'm pretty sure I have a strategy for length four now. The length three row made by the previous strategy is only blocked by B on one end; A can extend it to four on the other. On Thu, Aug 13, 2015 at 11:43 AM, Allan Wechsler <acwacw@gmail.com> wrote:
B cannot prevent A from owning two consecutive integers on the second move. Regardless of what B does, A can now place a "pivot" far enough away from the first pair that the reflection of the pair through the pivot is a distant pair of integers, neither of which are claimed. B cannot claim both, and A wins on the fourth move.
I haven't thought much about length four goals. This is very reminiscent of the "angels and demons" problem.
On Thu, Aug 13, 2015 at 8:59 AM, David Wilson <davidwwilson@comcast.net> wrote:
You'll have to forgive me. Having encountered the abbreviation "A.P." in high school, I assumed it was on a par with "GCD" or "LCM" in terms of general familiarity, meaning I didn't need to define it in this forum. Apologies. "A.P." indeed stands for "arithmetic progression".
I feel your pain. When I see something I don't understand in this forum, I usually wait for the follow-up messages to clarify the situation, or in the case of analysis geeks spouting about q-equations, Galois groups and hypergeometric functions, politely skip on to the next email. "Better to remain silent and be thought a fool than to speak out and remove all doubt."
But seriously, in any mathematical discussion you must assume some background material, which implies that someone is not going to understand what you're talking about.
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Dan Asimov Sent: Thursday, August 13, 2015 1:01 AM To: math-fun Subject: Re: [math-fun] Game question
David,
I can't remember the last time I saw A.P. used as an abbrev. to mean arithmetic progression — quite possibly I never did. It took me maybe 3 minutes before I thought of that (which I presume is what you mean, right?).
Maybe next time you can spell it out — or abbreviate it like "arith. prog." — the first time with e.g. "A.P." in parentheses, and then use A.P. after that?
(At first I thought it was probably some common abbrev. in number theory, a subject I don't have a lot of knowledge about.)
Thanks,
Dan
On Aug 12, 2015, at 9:22 PM, David Wilson <davidwwilson@comcast.net> wrote:
Consider a game in which two players, A and B, each choose distinct integers by turn.
A's object is to maximize the length of the longest A.P. among his selected integers.
B's object is to limit the length of A's longest A.P.
Show that B cannot prevent A from obtaining an A.P. of length 3.
Can B prevent A from obtaining an A.P. of some length N?
What is the smallest such N?
_______________________________________________ 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
Here's a simple strategy for length 4. You didn't say who goes first; I"ll prove the stronger version where B goes first. Call the first play by B b1, the second b2, whiile A's first play is 0 (if b1= 0, just translate everything). Choose X>1 coprime to b1 and b2. All subsequent plays by A will be on multiples of X, so we can ignore all plays that are not multiples of X, including B1 and B2. A's second play is at 2X. If B3 is anything other than -4X, -2X, 4X, or 6X, A can win by playing A3 at either -2X or 4X, with two threats of 4 in a row. If B plays at one of these, A plays at X, and at -X or 3X next. A proof (from a known theorem) that A wins for length 5. It is well-known by those who know about such things that the first player has a forced win at the original version of the game of Go-Moku, played on a 2-d array, where 5 in a row (orthogonally or diagonally) wins, on a sufficiently large board. use the above trick to make B's first move ignorable, then number a sufficiently large square board in the obvious way. This game is easier for A to win than simplified Go-Moku in many ways: 5 in a row for B does not win for B, and many sets of 5 that are not 5-in-a-row by the Go-Moku definition are still a win (5 in a row along a direction that is not orthogonal or diagonal, such as a knight's move, or every other spot along a row or a column). But every 5-in-a-row by Go-Moku rules is also an AP, so when A makes 5 in a row, he wins both games. I suspect A can force a win with lengths much greater than 5. In particular, if A can force k in a row on an N-dimensional board, that suffices to get an AP of length k, and the higher the dimension, the easier it is to force long rows. I think Winning Ways says something about n-dimensional k-in-a-row, but I don't have my copy handy. If I had to guess, I would guess that A can force an arithmetic progression of any fixed finite length. Andy On Thu, Aug 13, 2015 at 11:58 AM, Allan Wechsler <acwacw@gmail.com> wrote:
I'm pretty sure I have a strategy for length four now. The length three row made by the previous strategy is only blocked by B on one end; A can extend it to four on the other.
On Thu, Aug 13, 2015 at 11:43 AM, Allan Wechsler <acwacw@gmail.com> wrote:
B cannot prevent A from owning two consecutive integers on the second move. Regardless of what B does, A can now place a "pivot" far enough away from the first pair that the reflection of the pair through the pivot is a distant pair of integers, neither of which are claimed. B cannot claim both, and A wins on the fourth move.
I haven't thought much about length four goals. This is very reminiscent of the "angels and demons" problem.
On Thu, Aug 13, 2015 at 8:59 AM, David Wilson <davidwwilson@comcast.net> wrote:
You'll have to forgive me. Having encountered the abbreviation "A.P." in high school, I assumed it was on a par with "GCD" or "LCM" in terms of general familiarity, meaning I didn't need to define it in this forum. Apologies. "A.P." indeed stands for "arithmetic progression".
I feel your pain. When I see something I don't understand in this forum, I usually wait for the follow-up messages to clarify the situation, or in the case of analysis geeks spouting about q-equations, Galois groups and hypergeometric functions, politely skip on to the next email. "Better to remain silent and be thought a fool than to speak out and remove all doubt."
But seriously, in any mathematical discussion you must assume some background material, which implies that someone is not going to understand what you're talking about.
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Dan Asimov Sent: Thursday, August 13, 2015 1:01 AM To: math-fun Subject: Re: [math-fun] Game question
David,
I can't remember the last time I saw A.P. used as an abbrev. to mean arithmetic progression — quite possibly I never did. It took me maybe 3 minutes before I thought of that (which I presume is what you mean, right?).
Maybe next time you can spell it out — or abbreviate it like "arith. prog." — the first time with e.g. "A.P." in parentheses, and then use A.P. after that?
(At first I thought it was probably some common abbrev. in number theory, a subject I don't have a lot of knowledge about.)
Thanks,
Dan
On Aug 12, 2015, at 9:22 PM, David Wilson <davidwwilson@comcast.net> wrote:
Consider a game in which two players, A and B, each choose distinct integers by turn.
A's object is to maximize the length of the longest A.P. among his selected integers.
B's object is to limit the length of A's longest A.P.
Show that B cannot prevent A from obtaining an A.P. of length 3.
Can B prevent A from obtaining an A.P. of some length N?
What is the smallest such N?
_______________________________________________ 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
-- Andy.Latto@pobox.com
Let us say A always chooses the smallest nonnegative integer that has not yet been chosen. For a given k, what is the longest that B can hang on without A winning? Without loss of generality we can assume B always chooses numbers in an increasing sequence. On Wed, Aug 12, 2015 at 9:22 PM, David Wilson <davidwwilson@comcast.net> wrote:
Consider a game in which two players, A and B, each choose distinct integers by turn.
A's object is to maximize the length of the longest A.P. among his selected integers.
B's object is to limit the length of A's longest A.P.
Show that B cannot prevent A from obtaining an A.P. of length 3.
Can B prevent A from obtaining an A.P. of some length N?
What is the smallest such N?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [Golly link suppressed; ask me why] --
For some reason I am prompted to ask: what is known about maximal lengths of arithmetic progressions of 0's in the Morse-Thue sequence? I can see some sevens. On Thu, Aug 13, 2015 at 3:45 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Let us say A always chooses the smallest nonnegative integer that has not yet been chosen.
For a given k, what is the longest that B can hang on without A winning? Without loss of generality we can assume B always chooses numbers in an increasing sequence.
On Wed, Aug 12, 2015 at 9:22 PM, David Wilson <davidwwilson@comcast.net> wrote:
Consider a game in which two players, A and B, each choose distinct integers by turn.
A's object is to maximize the length of the longest A.P. among his selected integers.
B's object is to limit the length of A's longest A.P.
Show that B cannot prevent A from obtaining an A.P. of length 3.
Can B prevent A from obtaining an A.P. of some length N?
What is the smallest such N?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [Golly link suppressed; ask me why] --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Choose k sufficiently large that any 2-colouring of {1, 2, ..., 2^(2k + 1)} contains a monochromatic arithmetic progression of length N. The Thue-Morse sequence restricted to {1, 2, ..., 2^(2k + 1)} must therefore have either a blue or red arithmetic progression of length N. But since reflecting the interval inverts the colours: 0110100110010110 ... 1001011001101001 is the reflection of 1001011001101001 ... 0110100110010110 it must be the case that it contains both a blue and a red arithmetic progression of length N. Hence the Thue-Morse sequence contains arbitrarily long arithmetic progressions of each colour. Sincerely, Adam P. Goucher
Sent: Thursday, August 13, 2015 at 9:47 PM From: "Allan Wechsler" <acwacw@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Game question
For some reason I am prompted to ask: what is known about maximal lengths of arithmetic progressions of 0's in the Morse-Thue sequence? I can see some sevens.
On Thu, Aug 13, 2015 at 3:45 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Let us say A always chooses the smallest nonnegative integer that has not yet been chosen.
For a given k, what is the longest that B can hang on without A winning? Without loss of generality we can assume B always chooses numbers in an increasing sequence.
On Wed, Aug 12, 2015 at 9:22 PM, David Wilson <davidwwilson@comcast.net> wrote:
Consider a game in which two players, A and B, each choose distinct integers by turn.
A's object is to maximize the length of the longest A.P. among his selected integers.
B's object is to limit the length of A's longest A.P.
Show that B cannot prevent A from obtaining an A.P. of length 3.
Can B prevent A from obtaining an A.P. of some length N?
What is the smallest such N?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [Golly link suppressed; ask me why] --
_______________________________________________ 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
On Thu, Aug 13, 2015 at 4:56 PM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Choose k sufficiently large that any 2-colouring of {1, 2, ..., 2^(2k + 1)} contains a monochromatic arithmetic progression of length N.
How do you know that such a k exists?
Andy
Van der Waerden's theorem. Rich Schroeppel mentioned that Szemeredi's theorem, a hard generalisation of van der Waerden's theorem, kills the problem immediately without requiring the property that reversing the sequence flips the colours. In fact, Szemeredi actually kills the original 'game question': just keep choosing numbers arbitrarily from {1, 2, 3, ..., N}, and once you have N/2 of them (which your opponent can't prevent) then you can guarantee a length-k arithmetic progression (as long as you carefully chose N as a function of k). Sincerely, Adam P. Goucher
Szemeredi's Theorem (one of many) is that any large enough set of the natural numbers with positive upper density contains arithmetic progressions of any length. (Large-enough depends on the density.) https://en.wikipedia.org/wiki/Szemer%C3%A9di's_theorem In Wilson's game, player A can achieve a density ~ 1/2 just be choosing the smallest available number. Rich ---------------- Quoting "Adam P. Goucher" <apgoucher@gmx.com>:
Choose k sufficiently large that any 2-colouring of {1, 2, ..., 2^(2k + 1)} contains a monochromatic arithmetic progression of length N.
The Thue-Morse sequence restricted to {1, 2, ..., 2^(2k + 1)} must therefore have either a blue or red arithmetic progression of length N. But since reflecting the interval inverts the colours:
0110100110010110 ... 1001011001101001 is the reflection of 1001011001101001 ... 0110100110010110
it must be the case that it contains both a blue and a red arithmetic progression of length N.
Hence the Thue-Morse sequence contains arbitrarily long arithmetic progressions of each colour.
Sincerely,
Adam P. Goucher
Sent: Thursday, August 13, 2015 at 9:47 PM From: "Allan Wechsler" <acwacw@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Game question
For some reason I am prompted to ask: what is known about maximal lengths of arithmetic progressions of 0's in the Morse-Thue sequence? I can see some sevens.
On Thu, Aug 13, 2015 at 3:45 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Let us say A always chooses the smallest nonnegative integer that has not yet been chosen.
For a given k, what is the longest that B can hang on without A winning? Without loss of generality we can assume B always chooses numbers in an increasing sequence.
On Wed, Aug 12, 2015 at 9:22 PM, David Wilson <davidwwilson@comcast.net> wrote:
Consider a game in which two players, A and B, each choose distinct integers by turn.
A's object is to maximize the length of the longest A.P. among his selected integers.
B's object is to limit the length of A's longest A.P.
Show that B cannot prevent A from obtaining an A.P. of length 3.
Can B prevent A from obtaining an A.P. of some length N?
What is the smallest such N?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [Golly link suppressed; ask me why] --
_______________________________________________ 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
participants (7)
-
Adam P. Goucher -
Allan Wechsler -
Andy Latto -
Dan Asimov -
David Wilson -
rcs＠xmission.com -
Tom Rokicki