tailieunhanh - Báo cáo toán học: "Yet Another Hat Game"

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: Yet Another Hat Game. | Yet Another Hat Game Maura B. Paterson Department of Economics Mathematics and Statistics Birkbeck University of London Malet Street London WC1E 7HX UK Douglas R. Stinson David R. Cheriton School of Computer Science University of Waterloo Waterloo Ontario N2L 3G1 Canada dstinson@ Submitted Jan 21 2010 Accepted May 26 2010 Published Jun 7 2010 Mathematics Subject Classification 91A46 91A12 Abstract Several different hat games have recently received a fair amount of attention. Typically in a hat game one or more players are required to correctly guess their hat colour when given some information about other players hat colours. Some versions of these games have been motivated by research in complexity theory and have ties to well-known research problems in coding theory and some variations have led to interesting new research. In this paper we review Ebert s Hat Game which garnered a considerable amount of publicity in the late 90 s and early 00 s and the Hats-on-a-line Game. Then we introduce a new hat game which is a hybrid of these two games and provide an optimal strategy for playing the new game. The optimal strategy is quite simple but the proof involves an interesting combinatorial argument. 1 Introduction In this introduction we review two popular hat games and mention some related work. In Section 2 we introduce our new game and give a complete solution for it. In Section 3 we make some brief comments. research supported by NSERC discovery grant 203114-06 THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R86 1 Table 1 Analysis of Ebert s hat game for three players configuration guesses outcome brown brown brown gray gray gray lose brown brown gray gray win brown gray brown gray win brown gray gray brown win gray brown brown gray win gray brown gray brown win gray gray brown brown win gray gray gray brown brown brown lose Ebert s Hat Game The following hat game was posed in a 1998 computer science PhD thesis by Todd Ebert 6