Part 1 of the problem is figuring out how to find the shortest route. I drew a little diagram for the problem in the question, essentially I unfolded the box, and I can see that the shortest distance = sqrt(6^2 + (5+3)^2) = sqrt(100) = sqrt(10)
We can generalise this:
We are looking for integer solutions of this equation which brings us to part 2
What I noticed is that we need triangles with integer sides where A^2 + (B+C)^2 = d^2, and we can generate these pythagorean triples using the method from Problem 9, Please read that problem to understand better.
Essentially we generate triangles where d = m^2 + n^2, and A or (B+C) = m^2 - n^2 or 2mn, now for the final part of the problem, we need to figure out all the possible combinations of the triangles.
Case 1: A = m^2 - n^2, B + C = 2mn
Case 2: A = 2mn, B + C = m^2 - n^2
Now we note the following:
If 2A < B + C => B or C or both are greater than A this is impossible, so there are 0 combinations of this type
If A >= B + C => A >= B, C, we must ensure that B >= C
We can do a few example such as B+C = 5 => (B,C) = (4,1) or (3,2)
B+C = 6 => (B,C) = (5,1) or (4,2) or (3,3)
There will be floor((B+C)/2) combinations
If B+C >= A
You can do a few more examples B+C = 15, A = 8 => (A,B,C) = (8,8,7)
B+C = 12, A = 9 => (A,B,C) = (9,9,3) or (9,8,4) or (9,7,5) or (9,6,6) 4 possibilities
What I notice is that if B+C is divisible by 2, we can include the solution where B = C as a solution
Therefore if B + C is divisble by 2 then there are A - floor((B+C)/2) + 1 combinations
Otherwise there are A - floor((B+C)/2) combinations
I just wrote a quick functions combinations which does part 3, used my Primitive Pythagorean Triple generator for Part 2, and the problem is easily solved!
Input an integer (yourinput)
Code will output the least value M such that the number of solutions > yourinput