www.tombraiderforums.com

Go Back   www.tombraiderforums.com > Tomb Raider Series > The Last Revelation

Reply
 
Thread Tools
Old 05-02-18, 22:30   #1
xtimz
Historian
 
xtimz's Avatar
 
Join Date: Apr 2010
Location: Beijing, China
Posts: 374
Default 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.
xtimz is offline   Reply With Quote
Old 05-02-18, 22:38   #2
xtimz
Historian
 
xtimz's Avatar
 
Join Date: Apr 2010
Location: Beijing, China
Posts: 374
Default

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}
xtimz is offline   Reply With Quote
Old 06-02-18, 00:16   #3
The Great Chi
The Inscrutable One
 
The Great Chi's Avatar
 
Join Date: Apr 2006
Location: Beyond the Floating Islands
Posts: 9,124
Default

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
The Great Chi is offline   Reply With Quote
Old 07-02-18, 04:38   #4
xtimz
Historian
 
xtimz's Avatar
 
Join Date: Apr 2010
Location: Beijing, China
Posts: 374
Default

^ 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.
xtimz is offline   Reply With Quote
Old 12-02-18, 16:50   #5
Dug
Student
 
Join Date: Apr 2005
Location: London, England
Posts: 208
Default

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!
Dug is offline   Reply With Quote
Reply

Bookmarks

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off



All times are GMT. The time now is 03:32.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2018, vBulletin Solutions Inc.