The board game Ticket to Ride is a train-themed exercise in graph theory. The game has cities (nodes/vertices) which are connected by routes (links/edges).
Each route has two characteristics:
- Length, in the form of the number of segments ("trains") required
- Color (or lack thereof) required
Here is an image of the board, for reference. Routes not requiring a specific color are are gray/silver.
You score points and achieve goals by playing cards to "claim" routes. Example: to claim a six-segment, blue route, you need to play six blue cards.
To claim an uncolored route, you can play any color of cards, but they have to be the same color. So to claim a three-segment, uncolored route, you can play three red cards, three blue cards, or whatever.
Clearly, a colored route is harder to claim than an uncolored route, since you have to have enough cards of a specific color.
For example (refer to the board above):
- Helena to Winnipeg requires four cards of the blue color
- Helena to Calgary merely requires four cards of the same color.
There are eight colors. At any given time, you have an equal chance of having any of them in your hand.
Assuming the same route length, can we calculate the differential difficulty of claiming a route (1) allowing any color, and (2) those requiring a specific color?
For example: say we decide that the difficulty of claiming a four-car route of any color (ex: Helena to Calgary) is 1.0. Is there any way we could determine a numeric difficulty of claiming a four-car route that requires a specific color (ex: Helena to Winnipeg). Is this...1.5? 2.0?
Is there some way to calculate that degree of difficulty?
For small numbers of cards you are eight times as likely to get a set of $n$ cards as a set of $n$ cards of a given color. The chances of getting a set of each color are equal. When the number of cards you have is large enough to have two sets this starts to fail-the chance of an unknown color is less than eight times the chance of a given color. When you have lots of cards you will (almost surely) have a set of all colors, so the chance of any color is very slightly greater than the chance of a given color.
As an example, if you have six cards and ask about sets of three, the chance you have exactly three red cards is ${6 \choose 3}\left(\frac 18\right )^8\left(\frac 78\right )^8\approx 0.0196$. The chance you have any two sets of three is ${8 \choose 2}{6 \choose 3}\cdot \left(\frac 18\right )^8\approx 0.0016$ because you choose the two colors to have, the positions of the first one in the order, then have to draw cards of the correct color. The chance of having at least one set of exactly three is then about $8 \cdot 0.0196-0.0016$ because the $8 \cdot 0.0196$ counts the hands of two sets of three twice so we have to subtract it once.