DMS Combinatorics Seminar

Speaker: Peter Johnson, AU 

Topic: On a Two-Person Game Proposed in the Graduate Student Research Seminar

Abstract: In the February 9 GSRS, the following type of 2-player game was proposed:  For an integer t > 2, and integers 0 < a(1) < … < a(t – 1), let S = {0, a(1), … , a(t – 1)}.  Two players, Roberto and Babette, will take turns coloring integers with red and blue, respectively, with no integer allowed to be colored twice, until one of them achieves the (monochromatic) coloring of a set of the form c + dS, in which c and d are integers and d is not 0.  (If d is required to be > 0, the game is slightly different.)  When this is achieved, the game is over and the player achieving the coloring has won.  In the Seminar it was claimed that when t = 3 the player to go first has a winning strategy, regardless of what S is (although the strategy will vary as S varies).

      A number of questions arise, but in this talk I hope to raise questions that you may not have noticed right off, based on these games’ kinship with tic-tac-toe, and the obvious connection of certain modifications of these games (in which all the coloring is confined to a finite block of consecutive integers) to the famous 1927 theorem of B. L. van der Waerden about avoiding monochromatic k-term arithmetic  progressions in coloring blocks of consecutive integers.  (Note that every k-term arithmetic progression is a set of the form c + dS, S = {0, 1, 2, … , k – 1}, d > 0.)