Is the peeking relevant? How does it help?

math90 wrote: Is the peeking relevant? How does it help? It lets you see everyone else's answers. For example, suppose that everyone else picked the same answer. Then you can pick that same answer.

Just keep copying off the guy who's just behind you in overall score.. if there are many of them, then just choose any one.. I think this just works

TheOneYouWant wrote: Just keep copying off the guy who's just behind you in overall score.. if there are many of them, then just choose any one.. I think this just works How would we prevent against the following scenario ($n=3$): Scores (1,2,3,C): -4,-4,-4,0 Q: 0+0 A1: twenty-one; A2: 0; A3: cero AC: twenty-one (targets player 1) Scores : -6,-4,-4,-1 Q: 0+1 A1: 1; A2: twenty-one; A3: uno AC: twenty-one (targets player 2) Scores: -6,-6,-4,-2 Q: 0+2 A1: 2; A2: dos; A3: twenty-one AC: twenty-one (targets player 3) Scores: -6,-6,-6,-3 (Repeat $k$ times to get Scores: $-4-2k,-4-2k,-4-2k,-3k$, clearly C gets far behind when $k$ gets large)

Rafayaashary, I made the same mistake at first. We should subtract two points from all incorrect answers, not just the player we are targeting. Hmmm, the bound actually seems weak? How can the other players play such that you are forced to give up a 4-point lead for $n=4$? Edit: or even a 3-point lead for $n=3$?

So is there only one correct way to write the answer? In the example I gave, every player except the one we target does get it right, albeit by writing a different form of the answer. The assumption is that we can make the cheater as uninformed as we like, so he/she has no idea about the correct answer, and cannot interpret the others' answers-only copy.

Yes, I think that's the case. The problem statement left that a bit ambiguous but I agree that you're counterexample proves that interpretation of the problem to be false. Still haven't run into any counterexamples to show we need more than an $n$ point lead....

Yes, I'm sorry, it was a blunder on my part . Probably, this means that the strategy must alternate between turns in some way, I.e. if greater than 50 percent participants choose an option, choose that one..

rafayaashary1 wrote: So is there only one correct way to write the answer? Only one correct answer way to write the answer. laegolas wrote: Still haven't run into any counterexamples to show we need more than an $n$ point lead.... I have a proof that a lead of $2^{n-2}+1$ is sufficient. But this is still exponential in $n$ as $n \to \infty$. I would be interested in any proof that achieves even a polynomial bound in $n$.

Who wrote this?

mssmath wrote: Who wrote this? Linus Hamilton, I believe.

Let me stake my claim and post a complete solution for $2^{n-2}+1$. We first make the following reductions. First, change the weights to be $+1$, $-1$, $0$ respectively (rather than $0$, $-2$, $-1$); this clearly has no effect. Also, WLOG that all contestants except you initially have score zero (and that your score exceeds $2^{n-2}$). WLOG ignore rounds in which all answers are the same. Finally, ignore rounds in which you get the correct answer, since that leaves you at least as well off as before --- in other words, we'll assume your score is always fixed, but you can pick any group of people with the same answers and ensure they lose 1 point, while some other group gains $1$ point. The key observation is the following. Consider two rounds $R_1$ and $R_2$ such that: In round $R_1$, some set $S$ of contestants gains a point. In round $R_2$, the set $S$ of contestants all have the same answer. Then, if we copy the answers of contestants in $S$ during $R_2$, then the sum of the scorings in $R_1$ and $R_2$ cancel each other out. In other words we can then ignore $R_1$ and $R_2$ forever. We thus consider the following strategy. We keep a list $\mathcal L$ of subsets of $\{1, \dots, n\}$, initially empty. Now do the following strategy: On a round, suppose there exists a set $S$ of people with the same answer such that $S \in \mathcal L$. Then, copy the answer of $S$, causing them to lose a point. Delete $S$ from $\mathcal L$. (Do not add any new sets to $\mathcal L$.) Otherwise, copy any set $T$ of contestants, selecting $|T| \ge n/2$ if possible. Let $S$ be the set of contestants who answer correctly (if any), and add $S$ to the list $\mathcal L$. Note that $|S| \le n/2$, since $S$ is disjoint from $T$. By construction, $\mathcal L$ has no duplicate sets. So the score of any contestant $c$ is bounded above by the number of times that $c$ appears among sets in $\mathcal L$. The number of such sets is clearly at most $\frac{1}{2} \cdot 2^{n-1}$. So, if you lead by $2^{n-2}+1$ then you ensure victory. This completes the proof!

