The Path of Perfect Squares, Messily Walked

“If you can’t get there one way, go another way.”

The email feed Beyond Euclid offers problems. One of them caught my attention, then my obsession. And it reminded me of something about HOW to solve questions.

The Problem

“On 16 cards, whole numbers from 1 to 16 are written.

Can these cards be sorted so that when any two neighboring cards are taken, the sum of the numbers on them is a perfect square?”

— From Beyond Euclid # 83

Thinking about it…

We are dealing with integers.

What are the possible sums?

• The smallest sum would be the two smallest integers given, so 1 plus 2 = 3
• The largest sum would the sum of the two largest, 15 and 16. That sum is 31. So possible sums range from 3 to 31.
• Perfect square means “An integer that is the square of an integer,” thank you American Heritage dictionary. What are the perfect squares in that range of integers?
• 2² = 4
• 3² = 9
• 4² = 16
• 5² = 25
• Excluded are 6² = 36 (too large) and 1² = 1 (too small).
• So we are looking for pairs whose sum is in the bunch [4,9,16,25].

We want an ordering. It is a sequence in which

• All the integers must be used
• None of the integers can be paired with itself
• None of them can be used twice (that would make a loop)
• AND in that ordering, the sum of each pair of adjacent-in-the-ordering integers must be in our collection of perfect squares [4,9,16,25].

Whew.

A job for Python?

I play with Python a lot. Very much an amateur, I was able to build a webscraper to figure the fair market value of donated books for tax purposes. An amateur with a little experience.

The first part of the job was promising. I built some procedures that are in a comment to this piece.

They gave me a dictionary. For each entry’s key (the number to the left of the colon), I get of list of numbers that can be paired with it. Here it is:

{1: [3, 8, 15], 2: [7, 14], 3: [1, 6, 13], 4: [5, 12], 5: [4, 11], 6: [3, 10], 7: [2, 9], 8: [1], 9: [7, 16], 10: [6, 15], 11: [5, 14], 12: [4, 13], 13: [3, 12], 14: [2, 11], 15: [1, 10], 16: [9]}

For example entry 1:[3,8,15] means that following 1 with 3 would give 4, with 8 would give 9, and with 15 would give 16.

Those are possible pairs. They are reversible: if …1,3… works, so will …3,1… because 1 +3 = 3 + 1.

And then I ran aground. I just could not figure out code to make the sequence. I know — other Pythonistas could. But I thrashed about with loops and recursions, in vain.

Perhaps Another Way

I went back to pencil and paper. They are good companions to puzzlement. I made the same dictionary Python did, by hand.

This messy version, where the connections are shown graphically, showed me some new things.

For instance these graphs

have the same information as {…4:[5,12]…12:[4,13]}. But the graphs are more suggestive. What if we took each of those arrows as representing a piece of the path we are trying to build?

Since 4 → 5 implies that 5 → 4 satisfies our condition, we can rewrite our two diagrams as

And then glue them together at 4 → 12 to make a partial path:

And look — each step meets our condition:

• 5 +4 = 9, a square
• 4+12 = 16, a square
• 12+13 = 25, a square

Looking at diagrams has suggested a way of building paths!

But where do we begin or end?

Most of the entries in the dictionary go to two other numbers — like 4 going to 5 and to 12. Two entries, though, go to only a single other number. Might those be our end-points?

I took 16 as a starting point and began connecting out from it using the dictionary:

This approach seemed to work, so I continued it. The number 14 connects to 2, already used, and to 11. So eleven goes next. In very short order I had a string of numbers,

The sequence is (16,9,7,2,14,11,5,4,12,13,3,6,10,15,1,8).

If you take it as a sorting of cards the series seems to meet the problem’s specification: “Can these cards be sorted so that when any two neighboring cards are taken, the sum of the numbers on them is a perfect square?”

• Every integer from 1 through 16 is used.
• No integer is used twice
• Each pair of neighboring integers add up to a perfect square.

It is not the only sequence that does — the reverse of this (8,1…9,16) also meets the standard.

Notice please that there are two numbers that connect to not one nor two but three other numbers. 1 goes to 3 and 8 and 15. 3 goes to 1 and 6 and 13. These are further and perhaps fertile messy revelations I have not followed up on here.

The Moral of it All

For me the moral is simple. A starting version of it might be “If one approach to a problem does not work, try another.””

It was more than “another approach” though.

• Python is a lovely language, but it is all symbolic. It turned out the solution I found depended on leaving not only Python but also the world of symbolic solutions.
• It was not a trip to another computer language, nor to a spoken language. It was a trip to a different perceptual system. That new representation was visual and (forgive me) right-brained.
• The transition was messy.
• The mess was revelatory, and necessary.
• The mess was not the final desired state.

Perhaps the moral I would take home is:

STYMIED? MESSILY TRY ANOTHER PERCEPTUAL SYSTEM.