|Valentine's Day 2008 Mini-Challenge !|
Message #1 Posted by Valentin Albillo on 14 Feb 2008, 7:45 p.m.
It's been almost a year since I posted my latest S&SMC (#19), but since today it's my name's day, in
order to commemorate the event somewhat and also to mark time before the release of my new "S&SMC#20 Spring's
Special" (to be posted next April 1st), you may want to try this short Mini-Challenge for any HP calc
model of your choice, new or vintage (other pocket-sized brands also welcome, as well as faithful
emulators/simulators. PC or Mac programs are expressly disallowed. Let's see:
Valentine 2008's Mini-Challenge
Imagine two people playing the following "game": one of them selects five real numbers of his choice (say
x1, x2, ..., x5), and computes the sums for all different pairings of those numbers (x1+x2, x1+x3, ..., x4+x5).
He then tells the other person these sums (in whichever arbitrary order he chooses), and the other person must then
use those sums to try and compute the original five numbers.
Your task is thus:
"To write a program which accepts as input the sums of each pair of numbers, given in
arbitrary order, and proceeds to compute and output the five
real numbers which originated them, sorted in ascending order ."
For instance, suppose the five original numbers are:
1, 3, -4, 2.1, 3.9
and thus the corresponding sums for each pair are:
4, -3, 3.1, 4.9, -1, 5.1, 6.9, -1.9, -0.1, 6
the program must then accept these sums in whatever order (and must work for any ordering
of the sums) and proceed to compute and output the five numbers like this (example
particularized for the HP-71B):
Once you write the program, you must use it to find the solutions for these
S(1)? 5.1,6.9,-1.9,4,-3,6,3.1,4.9,-1,-0.1 (arbitrary order) [ENDLINE]
-4, 1, 2.1, 3, 3.9 (sorted original numbers)
1) 3734, 3768, 284, 3950, 466, 4000, 516, 500, 3966, 3784
3) 1, -5, 7, -17, -2, 10, -14, 4, -20, -8
4) -22, -4, 118, 4, 126, 144, -31, -23, -5, 117
The solution, if it exists, is unique. Of course, not every set of arbitrary "sums"
does have a solution. Your program may assume that the sums have actually been
computed from five actual real numbers so there is indeed a unique solution.
The behavior for inadequate initial sums which result in no solution may be left undefined as per the challenge specifications they are unacceptable input.
- You must optimize both for speed and size, in that order. Next week I'll post my original 5-line solution
for the HP-71B which finds the numbers in negligible time and is trivial to adapt to most any HP model. If you don't have the real HP model
of your liking, you may want to consider using any of the excellent freeware emulators/simulators
out there such as Emu71, Emu42S, Nonpareil, etc. Just google for the corresponding name.
If you succeed in solving the challenge for five numbers, you might want to try
the general case of N numbers and discuss in particular which values of N do indeed have
an unique solution (when the problem is solvable at all) so that the N numbers can
indeed be retrieved from their sums, and which values of N result in multiple solutions,
in which case it'll be impossible to retrieve the original numbers.
I won't post any solution for this general case but I'll discuss which N result in unique solutions and which don't.
Turning things up a notch ...
Relying on my experience with these Mini-challenges and keen forum visitors, I knew in advance some among you would eat the first part of this mini-challenge for breakfast, so let's turn things up a notch ...
"Write a program which, from the set of integers 1,2,...,9, selects and uses four of them to fill in a 3x3 matrix so that its determinant is 1 and replacing each element by its square still results in the determinant evaluating to 1."
For instance, your four selected numbers could be 1,2,3,4, and
you would perhaps consider filling up the 3x3 matrix with them like this:
1 1 1
1 3 2
3 4 4
where its determinant actually evaluates to 1, as specified. However, squaring each element gives the matrix:
1 1 1
1 9 4
9 16 16
which has determinant = 35 instead of 1, so regrettably this is not a solution.
Apart from the usual transformations that leave the determinant invariant (swapping of certain rows and columns, etc), the solution is unique, and you must optimize your program primarily for speed for this particular notch.
The final notch
After adding the previous notch I stated:
"If you manage to solve this with relative ease, perhaps I'll feel "forced" to turn things up still another notch ! Have you got what it takes ? ;-)"
and it seems that some of you do indeed have what it takes, namely an state-of-the art HP model and a version of the C language to run natively on it. This being so, here's the promised "final notch" for your consideration:
"Write a program to find four distinct integers such that the sum of any pair is a perfect square"
For example, the set formed by the three values 6, 58, and 138 is such that their sums in pairs are all perfect squares, namely 6 + 58 = 64 = 82, 6 + 138 = 144 = 122, and 58 + 138 = 196 = 142. Your program must find at least a set of four such numbers and I will of course post my original solution to this notch as well.
There will be no further expansions to this mini-challenge, which will hopefully serve as proper training for the incoming "S&SMC#20: Spring 2008 Special" due next April 1st and which will really, really test your programming, math, and resourcefulness to the most, and that's a promise ! :-)
So much for exposition. Now for your results, keep them coming ! :-)
Best regards from V.
Edited to turn things up a notch ! :-)
Edited to add a final notch ! :-)
Edited: 18 Feb 2008, 10:48 a.m. after one or more responses were posted