Conference rusure::math

    Who plays what is unimportant in counting these combinations (otherwise,
    the answer would simply be 3�3�3 = 27).  Counting:
    
    	Combinations that have all three the same:	3
    	Combinations that have exactly two the same:	6
    	Combinations that have all three different:	1
    						      ----
    	Total number of combinations:		       10

    If that's as far as the book goes, it's a pretty cheesy problem.
    I would think one could then continue along the lines of:
    
    "What is the probability a 3-player game concludes in 1 round?"
    
    (e.g., SPP is a win for S)
    
    "What is the expected length (in turns) of a game, when all players
    repeat if no clear winner emerges?"
    
    (exercise for the reader)
    
    So as a standalone question it's pretty silly, but as question 1 of a
    series it might make some sense.
    
      John

One way of looking at the problem is to attach digits to the letters in 
alpha order, e.g. p=0, r=1, s=2. Now a play is a 3-digit radix-3 integer, 
and the possible plays are those *in which the digits are in non-decreasing
order*. MAPLE is helpful here:

with(combinat, combine);
	...
combine([0$3,1$3,2$3],3);

 [[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 1, 1], [0, 1, 2], [0, 2, 2], [1, 1, 1],
     [1, 1, 2], [1, 2, 2], [2, 2, 2]]

or in terms of prs,

combine([p$3,r$3,s$3],3);

 [[p, p, p], [p, p, r], [p, p, s], [p, r, r], [p, r, s], [p, s, s], [r, r, r],
     [r, r, s], [r, s, s], [s, s, s]]
 
Counting permutations gives:

> nops(permute(3,0))+nops(permute(3,1))+nops(permute(3,2));
                                       10

    Suppose they were playing "Fire, Water, Earth, and Air" (i.e., 4 choices).
    Now how many combinations are there?  What if 5 people played?  Generalize.

Hmmm. Looks like 
> nops(permute(3,0))+nops(permute(3,1))+nops(permute(3,2));
                                       10

does not generalize well. I overlooked something. Anyhow,

combine([a$4,e$4,f$4,w$4],4);

   [[a, a, a, a], [a, a, a, e], [a, a, a, f], [a, a, a, w], [a, a, e, e],

       [a, a, e, f], [a, a, e, w], [a, a, f, f], [a, a, f, w], [a, a, w, w],

       [a, e, e, e], [a, e, e, f], [a, e, e, w], [a, e, f, f], [a, e, f, w],

       [a, e, w, w], [a, f, f, f], [a, f, f, w], [a, f, w, w], [a, w, w, w],

       [e, e, e, e], [e, e, e, f], [e, e, e, w], [e, e, f, f], [e, e, f, w],

       [e, e, w, w], [e, f, f, f], [e, f, f, w], [e, f, w, w], [e, w, w, w],

       [f, f, f, f], [f, f, f, w], [f, f, w, w], [f, w, w, w], [w, w, w, w]]

Gives 35 cases for 4 players, 4 options. There are 126 for 5 players, 5
options. 

Thanks for all of your help.  Can I understand, then, that the answer is 
obtained by combining (i.e. adding) all relevant permutations?

This problem was taken from a review book for the GMAT.  Judging by the 
relative complexity - mainly in setting up the permutations -  of the answers
that you gave me, I cannot believe that the question writers intended for the 
problem to be solved this way.  Then again, listing all of the possibilities 
by hand seems trivial.  Yet, that is how the answer was given in the book.

BTW, what is "Fire, Water, Earth, and Air?"  I assume this refers to the 
ancient idea of elements.  How do you play?

Thanks,

Tim

    Water beats Fire which beats Air which beats Earth which beats Water.

>	.4 (Gilbert)
>    Suppose they were playing "Fire, Water, Earth, and Air" (i.e., 4 choices).
>    Now how many combinations are there?  What if 5 people played?  Generalize.

	Suppose you've got P people each picking one of S symbols, then the
number of possible results is:
				( P+S-1 )
				(   P   )

	(Choose S-1 distinct elements, a_0,...,a_(S-2) from {0,...,P+S-2},
where a_i < a_(i+1), for all i.   Let b_i = a_i - i, for all i.   So b_i =<
b_(i+1), for all i, and b_(S-2) =< P.   Define b_(-1) = 0, b_(S-1)=P.   Label
the symbols {0,...,S-1}.   Let b_i-b_(i-1) be the number of people who get 
symbol i.)

>	.5 Lynn
>Gives 35 cases for 4 players, 4 options. There are 126 for 5 players, 5
>options. 

	Agrees with the above formula.

Cheers,
Andrew.

>	.6 Matthews
>BTW, what is "Fire, Water, Earth, and Air?"  I assume this refers to the 
>ancient idea of elements.  How do you play?
>	.7 Hallyburton
>    Water beats Fire which beats Air which beats Earth which beats Water.

	Well this isn't complete.   We need to define what happens when
