How do I know there are 68 trillion rides?

In 68 trillion ways to ride Nerang I counted the different loops you can ride from the main gate without riding any section of trail twice. The answer was about 68 trillion. My own first reaction was that it can’t possibly be right, and I suspect yours is the same.

So here’s the case for it, step by step: from a park small enough to count on paper, to the part a computer has checked one ride at a time, to a famous puzzle with a known answer that the same method gets right.

1. Count one junction by hand

Imagine the simplest trail park there is: a loop from the car park out to one junction and back, with a few small loops hanging off that junction. The rules are the same as the real count. Start and finish at the car park, never ride a section twice, and the ride ends when you get back.

With one small loop there are 6 rides, few enough to list. You can ride the big loop clockwise or anticlockwise and go straight home (2 rides). Or you can ride it either way and add the small loop, either way, when you pass the junction (2 × 2 = 4 more).

With two small loops there are 26 rides, and with three there are 158. Each extra loop can be left out or slotted in at any point in the order, in either direction. Written out, that’s:

Here’s how quickly that grows, next to the same small loops spread out along the way home, each at its own junction:

When each loop has its own junction, every loop is just “skip it, or ride it one of two ways”, so the count triples with each one. When the loops share a junction, the order you ride them in matters too, and that’s where it explodes. Twelve small loops off one junction already give about 6.5 trillion rides. I checked the formula against a computer listing every ride, up to five loops; they agree exactly.

2. Nerang has 50 loops, woven together

Any network has a number of independent loops: sections minus junctions plus one. For Nerang’s sanctioned trails and roads that’s 119 − 70 + 1 = 50. They don’t all hang off one junction, and one-way trails and dead ends rule some combinations out. But they’re woven together: most junctions are three- or four-way, and long rides pass through ten or more of them twice, so the order of the loops multiplies the count just as in the toy park.

Another way to see it: at each junction, a rider has on average about 1.65 ways to go that still lead home without repeating anything. A typical 30 km ride passes about 60 junctions. That’s 1.65 multiplied by itself 60 times, which is about 10¹³, or tens of trillions.

3. The part that’s proven outright

Up to 8 km nothing is estimated. The computer tries every turn, backs up, tries the next, and lists every ride one at a time. There are exactly 2,462,496. The same kind of exhaustive listing finds exactly 984 rides that use only green trails and roads, at any length.

That’s a proof by exhaustion: nothing is sampled, every possibility is checked. It just doesn’t scale. My laptop lists about 20,000 rides a second, so listing all 68 trillion would take about a century. With heavily optimised code and a lot of computers it could probably be done exactly. Until someone does, the long rides are estimated.

4. Why the estimate isn’t a guess

The estimate sends out virtual riders. At each junction a rider picks one of the ways it can go at random (only ways that can still get home) and keeps a running product of how many choices it had. Call that product the ride’s weight.

Here’s the key fact. The chance of a rider producing any particular ride is one over its weight. A ride with 3 choices, then 2, then 4 has a 1 in 24 chance of being produced, and a weight of 24. So when you average the weight over all the rides a rider might produce:

So the average weight isn’t roughly the number of rides. It’s exactly the number of rides, by construction. The only error is random scatter from not sending out infinitely many riders. (The idea dates back to the 1950s, and Donald Knuth popularised it for counting problems like this one in the 1970s.)

On its own, that scatter is huge, because a few rare riders end up with enormous weights. The refinement I used, sequential Monte Carlo, keeps a crowd of 50,000 riders moving together. After each junction, riders in busy parts of the network are copied and riders boxed into corners drop out, with the weights shared out so the average stays exactly right. It just makes the scatter much smaller.

To measure the scatter, I ran the whole estimate 16 times with different random numbers:

The runs range from 55 trillion to 93 trillion and average 67.8 trillion. Averaged together, the 16 runs pin it down to about ±4%. As a check, the same estimate reproduces the exact counts for 1 to 8 km, which it knows nothing about, to within 7%.

5. A guaranteed minimum

The ± figure assumes the usual bell-curve behaviour. Even without that, there’s a hard floor.

A run’s estimate can never be negative, and on average it’s exactly right. A number like that can be double the true value or more at most half the time. That’s Markov’s inequality, about as basic as probability gets. For all 16 independent runs to come out at double or more, the chance is at most ½ multiplied by itself 16 times: 1 in 65,536.

The smallest of the 16 runs was 54.7 trillion. So the true number is at least half of that, 27 trillion, with 99.998% certainty. And it’s at least 5.5 trillion (a tenth of the smallest run), with a 1 in 10¹⁶ chance of being wrong.

6. Testing the method on a puzzle with a known answer

In 1976 the computer scientist Donald Knuth asked how many paths cross a 10 × 10 grid from one corner to the opposite corner without visiting any point twice. There are far too many to list, so he estimated it with essentially this method, and got (1.6 ± 0.3) × 10²⁴. Later the exact count was computed: 1,568,758,030,464,750,013,214,100. His estimate was right.

I pointed my own code at the same puzzle. Its rule is stricter than the rides (no point visited twice, rather than no section ridden twice), but the estimator is the same. For grids up to 5 × 5 my code also lists every path, which checks the grid code itself. For bigger grids the exact answers come from the published sequence of these counts. The bigger the grid, the more scatter, so from 7 × 7 up I used 200,000 riders and 32 runs.

The estimate lands within 4% of the exact answer every time, including Knuth’s 10 × 10 grid, where the answer has 25 digits.

7. So what could actually be wrong?

The maths isn’t the weak point. What would change the number is what’s being counted:

• The trail data. A junction missing from the map, or a one-way trail that’s really two-way, changes the network. Every extra junction multiplies the count.
• The definition. “No section twice” and “clockwise and anticlockwise count separately” are choices. Counting only different sets of trails, in any order, still leaves about 1.1 trillion.
• Small differences. A ride that swaps one short connector for another counts as different, even if you’d call it the same ride.

The short version

Choices multiply. A dozen loops sharing one junction already makes trillions of rides, and Nerang has 50 loops woven through 70 junctions. The short rides are counted exactly. The long ones are estimated by a method that’s exactly right on average, matches the exact counts where they overlap, is beyond reasonable doubt at least 27 trillion, and gets a 25-digit puzzle right. So yes: about 68 trillion.