Wikipedia:Reference desk/Archives/Mathematics/2007 February 8

Mathematics desk
< February 7 << Jan | February | Mar >> February 9 >
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.



February 8

edit

Do square root of -i exists?

edit

Do square roots of -i exists? Does it have two roots? 202.168.50.40 00:39, 8 February 2007 (UTC)[reply]

 David Eppstein 02:09, 8 February 2007 (UTC)[reply]
Yes. In fact, once we move up from the real numbers to the complex numbers, we finally reach a set that is algebraically closed - in fact, this property is the basis of the fundamental theorem of algebra. What this means, effectively, is that every polynomial has solutions. One upshot of this is that every number in the complex numbers has square roots, cube roots, etc, since the square roots of some number a are just the solutions to the equation  . Maelin (Talk | Contribs) 03:13, 8 February 2007 (UTC)[reply]

e-mail of ministry education of research center

edit

I want tokown the e-mail of ministry education of research center

Which country do you live in? - Akamad 08:36, 8 February 2007 (UTC)[reply]

Algorithm for pairing players in round-robin chess tournament

edit

I wish to invite n players to participate in a round-robin chess tournament.

1. Is it possible to express as a function of n, the total number of ways that they can be paired for a) 1 round? b) n-1 rounds (the entire tournament)?

2. Is there an algorithm which I can use, without computer assistance, to quickly generate fixtures? Remember, in a round-robin tournament, each player plays everyone else only once. (One method I know is to factorise n, then generate fixtures for factors of n, and arrange the n players into groups of the factors.)

One way would be to have a table of n columns and n rows - for the first round pick a number randomly from the first row - this is who player one plays. Cross off that square in the array and remember to cross off the corresponding square (mark with a 1) eg if player 1 plays player 4, (ie you picked column 4 in row 1) then also cross off column 1.row 4. Repeat this for every row that does not already have a 1 in.
For the second round repeat the proceedure but obviously ignore squares that are already crossed off. Cross of each with a 2.
And repeat until all the squares are crossed out.
All you need is pen/paper (one sheet per tournament) and a method of randomly picking one square from a row.
There are other ways - if there are 6 or less players (or maybe 9) you could pick dominos randomly from out of a bag (ignore doubles) - so picking [6-3] means player 6 plays player 3. Then pick another domino - if you get for instance [4-3](player 3 has already been picked) put it back in the bag and pick again.
So you need to pick n/2 dominos per round. At the end of each round 'discard' the picked dominos and continue with the dominos remaining in the bag. You can get dominos with up to 9 dots - if you have say 6 players ignore any with more that a value 6 on either of the faces. Hope that helps.87.102.2.204 11:00, 8 February 2007 (UTC)[reply]
Have you tried the method you suggested? I used to do that, but in the last few rounds, I find it difficult to pair them and ensure everyone plays everyone else only once. That's why I thought up the "arrange players into groups of factors of n" method, which appears to be quite effective. I'm just wondering if there are methods even faster and more effecient than the "arrange players into groups of factors of n" method.
Ah yes - it does get more difficult especially towards the end - the dominos method is the other way round - as the dominos are discarded as matches are played - but in this case it might take a couple of goes to get matches at the beginning. I can't think of simpler methods - without using a computer.. Sorry.87.102.45.80 11:54, 10 February 2007 (UTC)[reply]

3. What are the algorithms computers use to quickly generate fixtures for round-robin tournaments?

There are a number of algorithms that could be used to do this - one factor is whether or not you want the selection in the first round to be random, or alternatively to always pick pairs in the same way for each round. I'm sure someone can give you more details.87.102.2.204 10:48, 8 February 2007 (UTC)[reply]
I could describe some algorhythms that would work if you wish - though they would be based on the methods already described - please say so if you want this.87.102.9.117 20:33, 10 February 2007 (UTC)[reply]
Go ahead and describe the algorithms, even if they are based on the "arrange players into groups of factors of n" method.
Oops, VERRY SORRY, the algorhythms I described "don't work" do they.. I'll take my blinkers off. I'll see if I can describe a simple one that does work, in the mean time there may may a delay...87.102.9.15 12:38, 11 February 2007 (UTC)[reply]