Here is a strategy I suggested on the test which seems like it should have a significantly stronger bound: For each player $X$, define $d_X$ to be the difference between your score and theirs. Break the set of all answers given into sets with all players who had the same answer, call these $A_1,A_2, \dots$ Answer the same answer as the players in $A_n$ such that $\sum_{X\in A_n} \frac{1}{d_X}$ is maximal. This strategy has the two key necessary benefits that it is more likely to choose a larger set of people, but is also more likely to choose players whose scores are close to yours. Unfortunately, bounding the minimum necessary lead you can win with (if any) using this strategy is more difficult than the actual problem. One could probably write a program that would run a large number of games where this strategy is used and determine a rough bound. However, I am not sufficiently skilled in that field to do so.

v_Enhance wrote: On a round, suppose there exists a set $S$ of people with the same answer such that $S \in \mathcal L$. Then, copy the answer of $S$, causing them to lose a point. Delete $S$ from $\mathcal L$. (Do not add any new sets to $\mathcal L$.) Otherwise, copy any set $T$ of contestants, selecting $|T| \ge n/2$ if possible. Let $S$ be the set of contestants who answer correctly (if any), and add $S$ to the list $\mathcal L$. Note that $|S| \le n/2$, since $S$ is disjoint from $T$. I'm sorry if this is a dumb question, but what if on a round there are two sets $S$ and $D$ of people with the same answer such that $S, D \in \mathcal L$? If we copy $S$ and it turns out that people from $D$ are correct then we don't add them to $\mathcal L$ since they're already there so how do we keep up with their score? From the second point we have $|S|, |D| \le n/2$ so it's possible for them to be disjoint.

math4444 wrote: I'm sorry if this is a dumb question, but what if on a round there are two sets $S$ and $D$ of people with the same answer such that $S, D \in \mathcal L$? If we copy $S$ and it turns out that people from $D$ are correct then we don't add them to $\mathcal L$ since they're already there so how do we keep up with their score? From the second point we have $|S|, |D| \le n/2$ so it's possible for them to be disjoint. Consider the current round and the round $R_S$ where people from $S$ answer correctly - no one will answer correctly in both rounds so we can just 'forget' them. So the current round doesn't add anything to $\mathcal L$ and the removal of $R_S$ remove $S$ from $\mathcal L$.

This is an amazing problem. I spent god-knows-how-long trying to find a monovariant...

Here is quite a crude solution for the original bound of $2^{n-1}$. Again, we do V_Enhance's reductions. To recap, we have a wrong answer for the $n$ people to be $-1$ point, a right answer for everyone to be $1$ point, and a wrong answer for the cheater to be $0$ points. Then the cheater's score is fixed. We don't care about the rounds where the cheater gets a question right, and we don't care about rounds where everyone gets the answer wrong, because the cheater's lead only increases. Hence we start the game with the cheater at WLOG $2^{n-1}$ points and everyone else at $0$ points. We consider the $n$ people of the set ${1, 2, ..., n}$ and note that at least one person gets a question right, and that person is not the cheater. The cheater does the following. Suppose a subset of the $n$ people get a question right in a round $R$. Then the next time that subset has the same answers, the cheater guesses their answer. Since we have removed from consideration when the cheater gets a question right, this subset must get the question wrong, and therefore their points are negated from the round $R$ ($+1$ and then $-1$). To maximize the number of points any of the $n$ non-cheaters get, we must run through all of the $2^n$ subsets before repeating one. For example, when $n = 3$, we must have something like ${(1)}, {(2)}, {(3)}, {(1, 2)}, {(2, 3)}, {(1, 3)}, {(1, 2, 3)}$ to be the sequence of subsets of people who get a question right. Then by Pigeonhole, we must repeat one of the subsets, and the past points are negated. Then the max number of points a person can get is the number of subsets that contain $c$, which is just $2^{n-1}$. Thus the max number of points one can receive is $2^{n-1}$, which can never exceed the cheater's score, and so the cheater will always win.

