Enigmatic Code

Programming Enigma Puzzles

Enigma 1108: Every vote counts

From New Scientist #2264, 11th November 2000 [link]

George was nominated for president of the Golf Club. There was only one other candidate, and the president was elected by a simple ballot of the 350 members, not all of whom in fact voted.

The ballot papers were taken from the ballot box one at a time and placed in two piles — one for each candidate — with tellers keeping a count on each pile.

George won (what did you expect?), and furthermore his vote was ahead of his opponent’s throughout the counting procedure.

“That must be a one-in-a-million chance,” said the demoralised loser.

“No,” said George. “Now that we know the number of votes we each received, we can deduce that the chance of my leading throughout the count was exactly one in a hundred.”

How many members did not vote?

[enigma1108]

Advertisements

2 responses to “Enigma 1108: Every vote counts

  1. Jim Randell 3 July 2017 at 8:43 am

    See also: Enigma 1465.

    We can consider the vote counting as path going from (0, 0) to (a, b) (where a and b are the number of votes for each candidate).

    This Python program constructively counts the possible paths. It runs in 389ms.

    from enigma import irange, cached, printf
    
    # count paths from (0, 0) to (x, y)
    # if flag is set only count paths where x > y
    @cached
    def paths(x, y, flag=0):
      if ((x == 1 and y == 0) if flag else (x == y == 0)): return 1
      n = 0
      if x > (y + 1 if flag else 0): n += paths(x - 1, y, flag)
      if y > 0: n += paths(x, y - 1, flag)
      return n
    
    # votes for george
    for a in irange(1, 349):
      # votes for the opponent
      for b in irange(0, min(a - 1, 350 - a)):
        # count the total number of paths
        t = paths(a, b)
        # count the number of paths where a > b
        n = paths(a, b, 1)
        # check the ratio is 100:1
        if n * 100 == t:
          s = a + b
          printf("votes cast = {s}, george = {a}, opponent = {b}")
    

    Solution: 150 members did not vote in the election.

    The only possible scenario is that George received 101 votes, and his opponent received 99 votes. So 200 of 350 members voted.

    Analytically, if George got a votes and his opponent got b votes then the number of different ways that the votes can be counted is:

    C(a + b, a) = C(a + b, b) = (a + b)! / (a! b!)

    And the number of ways they can be counted such that George is always ahead is:

    C(a + b – 1, b) – C(a + b – 1, b – 1) = (a – b) (a + b – 1)! / (a! b!)

    (See: [ https://en.wikipedia.org/wiki/Catalan%27s_triangle ]).

    We are interested in when the ratio of these two terms is 100:1. i.e. when:

    (a + b) / (a – b) = 100
    a / b = 101 / 99

    From which we see the solution is a = 101, b = 99 as a + b < 350.

    In this case the numbers involved are quite large:

    C(200, 99) = 89651994709013149668717007007410063242083752153874590932000
    C(199, 99) – C(199, 98) = 896519947090131496687170070074100632420837521538745909320

  2. Brian Gladman 8 July 2017 at 1:28 pm

    This solution is essentially the same as that given above by Jim. I could have combined the two path functions (as Jim does) but I found that it ran faster when they were kept separate. I also think it is a bit easier to understand these functions when they are kept separate.

    from functools import lru_cache
    
    # find all shortest paths in a rectangular grid between
    # (0, 0) and (x, y) [this is equal to (x + y)!/(x!.y!)]
    @lru_cache(None)
    def paths_all(x, y):
      # on either axis there is only one path to the endpoint
      if x == 0 or y == 0:
        return 1
      # otherwise the number of paths to the point is the sum
      # of those to the point on its left and the point below
      return paths_all(x - 1, y) + paths_all(x, y - 1)
    
    # find all shortest paths in a rectangular grid between
    # (0, 0) and (x, y) on which x is always greater than y
    # [this is equal to (x - y).(x + y - 1)!/(x!.y!)]
    @lru_cache(None)
    def paths_xgy(x, y):
      # don't count paths unless x > y
      if x <= y:
        return 0
      # on the x axis there is only one path to the endpoint
      if y == 0:
        return 1
      # otherwise the number of paths to the point is the sum
      # of those to the point on its left and the point below  
      return paths_xgy(x - 1, y) + paths_xgy(x, y - 1)
    
    # possible votes for George
    for g in range(1, 351):
      # possible votes for his opponent
      for h in range(min(g, 351 - g)):
        # look for situations in which the number of all count sequences
        # is 100 times the number for which  George always has the lead
        if paths_all(g, h) == 100 * paths_xgy(g, h):
          print(f'{350 - g - h} did not vote ({g} for George, {h} for Other).')
    

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: