www.tombraiderforums.com Lost Library: Snake problem vs. Linear algebra
 Register FAQ Calendar Mark Forums Read

 05-02-18, 22:30 #1 xtimz Historian     Join Date: Apr 2010 Location: Beijing, China Posts: 341 Lost Library: Snake problem vs. Linear algebra I've always wanted to write this. In Lost Library, the snake problem: Well, the solution is to solve linear equations in GF(2). GF(2) denotes "finite field", or "galois field" with 2 elements. It's simple. It's just 2 operations defined on 2-element set {0,1}. (1) Addition: 0+0 = 1+1 = 0, 0+1 = 1+0 = 1. (2) Multiplication: 0*0 = 0*1 = 1*0 = 0, 1*1 = 1. The difference between these and traditional operations is only 1+1=0. This is because pulling the same lever twice equals to zero. The following needs the definition of matrix multiplication, so I put them all in one image. Remember: they're matrices in GF(2), so the addition between elements should obey 1+1=0. That's it. Last edited by xtimz; 05-02-18 at 22:58.
05-02-18, 22:38   #2
xtimz
Historian

Join Date: Apr 2010
Location: Beijing, China
Posts: 341

In case the image is lost (as before), you can run the following Latex code to see the 2nd image.

Quote:
 \documentclass{article} \begin{document} \setlength{\parindent}{0em} Number the $7$ snakes clockwise. (Starting from anyone is OK). Let matrix $A$ \begin{displaymath} A = \left[ \begin{array}{ccccccc} 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 \end{array} \right] \end{displaymath} where the $i$th column of $A$ denotes which flame will change after the $i$th lever is pulled. For example, the $1$st, $4$th, $5$th elements are $1$ in column $1$, which means the $1$st, $4$th, $5$th flames will change after the $1$st lever is pulled. Let vectors $x$, $b$ denotes \begin{displaymath} x_i = \left\{ \begin{array}{ll} 1, & \mbox{$i$th lever pulled.} \\ 0, & \mbox{$i$th lever not pulled.} \end{array} \right. \end{displaymath} \begin{displaymath} b_i = \left\{ \begin{array}{ll} 1, & \mbox{$i$th flame lighted.} \\ 0, & \mbox{$i$th flame not lighted.} \end{array} \right. \end{displaymath} then we have the property $Ax=b$. For example, if the $1$st, $2$nd lever is pulled, let $x=(1,1,0,0,0,0,0)^T$, from the calculations $b=Ax=(1,1,0,1,0,1,0)^T$, so the $1$st, $2$nd, $4$th, $6$th flames will be lighted. In this way, we know which flame is lighted given which lever is pulled. The objective is to find which lever is pulled given which flame is lighted. By linear algebra, all we need is to find the inverse matrix of $A$, which is \begin{displaymath} A^{-1} = \left[ \begin{array}{ccccccc} 1 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 1 \end{array} \right] \end{displaymath} then we have $x=A^{-1}b$. For example, if all flames except the $1$st is lighted, let $b=(0,1,1,1,1,1,1)^T$, from the calculations $x=A^{-1}b=(0,1,0,0,0,0,1)^T$, so the $2$nd, $7$th lever should be pulled. \end{document}

 06-02-18, 00:16 #3 The Great Chi The Inscrutable One     Join Date: Apr 2006 Location: Beyond the Floating Islands Posts: 8,876 Well done There has been quite a number of very clever mathematical members on here over the years, who have analysed Tomb Raider puzzles using programs and complex maths. But for most of us, me included, we are totally lost on the mathematics of it all. I have trouble just filling in my tax return form each year __________________ Humble words by The Great Chi
 07-02-18, 04:38 #4 xtimz Historian     Join Date: Apr 2010 Location: Beijing, China Posts: 341 ^ I got an easy explanation by discussions with other people. To write easier, I'll use A' to denote the inverse of A, which was A^{-1} in the picture. From the meaning of the matrix and the inverse matrix, (1) the ith column of A is: which flame is lighted when only the ith lever is pulled. (2) the ith column of A' is: which lever is pulled when only the ith flame is lighted. So, if we want a given set of flames to be lighted, we just need to sum the corresponding columns in A'. For example, if we want flames {1,2} to be lighted, we sum the 1st, 2nd columns of A', which is (1,1,1,0,0,0,1), so the 1st, 2nd, 3rd, 7th lever should be pulled. Last edited by xtimz; 07-02-18 at 04:41.
 12-02-18, 16:50 #5 Dug Student   Join Date: Apr 2005 Location: London, England Posts: 205 I always felt like I've been cheated out of that puzzle... Every time I get across a puzzle like this in a game, I pull ever lever once to get an understanding and feel for the puzzle, and then proceed to think through it. With this puzzle, pulling every lever once solves it (if I remember correctly), so I've never actually given it any thought. Which makes me feel like a simpleton now, considering the amount of thought and clever maths you've put into it!

 Bookmarks