[quote name=\'TLEberle\' post=\'193872\' date=\'Aug 12 2008, 08:39 PM\']
[quote name=\'rjaguar3\' post=\'193808\' date=\'Aug 11 2008, 01:51 PM\']Thus, with optimal strategy and effective passing allowed, the no-order Carmen Sandiego game never terminates.[/quote]Well, the first player should have an advantage, since he had more points coming out of round one, right? (unless it was tied). Now, I was never keen on round two anyway, since it seems like nothing more than dumb luck with a soupçon of memory thrown in (and even that was just in remembering what's been visited), but there are a few things I can't wrap my head around.
How can you tell what the chances are for either person? They have a 1 in N chance of finding a relevant bit of information, and if they don't, N keep shrinking until someone wins. The only advantage seems like it would go to the player who has the first pick per cycle.
[/quote]
You can basically average over all possibilities. The recursion works something like this, if there are n key items to be found and m distractors remaining, and P(n,m) is the probability that the player whose turn it is will eventually win, then P(n,m) satisfies this recursion (when order matters):
P(0, m) = 1 [if all the key items have been found, it's just a matter of picking them in order]
P(n, m) = (1/(n+m))*P(n-1,m) [you found the first key item that you needed]
+ ((n-1)/(n+m))*(1-P(n-1,m)) [you found a key item, but it was out of order, so you "use some strategy" and allow the second player to get first crack at the new position]
+ (m/(n+m))*P(1-P(n,m-1)) [when m is not 0] [you found a distractor, so it's now the opponent's turn to play, and he has one less distractor to worry about]
When order matters, the recursion is similar [I will use Q(n,m) to denote the probability for the unordered game]
Q(0, m) = 1 [if all the key items have been found, it's just a matter of picking them]
Q(n, m) = (
n/(n+m))*Q(n-1,m) [you found a key item, and it's still your turn in the new position]
+ (m/(n+m))*Q(1-Q(n,m-1)) [when m is not 0] [you found a distractor, so it's now the opponent's turn to play, and he has one less distractor to worry about]
You saw my handwaving argument above, so I'll offer a formal proof by induction that the ordered game amounts to no more than a coin-flip when there are at least two key items left. (Feel free to skip over this if you're really not that interested.)
Suppose there are two key items. I will prove that P(2,m)=0.5 by induction. First, let m=0. Then P(2,0)=(1/2)*P(1,0)+(1/2)*(1-P(1,0))=0.5P(1,0)+0.5-0.5P(1,0)=0.5. Now assume that P(2,m)=0.5 for m=k. Then P(2,k+1)=(1/(3+k))*P(1,k+1)+(1/(3+k))*(1-P(1,k+1))+((1+k)/(3+k))*(1-P(2,k))=(1/(3+k))*P(1,k+1)+1/(3+k)-(1/(3+k))*P(1,k+1)+((k+1)/(k+3))*0.5=1/(3+k) + (0.5k+0.5)/(3+k)=(1.5+0.5k)/(3+k)=0.5. So P(2,m)=0.5
To show that P(n,m)=0.5 when n>=2, I will now use induction on n. We have already proven the n=2 case above. Let P(n,m)=0.5 for all m when n=r. Now I will induct on m. When m=0, note that P(r+1,0)=(1/(r+1))*P(r,0)+(r/(r+1))*(1-P(r,0))=(1/(r+1))*0.5+(r/(r+1))*0.5=((r+1)/(r+1))*0.5=0.5. Now, let P(r+1,m)=0.5 for m=k. Then P(r+1,m+1)=(1/(r+m+2))*P(r,m+1)+(r/(r+m+2))*(1-P(r,m+1))+((m+1)/(r+m+2))*(1-P(r+1,m))=(1/(r+m+2))*0.5+(r/(r+m+2))*0.5+((m+1)/(r+m+2))*0.5=((r+m+2)/(r+m+2))*0.5=0.5. So the induction is complete, and P(n,m)=0.5 when n >= 2. In particular, since 3 >= 2, then P(3,12)=0.5, which means that the original Carmen Sandiego game, under optimal strategy, is tantamount to a coin flip.
And in the format where you were allowed to violate police code by arresting the crook without evidence or due process, why would the second player stalemate? In order to win, you have to play the game, and that entails looking at new information. Just picking the same already chosen landmark seems like it would be self-defeating for either player.
Let's take an extreme case. Suppose that there are just four locations that haven't been picked, and the three key items have yet to be found. If you go first, you have to uncover all three key items without a miss. Any mistake, and I will now know where the three key items are, and will win on my turn. You will only uncover the three key items without a miss (3/4)*(2/3)*(1/2)=1/4 of the time, so, if you are the first to move from the impasse, I will win 75% of the time.
On the other hand, if you make the legal move of picking one of the 11 locations that we've already seen, you pass the turn to me. If I pick from the unseen locations first, you will now win with 75% probability. So my best move is to do the same thing and force the turn back to you.
Here, I must admit that the mathematical game differs from the game show. If the players were to try such a strategy on the game show, the producers would probably stop tape and have both contestants forfeit winnings. In that case, if both players knew the strategy, then it would become a game of chicken, rather than a stalemate. However, in the mathematical game, there are no such consequences.
(I would also like to point out that 14-year-olds would probably never be able to figure out such a strategy, so that's kind of moot)
Unless there's something that I missed in the original, then I apologize.
You didn't miss anything. It's okay.
Intuition sometimes leads even Math PhD's astray.
