Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Winning strong games through fast strategies for weak games. | Winning strong games through fast strategies for weak games Asaf Ferber School of Mathematical Sciences Raymond and Beverly Sackler Faculty of Exact Sciences Tel Aviv University Tel Aviv 69978 Israel. ferberas@ Dan Hefetz School of Mathematical Sciences Queen Mary University of London Mile End Road London E1 4NS England. etz@ Submitted Mar 8 2011 Accepted Jun 27 2011 Published Jul 15 2011 Mathematics Subject Classification 05C57 05C45 05C70 Abstract We prove that for sufficiently large n the first player can win the strong perfect matching and Hamilton cycle games. For both games explicit winning strategies of the first player are given. In devising these strategies we make use of the fact that explicit fast winning strategies are known for the corresponding weak games. 1 Introduction Let X be a finite set and let FC 2X be a family of subsets of X. In the strong game X F two players called Red and Blue take turns in claiming one previously unclaimed element of X with Red going first. The winner of the game is the first player to fully claim some F G F. If neither player is able to fully claim some F G F by the time every element of X has been claimed by either player the game ends in a draw. The set X will be referred to as the board of the game and the elements of F will be referred to as the winning sets. It is well known from classic Game Theory that for every strong game X F either Red has a winning strategy that is he is able to win the game against any strategy of Blue or Blue has a drawing strategy that is he is able to avoid losing the game against any strategy of Red a strategy stealing argument shows that Blue cannot win the game . THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P144 1 For certain games a hypergraph coloring argument can be used to prove that draw is impossible and thus these game are won by Red. Unfortunately not much more is known about strong games. In particular an explicit winning or drawing strategy is
