# 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]

### 2 responses to “Enigma 1108: Every vote counts”

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

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

for a in irange(1, 349):
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, flag=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.

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!)

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)