S2T2

Jim Randell 9:22 am on 17 June 2021 Permalink Reply
Tags: by: Nick MacKinnon ( 53 )   

• 

  Jim Randell 9:23 am on 17 June 2021 Permalink | Reply

  The winning ticket w is the geometric mean of two of the other tickets, say a and b:

  w = √(a⋅b)
  w² = a⋅b

  So, the range of tickets must include the interval [a, …, b]. And if this interval can be successfully coloured (with a, w, b red) then we have a solution.

  This Python program runs in 530ms.

  Run: [ @replit ]

  from enigma import (irange, divisors_pairs, empty, peek, filter2, mod, subsets, diff, printf)
  
  # check no number in <ns> is the mean of two other numbers in <ns>
  def check(ns):
    for ps in filter2(mod(2), ns):
      if any((x + y) // 2 in ns for (x, y) in subsets(ps, 2)): return False
    return True
  
  # colour tickets in <ts> to give reds <rs> and blues <bs>
  def colour(ts, rs, bs):
    if not ts:
      yield (rs, bs)
    else:
      (t, ts_) = (ts[0], ts[1:])
      # try red
      rs_ = rs.union([t])
      if check(rs_): yield from colour(ts_, rs_, bs)
      # try blue
      bs_ = bs.union([t])
      if check(bs_): yield from colour(ts_, rs, bs_)
  
  # consider possible 2-digit winning tickets
  for w in irange(10, 99):
    # consider possible other ticket whose geometric mean is w
    for (a, b) in divisors_pairs(w, 2):
      if not (a < b): break
  
      # can we colour the tickets?
      rs = {a, w, b}
      if not check(rs): continue
      ts = diff(irange(a, b), rs)
      try:
        (reds, blues) = peek(colour(ts, rs, empty))
      except ValueError:
        continue
  
      printf("red = {reds}, blue = {blues} [w={w}; a={a} b={b}]", reds=sorted(reds), blues=sorted(blues))
  

  Solution: The blue tickets were numbered: 10, 11, 14, 15.

  And the red tickets were: 9, 12, 13, 16.

  i.e. the sequence is: (R9, B10, B11, R12, R13, B14, B15, R16).

  The winning ticket is 12, which is the geometric mean of 9 and 16.

  And we can check that the sequence cannot be extended (with 8 or 17):

  >>> check([8, 9, 12, 13, 16])
  False
  >>> check([8, 10, 11, 14, 15])
  False
  >>> check([9, 12, 13, 16, 17])
  False
  >>> check([10, 11, 14, 15, 17])
  False
  

  ---

  For a faster execution time we can note that if we have a sequence of numbers such that no number is the mean of any other two.

  a[0], a[1], …, a[n]

  Then the sequence:

  a[0] + k, a[1] + k, …, a[n] + k

  also has this property.

  So if we find a pattern of red/blue colourings of consecutive numbers, we can also form another valid pattern by adding a constant to each of the numbers (or by swapping the colours).

  The following program finds all possible patterns (of length 4 or more):

  from enigma import printf
  
  # generate colourings, with at least k elements
  def patterns(s, n, choice=(0, 1)):
    j = len(s)
    if not (j < n): yield s
    for x in choice:
      for (i, y) in enumerate(s):
        if y == x:
          (d, r) = divmod(i + j, 2)
          if r == 0 and s[d] == x: break
      else:
        yield from patterns(s + [x], n, choice)
  
  # output patterns
  for ps in patterns([0], 4):
    printf("{ps}")
  

  And we could modify the original program to check that the sequence of tickets matches one of these patterns, although we can cut the run time of the program down to 51ms by simply rejecting sequences that are longer than the maximum pattern length (which is 8).

  Replacing line 26 with the following does the trick:

  if not (0 < b - a < 8): continue
  

  There are 3 viable patterns of length 8, which we can identify with the following sequences:

  (0, 0, 1, 1, 0, 0, 1, 1)
  (0, 1, 0, 1, 1, 0, 1, 0)
  (0, 1, 1, 0, 0, 1, 1, 0)

  Giving a total of 6 possible red/blue colourings.

  The solution sequence (R9, B10, B11, R12, R13, B14, B15, R16) matches the last of these patterns.

  LikeLike

  • 

    Jim Randell 9:26 am on 17 June 2021 Permalink | Reply

    The following approach is based on an observation by Brian Gladman [link].

    Suppose the winning number (at index w in the sequence), is between the numbers at indices a and b that are the components of the geometric mean.

    Then the sequence is:

    n, …, n + a, …, n + w, …, n + b, …
    (n + a)(n + b) = (n + w)²
    n = (w² − ab) / (a + b − 2w)

    So, given the values of the indices within the sequence a, w, b we can calculate the starting value of the sequence.

    The following Python program generates possible patterns, and then looks for indices that produce a viable value for n. The values of the blue tickets can then be determined.

    It runs in 48ms (but the internal runtime is only 243µs compared to 1.26ms for my previous program (with modification)).

    from enigma import (irange, subsets, div, group, printf)
    
    # generate colourings, with at least k elements
    def patterns(s, n, choice=(0, 1)):
      j = len(s)
      if not (j < n): yield s
      for x in choice:
        for (i, y) in enumerate(s):
          if y == x:
            (d, r) = divmod(i + j, 2)
            if r == 0 and s[d] == x: break
        else:
          yield from patterns(s + [x], n, choice)
    
    # collect patterns by length
    pats = group(patterns([0], 4), by=len)
    m = max(pats.keys())
    
    # consider values for a, w, b
    for (a, w, b) in subsets(irange(0, m - 1), size=3):
      # calculate n
      n = div(w * w - a * b, a + b - 2 * w)
      if n is None or n + w < 10 or n + w > 99: continue
      # look for patterns with length at least b + 1
      for (k, vs) in pats.items():
        if not (k > b): continue
        for ps in vs:
          # look for patterns where a, w, b are red
          red = ps[a]
          if not (red == ps[w] == ps[b]): continue
          # output solution
          blues = sorted(n + j for (j, x) in enumerate(ps) if x != red)
          printf("blues = {blues} [ps={ps} n={n} red={red} w={w}]")
    

    It turns out there is only one possible value for (a, w, b) = (0, 3, 7), which gives n = 9.

    So the sequence is maximal, and of the three candidates only (0, 1, 1, 0, 0, 1, 1, 0) has elements 0, 3, 7 the same. They are all 0, so the 1’s indicate the blue tickets.

    LikeLike