Simple puzzle

I sometimes play other types of internet games too, and on one of these sites, a puzzle was presented. What struck me as odd, was how everyone on that site struggled so hard to understand how to solve it. I'm guessing it's because the players here at LG are just smarter than elsewhere, and it's you guys I'm used to. So I thought I'd present the puzzle here, and see how many minutes it took you to solve it. So, here goes:

There are 21 ports in an area. Three produces good A, three produces good B, and so on for a total of seven goods. Every port sells what they produce, and will buy any other good (they will not but the good they produce themselves).

A trading route can consist of 2, 3, or 4 ports in a specific order. Sailing in a trading route is a continous business, so for a 3-port trading route, you'd go A-B-C-A-B-C-A-B.... and so on. A VALID trading route makes sure that no two consecutive ports produce the same good, because you then wouldn't be able to sell the good from the previous port.

The question is: How many UNIQUE, VALID trading routes are possible? Note that A-B-C and B-C-A is the same route, just with a different starting point.

Can a route visit the same port twice, eg: A-B-A-C - A-B-A-C - ...?

If yes, the answer is an infinite number of routes (aleph-0 I think).

Oh, it's 2, 3, or 4 ports, not any number of ports. Disregard my previous comment.

The answer to your first question is yes, Ypercube. A - B - A - C is a legal route. And also yes, a route consists of either 2, 3 or 4 ports. More ports would actually make the puzzle more fun, as it becomes incrisingly more difficult. Let's save that for later :-)

I don't see why it is difficult or interesting.

For visiting two ports there are 6+5+4+3+3+1 or 6.7/2=21 routes. For more ports you have to multiply each of these by the corresponding number which is tedious and becomes intractable soon.

Another riddle:

Whatever integer N, prove there exist integers a,b,c,d greater than N such that:

a²+b²+c²+d² = abc+abd+acd+bcd

Carrol, you are wrong even for two ports. Remember, there are 21 ports total - not 7. So a trading route can start in any of the 21 ports. And a port can trade with any other port producing a different good.

Oh, and I never SAID that it was difficult. However, you should get it right before dismissing it ;-)

Ok, you were the one to define routes by the list of letters of the goods, instead of P1A-P4B-P7C...

So for two goods you should multiply by 3x3 then I claim 189

I see I used letters both for posts and goods. Poor choise, I agree. And yes, 189 is obviously correct for 2 ports. 3 ports is also rather trivial - it only gets interesting when you get to 4 ports. And remember: No duplicate routes. For instance, the route A-B is identical to the route A-B-A-B.

For three ports, is it 1890?

3-port routes:  21 x 18 x 15 / 2

So either 2 or 3 ports you should add both: 2079 ?

For each starting port from P1 to P21 here is the number of routes I get:

270
270
270
180
180
180
108
108
108
54
54
54
18
18
18
0
0
0
0
0

For 3 ports it's 1890, correct. Yper, it's 21 x 18 x 15 / 3. You must divide by 3, not 2, since A-B-C, B-C-A and C-A-B are the same route, just starting at a different port.

So either 2 or 3 ports: 189 + 1890 = 2079, correct, Carrol.

For 4 ports, not counting 2-ports routes: 25515, for each starting port sum of:

4725
4455
4185
2610
2430
2250
1242
1134
1026
459
405
351
99
81
63
0
0
0
0
0

So for 2,3 or 4 ports: 27594 different routes.

25515 = 5 * 7 * 9³

I get a slightly higher number.

For an ABCD route, I removed all cycles BCDA, CDAB and DABC cycles, and all 2-routes ABAB.

For loops with a period of 4, I get ((7*6*5*4)/4)*3⁴ loops with 4 goods, ((7*6*5)/2)*3⁴ loops with 3 goods, and ((7*6)/2)*(3⁴-3²) loops with 2 goods, for a total of 27027 loops.

You didn't say anything against loops with a higher "period" than 4, did you? What about A-B-C-B-D-A-B-C-B-D-A etc., where A, B, C, D are different ports? I guess that doesn't count.

I get 23625 for port-4 routes

I get 23625 for 4-port routes, i.e:

(7 x 6 x 5 x 4) x 3^4 / 4  (for 4 goods, agree with urmaul)

7 x (6 x 5 / 2) x (3 x 4 x 3 x 3)   (for 3 goods, disagree) and

(7 x 6 / 2) x [ (3x2)x(3x2)/2 + 2x3x(3x2/2) + 3x3 ]   (for 2 goods, disagree as well)

Note: I counted an ABAB route as different from an AB route? Is this ok or they should be considered the same?

