[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

Problem Description

 Sally invited 17 guests to a dance party. She assigned each guest a number from 2 to 18, keeping 1 for herself.  At one point in the evening, Sally noticed the sum of each couple's numbers was a perfect square. Everyone was wearing their numbers on their clothing.  The question is, what was the number of Sally's partner?

Here's a reminder: a perfect square is attained by squaring, or multiplying by itself, an integer. So four is a perfect square of two. Nine is a perfect square of three. Sixteen is a perfect square of four. So these numbers are adding up to either 4, 9, 16, 25, etc.

Background & Techniques

Thus program solves the "Car Talk Puzzler" for October 20, 2008:  http://www.cartalk.com/content/puzzler/.   It can certainly be solved without a computer, but , for programmers, writing the code for solving a puzzle is usually more interesting and less tedious than using  pen and paper to solve the original puzzle.

I wrote about 50 lines of code to solve the puzzle, so we'll call it a beginner's level program although figuring out how to model the puzzle is probably an intermediate level problem.  If you are a programmer and want to challenge yourself, stop reading now, go write the code, and see if you agree.

Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.

Programmer's Notes:

First an observation that I didn't make until I saw the solution - there are only a few possible perfect square values to check.  The smallest sum for two dancers is 3 (1+2) and and the largest is 35 (17+18).  In that range, the only squares are 4, 9, 16, and 25.   I replaced the IsSquare function which tests any integer "squareness"  with a version that just checks these 4 values.

So the only possible partners for Sally are one less than a square, i.e. 3, 8, or 15.  To eliminate two of these, the strategy I used was to prove that those numbers  must be paired with someone else.   I pass through all possible pairs multiple times,  each time checking for pairs that meet the conditions that the sum is a perfect square and there is only one such square that can be formed for  for at least one number of the pair.    For example, on the first pass,   number 17 must be paired with number 8 because i17 is already larger than 4, 9, and 16, so 25 i(17_8) s the only possible square sum.   When such a unique pair is found, those numbers are flagged so we know that they cannot be paired with any other number on future passes.  In the program that is accomplished by filling an array, FinalPairs with it's paired value.   We repeat the loop until all the  numbers have been paired or a pass through all unpaired numbers produces no new pairs.  The final pairings are displayed in a listbox.  A Verbose  checkbox controls whether the results of each pass leading to the final solution are displayed.    

Running/Exploring the Program 

Suggestions for Further Explorations

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2018, Gary Darby    All rights reserved.