Water encounters Air, and when Fire encounters Earth.

	Take a step back, away from the four elements.

	We're trying to define a directed graph, where for any two distinct
vertices, u&v, either edge u->v exists or edge v->u exists, but not both.
Such a graph is called a *tournament*, I seem to remember.

	We want additional constraints to hold.   No symbol wins all the time 
(for then the game would be rather pointless), and no symbol loses all the 
time (for then that symbol would be rather unpopular).   This corresponds to
requiring that each vertex of the tournament is the invertex for at least one
edge, and the outvertex for at least one edge.   Call a tournament satisfying
these requirements a *fair* tournament.

	How many fair tournaments are there with four vertices

	Answer: 1.

	Each vertex, by the fairness requirement, must be a member of a cycle
of length at least 3.   You might think that you could have a fair tournament
like the one proposed in an earlier reply:

>                   -< Rock, Paper, Scissors, PhotonTorpedo >-

where you keep the 3-cycle RPS.   But it turns out that you can't define the
functionality of the PhotonTorpedo without permitting a 4-cycle.   And this
generalizes to the result that every fair tournament is Hamiltonian (proof
by induction.)

	So, for 4 vertices, we have to have a 4-cycle, and then there is up
to IM only one way to direct the other two edges, so any fair tournament on
4 vertices you design will be isomorphic to:

	+---->A-----+
	|     |     |
	|     |     |
	|     |     v
	F-----+---->E
	^     |     |
	|     |     |
	|     v     |
	+-----W<----+

Cheers,
Andrew.

	Now, the next question is: what's the best strategy for this 
symmetrical zero-sum two player game?   If by best we mean minimax, then the 
answer is not too hard.   The game's a little more diverting than RPS, because
each of the symbols is distinct from the others, whereas RPS has the boring
strategy (1/3,1/3,1/3).

	In RPS, if someone *doesn't* play probability 1/3 for each symbol, then
the opponent can take advantage of whatever symbol is being prefered, and
profit from it.   So (1/3, 1/3, 1/3) is the unique minimax strategy.

	In EAFW, the payoff matrix, M, is:

		 0 -1 -1 +1
		+1  0 -1 +1
		+1 +1  0 -1
		-1 -1 +1  0

	If x is the column vector of probabilities with which each strategy
is being selected, then x is a viable strategy if Mx =< 0.   (Ie, each element
of the column vector Mx =< 0.)   M is non-singular, so has no non-trivial null-
space.   The minimax strategy for EAFW is hence more complex to that of RPS.

	The unique minimax strategy turns out to be (0, 1/3, 1/3, 1/3).   
Someone playing E,A,F or W against this will score -1/3, 0, 0 or 0.   Maybe I 
could have guessed this, but I didn't.

Cheers,
Andrew.

    Something doesn't look right here.  In the .9 graph:
    
	+---->A-----+		Let's say W--->F means W beats F.
	|     |     |		Then F beats A and F beats E.
	|     |     |		E loses to A and loses to F.
	|     |     v
	F-----+---->E		Therefore doesn't it seem to make sense
	^     |     |		to choose F twice as much as E, and
	|     |     |		similarly A twice as much as W?
	|     v     |
	+-----W<----+		"Fair" seems a poor choice of terms here.
    
    Suppose there is no vector FE nor AW, i.e., F vs. E is a tie, just like
    W vs. A just like F vs. F or W vs. W.  While not a "tournament" in any
    strict sense, it's still a playable game, so I don't like the answer 1.
    
      John
    

.10>	In EAFW, the payoff matrix, M, is:
.10>	The unique minimax strategy turns out to be (0, 1/3, 1/3, 1/3).   
.11>    Intuitively I would say (1/6, 1/3, 1/3, 1/6)

Let's compare strategies

			   Andrew
		     |	 0 1/3 1/3 1/3
		-----+---------------
		1/6  |	 0  -1  -1  +1
	John	1/3  |	+1   0  -1  +1
		1/3  |	+1  +1   0  -1
		1/6  |	-1  -1  +1   0

What does John earn per play?

	1/6*(1/3*(-1-1+1)) + 1/3*(1/3*0) + 1/3*(1/3*0) + 1/6*(1/3*0)
	= -1/18

John's expected loss is 1/18 per play.

	Say that a fair tournament in n dimensions is *dull* if every minimax 
strategy looks like this (0,0,...0,1/r,1/r,...1/r), where there are n-r zeros
and r cases of 1/r.   Note, r will be odd.

Q:	What's the smallest non-dull fair tournament?

A:	dimension 5.   Try Foo beats RPS beats Bar beats Foo.   The payoff
for RPSFB is (1/9,1/9,1/9,1/3,1/3).   I allege that the other 5 fair 
tournaments of that dimension are dull (most with r=3, but the regular one
has r=5).

	But actually all that's happened here is we've embedded RPS inside
one vertex of RPS.   It's not *that* non-dull.

Andrew.