Mathematics – Combinatorics
Scientific paper
2004-07-28
Mathematics
Combinatorics
18 pages, 1 figure * Typo corrected in Definition 17. * Reference information completed for reference [4]
Scientific paper
10.1016/j.jcta.2005.02.003
The $q$-round Renyi-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\subseteq [n]$ and Carole either assigns 1 lie to each element of $A$ or to each element of $[n]\setminus 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 Renyi-Ulam liar game for which the winning condition is that at most one element has $k$ or fewer lies. We prove the existence of a winning strategy for Paul to the existence of a covering of the discrete hypercube with certain relaxed Hamming balls. Defining $F^*_k(q)$ to be the minimum $n$ such that Paul can win the $q$-round pathological liar game with $k$ lies and initial set $[n]$, we find $F^*_1(q)$ and $F^*_2(q)$ exactly. For fixed $k$ we prove that $F_k^*(q)$ is within an absolute constant (depending only on $k$) of the sphere bound, $2^q/\binom{q}{\leq k}$; this is already known to hold for the original Renyi-Ulam liar game due to a result of J. Spencer.
Ellis Robert B.
Ponomarenko Vadim
Yan Catherine H.
No associations
LandOfFree
The Renyi-Ulam pathological liar game with a fixed number of lies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Renyi-Ulam pathological liar game with a fixed number of lies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Renyi-Ulam pathological liar game with a fixed number of lies will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-457486