Enigmatic Code

Programming Enigma Puzzles

Enigma 1340: Stairs and sums

From New Scientist #2499, 14th May 2005

Andy has a new game which he plays on his stairs. These are numbered 0 (ground) to 9 (landing). He places his teddy on stair 9 and writes 9 on his score card. He pushes teddy over the edge, notes which stair he ends up on and writes that number on his card. He pushes teddy again over the edge of the stair he is on and again writes down the number of the stair he ends up on. He repeats this until teddy reaches the ground, when he stops.

Andy’s score for a game is the sum of the numbers on his card. Andy played his game many times and kept all the score cards. When he looked at all the cards he found an amazing thing. If he looked at which of the stairs (8, 7, …, 1, 0) teddy had ended up on when pushed off stair 9, he found teddy ended up on each stair the same number of times. Further, if Andy looked at all the cards with any particular initial sequence, say, 9, 7, 6 he found that all the remaining stairs, here, 5, 4, 3, 2, 1, 0 occurred equally often as the stair upon which teddy ended up when pushed off the last stair of the initial sequence, here, 6.

What was the average of all Andy’s scores?

[enigma1340]

Advertisements

2 responses to “Enigma 1340: Stairs and sums

  1. Jim Randell 13 March 2014 at 7:53 am

    A bit of analysis gives a recursive function that can be used to determine the average score from a given step. In this program I use the cached() function decorator from the enigma.py library to avoid recalculation. It runs in 55ms.

    from fractions import Fraction as F
    from enigma import cached, irange, printf
    
    # average score starting at step s
    @cached
    def avg(s):
      # are we at the bottom?
      if s == 0:
        return 0
      else:
        # there are s equally likely cases:
        #   s + avg(s-1)
        #   s + avg(s-2)
        #   ...
        #   s + avg(0)
        # the average of which is:
        #   s + (avg(0) + ... + avg(s-1)) / s
        return s + F(sum(avg(i) for i in irange(0, s - 1)), s)
    
    for s in irange(0, 9):
      r = avg(s)
      printf("avg({s}) = {f:.3f} ({r})", f=float(r))
    

    Solution: The average of Andy’s scores is 38231/2520, approximately 15.171.

    • Jim Randell 13 March 2014 at 7:59 am

      Here’s a second program I wrote that simulates 100 million random trials (poor Teddy!), and gets an answer of 15.171 in 19.6s (using PyPy), so it seems like the analysis is OK.

      from random import randint
      from enigma import irange, printf
      
      # number of trials
      N = 100000000
      
      def push(s):
        return (0 if s == 0 else s + push(randint(0, s - 1)))
      
      t = 0
      for i in irange(1, N):
        t += push(9)
      
      r = float(t) / N
      printf("avg = {r:.3f}")
      

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: