# 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, $$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 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, 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, 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. 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$$.

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

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$$.
• (Oh, note that $S = \sum s_i$) OP gave examples of how we can get at least 1 for even and odd cases. May 8, 2021 at 5:05
• @CalvinLin, the previous edition of the question had defined $S\le \min s_i$ and I solved the question for that. May 8, 2021 at 6:17