If they count as the same, my total number agrees with the Carroll's 25515.

@Carroll: I think that for the number theory question you can just use Vieta jumping.

ABAB is NOT different from AB. These trading routes cause the exact same behaviour. Also, no more than 4 ports in a trade route, urmual, which means the "period" is 2, 3 or 4.

Carrol: I'm not exactly sure where go go wrong, since I don't really know what you're doing, but if the numbers listed are possible routes starting at a specific port, I notice one error: You have five zeros at the end. I'm pretty sure it should only be 3. Let's look at goods A and B, produced in ports A1, A2, A3 and B1, B2, B3, and assume these are the six last ports. Then, A3-B1-A3-B2 is a valid trading route involving only A3 and "B" ports, so it's not a duplicate of any routes starting with another port.

urmaul and yper: I chose the same approach as you guys. We get the same result for 4 goods, but not for 3 and 2. I think it'll be easier if you stop separating the 7 and the 3, and start with 21 possibile first ports, 18 possible second ports - and then the "trouble" starts.

Carrol: I have no idea what wccanard means by "Vieta jumping", but I'm assuming it's related to your puzzle. I've had a look at it, but have no solution yet. I see a path that MAY lead to success, but it's very messy, and I'm not SURE it will lead to success. I'll try again tomorrow. It was a cool puzzle.

Marius: there's a Wikipedia page on it (I'm not sure if I can post the link but I'll try: Vieta jumping )

ypercube, can you explain how you get to 7 x (6 × 5 / 2) x (3 × 4 × 3 × 3) for 3 goods (period 4)? My calculation was: "The number of combinations of goods is (7*6*5)/2, because you have 7 choices for A, 6 for B and 5 for C in ABAC, and this counts every combination twice, e.g. 1213=1312. For every good there are three possible ports, that makes (7*6*5)/2*3^4.

Surely, if letters stand for ports, then ABAB=AB. I tried to account for that with "3⁴-3²". But if letters stand for goods, then ABAB is larger than AB, right? That's how I used letters.

I mean: ABAB contains A1-B1-A2-B2, but AB doesn't.

@wccanard, you are disqualified on math questions ;) yes it is difficult to answer this problem without Vieta jumping on the sum of roots of a quadratic. Each solution yields a greater one in a,b,c or d. Usually it is used the other way round for an infinite descend hence proving an impossibility or a lower bound.

@marius, why do you think only for routes starting from ports 19,20 or 21 it should be 0 ?

Also you need to remark that (1,1,1) is a solution.

By the same mechanism, you can generate all Markov numbers x^2+y^2+z^2=3xyz (here the sum of roots for x is 3yz, so from (x,y,z) triple you can get to (y,z,3yz-x) triple) .

@marius, I reread your comment and I agree, I effectively took any ABAB route to be the same as the 2-port AB route.

My new number 26271:

4851
4527
4203
2715
2490
2265
1326
1182
1038
522
441
360
141
105
69
21
12
3
0
0
0

Carroll: 26271 is the number I get too (for 4-port routes). Adding 2- and 3- port routes for the total routes, of course.

Now, I'll have to try solving YOUR puzzle...

I think I'm close, Carrol. Maybe I've actually got it.

First, I note that [1,1,1,1] is a solution. Solving the equation for a gives me 1=(bc + bd + cd +- sqrt(E)) / 2, where e is some expression of b, c and d. Now, bc + bd + cd is obviously an integer, if b, c and d is an integer. Let's therefore call the solution a = (F +- G)/2, where F is known to be an integer.

Solving for a with b=c=d=1, gives me a= (3 +- 1)/2. The lowest solution I already knew, a=1. The other solution gives a=2. That means that [1, 1, 1, 2] is also a solution. Because of symmetry, this means that a solution for a when b=1, c=1 and d=2, is a=1. Since a=(F +-G)/2, this means that (F-G)/2 is 1, meaning that (F+G)/2 has to be an integer larger than 1. Continuing this procedure, I will keep getting new integer solutions with increaqsingly higher values for a, with no upper boundary.

Yes you are not far:

calling old solution a and the new one you are looking for a', as you remarked, a is the smallest one, a=(F-G)/2 and a'=(F+G)/2, so a+a'=F=bc+cd+db.

So a'=F-a is an integer. And you can repeat on b,c,d to make each grow.

Or you can use Vieta jumping on the sum of the roots of a quadratic, for a: a² - (bc+cd+db)a + (-bcd+b²+c²+d²)=0 is your F, factor of a.

Or using aa'=(-bcd+b²+c²+d²) hence a'=(-bcd+b²+c²+d²)/a, but then you would have to prove it is an integer...