This riddle originates in the youtube video here. It's mathematical content was summarised here as follows:
There's a $5\times 5$ grid of nodes, all nodes are (bidirectionally) connected to their vertical and horizontal neighbour(s) (so no diagonals). the nodes have coordinates $(x,y)$, with $x=0\dots 4$, $y=0\dots 4$
you start at node $(2,4)$ and already have a "cost" of $4$.
moving down a node (so $y$ decreased by $1$) doubles that cost,
moving up a node (so $y$ increased by $1$) halves the cost,
moving left (so $x$ decreased by $1$) decreases the cost by two,
moving right (so $x$ increased by $1$) increases the cost by $2$.
an edge can only occur once in your path, you may pass nodes multiple times though.
is there a way to get to the lower right corner, point $(4,0)$, with a cost equal to zero?
The questioner in my second link wanted to know if there was a nice way to represent the problem mathematically. I suggested we could use quivers.
The graph in the problem can be thought of as a quiver where each vertex is connected both ways with each adjacent vertex. Since the cost functions are all affine, they can be represented as a representation of a quiver:
- Each vertex is represented by $\mathbb R^2$.
- The downward edges are represented by the matrix \begin{pmatrix}2&0\\0&1\end{pmatrix}
- the upward edges by the matrix \begin{pmatrix}1/2&0\\0&1\end{pmatrix}
- the leftward edges by the matrix \begin{pmatrix}1&-2\\0&1\end{pmatrix}
- and the rightward edges by the matrix \begin{pmatrix}1&2\\0&1\end{pmatrix}
- Then the matrices represent the changes in cost by acting on \begin{pmatrix}\text{cost}\\1\end{pmatrix}
Now I'm wondering if we can use the representation theory of quivers to solve the puzzle?
I'm not an expert in quivers, but I did notice that the vectors of the form \begin{pmatrix}1\\0\end{pmatrix} span a subrepresentation. Are representations of quivers always completely reducible? If so then finding the complementary representation might help.