1
$\begingroup$

Problem

A group of $n+1$ people $A_0,A_1,A_2,...,A_n$ is playing a game. First for each $A_i(0<i\leq n)$, $A_0$ randomly tell him a number $t_i\in\{-1,1\}$. After all person (except $A_0$) is told a number, each person (except $A_0$) $A_i$ should guess what $t_{i+1}$ is ($t_{n+1}=t_1$), then tell the number he guesses ($g_i\in\{-1,1\}$) to $A_0$. Then $A_i$'s score is $$ s_i=\frac{g_it_{i+1}+1}{2} $$ ($s_1=1$ if $g_i=t_{i+1}$, and $0$ otherwise.) It's known that everyone (except $A_0$) knows only his own number (i.e. $g_i$ can only be based on $t_i$) and his own guess $g_i$ (i.e. he can't change his strategy after the game starts). The group's score will be $S=s_1+s_2+...+s_n$. If they can make a strategy together before the game start, which strategy they should choose to maximize the maximal value of $S$ they can guarantee?


Special cases

  • When $n=3$, the strategy is, $g_1=-t_1, g_2=t_2$. We can make $S=1$.

  • When $n=2k+1,k\in\mathbb{Z}$, I'll show that we can make $S\geq1$.

Let $g_i=t_i$ for all $0<i\leq n$. I claim that there must be an $r$ such that $g_r=t_{r+1}$, which means $S\geq1$.

If $t_r\not=t_{r+1}$ for all $0<i\leq n$, then $t_r=-t_{r+1}$, so $t_{r+2}=t_r$ ($t_{n+2}=t_2$). So $$ t_1=t_3=t_5=...=t_7=t_{2k+1}=t_n=-t_{n+1}=-t_1 $$ , which means $t_1=-t_1$. Contradiction.

  • Similarly, When $n$ is even, let $g_i=t_i$ for all $0<i\leq n,i\not=p$, and $g_p=-t_p$. One can know that, using this strategy, $S\geq 1$.

Question

Can anyone find a

  • Stricter lower bound ($>1$),

  • An upper bound, or

  • An approximation or exact form

for $S$?


Edit. I suspect that $S=1$. If their strategy is $g_i=\epsilon_it_i$ where $\epsilon_i\in\{0,1\}$, then there is a situation that $t_{i+1}=-\epsilon_it_i$ for all $0<i<n$. In this situation, except $A_n$, everyone's guess will be wrong. We've showed that $S\geq1$. So $S=1$.

The problem is they don't need to make their guess based on $t_i$. Some of them may have a constant $g_i$.

$\endgroup$
8
  • $\begingroup$ Any suggestion for edits (especially clarification) is welcomed. $\endgroup$
    – atzlt
    May 7, 2021 at 15:52
  • $\begingroup$ For $n=3$, why do you only have 2 guesses? Did you mean $n=2$? $\endgroup$
    – Calvin Lin
    May 7, 2021 at 16:14
  • $\begingroup$ For $n$ even, what is $p$? It's not defined anywhere. Did you want $ p = n$? $\endgroup$
    – Calvin Lin
    May 7, 2021 at 16:16
  • $\begingroup$ FYI The initial definition of $s_i$ can be difficult to parse. I suggest just giving the definition in the brackets directly. $\endgroup$
    – Calvin Lin
    May 7, 2021 at 16:22
  • $\begingroup$ I don't understand the definition of $S$, to be honest. Can you clarify? Does it correspond to minimum possible sum of $\{s_i\}$? $\endgroup$
    – Joffan
    May 7, 2021 at 16:24

1 Answer 1

1
$\begingroup$

Let us define $y_i=g_i/t_i$. Actually $y_i$ denotes whether the $i$th player chooses to say the truth or lie about his assigned number $t_i$. We seek to maximize $$ \min_{1\le i\le n} s_i\equiv\min_{1\le i\le n} y_it_it_{i+1} $$ by choosing $\{y_i\}_{i=1}^n$ such that no choice of $\{t_i\}_{i=1}^n$ would degrade the result. However, for any choice of $\{y_i\}$, there is a choice of $\{t_i\}$ such that some $\{s_i\}$ become zero. To this end, in a scenario $A_0$ can randomly make $A_1$ to guess wrong by defining $t_2=-g_1$ and $t_{n}=t_{n-1}=\cdots =t_2$. Therefore, the maximal value of $S$ players can guarantee is $0$.

$\endgroup$
2
  • $\begingroup$ (Oh, note that $S = \sum s_i$) OP gave examples of how we can get at least 1 for even and odd cases. $\endgroup$
    – Calvin Lin
    May 8, 2021 at 5:05
  • 1
    $\begingroup$ @CalvinLin, the previous edition of the question had defined $S\le \min s_i$ and I solved the question for that. $\endgroup$ May 8, 2021 at 6:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .