Mathematics desk
< May 11	<< Apr \| May \| Jun >>	May 13 >

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.

May 12

Nim Variation

In Nim, given X = {x₁,x₂,x₃...x_n}, a move consists of reducing some x_i by an amount k. I'm pretty sure that if a move consisted of reducing any selection of an odd number of xs, each by an amount k, the game would remain unchanged. That is, any position with a winning strategy would keep that winning strategy, and no position without a winning strategy would gain one. So, just like in Nim, a position would have a winning strategy iff its heaps didn't Nim-sum to 0. I'm having trouble proving it, though. The first part is easy; from each position you'd still be able to reduce any 1 pile by an amount k, so anything I've assumed is a winning position reduces easily to an alleged losing position. The second part I can't get; how do I prove that if the Nim-sum across X is 0, it isn't 0 if you reduce any odd number of xs by equal amounts? Or equivalently, if n is odd, how do I prove that reducing all xs by equal amounts must change the Nim-sum? Counterexamples are also welcome. Black Carrot 05:25, 12 May 2007 (UTC)[reply]

An equivalent statement is: for odd n, the nim-sum (x₁+d) ⊕ ... ⊕ (x_n+d) is not equal to x₁ ⊕ ... ⊕ x_n – unless, of course, d = 0. Let p be the lowest bit position in the binary representation of d that has a 1 digit. For each i, x_i+d agrees with x_i in all lower position, but differs in position p. Then the nim-sum also agrees in all positions below p, while we find a difference at position p. An even number of differences in the same position would always cancel in the nim-sum; an odd number never does. --Lambiam ^Talk 08:51, 12 May 2007 (UTC)[reply]

Algorithm assistance

Consider the group < σ₁, σ₂, ..., σ_k >. What is the simplest way of determining the group's order? —The preceding unsigned comment was added by 149.135.125.155 (talk • contribs) 06:31, 12 May 2007 (UTC) - Please sign your posts![reply]

That would depend on what else you know about it, wouldn't it? Given no information, it seems like counting it would be simplest. Black Carrot 06:47, 12 May 2007 (UTC)[reply]

You are only given the generating set and no other information. The equivalent question to ask would be to determine its elements, and an algorithm to do that isn't so immediately apparent either. —The preceding unsigned comment was added by 149.135.125.155 (talk • contribs) 07:04, 12 May 2007 (UTC) - Please sign your posts![reply]

Do you mean checking it to see if it's in ascending or descending order ? This can be done with a single pass, using lines like this (FORTRAN used in the example):

ASC_FLAG = .TRUE.
DSC_FLAG = .TRUE.
DO I = 2,N
  IF (SIGMA(I-1) .GT. SIGMA(I)) THEN ASC_FLAG = .FALSE.
  IF (SIGMA(I-1) .LT. SIGMA(I)) THEN DSC_FLAG = .FALSE.
ENDDO

StuRat 06:59, 12 May 2007 (UTC)[reply]

No, you are given a generating set of a group, and I would like an indication of a simple algorithm to determine the order of the group generated by that generating set. —The preceding unsigned comment was added by 149.135.125.155 (talk • contribs) 07:04, 12 May 2007 (UTC) - Please sign your posts![reply]

There's a survey on algorithms for groups, including permutation groups (what I assume you mean by using sigmas to denote the generators) at [1]. It doesn't really have enough detail to tell you how to solve the problem, I think, but maybe it will give you a better idea where to look. —David Eppstein 07:07, 12 May 2007 (UTC)[reply]

I know where I'd look in texts, but the problem is, I don't have ready or simple access to them. I was hoping someone would outline some algorithm in a general way or point to some specific instance on the internet somewhere. I suppose what the effective question is: is there something simpler or easier than implementing the well-known Schrier-Sims algorithm? —The preceding unsigned comment was added by 149.135.125.155 (talk • contribs) 07:09, 12 May 2007 (UTC) - Please sign your posts![reply]

How large is that order going to be? In the thousands, millions, or more? Also, do you want this algorithm to be incorporated in a larger program? Depending on the circumstances and the magnitude of the problem, it may be acceptable to just generate the group and count the elements. If you have a non-humungous one-shot problem, you can use Magma's online calculator. --Lambiam ^Talk 08:04, 12 May 2007 (UTC)[reply]

I personally won't be using it for very large orders, but I want a basic algorithm that works and that I can replace with something better later. It's all very well and good to say "generate the group", but I need an algorithm to do that as well -- I can only think of very inefficient ones.

There is very inefficient and then there is very inefficient. Would this work for you? Below Q is a variable containing a stack or a deque – the order in which elements are "dequeued" is immaterial. Variable S contains a representation of a set (whose elements are permutations) that allows (1) a fast test for membership, and (2) fast addition of a new member. A hash table will do if it can handle collisions; pragmatically the operations then take O(n) time, where n is size needed for representing a permutation. Counter C is at all times the size of S.

Initialize (S, C) := ({id}, 1); Q := [id]; (where id is the identity permutation)

While Q is not empty:

Dequeue σ := head(Q);

For i := 1, ..., k:

Compute σ' := σ o σ_k;

If σ' ∉ S:

Set (S, C) := (S ∪ {σ'}, C+1); Enqueue σ' onto Q;

End If

End For

End While

This takes time O(knc), where k is the size of the set of generators, n the size of the underlying set, and c the order to be computed. If you don't have to do this thousands of times a second, and knc is not more than a million or so, then this naive algorithm is fine on a reasonably fast computer. Instead of an explicit stack, you can also use a recursive function with side effects. (Disclaimer: I haven't tested the above algorithm.) --Lambiam ^Talk 11:32, 12 May 2007 (UTC)[reply]

Great! I think this will work! I will test it tomorrow and will let you know how it goes.

Yes, it looks like it indeed works. Thanks very much!

statisticians (life story , summary of their contribution , detailed exposition of two applications)

i want to know about three statisticians ? —The preceding unsigned comment was added by 59.180.45.86 (talk) 09:13, 12 May 2007 (UTC).[reply]

Thomas Bayes would be a good one to do.

Sure. I was born in Sydney, went to the University of Sydney ... oh, I assume you mean important statisticians? Take your pick from Category:Statisticians. Confusing Manifestation 11:18, 12 May 2007 (UTC)[reply]

... or see list of statisticians. Gandalf61 11:21, 12 May 2007 (UTC)[reply]

Statistics has a shorter list of the more important contributors. --Salix alba (talk) 11:29, 12 May 2007 (UTC)[reply]

I agree Thomas Bayes is a good choice. Florence Nightingale is another one; an interesting story, and most people are unaware of her contributions to statistics. I'd also like to suggest William Sealy Gosset, aka Student. Together they cover quite different aspects of statistics. --Lambiam ^Talk 11:42, 12 May 2007 (UTC)[reply]

If A not equal to B

If A is never equal to B, and A - B = N, is N ever equal to 0? I don't think so but I'm not sure, thanks, Jeffrey.Kleykamp 16:53, 12 May 2007 (UTC)[reply]

I believe that is correct, N ≠ 0. StuRat 17:42, 12 May 2007 (UTC)[reply]

What manner of things are A and B? There are some types of mathematical object and operations called minus for which this is not true, but assuming you're dealing with numbers or somesuch thing, you're fine. Algebraist 17:46, 12 May 2007 (UTC)[reply]

Thanks Jeffrey.Kleykamp 17:53, 12 May 2007 (UTC)[reply]

Here is a proof of the statement. By checking all steps, unwarranted assumptions on the nature of the objects involved should become apparent. First, let us simplify the statement to be proved a bit, by removing the temporal aspect. ("2+2 is always 4" means the same as "2+2 = 4".) The statement is then: If A ≠ B and A − B = N, then N ≠ 0. Well, if A − B = N, then N = A − B, and since we may replace equals by equals without change of meaning, we can rephrase the statement as: If A ≠ B and A − B = N, then A − B ≠ 0. Notice now that N is no longer referenced, so the assumption A − B = N is no longer required, and we can remove it. We have now simplified the statement to: If A ≠ B, then A − B ≠ 0. Appealing now to the fact that a statement is equivalent to its contrapositive, we obtain the equivalent statement:

If A − B = 0, then A = B.

Thus far, no properties of the objects involved, including the operations, have been used. We now set out to prove the above statement, starting by assuming the antecedent A − B = 0, and working towards the consequent A = B. So assume that

A − B = 0.

Rewrite the left hand side, using the fact that A − B is the same as adding the additive inverse −B of B to A:

A + (−B) = 0.

Add B to both sides:

(A + (−B)) + B = 0 + B.

Rearrange the left hand side, using the associativity of addition:

A + ((−B) + B) = 0 + B.

The sum of the additive inverse of a number and the number itself equals (by definition) the neutral element of addition, which is 0:

A + 0 = 0 + B.

Using, at both sides, the fact that 0 is the neutral element of addition operation, we arrive at the desired conclusion:

A = B.

We have used no other properties than that + is the operation of an Abelian group whose neutral element is denoted as 0, and for which A − B is shorthand notation for A + (−B), where −B is the inverse of B. These assumptions hold for all number systems in use, and many other algebraic structures, such as rings. --Lambiam ^Talk 18:23, 12 May 2007 (UTC)[reply]

To hi-jack the question - in $\mathbb {F} _{2}$ , the field of two elements, what is (0 - 1) equal to? Is it 1? I'm trying to use the axioms for a field to prove it, but I'm not seeing it. It's ridiculously simple, isn't it? Icthyos 18:21, 12 May 2007 (UTC)[reply]

The following is an ugly proof, but if there are exactly two elements 0 and 1, then either 0 − 1 = 0, or 0 − 1 = 1. In the first case, we find (see above) that 0 = 1, which contradicts the fact that there are two elements. Conclusion: only the possibility 0 − 1 = 1 is left. A nicer proof is based on figuring out more constructively what 1 + 1 is, which can be done from first principles, or by appeal to the theorem that for prime p the field F_p, viewed as a ring, is the same as Z/pZ. --Lambiam ^Talk 18:36, 12 May 2007 (UTC)[reply]