Enigmatic Code

Programming Enigma Puzzles

Enigma 1383: Unique line-up

From New Scientist #2543, 18th March 2006

I have a set of cards numbered consecutively from 1 up to and including my nephew’s age. I gave him the cards and asked him to arrange them in a row so that the sum of any adjacent pair was a perfect square. He managed it and reported that there were actually only two ways of doing it, namely the line-up which he had displayed and the complete reverse of that order.

I asked him if the same would have been true had he been one year younger and I had correspondingly given him one card fewer. He said that it would, and he produced the second line-up by simply removing the left hand card from his line-up. I asked him if the same would have been true if he had been two years younger and I had originally given him two fewer cards. He said that it would, and he produced the line-up by simply removing the right hand card from his line-up.

How old is my nephew, and what was the number on the middle card in the original line-up?

[enigma1383]

Advertisements

2 responses to “Enigma 1383: Unique line-up

  1. Jim Randell 14 October 2013 at 10:03 am

    This Python3 program considers increasing n until it finds a solution. It runs in 60ms.

    from itertools import count
    from enigma import is_square, irange, first, cached, printf
    
    is_square = cached(is_square)
    
    # cs - cards remaining
    # ss - sequence of squares
    def squares(cs, ss):
      # are we done?
      if not cs:
        printf("[{n} {ss}]", n=len(ss))
        yield ss
      else:
        # choose the next card to add
        for c in cs:
          # does it make a square
          if ss and not is_square(ss[-1] + c): continue
          yield from squares(cs.difference([c]), ss + [c])
    
    # generate solutions
    def generate():
      r = dict()
      for n in count(1):
        # find (up to 3) possible sequences for n cards
        ss = first(squares(set(irange(1, n)), []), count=3)
        # are there only two solutions where one is the reverse of the other?
        if len(ss) == 2 and ss[0] == ss[1][::-1]:
          # record this solution
          r[n] = ss
          # are n-1 and n-2 already recorded
          if n - 1 in r and n - 2 in r:
            # find matching solutions
            for s in ss:
              if s[1:] in r[n - 1] and s[1:-1] in r[n - 2]:
                yield (n, s)
    
    # find the first solution
    for (n, s) in generate():
      printf("n={n} m={m} s={s}", m=s[n // 2])
      break
    

    Solution: Your nephew is 17. The number on the middle card is 12.

  2. arthurvause 19 October 2013 at 11:48 am

    OEIS sequence A090460, the number of essentially different permutations of the numbers 1 to n such that the sum of adjacent numbers is a square, reveals the age of the puzzler’s nephew (but not the middle card)

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: