|
Arithmetic Progression Game
The arithmetic progression game is a positional game where two players alternately pick numbers, trying to occupy a complete arithmetic progression of a given size. The game is parameterized by two integers ''n'' > ''k''. The game-board is the set . The winning-sets are all the arithmetic progressions of length ''k''. In a Maker-Breaker game variant, the first player (Maker) wins by occupying a ''k''-length arithmetic progression, otherwise the second player (Breaker) wins. The game is also called the van der Waerden game, named after Van der Waerden's theorem. It says that, for any ''k'', there exists some integer ''W''(2,''k'') such that, if the integers are partitioned arbitrarily into two sets, then at least one set contains an arithmetic progression of length ''k''. This means that, if n \geq W(2,k), then Maker has a winning strategy. Unfortunately, this claim is not constructive - it does not show a specific strategy for Maker. Moreover, the current upper bound for ' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Positional Game
A positional game is a kind of a combinatorial game for two players. It is described by: *Xa finite set of elements. Often ''X'' is called the ''board'' and its elements are called ''positions''. *\mathcala family of subsets of X. These subsets are usually called the ''winning-sets''. * A criterion for winning the game. During the game, players alternately claim previously-unclaimed positions, until one of the players wins. If all positions in X are taken while no player wins, the game is considered a draw. The classic example of a positional game is Tic-tac-toe. In it, X contains the 9 squares of the game-board, \mathcal contains the 8 lines that determine a victory (3 horizontal, 3 vertical and 2 diagonal), and the winning criterion is: the first player who holds an entire winning-set wins. Other examples of positional games are Hex and the Shannon switching game. For every positional game there are exactly three options: either the first player has a winning strategy, or ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Arithmetic Progression
An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common difference of 2. If the initial term of an arithmetic progression is a and the common difference of successive members is d, then the n-th term of the sequence (a_n) is given by: :a_n = a + (n - 1)d, If there are ''m'' terms in the AP, then a_m represents the last term which is given by: :a_m = a + (m - 1)d. A finite portion of an arithmetic progression is called a finite arithmetic progression and sometimes just called an arithmetic progression. The sum of a finite arithmetic progression is called an arithmetic series. Sum Computation of the sum 2 + 5 + 8 + 11 + 14. When the sequence is reversed and added to itself term by term, the resulting sequence has a single repeated value in it, equal to the sum of the first and last numbers ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Maker-Breaker Game
A Maker-Breaker game is a kind of positional game. Like most positional games, it is described by its set of ''positions/points/elements'' (X) and its family of ''winning-sets'' (\mathcal- a family of subsets of X). It is played by two players, called Maker and Breaker, who alternately take previously-untaken elements. In a Maker-Breaker game, Maker wins if he manages to hold all the elements of a winning-set, while Breaker wins if he manages to prevent this, i.e. to hold at least one element in each winning-set. Draws are not possible. In each Maker-Breaker game, either Maker or Breaker has a winning strategy. The main research question about these games is which of these two options holds. Examples A classic Maker-Breaker game is Hex. There, the winning-sets are all paths from the left side of the board to the right side. Maker wins by owning a connected path; Breaker wins by owning a connected path from top to bottom, since it blocks all connected paths from left to right. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Van Der Waerden's Theorem
Van der Waerden's theorem is a theorem in the branch of mathematics called Ramsey theory. Van der Waerden's theorem states that for any given positive integers ''r'' and ''k'', there is some number ''N'' such that if the integers are colored, each with one of ''r'' different colors, then there are at least ''k'' integers in arithmetic progression whose elements are of the same color. The least such ''N'' is the Van der Waerden number ''W''(''r'', ''k''), named after the Dutch mathematician B. L. van der Waerden. Example For example, when ''r'' = 2, you have two colors, say and . ''W''(2, 3) is bigger than 8, because you can color the integers from like this: and no three integers of the same color form an arithmetic progression. But you can't add a ninth integer to the end without creating such a progression. If you add a , then the , , and are in arithmetic progression. Alternatively, if you add a , then the , , and are in arithmetic progression. In fact, there is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
József Beck
József Beck (Budapest, Hungary, February 14, 1952) is a Harold H. Martin Professor of Mathematics at Rutgers University. His contributions to combinatorics include the partial colouring lemma and the Beck–Fiala theorem in ''discrepancy theory'', the algorithmic version of the Lovász local lemma, the Beck's theorem (geometry), two extremes theorem in combinatorial geometry and the second moment method in the theory of positional games, among others. Beck was awarded the Fulkerson Prize in 1985 for a paper titled ''"Roth's estimate of the discrepancy of integer sequences is nearly sharp"'', which introduced the notion of discrepancy on hypergraphs and established an upper bound on the discrepancy of the family of arithmetic progressions contained in , matching the classical lower bound up to a polylogarithmic function, polylogarithmic factor. Jiří Matoušek (mathematician), Jiří Matoušek and Joel Spencer later succeeded in getting rid of this factor, showing that the bound ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