We can replace $2^{n-1}$ by $2^{n-2}+1$. We prove by induction that, there is a strategy to peek answer such that there are two collection of subsets $\mathcal{P}$ and $\mathcal{Q}$ with the following properties: 1. $X \in \mathcal{Q}$ iff $\overline{X} \in \mathcal{P}$. 2. $X$ doesn't contain the first contestant for all $X\in \mathcal{P}$. 3. For any contestant $x$, the cumulative points gained by this contestant in comparison with the cheater doesn't exceed: \[ \sum\limits_{X \in \mathcal{P}, x\in X}1 - \sum\limits_{X \in \mathcal{Q}, x \in X}1 \] In the first question, let $X$ be the set of contestant with the same answer as the first one. Let the cheater peek the answer from set $X$. If the answer is true, then choose $\mathcal{P} = \mathcal{Q} = \emptyset$. If the answer is false, then choose $\mathcal{P} = \{\overline{X}\}$, $\mathcal{Q} = \{X\}$. It is easy to check that this choice satisfies the above properties. Thus, the statement holds. Now, for question $t$, let $X_1,...,X_{l}$ be the sets with different answers (people in same set choose same answer). If all people choose the same answer then the cheater just peeks the same answer, and the state of the game doesn't change. Therefore, we consider only the case $l\ge 2$. We consider following cases: Case 1: if $X_i\in \mathcal{P}$ for some $i$, then the cheater will choose the same answer as $X_i$. If the answer is true, then no one gains any point (not to mention some will lose some point in comparison with the cheater), thus keep $\mathcal{P}$ and $\mathcal{Q}$ as they are, any the statement still holds. If the answer is false, then at most all people in $\overline{A_i}$ gains $1$ points, and people in $A_i$ lose $1$ point. Thus, we can update $\mathcal{P} = \mathcal{P} \backslash \{ A_i \}$ and $\mathcal{Q} = \mathcal{Q} \backslash \{ \overline{A_i}\}$. It is easy to check that the properties are still hold. Case 2: None of the $A_i$ s belongs to $\mathcal{P}$. Assume that $A_1$ contains the first contestant. Let the cheater peek the answer from $A_1$. If the answer is true, then we don't need to update $\mathcal{P}$ and $\mathcal{Q}$. If the answer is false, then let $A_j$ is the set which got the right answer we have $A_j$ doesn't contain the first contestant. Because $A_j \notin \mathcal{P}$, then $\overline{A_j} \notin \mathcal{Q}$. We can update $\mathcal{P} = \mathcal{P} \cup \{ A_j \}$ and $\mathcal{Q} = \mathcal{Q} \cup \{\overline{A_j}\}$. The properties are still hold. With the above strategy, after any question, the cumulative points gained by each contestant doesn't exceed: \[ \sum\limits_{X \in \mathcal{P}, x\in X}1 - \sum\limits_{X \in \mathcal{Q}, x \in X}1 \]Because for any $X$ in $\mathcal{P}$ $X$ doesn't contain the first contestant, thus the accumulate points of the first one is always non-positive. For any other contestant $x$, there are at most $2^{n-2}$ sets in $\mathcal{P}$ containing $x$, thus the cumulative points of this contestant is at most $2^{n-2}$. This completes our solution $\blacksquare$.

With a bit of induction we can prove that an $n-2$ lead (over all contestants) can gaurantee a loss. I am 90% sure that we can indeed win with an $n$ point lead, (I've tested up to n=5), but the proof seems very hard to me.

Alternative proof for bound n. Can sb tell me what's wrong with that one: We claim that at any moment the leading player will have an advance of A on the second.Here A is the number of people who have the same score as the second(including him). Proof:By induction on the number of rounds 1.Base In the beginning we have scores (n,0,0,0,0,0,0.....,0)(0s) 2.If we have it for round i then the leader chooses the answer of one of the second payers and if its correct everything is ok.If its wrong his advance on the second will be n-1 and the number of people who are second will have been reduced by at least one.Whence,induction is finished.

Lamp909 wrote: Alternative proof for bound n. Can sb tell me what's wrong with that one: We claim that at any moment the leading player will have an advance of A on the second.Here A is the number of people who have the same score as the second(including him). Proof:By induction on the number of rounds 1.Base In the beginning we have scores (n,0,0,0,0,0,0.....,0)(0s) 2.If we have it for round i then the leader chooses the answer of one of the second payers and if its correct everything is ok.If its wrong his advance on the second will be n-1 and the number of people who are second will have been reduced by at least one.Whence,induction is finished. After some time, there is only a single player at second place and you are 1 point ahead of him. But on third place, there is one million players, and they are all just 2 points behind you. In the current round, the single player on second place will make a wrong prediction. The one million players on third place all will make a correct prediction. What does your strategy do?

Consider the difference between your points and the points of the rest of contestants. Suppose the contestant are divided into two groups $ A,B$ by their answers. In case you stick to the answer of, say, $ A$ and it is wrong, the distance between you and $ A$ increases with $ 1$ and between you and $ B$ (right answer) decreases with $ 1$. In case the answer is true, your distance to $ A$ remains the same and to $ B$ increases by $ 2$. This case is entirely in your favor, so suppose it never happens. Thus the situation may be interpret as follows Jerry (as providence) partitions a set $ M$ of $n$ mice (initially on the start line) into two groups. Tom (as You) picks a group and moves all the mice inside it one unit backwards, and the other mice - one unit ahead. Prove that a mouse cannot get further than $2^{n-1}-1$ units ahead of the start line. Consider all distinct configurations, Jerry can partition the mice, i.e. the set $ P:=\{\,\{A,(M\setminus A)\}: A\subset M, A\neq \emptyset, M\}$. We've removed $ \{\emptyset, M\}$ since it is entirely in favor of Tom (he would move all mice back) and Jerry should not play like that. So, a Jerry's move consists of choosing some $ p\in P$ and the Tom's move may be imagine as assigning to $ p$ either $ -1$ or $ 1$, corresponding to the two options, he has. Let the sequence of partitions, Jerry divides mice, is $ p_1,p_2,\dots; p_i\in P$. The strategy, Tom sticks to is: He assigns to $ p_1$ randomly $ -1$ or $ +1$. At $ i$-th step, Tom looks up whether $ p_i$ has occurred before. If not - it doesn't matter what he assigns to $ p_i$. Otherwise, let $ j, j<i$ be the last index with $ p_j=p_i$, Tom assigns to $ p_i$ the opposite sign he has already assigned to $ p_j$. Note that if a partition $ p$ occurs in $ p_1,p_2,\dots$ with different signs, those two occurrences can be canceled, it would not affect the positions of mice. Thus, if from $ p_1,p_2,\dots,p_n$ we cancel the repeating partitions there remains only a set of distinct partitions, i.e. a subset of $ P$. Since $ |P|=2^{n-1}-1$, and any mouse advances with at most $ 1$ after each move, it follows a mouse cannot advance more than $ 2^{n-1}-1$ units away from the start line. So, the distance of $ 2^{n-1}$ points cannot be catch up with. $ \blacksquare$ The strategy of Tom can be optimized. At the first appearance of a partition $ p=\{A,B\}, |A|\leq |B|$, Tom chooses to move back the mice in $ B$ and forward - those in $ A$. Then, after canceling, only these positions remains. Hence, a mouse $ x\in M$ advances only if $ x\in A, |A|\leq n/2$. Clearly, all such $ A$ are $ 2^{n-2}$, meaning any mouse can advance at most $ 2^{n-2}$ units, thus they cannot reach the distance $2^{n-2}+1$ units ahead. A bunch of problems with a similar schema have been commented here: https://dgrozev.wordpress.com/2019/11/25/of-mice-and-tom-part-1/

Can someone clarify whether the $n$ contestants include or exclude the cheater?? @ below thanks , but one more doubt is the answer to every question a yes or no ?

CantonMathGuy wrote: You are cheating at a trivia contest. For each question, you can peek at each of the $n > 1$ other contestants' guesses before writing down your own. Read carefully

............

Suppose we make the game harder by selling the souls of the other contestants to the devil. The devil doesn't want you to win either, so he decides the contestants' guesses. Then, after you cheat and submit your answer as well, the devil picks an answer to that question. If at some point the Devil can't win, he gives up. For example, he will never act in a way that increases your lead over everyone. Let $S$ be the set of other contestants, and at some point suppose the devil partitions $S$ into nonempty subsets $S_1,\ldots,S_k$ where the members of $S_i$ answer $i$. We will always answer one of $1,\ldots,k$. Given this, the devil should never pick the answer to be something other than $1,\ldots,k$, since doing so will increase your lead by $1$ over everyone. Further, note that if we answer $1 \leq a \leq k$, the devil should never decide that the answer is $a$, because your lead over all $S_i, i \neq a$ will increase while your lead over $S_a$ will not decrease. Thus, on each move, we pick some $1 \leq a \leq k$, and our lead increases by $1$ over every $S_i, i \neq a$, and decreases by $1$ over $S_a$. I will now describe a "winning strategy" if we are leading by $2^{n-1}$ points. Keep a running list $\mathcal{L}$ of all subsets of $S$ whose lead over has been previously decreased (corresponding to $S_a$), which starts empty. When we receive a partition of $S=S_1 \cup \cdots \cup S_k$ from the devil, we check if $S \setminus S_i$ has appeared in $\mathcal{L}$ for every $i$. If it has for some $i:=j$, then answer $j$. This decreases our lead over $S \setminus S_j$ by $1$ and increases it over $S_j$ by the same amount, which undoes the previous move where our lead over $S_j$ decreased by $1$. Then delete $S \setminus S_j$ from $\mathcal{L}$. Also, if the devil partitions $S$ into a single set $S_1$, just answer $1$, which doesn't change your lead over everyone, and don't add $S=S_1$ to $\mathcal{L}$. Otherwise, answer arbitrarily, adding the appropriate set to $\mathcal{L}$ At any point in time, $\mathcal{L}$ doesn't contain any duplicate sets, since the second time a subset shows up it gets deleted. Further, for any contestant, the amount of points they're behind by is at least $2^{n-1}$ minus the number of times they appear in some element of $\mathcal{L}$. Since there are unconditionally $2^{n-1}$ subsets of $S$ that contain a given contestant, and $S$ will never appear in $\mathcal{L}$ (and contains that given student), it follows that at any point a given student appears in $\mathcal{L}$ at most $2^{n-1}-1$ times, so we can guarantee that we are always ahead by at least one point. $\blacksquare$ Remark: Of course, we can improve the bound somewhat by optimizing our "arbitrary decision", but it's not necessary. We don't need the "never add $S$ to $\mathcal{L}$" condition if we only need to tie for first either.

Incredibly funny! Initially thought it was a scales invariant but it's even better. It's DP! Each round, WLOG everyone chooses either answer $A$ or answer $B$. This yields a partition of guessers. The answer will always be the opposite of what you choose. Just remember which side you agreed with the last time the partition appeared, and reverse it. If everyone guesses the same, just guess along with them. The gain for any given opponent will be maxed out at $2^{n-1} - 1$, corresponding to the number of partitions minus the case where everyone guesses the same.

The best bound I see here is about $(1-o(1))2^{n-2}$. More precisely, #13 gives $2^{n-2} - \frac{1}{2} \binom{n-1}{\frac{n-1}{2}} + 1$ for $n$ odd, and some people believe the true bound to be polynomial. We show that $2^{n-2} - \frac{1}{2} \binom{n-1}{\frac{n-1}{2}} + 1$ is in fact best possible for $n$ odd, and a similar lower bound can be obtained for $n$ even, although likely not matching the best upper bound. I will not write the full proof here since it is too technical, but I will give the main ideas and the interested reader can attempt to prove it fully. We rephrase the problem into the following general two-player game between Tom and Jerry (as described in #24). Let $V\subset \mathbb{R}^n$ be a finite set of vectors and $A\subseteq \mathbb{R}^n$ be a convex region. Let $z\in \mathbb{R}^n$ be an initial vector. Each turn, Jerry picks a vector $v\in V$, then Tom replaces the vector $z$ with either $z+v$ or $z-v$. The game is played indefinitely, and Jerry wins if at any point in time, he escapes $A$, i.e. $z\not\in A$. Tom wins otherwise. In the original problem, the set $V$ consists of picking vectors of the form $\{-1,+1\}^n$, but only picking exactly one of $v,-v$. The set $A$ is the region $\{x\in \mathbb{R}^n : \forall i, x_i < R\}$, where $R=2^{n-1}$ is the bound in the question, or any other number we want, and the initial vector $z$ is 0. This game is studied in [1] I Bárány, On a class of balancing games, Journal of Combinatorial Theory, Series A, Vol 26, Issue 2, (1979), 115-126, although in that paper, only the region $A$ being a ball is considered. The upper bound is basically equivalent to the original question, and the proof can be rephrased as follows. Let $P(V)=\{\sum_{v\in I} v : I\subseteq V\}$ be the set of all subset sums of $V$. Then, if the initial vector $z$ lies in some translate $a+P(V)$ for some $a\in \mathbb{R}^n$, then Tom can always guarantee $z$ to remain in $a+P(V)$. Now all Tom has to do is find such a translate that fits in $A$. For the lower bound, if Tom cannot find such a translate inside $A$, then Jerry win. The idea is a discrete version of Blaschke's Inclusion Theorem from differential geometry (for example, see this). Roughly speaking, it says that if $B_1,B_2$ are strictly convex, compact sets in $\mathbb{R}^2$ and $B_1$ "curves more" than $B_2$, then for any point $p\in \partial B_2$, $B_1$ can be placed inside $B_2$ and tangent to it at $p$. This result can be easily extended to higher dimensions by a simple projection argument, although care is needed to define what it means to "curve more" in higher dimensions. The proof in [1] first shows that Tom's strategy is equivalent to constructing a so-called $V$-closed set inside $A$. A set $T\subseteq \mathbb{R}^{n}$ is $V$-closed if for any $t\in T$ and $v\in V$, then either $t-v\in T$ or $t+v\in T$. If such a set does not exist, i.e. Tom has no winning strategy, then Jerry has a winning strategy. This is not completely obvious, since the game is played on an infinite sequence of moves, and there exists infinite games (Gale-Stewart games) with no winning strategy for either player. Nevertheless, since Tom's winning condition is determined after only finitely many moves, his payoff set is open, and hence the game is determined by the Gale-Stewart theorem (see https://en.wikipedia.org/wiki/Borel_determinacy_theorem). If $V$ contains no parallel vectors, then a (convex hull of a) $V$-closed set $T$ must "curve less" than $P(V)$. Meaning, for any extreme point $p$ of $\text{conv}(T)$, we can place $P(V)$ touching $\text{conv}(T)$ at $p$, so that $P(V)$ is locally contained in $\text{conv}(T)$. Hence $\text{conv}(T)$ contains $P(V)$ by a discrete Blaschke's theorem, which is the main content in [1]. However, this is only true if $T$ is bounded, which we can assume of $A$ is a ball. In our case, $A$ is an unbounded sector, and hence $T$ is allowed to be unbounded, and the discrete Blaschke's theorem no longer holds. For example, a thin (but thick enough) hyperplane is $V$-closed, but does not contain $P(V)$. However, I believe that is the only obstruction, and a hyperplane does not fit in $A$. The interested reader may attempt to prove this. Here is a more precise statement. Exercise. Let $T$ be a $V$-closed set containing $z$. Then, either $\text{conv}(T)$ contains a hyperplane, or $\text{conv}(T)$ contains a translate of $\text{conv}(P(V))$ containing $z$. It remains to check that if $R=2^{n-2} - \frac{1}{2} \binom{n-1}{\frac{n-1}{2}}$, then $A$ cannot contain a translate of $\text{conv}(P(V))$ containing 0. Therefore, Tom has no winning strategy, and hence Jerry has a winning strategy by Gale-Stewart.