How many ways are there to win Settlers of Catan?

Question

The object of the board game "The Settlers of Catan" is to obtain 10 "victory points". There are five ways to obtain victory points:

1. Settlements, worth 1 victory point. Each player starts the game with 2 settlements and can build up to 3 more, for a total of 5.
2. Cities, worth 2 victory points. Cities are built on top of settlements, replacing them in doing so. Players can build up to 4 cities.
3. Victory Point development cards, worth 1 victory point. Players can buy up to 5 such cards from the deck.
4. The Longest Road card, either held or not held, worth 2 victory points.
5. The Largest Army card, either held or not held, worth 2 victory points.

I remember that we can decompose this into the number of integer solutions to the equation:

$$ s + 2c + v + 2r + 2a = 10 $$ where $$ 0\leq s \leq 5; 0 \leq c \leq 4; 0 \leq v \leq 5; 0 \leq r \leq 1; 0 \leq a \leq 1 $$

and

$$ s + c \geq 2 $$

to account for the 2 starting settlements that can be upgraded into cities.

Also, it is possible to have 9 victory points and then take Longest Road or Largest Army, bringing your total to 11. I think the number of additional solutions here is

$$ \text{Solutions}(s + 2c + v = 9) + 2\times\text{Solutions}(s + 2c + v = 7) $$

multiplying by 2 to account for interchangeability of Longest Road and Largest Army, with bounds as above.

However, I don't remember how to find the number of solutions to these equations.

---

At commenters' request, here are some example solutions:

• 2 settlements, 2 cities, Longest Road, and Largest Army; $2 + 2(2) + 2 + 2 = 10$
• 4 settlements, 1 city, 4 Victory Point cards: 4 + 2(1) + 4 = 10
• Player has 4 cities and 1 Victory Point card and takes Longest Road, 2(4) + 1 + 2 = 11
• Player has 3 settlements, 1 city, 2 Victory Point cards, and Longest Road and takes Largest Army, 3 + 2(1) + 2 + 2 + 2 = 11

Answer 1

Rewriting slightly, you have $$s + v + 2(c + r + a) = 10$$ subject to $$0\leq s \leq 5 \\ 0 \leq v \leq 5 \\ 0 \leq c \leq 4 \\ 0 \leq r \leq 1 \\ 0 \leq a \leq 1 \\ s + c \ge 2$$ So clearly $s$ and $v$ must have the same parity. I think the easiest way to count solutions is to case split on $c+r+a$ ignoring the final constraint:

$$\begin{array}{c|c|c} c+r+a & \textrm{Number of solutions} & s+v & \textrm{Number of solutions} & \textrm{Total} \\ \hline 0 & 1 & 10 & 1 & 1 \\ \hline 1 & 3 & 8 & 3 & 9 \\ \hline 2 & 4 & 6 & 5 & 20 \\ \hline 3 & 4 & 4 & 5 & 20 \\ \hline 4 & 4 & 2 & 3 & 12 \\ \hline 5 & 3 & 0 & 1 & 3 \\ \hline & & & \textrm{Grand total} & 65 & \end{array}$$

and then subtract the cases $s+c < 2$. If $s=c=0$ then the others can only total 9, so there are two cases:

1. $s=0, c=1$: $s+v \le 5$ and $c+r+a \le 3$ so the only case is $s=0, v=4, c=1, r=1, a=1$;
2. $s=1, c=0$: $s+v \le 6$ and $c+r+a \le 2$ so the only case is $s=1, v=5, c=0, r=1, a=1$.

Therefore we have 63 solutions.

---

I disagree with you on the second case. I think that the correct way to state it is

$$s + v + 2(c + r + a) = 11$$ subject to $$0\leq s \leq 5 \\ 0 \leq v \leq 5 \\ 0 \leq c \leq 4 \\ 0 \leq r \leq 1 \\ 0 \leq a \leq 1 \\ r + a \ge 1$$

Then the same case split gives

$$\begin{array}{c|c|c} c+r+a & \textrm{Number of solutions} & s+v & \textrm{Number of solutions} & \textrm{Total} \\ \hline 1 & 2 & 9 & 2 & 4 \\ \hline 2 & 3 & 7 & 4 & 12 \\ \hline 3 & 3 & 5 & 6 & 18 \\ \hline 4 & 3 & 3 & 4 & 12 \\ \hline 5 & 3 & 1 & 2 & 6 \\ \hline & & & \textrm{Grand total} & 52 & \end{array}$$

Here we only have one overcount case:

• If $s=0, c=1$ then we get $s=0, v=5, c=1, r=1, a=1$.
• If $s=1, c=0$ then we can't get a total of 11.

So we get 51 solutions, which added to the previous 63 makes 114.