Enigmatic Code

Programming Enigma Puzzles

Enigma 1311: Minimal clockspan

From New Scientist #2469, 16th October 2004

I have a clock with a sweep second hand, and I watch how the three hands – hour (H), minute (M) and second (S) – come together and spread apart.  Let us call their span, at any given moment, the smallest fraction of the clock face to contain all three hands.

I ignore the hands’ thickness, so at 12.00.00 the span is zero. At 12.00.01 it is just under 1/60, because H has just past 0 (the vertical); S is in position 1/60 (that is 1/60th of the clock face from 0); and M is between them.  After that the span gets bigger, but by 12.01.00 it is down again to exactly 1/60, with S at 0, M at 1/60 and, this time, H in between.

(a) Between 12.00.01 and 18.00.00, at what time is the span a minimum?   (Give your answer to the nearest minute)

(b) What exact fraction is this minimum span?

[enigma1311]

Advertisements

2 responses to “Enigma 1311: Minimal clockspan

  1. Jim Randell 7 July 2014 at 8:49 am

    Assuming all hands move smoothly and continuously, I used the observation that for any given minute the hour and minute hands will only move slightly, whereas the second hand can be positioned anywhere, and in particular at any point between the hour and minute hands. The minute hand will move faster than the hour hand, so if the minute hand is past the hour hand then the hands will be moving apart, so the minimal span will be when the second hand is coincident with the hour hand. Conversely if the hour hand is past the minute hand then the hands will be moving together, so the minimal span will also be when the second hand is coincident with the hour hand. And finally if the minute hand overtakes the hour hand then the minimal span will be zero when all three hands are coincident, so again we can just consider when the second hand is coincident with the hour hand (although, in fact, this situation doesn’t happen).

    So for each minute we only need to consider the distance between the minute and hour hands at the time that the second hand is coincident with the hour hand. (We could further reduce the number of cases considered by looking at times when the hour and minute hands are “close”, i.e. close to the time that they are coincident).

    Also for simplicity I consider the time period between 00:00 and 06:00, the hand movements will be identical to the period in the question.

    This Python program runs in 80ms.

    from fractions import Fraction as F
    from enigma import irange, Accumulator, printf
    
    # determine the span between two (fractional) positions
    def span(a, b):
      s = abs(a - b)
      return (1 - s if 2 * s > 1 else s)
    
    # find the minimum span
    r = Accumulator(fn=min)
    
    # consider each minute
    for t in irange(0, 360):
      (h, m) = divmod(t, 60)
    
      # hour and minute hand starting positions (as fractions)
      H = F(t, 720)
      M = F(m, 60)
    
      # the hour hand moves from t/720 to (t+1)/720
      # so the second and hour hands are coincident when:
      # s/60 = t/720 + s/(720*60)
      # s = 60t/719
      s = F(60, 719) * t
      if h == m == s == 0: continue # 00:00:00 is excluded
      r.accumulate_data(span(H + F(s, 43200), M + F(s, 3600)), (h, m, s))
    
    (h, m, s) = r.data
    printf("minimum span = {r.value} at {h:02d}:{m:02d}:{s:06.3f}", h=h + 12, s=float(s))
    

    Solution: (a) The minimum span occurs at 15:16 (to the nearest minute); (b) The minimum span is 1/719 of the clock face.

    To the nearest millisecond the time of the minimum span is 3:16:16.356. The fractional part of the seconds is 256/719. The span is slightly more than 0.5°.

    The same span will also occur at 8:43:43.644 (the fractional part of the seconds is 463/719), but this is outside the specified time period.

  2. Brian Gladman 10 July 2014 at 10:05 am

    This version is based on Jim’s observation that the minimum span will occur when the hour and second hands coincide.

    # This is based on Jim's observation that the minimum span occurs
    # when the hour and second hands coincide. At time t (in seconds), 
    # the positions of the hour, minute and second hands as fractions
    # of the clock face are the fractional parts of:
    # 
    #   hour = t / (12 * 60 * 60) ; min = t / (60 * 60) ; sec = t / 60
    #
    # the hour and second hand are coincident when:
    # 
    #   t / 60 - t / (12 * 60 * 60) = an integer (j)
    #
    # which gives times t given by:
    #
    #   t = 12.60.60.j / 719
    #
    # The span between this position and the position of the minute
    # hand is then the fractional part of:
    #
    #   span = t / (60 * 60) - t / (12 * 60 * 60) = 11.j / 719
    #
    # We are interested in how small this can be, i.e. is there a j
    # value such that this span is very close to an integer (k):
    #
    #   span = 11.j / 719 = k + g / 719
    #
    # such that g is a small positive or negative integer. This gives:
    #
    #   11.j - 719.k = g
    # 
    # This equation is Bezout's identity, for which the values of j, k
    # and g that satisfy it can be found using the extended greatest
    # common divisor algorithm as follows.
    
    def xgcd(a, b):
      u, u1 = 1, 0
      v, v1 = 0, 1
      while b:
        q = a // b
        u, u1 = u1, u - q * u1
        v, v1 = v1, v - q * v1
        a, b = b, a - q * b
      return u, v, a
    
    # find j, k and g values for the minimum span
    j, k, g = xgcd(11, -719)
    # compute the time (in seconds) at which this span occurs
    t = 12 * 60 * 60 * j / 719
    # convert to hours, minutes and seconds
    m, s = divmod(t, 60)
    h, m = divmod(int(m), 60)
    print('The minimum span is {}/719 at {}:{}:{:.3f}'.format(g, h + 12, m, s))
    

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: