Minimum amount of required chits to award player points

Question

There is a board game for up to four players that has 7 rounds and at the end of each round the game awards the first player 3 points, the second 2, the third 1 and the fourth 0 points.

The points are awarded to each player through chits. There are 7 3-point chits, 7 2-point chits and 7 1-point chits for a total of 21 chits.

What would be the minimum amount of chits required, if the chits could represent any integer value and the players could exchange chits back and forth? For example, if a player had 3 points and got awarded 3 more, they could exchange their 3-point chits with:

a. a 6-point chit or b. a 5-point chit and a 1-point chit or c. a 4-point chit and a 2-point chit or d. any other combination of chits

I understand that this will obviously NOT be the most convenient way to award points to the users, since the players will have to keep hunting for the appropriate chit combination to keep their score, but the question came up during game design and thought of asking here...

Thanks!

Answer 1

A first step is to enumerate the multisets of possible scores. For example, at the end of round 1, the scores are $\{3,2,1,0\}$, and at the end of round 2 they can be any of the following $16$ multisets:

3 3 3 3 
4 3 3 2 
4 4 2 2 
4 4 3 1 
4 4 4 0 
5 3 2 2 
5 3 3 1 
5 4 2 1 
5 4 3 0 
5 5 1 1 
5 5 2 0 
6 2 2 2 
6 3 2 1 
6 3 3 0 
6 4 1 1 
6 4 2 0 

It turns out that there are $792$ such multisets across the $7$ rounds.

Now you can use integer linear programming to find a smallest multiset of chits that can cover each multiset. Let nonnegative integer decision variable $x_i$ be the number of chits of amount $i$. Let nonnegative integer decision variable $y_{ijm}$ be the number of chits of amount $i$ used to represent score $j$ in multiset $m$. The problem is to minimize $\sum_{i=1}^{21} x_i$ subject to linear constraints \begin{align} \sum_i i\ y_{ijm} &= j &&\text{for all $m$ and $j\in m$} \tag1\label1 \\ \sum_{j\in m} y_{ijm} &\le x_i &&\text{for all $m$ and $i$} \tag2\label2 \end{align} Constraint \eqref{1} represents each $j$. Constraint \eqref{2} uses only the available chits.

In your example solution, $x_1=x_2=x_3=7$, yielding objective value $21$.

A better solution is $x_1=x_2=2, x_3=12$, with objective value $16$.

An optimal solution turns out to be $x_1=x_2=x_3=x_5=x_7=2, x_6=1$, with objective value $11$.

An alternative optimal solution is $x_1=x_2=x_3=x_6=2, x_4=x_5=x_9=1$, with objective value $11$.

---

Additional results in response to the comments:

Restricting to $i\in\{1,3,5,10\}$ yields optimal solution $x_1=6,x_3=5,x_5=3,x_{10}=1$, with objective value $15$.

Restricting to $i\in\{1,2,5,10\}$ yields optimal solution $x_1=4,x_2=6,x_5=4,x_{10}=1$, with objective value $15$.

---

For $5$ players with scores $\{4,3,2,1,0\}$ and $7$ rounds, there are $7713$ multisets of possible scores to cover, and an optimal solution is $x_1=x_2=x_3=x_4=x_6=x_8=2, x_{10}=x_{12}=1$, with objective value $14$.