| The following search game is considered in this paper: there are two players, say Paul (or questioner) and Carole (or responder). They fix three integers n≥1, e≥0 and q≥2. Carole chooses a number x*∈S = {1.2.…, n}, Paul has to find the number x* by asking q-ary queries and Carole is allowed to lie at most e times. The main aim of this model is to find an algorithm which allows Paul can guess x* successfully with minimum number of queries. The main results of this paper are as following:For the q-ary pathological search game with one lie, by introducing concepts of typical-state, state-character, etc., we establish an algorithm which transfers a typical-state with big character to a small one, and get a sufficient condition for Paul to win the game. We obtain a necessary condition which assure Paul can win the game, through designing the first query elaborately. Based on above conclusions, for n≥qq-1, we give an optimal algorithm allowing Paul can win; for n < qq-1, we get an inferior-optimal algorithm, and explain the reason why can not get an optimal algorithm by some examples.Q-ary search game with one lie and bi-interval queries is solved completely. At first, we introduce the q-ary search game with one lie and bi-interval queries by extending the binary liar game with bi-interval queries. Then, we establish the necessary and sufficient conditions which assure Paul can win by introducing the concepts of "order relation" , "arc" and "well-shaped state". At last, we determine the accurate values of minimum number of queries which assure Paul can win, and provide the corresponding algorithm. |
PDF Full Text Request