Mathematics desk
< March 1	<< Feb \| March \| Apr >>	March 3 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 2

Nim Variation

I've been trying to solve a variation of Nim, and it's pretty hard. Let me know if you have any ideas. You start out with k many piles of counters, each pile being any size greater than zero. In a turn, you may remove as many counters (n) as you want from a single pile, and the same number (n) from each of as many other piles as you feel like as long as there are enough in each one. The goal is to take the last counter. For k=1, it's trivial. For k=2, it's Wythoff's Game. For k>2, I can't make heads or tails of it, and neither can the Math Club I'm in. We've solved some special cases and found one or two things of interest, but not much. The Sprague-Grundy Theorem doesn't work because you can play in more than one subgame at once. Black Carrot 06:21, 2 March 2007 (UTC)[reply]

I don't have it to hand, but Winning Ways for your Mathematical Plays might cover it (if you haven't tried this already, of course). Algebraist 18:36, 2 March 2007 (UTC)[reply]

(after brief thought) I'm not sure what you mean by Sprague–Grundy not applying. The game is clearly impartial (and perfect information and normal and ending) and hence equivalent to nim. Presumably you mean that since it doesn't break down into subgames this fact isn't very helpful? Algebraist 18:38, 2 March 2007 (UTC)[reply]

I don't know what you mean by "equivalent", all I know is that Sprague-Grundy doesn't apply (I tried) and the article says so. The assumption that you may play in only one subgame at a time is central to the theorem as it's explained in that article and every article I can find. Without that, you can't assume that L+L=L and W+L=L (W = definite win L = definite lose) and that W+W is the only question mark. You can't get away with Grundy numbers, because a Losing combination of piles + another Losing combination of piles doesn't always equal a larger Losing combination of piles (0+0/=0). (Ex: (5,3)+(2,1)=L+L=(5,3,2,1)=W) Not all 0s are created equal, see, and Grundy numbers treat them as identical. So, the best guess I have is that I need a more flexible tool. Black Carrot 10:43, 3 March 2007 (UTC)[reply]

