050218, 22:30  #1 
Historian
Join Date: Apr 2010
Location: Beijing, China
Posts: 374

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 2element 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; 050218 at 22:58. 
050218, 22:38  #2  
Historian
Join Date: Apr 2010
Location: Beijing, China
Posts: 374

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


060218, 00:16  #3 
The Inscrutable One
Join Date: Apr 2006
Location: Beyond the Floating Islands
Posts: 9,124

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 
070218, 04:38  #4 
Historian
Join Date: Apr 2010
Location: Beijing, China
Posts: 374

^ 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; 070218 at 04:41. 
120218, 16:50  #5 
Student
Join Date: Apr 2005
Location: London, England
Posts: 208

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 
Thread Tools  

