Enigmatic Code

Programming Enigma Puzzles

Enigma 1398: Not the World Cup

From New Scientist #2558, 1st July 2006

Not being a football fan, I have been following a different international competition. The teams entering are divided into groups of equal sizes and then, within its own group, each team plays each other team once. Then just the two top teams from each group qualify and proceed to the next round, the rest being eliminated. The qualifying teams then have a knock-out competition (with some “byes” through the first round if necessary) eventually progressing to the semi-finals and then the final. Also, the two losing semi-finalists play to decide the third and fourth places.

Having counted the number of teams entering this year, the groups have been decided and the competition is about to start. In the end the average number of games played by each team will be a whole number and no team can possibly play precisely six games.

How many teams entered the competition?

[enigma1398]

Advertisements

One response to “Enigma 1398: Not the World Cup

  1. Jim Randell 25 August 2013 at 9:12 am

    This Python program considers possible numbers of teams up to 300 (or you can specify a limit on the command line). It runs in 36ms.

    from itertools import count
    from enigma import irange, divisors, printf
    
    # consider up to N teams
    import sys
    N = (300 if len(sys.argv) < 2 else int(sys.argv[1]))
    
    # suppose the total number of teams is t
    for t in irange(3, N):
      # find possible groups (groups must have at least 3 teams)
      for f in divisors(t):
        if f < 3: continue
        g = t // f
    
        # in the qualifying round:
        # 2g teams qualify, having played f-1 games
        # t - 2g teams are eliminated, having played f-1 games
        games = t * (f - 1)
        # all eliminated teams play f-1 games, so that can't be 6
        if f - 1 == 6: continue
    
        # in the knockout round:
        # q = 2g teams qualify, there are q-1 games to decide the winner
        # (each with two teams) and 1 game to decide third place (with 2 teams)
        q = 2 * g
        games += 2 * q
        # average number of games per team is a whole number
        (avg, r) = divmod(games, t)
        if r > 0: continue
    
        # and possible games for each team is (1,..., n) for 2^n <= q
        ps = list()
        for n in count(1):
          if 2 ** n > q: break
          ps.append(n + f - 1)
        # eventually we get to the semi-finals, so there must be at least 3 rounds
        if len(ps) < 3: continue
        # but, the third place decider removes the second largest number of games
        ps.pop(-2)
        # and if there are byes then some teams will play one fewer game
        if 2 ** (n - 1) < q:
          ps.extend(list(p - 1 for p in ps[1:]))
        # but no team can play 6 games
        if 6 in ps: continue
    
        printf("{t} teams, {g} groups of {f}, qualifying teams = {q}, total games = {games}, average = {avg}, possibles = {ps}")
    

    Solution: 32 teams entered the competition.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: