All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Horoscope Hijinks I (Posted on 2006-11-28)
The twelve signs of the horoscope (AQUARIUS, ARIES, and so on) run a race along the Zodiac. In how many different ways can the race end, if ties are possible?

 See The Solution Submitted by Federico Kereki Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Can this be done without a computer? -- computer solution | Comment 4 of 7 |

I get 28,091,567,595 ways they can cross the finish line, best explained by the table below, produced by two stages of computer program.

The table lists the 77 ways in which the groups may be formed without regard to which zodiacal signs are members thereof.  The ways column lists how many ways the zodiacal signs can occupy that configuration of sets. The factor specifies how many ways those sets of people (each set being a cohort of tied individuals) can be rearranged.  I'll start by describing the first few lines.

The first row is all 1's, indicating each person crossed the finish line individually--there were no ties, so each group consisted of one member. There were 12! = 479001600 ways of populating the groups with individual members. Once this is done, there's no further rearranging needed, so the total ways for this is just the 12!.

The second row represents 10 individuals crossing the finish line separately and one pair crossing together. There are 12! / 2! ways of populating the groups, as the last two positions are indifferent as to the order of entry of their individual members.  But there are 11 positions that the group of two can have: the illustrated line has them tied for last place (places 11 and 12), but they may be tied for 1 and 2, or 2 and 3, or 3 and 4, etc., so we need to multiply by a factor of 11 to get the total ways accounted for by this line.

To take a more complicate case, consider the line

` 1  1  1  1  2  2  4                        4989600  105    523908000`

The 4989600 represents just the ways that individuals can come in places 1 through 4, with a tie for 5th and 6th place, a tie for 7th and 8th, as well as a 4-way tie for 9th thru 12th. This is 12!/(2!2!4!), as within the two groups of 2 and one group of 4, order doesn't matter.  But again, the 1,1,1,1,2,2,4 could itself be rearranged, into 7!/(4!2!) = 105 ways, each with 4989600 ways of filling the members' names, so the total ways is 4989600*105 = 523908000.

The total of the 77 total ways is 28,091,567,595, which is the answer.

`                                              ways factor  total ways 1  1  1  1  1  1  1  1  1  1  1  1       479001600    1    479001600 1  1  1  1  1  1  1  1  1  1  2          239500800   11   2634508800 1  1  1  1  1  1  1  1  1  3              79833600   10    798336000 1  1  1  1  1  1  1  1  2  2             119750400   45   5388768000 1  1  1  1  1  1  1  1  4                 19958400    9    179625600 1  1  1  1  1  1  1  2  3                 39916800   72   2874009600 1  1  1  1  1  1  1  5                     3991680    8     31933440 1  1  1  1  1  1  2  2  2                 59875200   84   5029516800 1  1  1  1  1  1  2  4                     9979200   56    558835200 1  1  1  1  1  1  3  3                    13305600   28    372556800 1  1  1  1  1  1  6                         665280    7      4656960 1  1  1  1  1  2  2  3                    19958400  168   3353011200 1  1  1  1  1  2  5                        1995840   42     83825280 1  1  1  1  1  3  4                        3326400   42    139708800 1  1  1  1  1  7                             95040    6       570240 1  1  1  1  2  2  2  2                    29937600   70   2095632000 1  1  1  1  2  2  4                        4989600  105    523908000 1  1  1  1  2  3  3                        6652800  105    698544000 1  1  1  1  2  6                            332640   30      9979200 1  1  1  1  3  5                            665280   30     19958400 1  1  1  1  4  4                            831600   15     12474000 1  1  1  1  8                                11880    5        59400 1  1  1  2  2  2  3                        9979200  140   1397088000 1  1  1  2  2  5                            997920   60     59875200 1  1  1  2  3  4                           1663200  120    199584000 1  1  1  2  7                                47520   20       950400 1  1  1  3  3  3                           2217600   20     44352000 1  1  1  3  6                               110880   20      2217600 1  1  1  4  5                               166320   20      3326400 1  1  1  9                                    1320    4         5280 1  1  2  2  2  2  2                       14968800   21    314344800 1  1  2  2  2  4                           2494800   60    149688000 1  1  2  2  3  3                           3326400   90    299376000 1  1  2  2  6                               166320   30      4989600 1  1  2  3  5                               332640   60     19958400 1  1  2  4  4                               415800   30     12474000 1  1  2  8                                    5940   12        71280 1  1  3  3  4                               554400   30     16632000 1  1  3  7                                   15840   12       190080 1  1  4  6                                   27720   12       332640 1  1  5  5                                   33264    6       199584 1  1  10                                       132    3          396 1  2  2  2  2  3                           4989600   30    149688000 1  2  2  2  5                               498960   20      9979200 1  2  2  3  4                               831600   60     49896000 1  2  2  7                                   23760   12       285120 1  2  3  3  3                              1108800   20     22176000 1  2  3  6                                   55440   24      1330560 1  2  4  5                                   83160   24      1995840 1  2  9                                        660    6         3960 1  3  3  5                                  110880   12      1330560 1  3  4  4                                  138600   12      1663200 1  3  8                                       1980    6        11880 1  4  7                                       3960    6        23760 1  5  6                                       5544    6        33264 1  11                                           12    2           24 2  2  2  2  2  2                           7484400    1      7484400 2  2  2  2  4                              1247400    5      6237000 2  2  2  3  3                              1663200   10     16632000 2  2  2  6                                   83160    4       332640 2  2  3  5                                  166320   12      1995840 2  2  4  4                                  207900    6      1247400 2  2  8                                       2970    3         8910 2  3  3  4                                  277200   12      3326400 2  3  7                                       7920    6        47520 2  4  6                                      13860    6        83160 2  5  5                                      16632    3        49896 2  10                                           66    2          132 3  3  3  3                                  369600    1       369600 3  3  6                                      18480    3        55440 3  4  5                                      27720    6       166320 3  9                                           220    2          440 4  4  4                                      34650    1        34650 4  8                                           495    2          990 5  7                                           792    2         1584 6  6                                           924    1          924 12                                               1    1            1                                         1191578522       28091567595`

The first program computed all the columns except the factor and total ways. Its results were placed into a file that the second program read.

First program:

10    Fact12=!(12)
100    for A=1 to 12
200     if A=12 then ?a,tab(41);:print using(10,0),Fact12//Fact12: Ct=Ct+Fact12//Fact12
300    for B=A to 12-A
400     if A+B=12 then ?a;b;tab(41);:print using(10,0),Fact12//(!(A)*!(B)) Ct=Ct+Fact12//(!(A)*!(B))
500    for C=B to 12-A-B
600     if A+B+C=12 then ?a;b;c;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)): Ct=Ct+Fact12//(!(A)*!(B)*!(C))
700    for D=C to 12-A-B-C
800     if A+B+C+D=12 then ?a;b;c;d;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)): Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D))
900    for E=D to 12-A-B-C-D
1000     if A+B+C+D+E=12 then ?a;b;c;d;e;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)): Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E))
1100    for F=E to 12-A-B-C-D-E
1200     if A+B+C+D+E+F=12 then ?a;b;c;d;e;f;tab(41);:print using(10,0),fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)): Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F))
1300    for G=F to 12-A-B-C-D-E-F
1400     if A+B+C+D+E+F+G=12 then
1409     :?a;b;c;d;e;f;g;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G))
1410     :Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G))
1500    for H=G to 12-A-B-C-D-E-F-G
1600     if A+B+C+D+E+F+G+H=12 then
1609     :?a;b;c;d;e;f;g;h;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H))
1610     :Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H))
1700    for I=H to 12-A-B-C-D-E-F-G-H
1800     if A+B+C+D+E+F+G+H+I=12 then
1809     :?a;b;c;d;e;f;g;h;i;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I))
1810     :Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I))
1900    for J=I to 12-A-B-C-D-E-F-G-H-I
2000     if A+B+C+D+E+F+G+H+I+J=12 then
2009     :?a;b;c;d;e;f;g;h;i;j;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I)*!(J))
2010     :Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I)*!(J))
2100    for K=J to 12-A-B-C-D-E-F-G-H-I-J
2200     if A+B+C+D+E+F+G+H+I+J+K=12 then
2209     :?a;b;c;d;e;f;g;h;i;j;k;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I)*!(J)*!(K))
2210     :Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I)*!(J)*!(K))
2300    for L=K to 12-A-B-C-D-E-F-G-H-I-J-K
2309     ?a;b;c;d;e;f;g;h;i;j;k;l;tab(41);:print using(10,0),Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I)*!(J)*!(K)*!(L))
2310     Ct=Ct+Fact12//(!(A)*!(B)*!(C)*!(D)*!(E)*!(F)*!(G)*!(H)*!(I)*!(J)*!(K)*!(L))
2500    next
2600    next
2700    next
2800    next
2900    next
3000    next
3100    next
3200    next
3300    next
3400    next
3500    next
3600    next
3700    print tab(40);:? using(11,0),Ct
3800

The second program read the first program's output, computed the factor and the total ways:

DECLARE FUNCTION fact# (x#)
DEFDBL A-Z
OPEN "horoshij.txt" FOR INPUT AS #1
OPEN "horoshi2.txt" FOR OUTPUT AS #2
DO
LINE INPUT #1, l\$
lCt = 0: typCt = 0: longCt = 0
IF LEFT\$(l\$, 3) > "   " THEN
FOR i = 1 TO 34 STEP 3
s\$ = MID\$(l\$, i, 3)
IF s\$ > "   " THEN
lCt = lCt + 1
longCt = longCt + 1
IF lCt > 1 THEN
IF s\$ <> ps\$ THEN
typCt = typCt + 1
nCt(typCt) = lCt - 1
lCt = 1
END IF
END IF
ELSE
EXIT FOR
END IF
ps\$ = s\$
NEXT
typCt = typCt + 1
nCt(typCt) = lCt
factor = fact(longCt)
FOR i = 1 TO typCt
factor = factor / fact(nCt(i))
NEXT
oNum = VAL(MID\$(l\$, 40))
tNum = oNum * factor
PRINT #2, l\$;
PRINT #2, USING "##### ############"; factor; tNum
tot = tot + tNum
ELSE
PRINT #2, l\$;
PRINT #2, USING "     ############"; tot
END IF
LOOP UNTIL EOF(1)
CLOSE

FUNCTION fact (x)
f = 1
FOR i = 2 TO x
f = f * i
NEXT
fact = f
END FUNCTION

A similar pair of programs verifies Jer's finding of 75 for 4 racers:

` 1  1  1  1                                      24    1           24 1  1  2                                         12    3           36 1  3                                             4    2            8 2  2                                             6    1            6 4                                                1    1            1                                                 47                75                                                 but finds 541, rather than 931 for 5 racers:`
` 1  1  1  1  1                                  120    1          120 1  1  1  2                                      60    4          240 1  1  3                                         20    3           60 1  2  2                                         30    3           90 1  4                                             5    2           10 2  3                                            10    2           20 5                                                1    1            1                                                246               541`

 Posted by Charlie on 2006-11-28 16:00:11

 Search: Search body:
Forums (0)