Enigmatic Code

Programming Enigma Puzzles

Enigma 1029: Chancelot

From New Scientist #2185, 8th May 1999

The company Chancelot has been asked to set up a lottery for a foreign country. It will work a bit like Britain’s own lottery with participants choosing some numbers: then the winning numbers will be decided by the company choosing some numbered balls at random.

The government has laid down some strict guidelines:

1. It wants participants to have to choose six numbers from 1, 2, …, N, where the top number N has not yet been decided. Then six of the numbered balls will be chosen and the winner’s choices must match all six.

2. It believes that the public is always suspicious when the winning selection includes two consecutive numbers. Therefore of all the combinations of six numbers from the N, it wants more than half of them not to include two consecutive numbers.

3. To give the public a fair chance of winning, it wants N to be the lowest possible satisfying the above conditions.

How many balls will there be in Chancelot’s lottery?

[enigma1029]

One response to “Enigma 1029: Chancelot

  1. Jim Randell 4 January 2019 at 8:22 am

    The number of different ways of choosing 6 numbers from N is: C(N, 6).

    One way to count the number of non-consecutive choices is to think of the numbers chosen in order:

    (a, b, c, d, e, f)

    and no two of them are consecutive, so we can move f one closer to e, and then move e and f one closer to d, and so on, until we end up with:

    (a, b – 1, c – 2, d – 3, e – 4, f – 5)

    This maps any non-consecutive choice of 6 numbers from N onto a normal choice of 6 numbers from (N – 5), and vice versa.

    So the number of non-consecutive choices of 6 numbers from N is: C(N – 5, 6).

    We want the non-consecutive choices to be more than half of the total choices:

    C(N – 5, 6) / C(N, 6) > 1 / 2

    This Python program looks for the lowest number of balls that will achieve this. It runs in 84ms.

    Run: [ @repl.it ]

    from itertools import count
    from enigma import C, printf
    
    for N in count(11):
      c = C(N, 6)
      n = C(N - 5, 6)
      printf("[N = {N}, {c} / {n} = {f:.3f}]", f=float(n) / float(c))
      if 2 * n > c: break
    
    printf("{N} balls")
    

    Solution: There will be 49 balls in the lottery.

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: