Three against the devil: a combinatorial game
A team of three sinners plays a game against the devil. They confer on strategy beforehand; then they go into three separate rooms, and there is no more communication between them. The play in each room follows the same rules, as described below.
A move consists of choosing some numbers from the set $\{1,\dots,N\}$ where $N$ is a fixed natural number. A number can only be chosen once; thus the two players in the room, sinner and devil, are dividing a finite set between them, as in tic-tac-toe or hex. The devil moves first, and chooses two numbers at each turn. The sinner moves second, and chooses three numbers at each turn. Play continues until all $N$ numbers have been chosen.
The sinners win if there is at least one number which is chosen by all of them; otherwise the devil wins.
Question: Do the sinners have a winning strategy if $N$ is sufficiently large?
We are not interested in randomized strategies. A winning strategy is a deterministic strategy which is sure to win against arbitrary play by the devil.
I don't know if there's an affirmative answer for $N=\omega$, nor whether an affirmative answer for $N=\omega$ would imply an affirmative answer for some finite $N$.
You can ask the same question for larger teams, but a team of three is the smallest interesting case. A team of two wins automatically if $N\ge5$.
The devil has to move first, or else it's a trivial win for the sinners.
The $3$-to-$2$ biased game ($3$ moves for the sinners, $2$ for the devil) is the simplest interesting case. The $1$-to-$1$ game is an easy win for the devil, even against a team of two. The sinners can win the $2$-to-$1$ version (with teams of any finite size) if N is large enough, but that's not completely trivial.
I called the team players "sinners" because I didn't know what else to call them; "men" or "women" would be sexist, "persons" or "humans" sounds too stilted. I guess "mortals" would work but I didn't think of that until now.
I used the combinatorial-game-theory tag because it seemed right to me, but I see that the official explanation says it's for perfect-information games. Was that a sin?
Edit for clarification: Judging from the comments, my poetic imagery about the Prince of Darkness is confusing people. It doesn't matter what the devil knows or doesn't know, because I'm asking for strategies which win against arbitrary play by the devil, in other words, in the worst case.
If it helps, you may imagine that the devil, instead of playing maliciously, is making random moves. The players then have an excellent chance of winning. The question is whether, for some $N$, there is a strategy which wins with probability one.
To put it more prosaically, let $B=\{1,\dots,N\}$, and define a strategy as a function $\sigma:2^B\rightarrow2^B$ such that, for each $X\subseteq B$, we have $\sigma(X)\subseteq X$ and $|\sigma(X)|=\min\{3,|X|\}$. The question is whether, for sufficiently large $N$, there exist strategies $\sigma_1,\sigma_2,\sigma_3$ such that, whenever $S_i$ is the set of numbers obtained by the sinner in a $\sigma_i$-compatible play (whatever that means--definition left as an exercise for the reader), we have $S_1\cap S_2\cap S_3\ne\emptyset$.
P.S. Shorter answer: Yes, the devil knows the sinners' strategies.
Edited again for further clarification: I believe the following restatement is equivalent to the original question:
Question (restated): Do there exist (for some $N$) families $\mathcal W_1,\mathcal W_2,\mathcal W_3\subseteq2^{\{1,\dots,N\}}$ such that (1) player $i$ has a strategy which guarantees that he will get all elements of some set $W_i\in\mathcal W_i$, and (2) if $W_i\in\mathcal W_i$ for $i=1,2,3$, then $W_1\cap W_2\cap W_3\ne\emptyset$? (As before, the Adversary goes first, and picks two numbers at each turn; the Player goes second, and picks three numbers at each turn.)
I guess I should have stated it that way in the first place instead of confusing the issue by trying to make it a story problem. Sorry about that!
Follow-up questions about Zackkenyon's answer:
I haven't gotten into the details yet. I have a big-picture question about just what it is that you're proving.
Your proof starts in talking about a number $k$ and and a partition into sets $S_{k,i}$, without explaining where they come from or what they have to do with anything. First I have to introduce some notation. Then I'll try to state what I think you're doing, so you can tell me if I'm right or wrong.
A strategy for the sinners is an ordered triple $\sigma=(\sigma_1,\sigma_2.\sigma_3)$ where $\sigma_i$ tells sinner $i$ how to play in room $i$. Given a natural number $k$ and a partition $\mathcal S=\{S_1,S_2,\dots\}$ of $[N]$ into $k$-element sets, I'll say that a strategy $\sigma=(\sigma_1,\sigma_2,\sigma_3)$ has property $Z(k,\mathcal S)$ if it guarantees that, regardless of how the devil plays, there will be some $i$ such that every number in $S_i$ is picked by sinner 3, while at least one number in $S_i$ is picked by both sinner 1 and sinner 2.
Clearly, if the strategy $\sigma$ has property $Z(k,\mathcal S)$ for some natural $k$ and some partition $\mathcal S$ into $k$-element sets, then $\sigma$ is a winning strategy. Maybe I'm missing something obvious, but I see no reason for the converse to hold; except, of course, that it holds vacuously if there are no winning strategies. Offhand, it seems to me that what you're doing is showing that no strategy can have the property $Z(k,\mathcal S)$.
Have I got that right? Does your argument show (I) that the sinners have no winning strategy of any kind, or does it just show (II) that a certain natural type of strategy (which most people think of first when trying to prove the affirmative) can't exist, while leaving open the possibility that some more exotic kind of strategy will do the trick? In case (I) I'd like to see some explanation of how that follows from what you wrote, or if there's some further part of the argument that you didn't write down. In case (II), that's a nice partial answer, but of course it doesn't dispose of the question.
To make the question clearer, let me try to define in general what it means for a triple $\sigma=\sigma_1,\sigma_2,\sigma_3$ to be a winning strategy for the sinners, so we can compare it to (what I understand to be) your approach. First lets consider what happens in room 3: using the strategy $\sigma_3$, sinner 3 acquires some set S of size $2N/5$. (No harm in assuming $N$ divisible by $5$.) Let $\mathcal S=\{S_1,S_2,\dots\}$ be the collection of all sets obtained in this way, with sinner 3 using $\sigma_3$ against all possible plays by the devil. Sinner 3 is guaranteed to get all elements of some $S_i$, but which $S_i$ he gets is up to the devil. Plainly, then, for the sinners to have a forced win, $\sigma_1$ and $\sigma_2$ have to guarantee that for each index $i$ there is at least one element of $S_i$ which is picked by both sinner 1 and sinner 2.
This is sort of like your $Z(k,\mathcal S)$ with $k=2N/5$, the big difference being that the $S_i$'s are not disjoint, which seems to really confuse the issue. Does your argument work if the $S_i$'s are not disjoint?
Solution 1:
This is a most intriguing problem and took many, many, many thinking hours to solve, I even wrote a script to better understand it.
It is possible for the sinners (players) to win every time. The number of players playing is irrelevant and the number of numbers they choose per turn is irrelevant as long as the players get to choose more numbers than the devil. In other words:
Theorem. Let $n,m,k\in\mathbb{N}$ such that $n>m$, then a $$n\text{-to-}m\text{ bias game & with }k\text{ players playing,}$$ has a winning solution for the players.
To show how this solution works, lets first demonstrate the $3$-to-$2$ bias scheme with $3$ players playing. Let $N=10^{2101}$, and $P=\{1,\ldots,10^{2101}\}$ be a large set.
Player 1 has only one job, pick one number in each of the sets $\{3n+1,3n+2,3n+3\}$; this can easily be done since the devil can only pick up to two numbers at a time.
So, Player 2 is now presented with $N'=10^{2101}/3$ sets, $P'=\{A_1,\ldots, A_{N'}\}$. Let $$P'_1=\{A_1,\ldots,A_{1000}\} \\ P'_2=\{A_{1001},\ldots,A_{2000}\} \\ \vdots \\ P'_{10^{2101}/3000}=\{A_{10^{2101}/3-999},\ldots,A_{N'}\}$$
such that each set, $A_i$, is size three and in each set, $A_i$, Player 1 has chosen at least one number. Now the devil chooses two numbers, in say $P_i'$ and $P_j'$, whatever the numbers delete the sets that contain those numbers from $P_i'$ and $P_j'$. Now pick two numbers from two different sets remaining in $P'_i$ and $P'_j$; for your third choice pick a number from a set, different than the first two number's sets, from either $P'_i$ or $P'_j$ whichever of the two has least number of sets that you have chosen numbers from. For some fixed $i$, $P'_i$ will eventually have about 80% of it's sets deleted (because the devil will have chosen from those sets), however, $P'_i$ will now consist of about 200 sets that each contain a number that Player 2 has picked. We continue in this fashion till $P'_i$ contains about $$1000\cdot (.2)^3 \approx 8$$ sets that Player 2 will have chosen all the numbers in and thus Player 1 and Player 2 will be sharing a number in one of the sets in $P'_i$.
Eventually Player 3 will be presented, $R=\{R_1,\ldots,R_{10^{2101}/3000}\}$, with $$R_1=\{1,\ldots,3000\} \\ R_2=\{3001,\ldots,6000\} \\ \vdots $$ a collection of about $10^{2101}/3000$ sets and the only knowledge that Player 3 has, is that Player 1 and Player 2 share an element in each $R_i$. The devil goes first and picks two numbers; whatever numbers the devil picks, delete those sets from $R$. For example, suppose the devil picks $1$, then delete the entire set $R_1=\{1,\ldots,3000\}$ from $R$. Now from the remaining sets (which the devil hasn't touched yet) choose three numbers, one from each of three sets in $R$. Phase 2: The devil will now pick two more numbers from two more sets, maybe from sets you have chosen from, maybe from sets that you haven't, whatever the case, delete those sets from $R$ and again choose from the remaining sets (which the devil hasn't touched) three more numbers from sets that you haven't already chosen. Since you always get one extra move than the devil, then when all sets in $R$ have been exhausted, you have thrown out at most ruffly 80% of the sets (since the devil chose from them); however the remaining sets will all have one number in them that you have chosen and no numbers that the devil has chosen. We define the remaining sets as $R'$. Again, $R'$ is about 20% the size of $R$. We now repeat the process on $R'$ and arrive at $R''$, a set 20% the size of $R'$ but now every set in $R''$ has two elements that you have chosen and the devil has chosen none of numbers in those sets. With this pattern, a calculation of $$\frac{10^{2101}}{3000}\cdot (.2)^{3000} \approx 4$$ shows that there will be about $4$ sets remaining that Player 3 will have chosen all the numbers in and the devil hasn't chosen any. Thus, all three players will have chosen at least one number in common.
You can see that large numbers are required to ensure that a winning solution is reached. Let us suppose for a moment that a fourth player joined our group of three players, now how to we proceed to ensure that they still win?
The whole process above, ensures that the first three players will be sharing a number in the set $\{1,\ldots,10^{2101}\}$. We will repeat this process with another set $\{10^{2101}+1,\ldots,2\cdot 10^{2101}\}$. Player 3 will have two sets to juggle a $A$ and $B$, which each contain $10^{2101}/3000$ sets. The devil may play entirely in $A$ or play entirely in $B$ or may choose to play in each set. Player 3 simply needs to make sure that $A$ and $B$ lose sets at an equal rate. If Player 3 focuses all their attention on $A$ and the devil keeps playing in $B$, then Player 3 will end up with 0% useful sets in $B$. To keep this from happening Player 3 should play in $A$ if the devil plays in $A$ and should play in $B$ in the devil plays in $B$. If the devil chooses one number in $A$ and one number in $B$, then Player 3 should choose one number in $A$ and one number in $B$ and then use their third choice on the set that has (currently) the least number of 'good sets'.
This will give us two sets, $\{1\dots,10^{2101}\}$ and $\{10^{2101}+1,\ldots,2\cdot 10^{2101}\}$, in which the first three players share a number in those sets. How many sets will we need to accomplish like this till Player 4 has enough sets? Well we want $N$ sets such that: $$N\cdot (.2)^{10^{703}}>1.$$ So, a &%#@ing &*#@ number of sets.
But it is possible and then Player 4 will be presented with $N$ sets that each have $10^{2101}$ numbers such that in each set there is at least one number that the first three players share. And so, Player 4 can continue in the same fashion that Player 3 did.
If anyone knows of an easier way to describe my method, please let the community know.
Solution 2:
Not yet proven, but hopeful: The sinners cannot win the game.
The argument so far.
The statement, "sinner 3 has won the game"
is equivalent to the statement
"Of all the numbers that sinner 3 has chosen, one of them was a number which both sinner 1 and sinner 2 have chosen."
likewise the statement "sinner 3 knows he has won the game" is equivalent to the statement "Sinner 3 knows that of all the numbers he has chosen, one of them was a number that sinner 1 and sinner 2 chose"
If the sinners have an absolutely winning strategy, then sinner 3 knows he has won the game.
For each k, we may partition the set of choices into disjoint sets with k elements each, call such a partition $\{S_{k,i}\}_{i\in [1,N/i]}$.
or rather there exists a proof of the statement
for a given strategy $K=(\sigma_1,\sigma_2,\sigma_3)$, $\exists$ $x$ in $S_{k,i}$ : sinner 1 has chosen $x$, and sinner 2 has chosen $x$
and sinner three possesses all of the number in that $S_{k,i}$
if for a given strategy K, there exists a proof of $\exists x \in S_{k,i}$, call such an $S_{k,i}$ a guaranteed k-overlap.
thm 1: $\forall k$ there are at most $2^{(\lfloor k/2\rfloor +1)}-2$ of the $S_{k,i}$ such that for each of them there is a guaranteed k-overlap.
A sinner holds a majority of the numbers in $S_{k,i}$ if he has chosen $\lfloor{k/2}\rfloor+1$ of them.
A sinner holds a lead in an $S_{k,i}$ if at any point in the game, the sinner has selected more elements from $S_{k,i}$ than the devil.
If a sinner holds a majority, then the sinner holds a lead. Likewise, the set of $S_{k,i}$ for a given strategy in which the sinner can prove he holds a majority is a subset of the $S_{k,i}$ in which he can prove that he has a lead.
Lemma 1: $\forall k$, each of the sinners may prove that they have a lead in no more than $2^{\lfloor k/2\rfloor}-1$ of the $S_{k,i}$.
for a given state in the game, let the sequence $\{D_n\}$ refer to the $S_{k,i}$ in which the devil has chosen n more numbers than the player, and such that the player does not have a lead.
let the set $X$ refer to the $S_{k,i}$ in which the player has a lead.
we separate the devil's strategy into rounds. The devils strategy is simple, in round $m$ the devil will continue to move as long as there are bins which he has taken less than $m$ balls from, and for which the sinner does not have a lead.
1 Let $Q_i = \sum_{n}{\# D_n*(n+1)}$ after round i.
2 for every ball the devil takes from a bin in round $i$, $Q_i$ increases by 1.
3 for every ball that the player takes from sone $D_n$ in round $i$, $Q_i$ decreases by 1.
4 $Q_i$ decreases by the number of balls the devil collected in in round i divided by 2.
5 $Q_0$ is equal to the number of bins = $2^{\lfloor k/2\rfloor}$.
6 if $Q_{\lfloor k/2\rfloor}$ is positive, then the devil has half, or 1 less than a majority in some $S_k,i$ for which the sinner does not have a lead, in the latter case the devil moves here immediately after completing round $\lfloor k2\rfloor$.
7 $Q_i\le Q_{i+1}*2 \Rightarrow Q_0\le Q_{\lfloor k/2\rfloor}*2^{\lfloor k/2\rfloor}\Rightarrow Q_{\lfloor k/2\rfloor} \ge 1$
Define a pair-majority to be an $S_{k,i}$ in which sinners 1 and 2 have between them selected $k+1$ numbers. It follows that if they hold a pair majority, then one of them holds a majority.
Corrolary 1: the sinners can guarantee a pair-majority or a lead in at most $2^{\lfloor k/2\rfloor+1}-2$ of the $S_{k,i}$.
Lemma 2: if sinners 1 and 2 do not have a pair-majority or a lead in an $S_{k,i}$, then it is not a guaranteed k-overlap.
this is at most the simpler 1-1 game with two players.
We invoke some of the special abilities of the devil for a quick proof. The devil is playing the two games simultaneously. he makes his first choice $\alpha$ in his game with sinner 1 arbitrarily, he then plays whatever player 1 played last in his game with player 2 and vice versa until player 2 selects $\alpha$. The devil repeats this process until there are no more numbers, and player 1 and player 2 do not have an overlap.
this proves thm 1
Thm 2: given $3^{k-3}+1$ or 2 if $k<3$ guaranteed k-overlaps, the devil may prevent sinner 3 from selecting all the values in any of them.
I didn't really think of a succinct way to prove this, but it is clear from sinner 3's strategy to achieve this condition. which involves selecting 1 number from each set, then selecting one from the third of these the devil could not select one from, then again from the next third and so on, until only three in one set remain, at which point the sinner selects all three.
since $(3^{k-3}+1\ or\ 2) \ge 2^{\lfloor k/2\rfloor+1}-2$, for all $k\ne 4$, and there are zero guaranteed overlaps for k=4. (similar to proof of lemma 2). There exists no strategy K such that there is a proof of the statement $S_{k,i}$ contains an element sinner 1 and sinner 2 have chosen, and that sinner 3 has chosen all the elements in that $S_{k,i}$. therefore there exists no winning strategy.$\square$
Solution 3:
I don't think there is a winning strategy as the game is described. If the devil chooses x number of cards from y number of sinners then a solution exists when the sinners can choose xy-1 numbers. This is a pigeonhole problem. Finally, if the sinners are allowed xy-1 numbers the winning strategy is to pick the lowest numbers the devil doesn't pick.