"Perfect Square" Dance

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



Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.


Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.


Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only



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

I wonder if 18 is unique as the total number of dancers which has a solution.  It should be easy to modify the program to check.


Original:  October 21, 2008

Modified:  February 18, 2016

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.