کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9515369 | 1343449 | 2005 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The Rényi-Ulam pathological liar game with a fixed number of lies
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The q-round Rényi-Ulam pathological liar game with k lies on the set [n]â{1,â¦,n} is a 2-player perfect information zero sum game. In each round Paul chooses a subset Aâ[n] and Carole either assigns 1 lie to each element of A or to each element of [n]⧹A. Paul wins if after q rounds there is at least one element with k or fewer lies. The game is dual to the original Rényi-Ulam liar game for which the winning condition is that at most one element has k or fewer lies. Define Fk*(q) to be the minimum n such that Paul can win the q-round pathological liar game with k lies and initial set [n]. For fixed k we prove that Fk*(q) is within an absolute constant (depending only on k) of the sphere bound, 2q/q⩽k; this is already known to hold for the original Rényi-Ulam liar game due to a result of J. Spencer.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 112, Issue 2, November 2005, Pages 328-336
Journal: Journal of Combinatorial Theory, Series A - Volume 112, Issue 2, November 2005, Pages 328-336
نویسندگان
Robert B. Ellis, Vadim Ponomarenko, Catherine H. Yan,