Simple puzzle General forum
36 replies. Last post: 2016-04-22
Reply to this topic Return to forum-
Marius Halsor at 2016-04-19
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.
-
ypercube at 2016-04-19
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).
-
ypercube at 2016-04-19
Oh, it's 2, 3, or 4 ports, not any number of ports. Disregard my previous comment.
-
Marius Halsor at 2016-04-19
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 :-)
-
Carroll at 2016-04-19
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.
-
Carroll at 2016-04-19
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
-
Marius Halsor at 2016-04-19
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 ;-)
-
Carroll at 2016-04-19
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
-
Marius Halsor at 2016-04-19
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.
-
Carroll at 2016-04-19
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
-
Marius Halsor at 2016-04-19
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.
-
Carroll at 2016-04-19
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.
-
Carroll at 2016-04-19
For an ABCD route, I removed all cycles BCDA, CDAB and DABC cycles, and all 2-routes ABAB.
-
urmaul at 2016-04-19
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.
-
urmaul at 2016-04-19
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.
-
ypercube at 2016-04-19
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)
-
ypercube at 2016-04-19
Note: I counted an ABAB route as different from an AB route? Is this ok or they should be considered the same?
-
wccanard at 2016-04-19
@Carroll: I think that for the number theory question you can just use Vieta jumping.
-
Marius Halsor at 2016-04-19
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.
-
wccanard at 2016-04-19
Marius: there's a Wikipedia page on it (I'm not sure if I can post the link but I'll try: Vieta jumping )
-
urmaul at 2016-04-19
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.
-
Carroll at 2016-04-19
@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 ?
-
Carroll at 2016-04-19
Also you need to remark that (1,1,1) is a solution.
By the same mechanism, you can generate all Markov numbers x2+y2+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) .
-
Carroll at 2016-04-19
@marius, I reread your comment and I agree, I effectively took any ABAB route to be the same as the 2-port AB route.
-
Carroll at 2016-04-20
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
-
Marius Halsor at 2016-04-20
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…
-
Marius Halsor at 2016-04-22
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.
-
Carroll at 2016-04-22
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…