OK All I can come up with is a method which checks a set of nn(n+1)/2 possible combinations until it finds a match set up for (n-1) games that isn't invalid - not very good and I'm sure you could imagine a method of setting up n(n+1)/2 loops each looping from 1 to n and then checking each combination for invalidity. Apologies for the un-thought-out gunk above.87.102.9.15 14:10, 11 February 2007 (UTC)[reply]

Here's one that should work. it uses an n x n array where array(4,3)=7 means that player 4 plays player 3 in round 7.

n=number of players
Make Array A(n,n) ; initially all values in the array are 0
x=1
Loop3: y=x+1
Loop2: A(x,y)=A(x,y)+1, A(y,x)=A(y,x)+1
IF A(x,y)<n THEN GOTO Loop4
A(x,y)=0, A(y,x)=0, y=y-1
IF y>x THEN GOTO Loop2
x=x-1, GOTO Loop3
Loop4: DO PROCEDURE "Check_Array_Validity" ; the procedure (see below) returns Q=true or false
IF Q=false THEN GOTO Loop2
y=y+1
IF y<=n THEN GOTO Loop2
x=x+1
IF x<=n THEN GOTO Loop3
DO PROCEDURE "Print results"
END.
PROCEDURE "Check_Array_Validity"
a=1
Loop1
IF A(x,a)=A(x,y) AND NOT (a=y) THEN Q=false, EXIT
IF A(a,y)=A(x,y) AND NOT (a=x) THEN Q=false, EXIT
a=a+1
IF a<=n THEN GOTO Loop1
Q=true, EXIT
PROCEDURE "Print results"
FOR r=1 to n-1
PRINT "Round Number:",r
FOR x=1 to n
FOR y=x to n
IF A(x,y)=r THEN PRINT "Player No.",x," plays ,"player No. ",y
NEXT y
NEXT x
NEXT r
EXIT

This should work - it goes through all the possible sets of matches until it finds one that is valid - Absolutely terrible when n=big I'm afraid.83.100.255.117 16:42, 12 February 2007 (UTC)[reply]

Though if you look at Round-robin_tournament#Scheduling_Algorithm it gives an algorhythm that is millions of times simpler..83.100.255.117 16:47, 12 February 2007 (UTC)[reply]

arcsin(\sqrt{2/3})

edit

A numerical approximation of   may be  . But is there a nice exact representation known, analogous to  .

88.74.0.242 11:14, 8 February 2007 (UTC)[reply]

Not what you want, but it equals 54.7356103° as well. − Twas Now ( talkcontribse-mail ) 11:47, 8 February 2007 (UTC)[reply]
This looks like it will end up an ugly number either way. − Twas Now ( talkcontribse-mail ) 11:50, 8 February 2007 (UTC)[reply]

As a nice english expression - how about "the angle that the edge of a tetrahedron placed on a horizontal plane makes with the horizontal" - ?87.102.2.204 11:52, 8 February 2007 (UTC) I'm guessing that this is the angle you seek - there doesn't seem an expresion for it that isn't an infinite series (I can't currently find the page that lists the angles that have 'simple' sines and cosines - there is one but I can't recall it's name - it's not in that list).83.100.158.135 15:35, 8 February 2007 (UTC)[reply]

Note if someone could supply an expression for arcsin (a/b) in terms of arcsin (a) and arcsin (b) that would help since sqrt(3)/2 and 1/sqrt(2) could be used. I'm not aware of such a thing...83.100.158.135 15:37, 8 February 2007 (UTC)[reply]
See Exact trigonometric constants - your value notable by it's absence -sorry.83.100.158.135 15:40, 8 February 2007 (UTC)[reply]
Plouffe's Inverter gives the formula   which probably doesn't help you. – b_jonas 20:59, 8 February 2007 (UTC)[reply]
Hey, thanks! Ever since the Inverse Symbolic Calculator kinda died I've been wishing there were a similar thing.
I've found it in Sloane's link collection: [1]. – b_jonas 11:22, 10 February 2007 (UTC)[reply]