2
$\begingroup$

Ok, I've been puzzling over this problem for a while now and I think I'm close, but I'm running into a bit of a dead end.

For those curious, this puzzle comes from the game West of Loathing. It's simple to solve by brute force guess and check, so I have the solution, but I wanted to see if there was a more formal way to approach these types of problems.

The linear equation is $411x+295y+161z=3200$. The trivial solution I found was $x=4, y=2, z=6$.

The question is, can I systematically come up with all natural number solutions to this equation?

My thought was first to look at the extended Euclidean algorithm like I typically would do for two variables. I tweaked it a bit using the identity $gca(a,b,c) = gca(a, gca(b,c))$. Since they are all prime, I ended up with gca = 1 which 3200 is divisible by, so there is a solution.

Following the algorithm, and applying it first to 295 and 116, and then applying that to 161, I ended up with the expression $161+(-160)*(124*295-89*411) = 1$ which is a valid integer solution once you multiply both sides by 3200.

That's where I've been stuck. In previous such problems, to find the natural number solutions, I would parameterize it by some variable $t$, then all solutions can be found using $t$, including ones that meet some additional criteria like $x >0, y >= 0$. I feel something similar should be possible with this form as well so you can find expressions for $x$, $y$, and $z$ such that all solutions are included. However, I can't figure out how to parameterize the solution. Given the generalization before, my hunch would be that you would need two integer parameters, and the solution space would allow any integer values for those two parameters (basically allowing traversal of the plane). I would expect a solution (at least for the integer solutions) in the form of a set of vectors $\{(x,y,z) \in \mathbb{Z}^3 \mid x=f(j,k), y=g(j,k), y=h(j,k) \forall j,k \in \mathbb{Z}\} $.

Any help or suggestions on how to parameterize it to find the general solution would be helpful. Secondly, if finding the natural number solutions isn't as simple (like it is with two variables) as adding a single inequality and solving, then I would appreciate pointers on how to add that constraint as well.

$\endgroup$
  • $\begingroup$ you are right about traversing the plane. The set of integer vectors with $411x+295y +161z = 0$ forms a "lattice". An integer basis made of two vectors can be found by some matrix methods restricted in certain ways, in turn this can be revised to a "reduced" basis. All integer solutions to the original 3200 problem can then be found by adding lattice vectors to one fixed solution. $\endgroup$ – Will Jagy Jan 15 at 3:06
1
$\begingroup$

Here is a reduced lattice basis, as two columns:

$$ \left( \begin{array}{rrr} 411 & 295 & 161 \end{array} \right) \left( \begin{array}{rr} 3 & -28 \\ -8 & 21\\ 7 & 33 \\ \end{array} \right) = \left( \begin{array}{cc} 0& 0 \end{array} \right) $$ The Gram matrix for the basis is $$ \left( \begin{array}{rr} 122 & -21 \\ -21 & 2314\\ \end{array} \right) $$ and is just $B^T B,$ where $B$ is the 3 by 2 matrix with basis vectors as columns.

========================================================================





? row = [ 411, 295, 161]
%4 = [411, 295, 161]
? r1 = [ 1,0,0; 0,1,0; 0,-2,1]
%5 = 
[1  0 0]

[0  1 0]

[0 -2 1]

? row * r1
%6 = [411, -27, 161]
? r2 = [ 1,0,0; 15,1,0; 0,0,1]
%7 = 
[ 1 0 0]

[15 1 0]

[ 0 0 1]

? row * r1 *r2
%8 = [6, -27, 161]
? r3 = [ 1,0,-27; 15,1,0; 0,0,1]
%9 = 
[ 1 0 -27]

[15 1   0]

[ 0 0   1]

? r3 = [ 1,0,-27; 0,1,0; 0,0,1]
%10 = 
[1 0 -27]

[0 1   0]

[0 0   1]

? row * r1 *r2 *r3
%11 = [6, -27, -1]
? r4 = [ 0,0,1; 0,1,0; -1,0,0]
%12 = 
[ 0 0 1]

[ 0 1 0]

[-1 0 0]

? row * r1 *r2 *r3 *r4
%13 = [1, -27, 6]
? r5 = [ 1,27,-6; 0,1,0; 0,0,1]
%14 = 
[1 27 -6]

[0  1  0]

[0  0  1]

? row * r1 *r2 *r3 *r4 *r5
%15 = [1, 0, 0]
? r = r1 *r2 *r3 *r4 *r5
%16 = 
[  27    729  -161]

[ 405  10936 -2415]

[-811 -21899  4836]

? row * r
%17 = [1, 0, 0]
? pick = [ 0,0; 1,0;0,1]
%18 = 
[0 0]

[1 0]

[0 1]

? r * pick
%19 = 
[   729  -161]

[ 10936 -2415]

[-21899  4836]

? basis_col =r * pick
%20 = 
[   729  -161]

[ 10936 -2415]

[-21899  4836]

? basis_row = mattranspose(basis_col)
%21 = 
[ 729 10936 -21899]

[-161 -2415   4836]

? g = basis_row * basis_col
%22 = 
[ 599693738 -132431373]

[-132431373   29245042]

? matdet(g)
%23 = 281867
? q
%24 = q
? q = qflll(basis_col)
%25 = 
[ -53  441]

[-240 1997]

? red = basis_col * q
%26 = 
[ 3 -28]

[-8  21]

[ 7  33]

? red_row = mattranspose(red)
%27 = 
[  3 -8  7]

[-28 21 33]

? h = red_row * red
%28 = 
[122  -21]

[-21 2314]

? matdet(h)
%29 = 281867
? 
? h = red_row * red
%28 = 
[122  -21]

[-21 2314]

? matdet(h)
%29 = 281867
? 
? 
? row
%30 = [411, 295, 161]
? red
%31 = 
[ 3 -28]

[-8  21]

[ 7  33]

? row * red
%32 = [0, 0]
? 
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.