I have now shifted my ass as far as a library and discovered that this is not covered in Winning Ways (unless I'm being very dense), though they do cover the nim-variant where one can remove any number from at most k piles at once (i.e. need not be the same from each pile). I simply meant that any collection of piles for this game is equivalent to some nimber (as Sprague-Grundy states), but since the union of two combination of piles is not the game-theoretic sum of those combinations, this fact is essentially useless. I (being lazy) haven't tried attacking your game yet, but Wythoff's game isn't exactly easy so I'm guessing this one is going to be pretty hard. Sorry to be useless Algebraist 21:26, 3 March 2007 (UTC)[reply]

That's okay. I deeply appreciate the sacrifices you've made on my behalf already. Black Carrot 06:32, 4 March 2007 (UTC)[reply]

Solving simultaneous equations with 4 variables

How is it possible to solve S.E. with 4 variables? The equations are:

y = 14^3 a + 14^2 b + 14 c + d

y = 23.7^3 a + 23.7^2 b + 23.7 c + d

y = 303.5^3 a + 304.5^2 b + 304.5 c + d

y = 78.2^3 a + 78.2^2 b + 78.2 c + d

How can I find the values of A, B, C, D! or is there a better way? —Preceding unsigned comment added by 219.78.192.85 (talk • contribs)

Unless y has a fixed value, then you have five variables, not four - your variables are {y,a,b,c,d}. Note that {0,0,0,0,0} is a solution. Also, if {y,a,b,c,d} is a solution then so is any multiple of this solution i.e. {ky,ka,kb,kc,kd} - in other words, your equations are homogenous and linear.

As you have four homogenous linear equations in five dimensional {y,a,b,c,d} space, your solution set is a line through the origin (well, I am assuming the equations are independent here - I haven't checked that).

To find a point on this line (as well as the origin) set y equal to 1 and find the inverse of the 4x4 matrix formed by your 16 co-efficients. The equations are then solved by setting a equal to the sum of the entries in the top row of the inverse matrix; b equal to the sum of the entries on the second row etc. If y has some definite value other than 1 - say y=k - then just multiply the co-ordinates of this point by k. Gandalf61 12:52, 2 March 2007 (UTC)[reply]

... which is the general method, but spending another 30 seconds looking at the equations I now see that in this case the solution set has a simple structure and can be found "by inspection" - but I won't say any more in case this is homework. Gandalf61 12:57, 2 March 2007 (UTC)[reply]

I assume that the coefficient 303.5 is a mistake?81.153.220.170 14:57, 2 March 2007 (UTC)[reply]

And here's me thinking that with rep theory finished I was safe from the Vandermonde matrix for another day. That thing does turn up an awful lot. Algebraist 18:32, 2 March 2007 (UTC)[reply]

Assume that Y is a constant.

Y = 2744 A + 196 B + 14 C + D (eqn 1)

Y = 1892819 A + 561.7 B + 23.7 C + D (eqn 2)

Y = 27956067.9 A + 92720.25 B + 304.5 C + D (eqn 3)

Y = 478211.8 A + 6115.24 B + 78.2 C + D (eqn 4)

D = Y - 2744 A - 196 B - 14 C (from eqn 1)

We now have D = linearfunc(Y,A,B,C)

Next substitute eqn 1 into eqn 2

Y = 1892819 A + 561.7 B + 23.7 C - 2744 A - 196 B - 14 C + Y

Now clearly Y = anyvalue and so we get 0 = linearfunc(A,B,C) which means that C = linearfunc(A,B)

Note that: D = linearfunc(Y,A,B,C) plus C = linearfunc(A,B) becomes D=linearfunc(Y,A,B)

Now clearly, when we can substitute D=linearfunc(Y,A,B) and C=linearfunc(A,B) into eqn 3 to get B = linearfunc(A)

Next we can substitute D=linearfunc(Y,A) and C=linearfunc(A) and B=linearfunc(A) into eqn 4 to get Y = somenumber * A + Y

Clearly A=0 thus B = 0 thus C = 0 thus D = 0 which means that Y = 0

The main trick to understand is that D is substituted with ( Y - 2744 A - 196 B - 14 C ) and please note very very carefully that D is replaced with ( 1*Y + linearfunc(A,B,C) ).

Furthermore, neither A , B nor C is ever substituted with Y. So no matter how we substitute, we always end up with exactly one Y on the lefthandside of the equation and exactly one Y on the righthandside of the equation.

Solution completed. 211.28.130.252 00:04, 3 March 2007 (UTC)[reply]

I don't follow your logic. If you cancel y from both sides of your last equation you get an equation in a,b and c - you have simply subtracted equation 2 from equation 1. But it does not follow from this that a,b and c are 0, and it tells you nothing about the value of y. Gandalf61 00:21, 3 March 2007 (UTC) You have changed your argument, but you have still concluded that y=0. But there are solutions to the equations where y is not 0 - for example a=b=c=0, y=d=1. So you have not found all solutions - you have only found one point in the solution set. Gandalf61 10:54, 3 March 2007 (UTC)[reply]

I'm confused by the variable y as well. If you perhaps meant something like this:

0 = 14^4 + 14^3 a + 14^2 b + 14 c + d

0 = 23.7^4 + 23.7^3 a + 23.7^2 b + 23.7 c + d

0 = 303.5^4 + 303.5^3 a + 304.5^2 b + 304.5 c + d

0 = 78.2^4 + 78.2^3 a + 78.2^2 b + 78.2 c + d

then that's easy to solve from Viète's formulas. – b_jonas 15:00, 4 March 2007 (UTC)[reply]

Smoothing titration data

I have a set of data I generated from a titration lab with volume added (Vt) vs. pH, and the objective is to find the titration equivalence points. The raw curve looks something like [1], and the equivalance points are at the inflection points (second deriv. = 0). It is easy enough to just plot my data and estimate where I think it should be, but I've been trying to come up with a more analytical method. While my first plot of the data looks fairly smooth, when I graph ΔpH/ΔdVt, the more subtle points get shrouded in noise, and then the Δ²pH/ΔdVt² is pretty much trash. What I ended up doing was:

Taking difference in pH (y) divide by difference in volume (x) to obtain y'
Averaged the two volume points used for y' to obtain x'. (Note: differences between volume (x) points are not constant; they can vary from 0.05 mL near critical points to 2 mL elsewhere, but there are no major jumps)
Averaged 3 y' points and called that the y'-smoothed for the x' point in the middle of the three.
Plotted y'-smoothed vs. x' and read the x' value at the maximum and minimum points for the result

However, I have a few doubts about if it is actually accurate (I have the feeling it suffers something like a off-by-one error, but not sure how), and am wondering if I'm making some incorrect assumptions and/or if there is a better, more correct approach. Atropos235 22:41, 2 March 2007 (UTC) (ps. not sure if this should be at WP:RD/S, but it seems more statistics (math) oriented)[reply]

What you want to do in general is fit your data with a smooth function (possibly a polynomial, although you'll probably want to stick to orders no greater than, say, 5: see Runge's phenomenon). Then analytically find the inflection point of the smooth function. (Of course, if it has order greater than 3 it may have more than one such point; you'll have to consider whether to average them or throw some of them out or...) --Tardis 06:13, 3 March 2007 (UTC)[reply]

Agree in principle with this approach, but instead of polynomials, write out what you know about your system and try to solve for the functional form analytically. You know charge balance ([OH^-] + [OAc^-] == [H⁺] + (countercation charge) * [countercation to hydroxy added]), acid dissociation ([H⁺]*[OAc-]/[HOAc] = 1.8*10^-5), water dissociation ([H⁺]*[OH^-]=10^-14), and mass balance (([HOAc] + [OAc^-])*vol = mol HOAc added. Then you can solve for [H+],

Unfortunately, you get cubic equations (I think) in [H⁺] to solve; a trick you may have seen in class is to simplify one of the equations you know, here try the charge balance equation by dropping the [OH^-]. Now the solution will only be approximate, but until you add enough OH^- so that there comparable amounts of it and OAc^-, the solution will be pretty good. When you solve this, you get quadratic equations (I think) in [H⁺]. The solutions will be functions of [countercation to hydroxy added] (which is equivalent to your OH^- added but for the multiplicative charge of the cation).

Now you can differentiate (twice) the correct solution, plug in the values of (mol HOAc), volume, countercation charge, Kw and Ka, and set equal to zero. If, on the other hand, you are to assume you don't know Ka, and this exercise is to show how to estimate it (which is what it sounds like wsince you have real data), then use a curve fitting algorithm using added OH^- as the independent variable and [H⁺] as the dependent variable. You will get an estimate of Ka; plug it in to the second derivative expression obtained above, set to zero, and solve for added OH^-. Baccyak4H (Yak!) 20:19, 6 March 2007 (UTC)[reply]