Solution of Ulam's searching game with three lies or an optimal adaptive strategy for binary three-error-correcting codes

被引：19

作者：

Deppe, C ^{[1
]}

机构：

[1] Univ Bielefeld, Dept Math, D-33501 Bielefeld, Germany

来源：

DISCRETE MATHEMATICS | 2000年 / 224卷 / 1-3期

关键词：

searching with lies; transmission with feedback; Ulam's game;

D O I：

10.1016/S0012-365X(00)00109-6

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper we determine the minimal number of yes-no queries that are needed to find an unknown integer between 1 and N, if at most three of the answers are lies. This strategy is also an optimal adaptive strategy for binary three-error-correcting codes. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：79 / 98

页数：20

共 30 条

[1]

Ahlswede R., 1987, Search Problems

[2] Searching with lies [J].

Aigner, M .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1996, 74 (01) :43-56

[3]

AIGNER M, 1988, COMBINATORIAL SEARCH

[4]

[Anonymous], MATH SEMESTERBER

[5]

[Anonymous], MATH MAG

[6]

BALAKIRSKY VB, 1998, 98070 U BIEL

[7]

Berlekamp E. R., 1968, Error correcting codes, P61

[8] SOLUTION OF ULAMS PROBLEM ON BINARY SEARCH WITH 2 LIES [J].

CZYZOWICZ, J ;

PELC, A ;

MUNDICI, D .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1988, 49 (02) :384-388

[9] ULAM SEARCHING GAME WITH LIES [J].

CZYZOWICZ, J ;

MUNDICI, D .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1989, 52 (01) :62-76

[10] SEARCHING WITH A FORBIDDEN LIE PATTERN IN RESPONSES [J].

CZYZOWICZ, J ;

LAKSHMANAN, KB ;

PELC, A .

INFORMATION PROCESSING LETTERS, 1991, 37 (03) :127-132

← 1 2 3 →