Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Optimal Penney Ante Strategy via Correlation Polynomial Identities. | Optimal Penney Ante Strategy via Correlation Polynomial Identities Daniel Felix Department of Mathematics University of California at San Diego La Jolla CA 92093-0112 dfelix@ Submitted Oct 19 2004 Accepted Mar 30 2006 Published Apr 4 2006 Mathematics Subject Classifications 60C05 05A19 Abstract In the game of Penney Ante two players take turns publicly selecting two distinct words of length n using letters from an alphabet Q of size q. They roll a fair q sided die having sides labelled with the elements of Q until the last n tosses agree with one player s word and that player is declared the winner. For n 3 the second player has a strategy which guarantees strictly better than even odds. Guibas and Odlyzko have shown that the last n 1 letters of the second player s optimal word agree with the initial n 1 letters of the first player s word. We offer a new proof of this result when q 3 using correlation polynomial identities and we complete the description of the second player s best strategy by characterizing the optimal leading letter. We also give a new proof of their conjecture that for q 2 this optimal strategy is unique and we provide a generalization of this result to higher q. 1 Introduction We are interested in a generalization of the coin flipping game Penney Ante invented in 1969 by Walter Penney. In its original version two players take turns publicly selecting distinct binary sequences of a fixed length n. They flip a fair coin with sides labelled 0 and 1 until the last n results match one player s sequence and that player is declared the winner. We study a version of this game in which the coin is abandoned in favor of a fair q sided die. The faces of our die are labelled with the elements of a set Q of size q. We call Q an alphabet and its elements letters. We will refer to a finite string of letters as a word. Penney Ante s most striking feature is the nontransitivity of its beating relation among words of fixed length n 3 where we say .
