How many possible trade routes contest. 15M gold prize!

[Haron]

Wait a minute!

For a 4 port trading route, you can also have the route A-B-A-C, where the port A appears twice! These routes have to be added to the previous result.

Number of such routes, assuming one always starts with the port visited twice (not removing duplicates): 21*20*19 (There are three different ports). However, these routes only have two duplicates: A-B-A-C and A-C-A-B.

So, we have to add 21*20*19/2 = 3990, for a total of 42770 possible trade routes.

[Haron]

I see you consider "reverse" trade routes identical ato it's trade route - A-B-C = C-B-A. This is wrong (it's only correct for 2 port trade routes), but you'd get the result (42770 - 210)/2 + 210 = 21490 (since 210 is the number of trade routes with 2 ports, where the reverse route is already removed).

[Not me]

you need to divide by 24 because there is 24 combinations of each set of numbers. example (1 2 3 4) 1; 1234 2; 1243 3; 1324 4; 1342 5; 1423 6; 1432 7; 2134 8; 2143 9; 2314 10; 2341 11; 2413 12; 2431 13; 3124 14; 3142 15; 3214 16; 3241 17; 3412 18; 3421 19; 4123 20; 4132 21; 4213 22; 4231 23; 4312 24; 4321

It's the same with 3. example (1 2 3) 1; 123 2; 132 3; 213 4; 231 5; 312 6; 321

[Most Lee Harmless]

'This is a somewhat complicated problem because some trade routes are duplicates of other trade routes (such as 1-2-3-4 and 2-3-4-1) (also 1-2 and 1-2-1-2 and 2-1-2 and 1-2-1).'

If 1-2-1 and 2-1-2 are disqualified due to the presence of '1-2' , it stands that 1-2-1-3 must also be disqualified as '1-2' and '1-3' pre-exist.

Using the conditions stated by Captain Dungeness, there can only be 200 unique routes composed of unique pairs between 21 destinations : there can not be any 3 or 4 destination routes as any would contain pairs from the original 200 routes thus disqualifying them as 'unique'.

[Haron]

NotMe, that is wrong. Trade routes 1-2-3-4 and 1-3-2-4 are NOT the same trade routes. Assume ports 1 and 3 trade cotton, while 2 and 4 trades tobacco, and you'll find that these trade routes are VERY different. 1-2-3-4 and 2-3-4-1 ARE the same trade routes, though.

That's why I also stated that treating a "reverse" trade route as a duplicate is wrong. 1-2-3 and 3-2-1 are NOT the same. You can get VERY different outcomes from these two trading routes. If they produce three different goods A, B and C, and port 1 has a HIGH price for C, and LOW price for B, port 2 has a HIGH price for A and a LOW price for C, and port 3 has a HIGH price for B and a LOW price for A, then clearly going A-B-C is much more profitable than going C-B-A.

[Admiral Nelson]

Is this going to be like " Guess the Captain day?" where one of his own guild-mates won?

[Haron]

Danik, that is also wrong. 1-2-1 is identical to 1-1-2, which is actually identical to 1-2. thus, 1-2-1 is not a 3 port trading route at all, but a 2 port trading route. 1-2-1-3, however, is a "true" 4 port trading route. It will give a different result than a 1-2 trading route, and also a different result than any other trading route (except 2-1-3-1 and 3-1-2-1, which are its duplicates).

[Brazzler]

Well, it's all here https://www.mathsisfun.com/combinatorics/combinations-permutations.html


There are 21 ports to choose from, and we choose 4 of them (with repeat)
so the number must be 21!/[4!*(21-4)!]=5985

I considored the same thing since I did it last year. But there is more to it than just that. It only accounts for each port is only visited once. Not if one is visited twice.

[Most Lee Harmless]

Danik, that is also wrong. 1-2-1 is identical to 1-1-2, which is actually identical to 1-2. thus, 1-2-1 is not a 3 port trading route at all, but a 2 port trading route. 1-2-1-3, however, is a "true" 4 port trading route. It will give a different result than a 1-2 trading route, and also a different result than any other trading route (except 2-1-3-1 and 3-1-2-1, which are its duplicates).

Its a logic trap : read the conditions given by Captain Dungeness : if 1-2-1-2 is disqualified due to 1-2 being 'unique', then 1-3 is also unique and disqualifies any combination of ports containing 1-3 or its reverse : between them, they will disqualify any combination of ports containing 1, 2, or 3 : This will then apply to all combinations of 3 or 4 ports once you have established the first set of unique pairs between 21 ports : 1 > 2 up to 21 ; 2 > 3 up to 21 ; and so on.

The essential condition seems to be that you may not travel the same route between 2 ports twice, nor in reverse : ergo, once you have used that route, you cannot use it again in any other combination.

[Haron]

1-2-1-2 is disqualified because it's IDENTICAL to 1-2. Setting up these trade routes will make your ship do the same thing. The same is NOT true for 1-2-1-3, Danik. That's a separate trade route which you can NOT achieve with a 2 port trade route - or a 3 port trade route, for that matter.