Enigmatic Code

Programming Enigma Puzzles

Enigma 1485: Fund raiser

From New Scientist #2647, 15th March 2008

Our local church runs a lottery which is a simpler version of the UK’s National Lottery. To enter, you have to pay 10 pence and on a card tick a certain number of boxes from those labelled 1,2,3, … up to some number.

I am quite a gambler so I enter lots of times each week: In fact, I enter every possible combination in which no two of the chosen numbers are consecutive.

The lottery has been such a success that the church wants to increase the number of possible combinations without having to reprint its lottery cards. So it has simply changed the rules so that from next week onwards entrants will have to tick one more number than they did previously. If I continue my system of entering every possible combination in which no two numbers are consecutive, then my weekly outlay will go up by 50%.

How many numbers are on the card?

From next week, how many boxes have to be ticked?

[enigma1485]

Advertisements

One response to “Enigma 1485: Fund raiser

  1. Jim Randell 26 November 2012 at 9:38 am

    The following Python program runs in 39ms.

    from itertools import count
    from enigma import irange, cached, printf
    
    # how many choices of m non-consecutive numbers from n consecutive numbers
    @cached
    def choose(m, n):
      if n < 1: return 0
      if m == 1: return n
      return sum(choose(m - 1, i) for i in irange(1, n - 2))
    
    def solve():
      # n = number of boxes on the card
      for n in count(1):
        # previous non-consecutive choice count
        cp = None
        # m = number of boxes to tick
        for m in irange(1, (n + 1) // 2):
          c = choose(m, n)
          printf("[{m} of {n} => {c}]")
          # look for <choices> = 1.5 * <previous choices>
          if cp is not None and 2 * c == 3 * cp:
            printf("n={n} m={m1} c={cp} => n={n} m={m} c={c}", m1=m - 1)
            return
          cp = c
    
    solve()
    

    Solution: There are 14 numbers on the card. From next week 4 boxes should be selected.

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: