Connecting cities

While there are a couple of major cities on the moon, currently the network connectivity between two of them has so far been limited to the use of satellites in moon orbit. There are several different options being considered to provide alternative means of network connectivity between these cities, which are 856 kilometres distant from each other.

• Option 1: Single-mode fibre cabling can run for up to 40 kilometres before repeaters are required
• Option 2: Microwave radio transmission can transmit for 12 kilometres before repeaters are required
• Option 3: Laser links can transmit for 2 kilometres before repeaters are required
• Option 4: Copper cabling can transmit for 1 kilometre before repeaters are required

Each of the options has various benefits and drawbacks. Microwaves and lasers can transmit over valleys, or up and over mountains without having to install cabling in complicated terrain. Fibre optic cabling can be used for long distances, but needs to be buried to keep it safe from damage which increases the expense. Copper cabling is convenient for locations within existing towns and cities.

A friend of yours is on the planning committee for this new network connection and has asked for your advice.

Looking at the various range capacity of each link involved, you soon realise there are a lot of different options available to achieve the 856 kilometres of distance.

How many different options exist?

Example

Consider a smaller example where a 5 kilometre distance needs to be connected, and you have 3 different options available each with a range of 3 kilometres, 2 kilometres, or 1 kilometre.

The number of options available in this smaller scenario would be 13. Each of these options is as follows...

3 + 2
3 + 1 + 1
2 + 3
2 + 2 + 1
2 + 1 + 2
2 + 1 + 1 + 1
1 + 3 + 1
1 + 2 + 2
1 + 2 + 1 + 1
1 + 1 + 3
1 + 1 + 2 + 1
1 + 1 + 1 + 2
1 + 1 + 1 + 1 + 1

Your task

To provide network connectivity across a distance of 856 kilometres, and 4 options that can each cater to distances of 40 kilometres, 12 kilometres, 2 kilometres, or 1 kilometre, how many different options are there to cover this distance?

Hint

Learn about dynamic programming, specifically the climbing stairs problem.