S2T2

Jim Randell 8:18 am on 21 February 2023 Permalink Reply
Tags: by: Adrian Somerfield ( 13 )   

• 

  Jim Randell 8:19 am on 21 February 2023 Permalink | Reply

  First we note that the digit 9 can use the same symbol as the digit 6, so we only need to consider the symbols 0-8. (Although it turns out that we get the same answer even if the digits 6 and 9 use different symbols).

  We can quickly find a theoretical minimum collection of symbols required to express the squares between 2001 – 3000 by considering the multiset union of each of those squares (considered as a multiset of corresponding symbols). And with two symbols per card we can determine the theoretical minimum number of cards required to accommodate these symbols. (Although this does not tell us that an appropriate set of cards can be constructed).

  We can then start adding in additional squares until we can no longer fit all the required symbols on the required number of cards, and this gives us a theoretical maximum constructible square to answer the puzzle.

  We can then check that this solution is achievable by constructing a collection of cards of the appropriate size that allows all the required squares to be made.

  This Python program runs in 56ms. (Internal runtime is 809µs).

  Run: [ @replit ]

  from enigma import (irange, inf, sq, nsplit, join, multiset, divc, delete, cache, printf)
  
  # symbols used to represent digits (6 and 9 are the same symbol)
  sym = dict(zip(irange(0, 9), "0123456786"))
  
  # words to be spelled out
  word = cache(lambda n: join(sym[d] for d in nsplit(n)))
  
  # find the minimum number of cards required (n symbols per card)
  min_cards = lambda m, n=2: divc(m.size(), n)
  
  # collect the symbols required to make the initial set of numbers
  ns = list(sq(i) for i in irange(45, 54))
  m = multiset()
  for n in ns:
    m.union_update(word(n))
  k = min_cards(m)
  printf("{k} cards = [{a} .. {b}] ({s} symbols)", a=ns[0], b=ns[-1], s=m.size())
  
  # add extra numbers until another card is required
  for i in irange(55, inf):
    n = sq(i)
    w = word(n)
    m_ = m.union(w)
    k_ = min_cards(m_)
    printf("{k_} cards = [{a} .. {b}] ({s} symbols)", a=ns[0], b=n, s=m_.size())
    if k_ > k: break
    ns.append(n)
    m = m_
  
  # now try to construct a set of <k> cards that covers the numbers <ns>
  
  # can we make word <w> with cards <cs>
  def make(w, cs):
    if not w:
      return True
    x = w[0]
    for (i, c) in enumerate(cs):
      if x in c and make(w[1:], delete(cs, [i])):
        return True
    return False
  
  # make a set of <k> cards, the can make words <ws>, symbol counts in <m>
  def cards(k, ws, m, cs=[]):
    # are we done?
    if k == 0:
      if all(make(w, cs) for w in ws):
        yield tuple(sorted(cs))
    elif k > 0 and m:
      # make the next card
      x = m.min()
      for y in m.keys():
        if x < y:
          c = x + y
          if (not cs) or (not c < cs[-1]):
            yield from cards(k - 1, ws, m.difference([x, y]), cs + [c])
  
  # try to make a <k>-set of cards that covers numbers <ns>
  if m.size() % 2 == 1: m.add('?')
  for cs in cards(k, list(word(n) for n in ns), m):
    printf("cards = {cs}", cs=join(cs, sep=" ", enc="()"))
    break
  

  Solution: The last square that he could make was 3721.

  ---

  To make the squares 2025 – 2916 requires a collection of 13 symbols, so we need 7 cards to accommodate these.

  And if we also include the squares up to 3721 then we need a collection of 14 symbols, which still requires 7 cards.

  But to also include the next square (3844) would require 15 symbols (as we need to have two 4’s), and this cannot be accommodated with 7 cards.

  There are many sets of 7 cards that allow the squares 2025 – 3721 to be made, for example:

  (02 07 13 18 26 39 45)

  (And this set works if 6 and 9 are different digits, or if they are the same digit).

  LikeLike