2
$\begingroup$

Denote strings $u,v$ from $\{0,1\}^n$.

Denote concatenated pair $[uv]$.

Denote $$[uv]_{1}=\{[uv]\oplus e_i\}_{i=1}^{2n}$$ collection of pairs with Hamming distance $1$ from $[uv]$ string concatenation.

$e_i\in\{0,1\}^{2n}$ is almost $0$ vector with $1$ at $i$th position.

Denote $\mathsf{G_{2n}}$ to be universe of deterministic games played by Alice, Bob where Alice gets a random string $u$ from $\{0,1\}^n$, Bob gets a random string $v$ from $\{0,1\}^n$ where games in universe either ends in win by one side or draw (games containing drawing a possibility).

Take values $c\geq1$, $r>2$ fixed.

Is is true that $\forall n\in\Bbb N$, there is no game $G\in\mathsf{G_{2n}}$ such that following conditions will be satisfied?

$1.$ If at every string pair $u,v$ that results in a win, number of pairs from collection $[uv]_1$ that results in a draw is atmost $n^{\frac{1}{rc}}$.

$2.$ If at every string pair $u,v$ that results in a draw, number of pairs from collection $[uv]_1$ that results in a win is atmost $n^{\frac{1}{rc}}$.

$3.$ There is a pair $u,v$ that results in a win (or draw) such that balls of vectors with hamming distance atleast $n^{\frac{1}{c}}$ from $u,v$ respectively contains atleast a pair of $u,v$ that results in a draw (or win).

Improve this question
$\endgroup$
2
  • $\begingroup$ I'm not sure I understand your question, especially where games come to play, as this seems to be a problem about subsets of $\{0,1\}^n$, but aren't all conditions satisfied if a game is a win if and only if the first coordinate of $u$ is $1$? $\endgroup$
    – domotorp
    Jan 28, 2015 at 21:20
  • $\begingroup$ @domotorp I am thinking of a game as a protocol tree that is fixed (just like game Nim plays). $\endgroup$
    – Turbo
    Jan 28, 2015 at 21:23

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.