The route puzzle

Posted on June 17, 2016 by Brent

While poking around some old files I came across this puzzle:

(Click for a larger version.) I didn’t make it, and I have no idea where I got it from (do you know?). But in any case, wherever it comes from, I think it’s a really great puzzle. I did find the number that can make it through the diagram, but I never did completely finish proving that the solution is unique.

Can you solve it? Let’s see if we can prove it together. Please don’t post the number in the comments. But please do post proofs that certain combinations of nodes are impossible. For example, you might post a proof that no triangular number can be one more than a prime; that would mean the leftmost path is impossible.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

This entry was posted in arithmetic, challenges, number theory, proof, puzzles and tagged cube, perfect, prime, puzzle, route, square, triangular. Bookmark the permalink.

7 Responses to The route puzzle

Daniel He hetianding says:

June 17, 2016 at 10:05 pm

I shall make a computer program that does this for me. Sometimes, computer programmers do not use brains, and instead uses brute force.
- John Armstrong says:
  
  June 21, 2016 at 5:44 pm
  
  Let us know when your program finishes testing all nonnegative integers. We’ll wait.
Oscar Cunningham says:

June 18, 2016 at 9:21 am

(Hmmm.. I don’t think this is the intended solution, but $1$ goes down the right hand side of the diagram. Maybe they’re using a different definition of “number”, “coprime” or “another” to me.)

I can prove that there’s no other solution going down the right hand side. Let $p^n$ be a prime power with $n\geq 1$ . Then a number less than $p^n$ is coprime to $p^n$ iff it doesn’t divide by $p$ . Every $p$ th number divides by $p$ , so there are $p^n\left(1-\frac 1p\right)=p^{n-1}(p-1)$ such numbers. This is clearly not a prime power unless $p=2$ or $n=1$ . In neither of these cases can $p^n$ be an odd square.
- Brent says:
  
  June 18, 2016 at 1:37 pm
  
  Hmm, good point, it’s a bit ambiguous. I think the intention is that there are zero numbers less than 1 which are coprime to 1, and 0 is not a prime power. I guess we should take “positive integer” as the definition of “number” for the purposes of this puzzle.
Daniel He hetianding says:

June 18, 2016 at 12:14 pm

So far I got: No number can be 4 more than a square and also a odd square number. This is because there has to be two squares that differ by 4 which is impossible. The smallest square numbers are 0, 1, 4, 9, 16 and none of them differ by 4.
Oscar Cunningham says:

June 18, 2016 at 2:29 pm

I can prove that we can’t go down the left hand side after. The triangle number $(n^2+n)/2$ divides by $5$ when $n$ is of the form $5m$ or $5m-1$ . Hence if our triangle number is one more than a prime then the prime is of the form $\left((5m)^2+(5m)\right)/2 - 1$ or $\left((5m-1)^2+(5m-1)\right)/2 -1$ . These factor as $(5m+2)(5m-1)/2$ and $(5m-2)(5m+1)/2$ . These numbers have two factors each greater than $2$ , so even when we divide by the $2$ they wont be prime.
Lucas A Brown says:

July 1, 2016 at 12:04 am

I have nearly solved the whole thing. All I have left to do is prove that (2,2) and (5,11) are the only positive solutions of the Mordell equation n^3=4+k^2 and prove that there are no odd cubic perfect numbers that are multiples of 5. My work can be found at https://drive.google.com/file/d/0B31DVyBvktcrc1dmNHZpTlZCLTA