[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? Background & TechniquesThus 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. |