Tricky Triangularization

Computer Science Level 4

A root path is a path in a triangular lattice which contains exactly one vertex in each row.

What is the maximum sum of the numbers on the vertices of a root path in this lattice of 500 rows?

Details and Assumptions

  • For eg, in the following lattice, the vertex \(\color{blue}{5}\) can only be connected to the \(\color{red}{\text{red}}\) vertices in a root path.
    \[1\\\color{red}{2}\quad\color{red}{3}\\4\quad\color{blue} {5}\quad6\\7\quad\color{red}{8}\quad\color{red}{9}\quad 1\]
  • All neighbouring vertices must be connected with an edge.
  • Explicit example of maximum sum root path, highlighted in red:

    \[\color{red}{3}\\ \color{red}{7}\quad 4\\ 2\quad \color{red}{4}\quad 6\\ 8\quad 5\quad \color{red}{9}\quad 3\]

  • Bruteforce is not the best idea because \(2^{499}\) paths exist. An efficient solution can find the answer well under a second.

Note: This problem is inspired by a Project Euler problem

Problem Loading...

Note Loading...

Set Loading...