#!/usr/bin/env python """ tournament_triples.py From July 2002 issue of http://cs.nyu.edu/~gottlieb/tr/back-issues/ : A round robin tournament has 13 contestants. Each contestant plays each of the others once, and each wins 6 times and loses 6 times. How many of these triples (A,B,C) are 'cyclic', i.e. A beats B who beats C who beats A? ==================== An analytic solution: * Number the players 1 to 13, and consider player 7. * Name the six who beat him (1..6), and the six he beats (8..13). * Now look at triples which include player 7. There are three types: (a) 15 = 6*5/2 triples of the form (1..6):(1..6):7 None of these are cyclic, since player 7 is beaten twice. (b) 36 = 6*6 triples of the form (1..6):7:(8..13) . Some of these may be cyclic if the (8..13) beats the (1..6). (c) 15 = 6*5/2 triples of the form 7:(8..13):(8..13) Again, none of these are cyclic. * What's needed, then, is to know how many of the 36 games between the (1..6) players and the (8..13) players won by ether group. To answer that, consider all the games played by the players in the (1..6) group. There are three possibilities for the other player: another (1..6) player, player 7, or a (8..13) player. * That number can be found by analyzing the tally of all games played between the (1..6) players. Let a players score be +1 for a win, -1 for a loss. Then every player - and hence any set of players - have a total score of 0. So the group of (1..6) players will have a total score of 0 for all their games. * The games that include a player from the (1..6) group can have one of three types of opponents: (A) (1..6) vs (1..6) The net score of all these 15 games is 0, since the group gains 1 and loses 1. (B) (1..6) vs 7 The net score of these 6 games is 6, since by construction these players beat player 7. (C) (1..6) vs (8..13) The net score for the (1..6) players of these 36 games must be -6, so that (A)+(B)+(C) = 0 + 6 - 6 = 0. That means the score must be (1..6) beats (8..13) : 15 # sum = 36 (8..13) beats (1..6) : 21 # difference = -6 * Therefore of all the (a)-(b)-(c) triples, there are exactly 21 cyclic ones. Now all that we need to do is extend that to all players. * Taking this 21 and multiplying by the 13 players isn't quite right, since that counts the same triple (say 7->1->5->7) multiple times. But all we need to do is figure out what the multiple is, and that's straightforward: there are three other versions of that triple, namely (1,5,7) and (5,7,1) in the 21*13 overcount. Therefore the final result is 21*13/3 = 91. * Doing all of that in the general case gives f(n) = n * ( ((n - 1)/2 )^2 + (n-1)/2)/2 )/3 = n *(n-1)*(n+1)/24 which gives : n f(n) --------- 3 1 5 5 7 14 9 30 11 55 13 91 15 140 The formula is in fact just "n+1 choose 4" = C(n+1, 4). Maybe there's a simple reason for that. ================================================= A brute-force "try to construct one" simulation: The code below implements a verification of this result by trying to explicitly constructing such a tournament. Note that: (1) The constraints may fail if, say, two players who each have (N-1)/2 wins play each other; that's less likely if do all player 1 matches, then all player 2, etc. (2) The program always returns the same number of cyclic triples if it can construct a tourney. That isn't a proof that *all* valid tourneys have this property, but it does get more convincing as the number of attempts gets bigger. Running it from the command line looks like this: $ ./tournament_triples.py --- cyclic triples in a round-robin tournament --- Number of players? (13) 3 Number of tourneys? (1) Shuffle pairs? (no) . - done. All 1 tourneys constructed succesfully. Found 1 cyclic triple with 3 players. $ ./tournament_triples.py --- cyclic triples in a round-robin tournament --- Number of players? (13) Number of tourneys? (1) 100 Shuffle pairs? (no) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . - done. Failed 20 times out of 100. Found 91 cyclic triples with 13 players. $ ./tournament_triples.py --- cyclic triples in a round-robin tournament --- Number of players? (13) Number of tourneys? (1) 100 Shuffle pairs? (no) yes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . - done. Failed 97 times out of 100. Found 91 cyclic triples with 13 players. Jim Mahoney | April 2010 """ import random, sys def coinFlip(): """ Return True or False >>> coinFlip() in [True, False] True """ return 0 == random.randint(0,1) def printTick(): """ Print a single '.', without a newline, and send it to the terminal immediately. """ print ".", sys.stdout.flush() def manyTimes(nPlayers=13, nTimes=1, shufflePairs=False): """Repeatedly construct tourneys. Tell user if (a) constraints aren't satisfied or (b) number of cyclic triples varies. """ cyclicResults = {} nFailed = 0 i = 0 while i < nTimes: i += 1 printTick() try: tourney = Tourney(nPlayers, shuffle=shufflePairs) cyclicResults[tourney.nCyclic] = \ cyclicResults.get(tourney.nCyclic, 0) + 1 except: nFailed += 1 print " - done." if len(cyclicResults) > 1: print "!! Found several different results: %s !!" \ % str(cyclicResults.keys()) if nFailed > 0: print "Failed %i times out of %i." % (nFailed, nTimes) else: print "All %i tourneys constructed succesfully." % nTimes if nFailed == nTimes: tourney = 'nothing' return tourney def interactive(): print "--- cyclic triples in a round-robin tournament ---" try: nPlayers = int(raw_input("Number of players? (13) ")) except: nPlayers = 13 try: nTimes = int(raw_input("Number of tourneys? (1) ")) except: nTimes = 1 shufflePairs = 'yes' == raw_input("Shuffle pairs? (no) ") tourney = manyTimes(nPlayers, nTimes, shufflePairs) print 'Found ' + str(tourney) + '.' class Tourney: """ a tournament satisfying the constraints >>> t3 = Tourney(3) >>> t3.players() [0, 1, 2] >>> t3.wins[0] 1 >>> t3.results[(0,1)] in [True, False] True >>> t3.nCyclic 1 >>> t5 = Tourney(5) >>> t5.nCyclic 5 """ def __init__(self, nPlayers, shuffle=False): """ Initialize tournament, with scores initially zero. """ # Shuffling makes constructing a successful tourney less likely. self.shuffle = shuffle # player id's and list indeces are 0 ... N-1 . if nPlayers % 2 != 1: raise Exception('Number of tourney players must be odd.') self.N = nPlayers self.nCyclic = 0 # number of a->b->c->a cylic triples self.limit = (self.N-1)/2 self.wins = [0]*self.N # total number of wins for each player self.losses = [0]*self.N # total number of losses for each player self.results = {} # (winner,loser)->True; (loser,winner)->False; self.playAllGames() self.analyze() def __str__(self): cycles = 'cyclic triple' if self.nCyclic > 1: cycles += 's' return "%i %s with %i players" % \ (self.nCyclic, cycles, self.N) def players(self): return range(self.N) def pairs(self): players = self.players() pairs = [(i,j) for i in players for j in players if i < j] if self.shuffle: random.shuffle(pairs) return pairs def isOutcomeOK(self, winner, loser): """ If given winner and loser doesn't violate constraints, store results and return True; otherwise return False. """ if self.wins[winner] < self.limit and self.losses[loser] < self.limit: self.wins[winner] += 1 self.losses[loser] += 1 self.results[(winner, loser)] = True self.results[(loser, winner)] = False # print " %i beats %i : YES " % (winner, loser) return True else: # print " %i beats %i : NO" % (winner, loser) return False def playAllGames(self): """ Play all pairwise games. Store results in self.results, self.wins, and self.losses.""" # Method: # Loop over each pair: # Decide who wins by coin flip. # If that doesn't violate constraints, save results and move on. # Otherwise, swap who wins. # If that doesn't violate constraints, save results. # Otherwise, fail with an error. # Hmmm. I haven't seen this ever fail; not sure for (player1, player2) in self.pairs(): if coinFlip(): (player1, player2) = (player2, player1) if not self.isOutcomeOK(player1, player2): if not self.isOutcomeOK(player2, player1): raise Exception('inconsistent tourney') def analyze(self): """ After playing games, count cylic triples and store in self.nCyclic. """ # Just a brute force count over all triples. self.nCyclic = 0 players = self.players() triples = [(i,j,k) for i in players for j in players for k in players if i < j < k] for (a, b, c) in triples: if self.results[(a,b)] == self.results[(b,c)] \ == self.results[(c,a)]: self.nCyclic += 1 if (False): # set to True to test detection of different results if random.randint(1,10) == 3: # sometimes ... self.nCyclic = 7 # give the wrong answer. def _tests(): import doctest from doctest import testmod testmod() if __name__ == '__main__': _tests() interactive()