Combinatorics and Riven

How many possible solutions are there to Riven’s puzzles?

Puzzle	Number of solutions
Catherine’s Prison	364
Telescope	3 906
Fire Marble Domes	53 130
Moiety Gateway	6 375 600
Fire Marble Puzzle	58 752 420 690 993 751

The table lists the maximum number of guesses you’d need to try if you attempted to solve each puzzle by brute force, assuming you didn’t know that ‘5’ is a special number in the Rivenese world. The rest of this page explains how to derive the numbers.

First, a math review: In how many ways can you select k out of n objects? The answer depends on the following:

• Does the order of selection matter?
• Can you select an object more than once?

You can find the formulas below in any combinatorics textbook:

Name	Type	Number of selections	Example: n = 3, k = 2
Sequence	Ordered, unlimited repetition	nk	9 ways: 11, 12, 13, 21, 22, 23, 31, 32, 33
Permutation	Ordered, no repetition	nPk = n! / (n − k)!	6 ways: 12, 13, 21, 23, 31, 32
Combination	Unordered, no repetition	nCk = nPk / k!	3 ways: 12, 13, 23

Note: The exclamation mark, pronounced ‘factorial’, represents a product of consecutive integers:

n!

=

n × (n − 1) × ... × 3 × 2 × 1

For instance, 1! = 1, and 5! = 5 × 4 × 3 × 2 × 1 = 120. As a special case, 0! = 1.

Interestingly enough, the telescope on Temple Island is both the first puzzle you encounter and the last puzzle you solve. It’s mounted over a locked hatch that, when opened, affords a spectacular view of the Star Fissure below.

The question: To open the hatch, you must push the five buttons on it in the correct order. You may push each button any number of times. How many possible solutions are there?

The math: Since order is important and repetition is allowed, we use the formula for the number of sequences: n^k. In this problem, n = 5 (you can select from five buttons) and k, the number of button pushes, is unknown. (Pretend that you’ve never played Riven.) So the number of possible sequences is n^k = 5^k:

k	5k
0	1
1	5
2	25
3	125
4	625
5	3125
Total	3906

Here’s why k goes from 0 to 5: If you don’t know how many buttons to push, then you’ll try the zero-button sequence first — in other words, see if you can open the hatch without pushing any buttons. Next, you’ll try all 5 one-button sequences, and failing that, all 25 two-button sequences, and so on.

The table stops at k = 5 because the correct sequence is five buttons long, and by the time you finish trying all possible five-button sequences, you’ll have opened the hatch. Thus, the puzzle has 3906 possible solutions. (Of course, if you’ve explored Riven and know that k = 5, then you only need to worry about 3125 possible solutions.)

Bonus question: How many button pushes are needed to try all 3125 five-button sequences? Hint: Because the lock mechanism remembers the last five buttons pushed, the answer is less than 5 × 3125. [Solution]

Not long after Catherine returned to Riven, she was captured by Gehn and imprisoned on Riven’s smallest island, in a cell located atop a massive tree stump.

The question: To release Catherine, you must press three buttons in the correct order. You may press each button any number of times. How many possible solutions are there?

The math: Since order is important and repetition is allowed, we again use the formula for the number of sequences: n^k. In this problem, n = 3 (you can select from three buttons) and k, the number of button pushes, is unknown. So the number of possible sequences is n^k = 3^k:

k	3k
0	1
1	3
2	9
3	27
4	81
5	243
Total	364

The table stops at k = 5 because the correct sequence is five buttons long, and by the time you finish trying all possible five-button sequences, you’ll have released Catherine. Thus, the puzzle has 364 possible solutions.

The Moiety Gateway puzzle protects the linking book to the rebel Age. Hidden within a secret cavern on Jungle Island, the puzzle consists of a circle of 25 stone slabs, each imprinted with the image of an animal.

The question: To access the linking book, you must press five of the 25 slabs in the correct order. You may press each slab only once. How many possible solutions are there?

The math: Since order is important and repetition is not allowed, we use the formula for the number of permutations: _nP_k. In this problem, n = 25 (you can select from 25 slabs), and k = 5 (you need to pick five of the slabs). Plug in those values to get the number of permutations:

nPk	=	25P5
	=	25! / (25 − 5)!
	=	25! / 20!
	=	25 × 24 × 23 × 22 × 21
	=	6375600

Thus, the puzzle has over six million possible solutions.

(You can get the fourth line above by replacing each factorial in the third line with the equivalent product of integers, and canceling common terms from the numerator and denominator of the fraction.)

For easy access to his 233rd Age, Gehn constructed a Fire Marble Dome on every Rivenese island and placed a linking book within each dome. He also installed a coded access system to keep out would-be intruders.

The question: To access the linking book, you must move each of the five sliders on the dome to one of 25 positions. The sliders are indistinguishable, and at most one slider can occupy any position. How many possible solutions are there?

The math: [To be written...]

nCk	=	25C5
	=	25P5 / 5!
	=	6375600 / 120
	=	53130

The Fire Marble Puzzle — found atop the Great Dome on Temple Island — is the central and most complex puzzle in Riven. To solve it, you must gather clues that are scattered all over the Rivenese world.

The question: Place up to six differently colored marbles onto a 25x25 grid of holes. Each hole can contain only one marble, and some of the marbles might not be needed. How many possible solutions are there?

The math: [To be written...]

f(n)	=	625Cn × 6Pn
	=	625Pn × 6Pn / n!

Here are the calculations for f(n) when n = 0, n = 1, and n = 2:

f(0)	=	625P0 × 6P0 / 0!
	=	(625! / 625!) × (6! / 6!) / 0!
	=	1 × 1 / 1
	=	1

f(1)	=	625P1 × 6P1 / 1!
	=	(625! / 624!) × (6! / 5!) / 1!
	=	625 × 6 / 1
	=	3750

f(2)	=	625P2 × 6P2 / 2!
	=	(625! / 623!) × (6! / 4!) / 2!
	=	(625 × 624) × (6 × 5) / 2
	=	5850000

n	f(n)
0	1
1	3 750
2	5 850 000
3	4 859 400 000
4	2 266 910 100 000
5	563 100 468 840 000
6	58 187 048 446 800 000
Total	58 752 420 690 993 751

Bonus question: The telescope puzzle has 3125 possible five-button sequences. How many button pushes are needed to try them all?

Solution: Number the buttons 1–5, and imagine that you push the buttons and try the hatch in the following order:

1 1 1 1 1–2–2–2–2–2–

(That’s five 1’s, five 2’s, and six dashes. Each dash means “try to open the hatch”.)

The lock mechanism remembers the last five buttons pushed, so with just 10 button pushes, you’ve already tried 6 five-button sequences: 11111, 11112, 11122, 11222, 12222, and 22222. It’s not hard to see that, if you continue to alternate between pushing a button and trying the hatch, you can try n five-button sequences with n + 4 button pushes. It’s also easy to see that you need at least n + 4 button pushes to try n different sequences.

So, in order to try the 3125 possible five-button sequences, you need at least 3125 + 4 = 3129 button pushes — maybe more. Is there a sequence of 3129 button pushes that lets you try all five-button sequences?

It isn’t obvious, but there are actually quite a few. (Mathematicians even have a name for them: ‘de Bruijn sequences’.) Thus, only 3129 button pushes are needed to try all 3125 five-button sequences.