Poker Players' Problem

This problem seems like a generalization of the famous 6-person friend/enemy problem. Thus, we will try to find a general formula or something like that to find out the maximum value of $n$ .

To make things simpler, let's call three people who have pairwise played the same number of games a "triangle".

---

Trivial case: $n=1$ .

We need at least $3$ people to have a triangle (duh).

---

First case: $n=2$ .

This case is equivalent to the friend/enemy problem. We know that the minimum number of people we need to have a triangle is $6$ . Let's look at the proof:

Suppose $A$ played $1$ games with $B$ , $C$ , and $D$ . Then $B$ , $C$ , and $D$ cannot play $1$ games with any of the others or else there would be a $1$ -game triangle. However, that would mean that $B$ , $C$ , and $D$ for a $2$ -game triangle. Thus, we know that $A$ cannot play $1$ game against three different people: $A$ must have played $1$ game with at most $2$ people.

But this argument also works for $2$ games: thus, $A$ played $2$ games with at most $2$ people. However, that means $A$ played at most $4$ games total. Thus, if there were $6$ people, then $A$ would have to play $5$ people, thus forcing a triangle.

---

Second case: $n=3$

We can use our previous cases to our advantage. Suppose $A$ played $1$ game with $6$ people. Then out of these $6$ people, nobody can play $1$ game with any other or else it would form a $1$ -game triangle. Thus, they all must have played $2$ or $3$ games with each other. However, our previous case says that there must exist either a $2$ -game triangle or a $3$ -game triangle in these $6$ people. Thus, we know that $A$ played $1$ game with at most $5$ people.

Similarly, $A$ played $2$ and $3$ games with at most $5$ people. Thus, $A$ played at most $15$ games. Thus, if there were $17$ people, then the group is forced to have a triangle.

---

General case:

Let the minimum number of people needed to ensure a triangle with $k$ possible number-of-games-played be $a_k$ . We see that $a_1=3$ , $a_2=6$ , and $a_3=17$ .

Suppose there are $n$ possible number-of-games-played. If $A$ played $1$ game with $a_{n-1}$ people, then we know that a triangle is forced. Thus, we know that $A$ played $1$ game with at most $a_{n-1}-1$ people. This is also true for playing $i$ games, where $i=2\to n$ .

Thus, we know that $A$ played with at most $n(a_{n-1}-1)$ people. Thus, if there were $n(a_{n-1}-1)+2$ people, then there will be a forced triangle.

Thus, $a_n=n(a_{n-1}-1)+2$ . This works out: $a_2=2(a_1-1)+2=6$ $a_3=3(a_2-1)+2=17$

We can continue on: $a_4=4(a_3-1)+2=66$ $a_5=5(a_4-1)+2=327$ $a_6=6(a_5-1)+2=1958$ $a_7=7(a_6-1)+2=13701$

We see that at $n=7$ , we need at least $13701$ people to guarantee a triangle. In addition, at $n=6$ , we need at least $1958$ people. Thus, the maximum possible value of $n$ is $\boxed{6}$ .