tailieunhanh - Báo cáo toán học: "A Note on the First Occurrence of Strings"

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í toán học quốc tế đề tài: A Note on the First Occurrence of Strings. | A Note on the First Occurrence of Strings Ying-Chao Hung Department of Statistics National Chengchi University Taipei 11605 Taiwan hungy@ Robert W. Chen Department of Mathematics University of Miami Coral Gables FL 33124 USA chen@ Alan Zame Department of Mathematics University of Miami Coral Gables FL 33124 USA May-Ru Chen Department of Applied Mathematics National Sun Yat-sen University Kaohsiung 80424 Taiwan chenmr@ Submitted Jun 20 2009 Accepted Jan 3 2010 Published Jan 14 2010 Mathematics Subject Classification 65C50 Abstract We consider the context of a three-person game in which each player selects strings over 0 1 and observe a series of fair coin tosses. The winner of the game is the player whose selected string appears first. Recently Chen et al. 4 showed that if the string length is greater and equal to three two players can collude to attain an advantage by choosing the pair of strings 11. 10 and 00 . 01. We call these two strings complement strings since each bit of one string is the complement bit of the corresponding bit of the other string. In this note we further study the property of complement strings for three-person games. We prove that if the string length is greater than five and two players choose any pair of complement strings except for the pair 11. 10 and 00 . 01 then the third player can always attain an advantage by choosing a particular string. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 N5 1 1 Introduction and Preliminaries Consider a game in which players select strings over 0 1 and observe a series of fair coin tosses . a string a s1s2 . where each s is chosen independently and randomly from 0 1 . The winner of the game is the player whose selected string appears first. This problem has been formulated as a game or studied as a classical probabilistic problem by Chen 1 Chen and Lin 2 Chen and Zame 3 Chen et al. 4 Guibas and Odlyzko 6 Li 7 Gerber and Li 5 and Mori