Valentine's Day 2008 Mini-Challenge ! - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: Valentine's Day 2008 Mini-Challenge ! (/thread-132888.html) |
Valentine's Day 2008 Mini-Challenge ! - Valentin Albillo - 02-14-2008
Hi all,
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 Your task is thus:
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.9and thus the corresponding sums for each pair are: 4, -3, 3.1, 4.9, -1, 5.1, 6.9, -1.9, -0.1, 6the 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):
>RUNOnce you write the program, you must use it to find the solutions for these sample sums:
Note:
If you succeed in solving the challenge for five numbers, you might want to try
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 ...
For instance, your four selected numbers could be 1,2,3,4, and
1 1 1 where its determinant actually evaluates to 1, as specified. However, squaring each element gives the matrix:
1 1 1 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 notchAfter adding the previous notch I stated:
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:
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
Re: Valentine's Day 2008 Mini-Challenge ! - dbatiz - 02-14-2008 Happy Valentine’s Day! Thank you for devising yet another interesting challenge. This one had me guessing until I saw you mention your solution was a 5 liner. I thought this must be more of a math problem then a logic problem. I have solved your examples, but before I post my technique I wanted to ask a question: Are all solutions welcome? I solved it using my 50g, but I didn’t need to write any code. I didn’t want to be a spoiler. I’ve been chewing on the general case of N numbers. My gut tells me that if the number of pairings exceeds the number of original values, there is enough data to find a unique solution. I’m guessing that for N>2 there will be a unique solution, if one exists. Thanks again, Very respectfully, David PS Edited to add the last paragraph about the general case of N PPS I jumped the gun. There's much more to this challenge than I originally thought. I thought I had accounted for the random ordering of the sums, but my technique didn't work. This may take a while.... Again, thank you Valentine for an interesting challenge!
Edited: 14 Feb 2008, 10:14 p.m.
Re: Valentine's Day 2008 Mini-Challenge ! - Thomas Klemm - 02-14-2008 Hi Valentin
Here's my program for an HP-48GX: \<< SORT \-> L And here are the solutions to your examples:
Thanks for the nice mini-challenge and all the best for your day.
Kind regards Re: Valentine's Day 2008 Mini-Challenge ! - Paul Dale - 02-14-2008 Pipped for the 48/49 solution. Mine solution (neither smallest nor fastest) is:
<< 10 ->LIST SORT -> A Assuming I've not made any typos. Input is the 10 sums on the stack, output is an array containing the 5 unknowns in ascending order. Execution time is essentially instant on my 49g+. One possible improvement would be to invert the matrix ahead of time and include that inline instead of calculating the inverse every time.
- Pauli
Re: Valentine's Day 2008 Mini-Challenge ! - Thomas Klemm - 02-15-2008 A version without local variable: \<< SORT DUPSeems to be a little slower though? I'm not sure about the influence of the determinant of the matrix. It might be better if it is 1. However Egan will probably post a 50g/HPGCC3 version which is way faster and Raymond might beat us all with a native assembler program. Re: Valentine's Day 2008 Mini-Challenge ! - Thomas Klemm - 02-15-2008 Here's the listing for an HP-11C: 001 LBL A 021 STO 2 041 GTO 3 061 4 081 -
Example 1: Display Command
For those too lazy to type that program into nonpareil emulator
H4sIAAAAAAAAA5WXTU/jMBCG7/srsr5D7XyQRmrLATistLusBFqJE3KccYnIR0kDC/9+J2lrx07apEV Edited: 15 Feb 2008, 5:07 p.m.
Re: Valentine's Day 2008 Mini-Challenge ! - Steve Perkins - 02-15-2008 This is, as usual an interesting problem. I've been trying to get a feel for the problem using smaller amounts of numbers and sums. So far I've observed:
2 numbers 1 sum: infinite solutionsI think these are correct so far. More work to do if I have time. Re: Valentine's Day 2008 Mini-Challenge ! - Bram - 02-16-2008 Hi Valentin, I found the time to do some thinking and programming.
For the first part of your again inspiring challenge I was considering the following steps.
I’ve written a program for my HP-41CV in which the ten given sums must be in the regs 01 upto 10. It computes sum5 first. It then generates the 45 new sums and puts them in regs 40 upto 84 and finally hunts for the triplets in this array. It displays one by one the 5 original numbers. It does so in a reasonable time. (listing of program will come later)
Re: Valentine's Day 2008 Mini-Challenge ! - Rodger Rosenbaum - 02-16-2008 Can you solve the case of 6 numbers whose pairwise sums are: 4,12,4,5,7,8,2,6,10,5,9,13,6,10,14 and the case of 7 numbers whose pairwise sums are: 9,3,10,8,9,3,4,15,10,15,8,9,3,9,2,10,16,9,10,3,9 Also, your program will return a solution even when that solution when used to recreate the pairwise sums doesn't give the sums that you started with. That would be one way to determine if the original pairwise sums have a unique solution.
Can you find a way to determine if some given sums have a unique solution without first solving with your program as it stands?
Re: Valentine's Day 2008 Mini-Challenge ! part 2 - Egan Ford - 02-16-2008 Quote:Solution: | 3 3 5 | | 9 9 25 |I use an unimaginative bruce force attack on the problem and cracked it in 14 seconds with 50g/HPGGC3.
Output: Valentine's Day 2008Algorithm: (for complete HPGCC3 code goto http://sense.net/~egan/v08det.c) int det(int *a) { Quote:Easy. :-) IMHO, The general solution to N in part one is the harder problem. I may have a UserRPL solution for that today. Re: Valentine's Day 2008 Mini-Challenge ! - Alex L - 02-16-2008 I took on part one. A five-liner for the 71B, eh? Well, I got it down to four, if you don't mind entering the sums one at a time. I'm looking forward to learning more about input processing. This runs on a bare-bones, no-ROMs 71B. It's instant, as much of the work happens in the input loop.
10 T=0 @ L=MAXREAL @ M=L @ N=-M @ P=N The Final Notch (Re: Valentine's Day 2008 Mini-Challenge !) - Valentin Albillo - 02-18-2008 Hi, Egan:
so I've kept my promise and have added a final notch to the mini-challenge, you'll find it edited-in directly in my original post.
See whether you find it to your liking and considerable programming abilities.
Best regards from V.
Re: Valentine's Day 2008 Mini-Challenge ! - Thomas Klemm - 02-18-2008 The solutions are:
Let's assume the solution is [a, b, c, d, ...]
In the case of 6 numbers I got the solution with b+c=4: | 1 1 0 0 0 0 | | a | | 2 |
And here's the equation in the case of 7 numbers: | 1 1 0 0 0 0 0 | | a | | 2 |
Quote:
The program behaves as specified in Valentin's note: Quote:
As for your last question: I don't know of a simple way to determine whether the sums have actually been computed from five real numbers.
Re: Valentine's Day 2008 Mini-Challenge ! - Rodger Rosenbaum - 02-18-2008
Quote:
Yes, I realized that. I wasn't complaining that your program didn't meet Valentin's specifications. I was just mentioning it as a prelude to asking for a method to determine if a true solution exists.
Re: Valentine's Day 2008 Mini-Challenge ! part 3 - Egan Ford - 02-18-2008 Quote:I could have written this in UserRPL or BASIC, possibly RPN, but I selected C because I needed the speed for the five distinct integers variant of this problem. (And, HPGCC is my latest toy :-) The program below takes an argument of 3, 4, or 5 and searches for that number of distinct integers such that the sum of any pair is a perfect square.
Output for 3, 4, and 5: 3:The "Threes" and "Fours" are the number of n-1 and/or n-2 sets found along the way. Searching for 5 integers takes a long time at 192Mhz and 2.5x longer at 75Mhz (HPGCC2). Thanks again Valentin for the challenges, and thanks to Mr. Glasbey for the algorithm. For an entertaining read pick up the March 1978 edition of The Mathematical Gazette.
Code: #include <hpgcc49.h>Edited: Optimizations to increase speed 4x. Edited: More optimizations.
Edited: 20 Feb 2008, 8:52 p.m. after one or more responses were posted
Re: Valentine's Day 2008 Mini-Challenge ! part 3 - Paul Dale - 02-19-2008 I had a solution to this problem last night but was still working on getting it faster. Interestingly, it is different (smaller?):
3362 482 359 2 There are many others of course. Also, one major possibility for speeding up your program is to avoid a lot of the sqrt calls thus:
#define MAX 100 and initialise the array via:
for (i=0; i<MAX; i++) On my desktop system this change provides a reasonable speed up even with hardware floating point support. For the paranoid, check if x+y >= MAX*MAX in checkit() and do the old code in this case. - Pauli edit: added a not in the code
Edited: 19 Feb 2008, 5:41 p.m.
Re: Valentine's Day 2008 Mini-Challenge ! - Steve Perkins - 02-19-2008 Very nice Alex! This seems to head in the direction I wanted to go (before the holiday weekend distracted me). Your solution is more elegant than I envisioned. I especially like how you didn't bother storing the sums at all, just kept the total sum and the 2 smallest and 2 largest values. Those are all it takes to solve the problem in the case of 5 original numbers.
Good job.
Re: Valentine's Day 2008 Mini-Challenge ! part 3 - Paul Dale - 02-19-2008 Another speed up is to precalculate the sqrt calls:
static int sqrttbl[MAX*MAX]; Initialise this array via:
for (i=0, n=1; n<MAX*MAX; n++) { and change the existing calls to sqrt() to isqrt().
- Pauli
Re: Valentine's Day 2008 Mini-Challenge ! - Steve Perkins - 02-20-2008 Consider the following sets of pairwise sums from 6 numbers: 4 8 8 10 10 14 14 16 16 18 20 20 22 22 28 Clearly you need more than the 3 lowest and 3 highest sums to determine which solution works. My simple early attempts at a solver for 6 numbers gave both sets as possible solutions. Do we have to go back and compare the entire set of sums, or is there an easier way? Can we always resolve the 2 candidate solutions by comparing with the complete set of sums, or are there cases where 2 sets of original numbers generate identical sums? I don't believe identical sums can come from 2 sets, except back in the simple case of 6 sums from 4 numbers. With 7 numbers and 21 sums it looks like we would have 4 guesses based on the 3 greatest and 3 least sums. It gets more complicated quickly. It feels like I'm getting closer to the general solution, but there may be cases that limit the possibilities. I wish I could be more rigorous, but time is (as always) limited.
Edited: 20 Feb 2008, 1:13 p.m.
Re: Valentine's Day 2008 Mini-Challenge ! - Steve Perkins - 02-20-2008 This has been, as usual, an interesting problem. I think I have the general case for up to 11 numbers:
2 numbers 1 sum: infinite solutions In each case of 6+ original numbers, you can always resolve the solution by calculating the partial sums of the candidate guesses and comparing with the original entries.
I haven't found a reasonable equation to get a handle on the number of guesses. I wouldn't even be surprised to have made a mistake. The basic idea, is to guess which partial sum corresponds to each row of the sparse matrix: 1 1 0 0 0 ... The first 2 and last two rows are determined (2 least and 2 greatest sums). The others require guessing.
If the sorted solution is [a b c d e ...] and the sorted partial sums are [s1 s2 s3 s4 s5 ...] then row 3 of our sparse matrix can be s3 or s4. Row 4 can be s4-s7. Row 5 can be s5-s11. A similar guess is made for the last rows. I hope there are more simplified ways to tackle this. Hopefully someone can enlighten me further.
Re: Valentine's Day 2008 Mini-Challenge ! - Alex L - 02-20-2008 Thanks! Of course, my solution's only valid because Valentin originally constrained the problem such that we could assume valid input.
And equally of course, my comment about why the solution is fast is a red herring. :)
Re: Valentine's Day 2008 Mini-Challenge ! part 3 - Egan Ford - 02-20-2008 Hi Paul, In the past I have used static tables (e.g. in the 80s I used cos/sin tables for faster real time 3d graphics), and dynamic tables (e.g. SSMC19 A+ 71B solution--more 80s tech) to increase critical parts of applications. I thought about something similar for this problem but quickly (too quickly) dismissed it without testing. Post 1980s processor performance has quickly outpaced memory performance. The number of clock cycles needed to access memory, especially a large table (i.e. cache miss), is often longer than calculating basic functions like sin, cos, sqrt. I assumed that this would also have been the case. But, I forgot that the ARM processor has no floating point processor. The same tricks I used in the 80s should apply here as well. Lets see... The baseline for 3 and 4 integers is 0 seconds. The baseline for 5 integers is 451 seconds (initially it was 2000+ seconds, but a few small algorithm optimizations dropped this down to 451). BTW, none of the optimization changes noticeably increased or decreased the performance of the 3 and 4 (original problem) integer cases. They run so fast that the results are present before you can remove your finger from the button that launched it. Late last night I was able to work on checkit optimization. My first test was to reduce the impact of sqrt with isqrt. Unfortunately HPGCC3 does not have an isqrt function, so I wrote one, a poor one, and performance was a bit worse (2 seconds slower for the 5 integer case). So I went shopping and took the first Google hit for "isqrt". The faster isqrt reduced the time from 451 to 293 seconds.
For my 2nd test I wanted to find a way to call sqrt as little as possible. The following code should identify 99.25% of non-square numbers. I measured a 61% hit rate. Of the 39% of the numbers that slipped through, 11% were non-square and 89% were perfect squares. The "mod filter" caught ~96% of the non-square numbers. register int a, b = x + y;This code reduced the time from 451 to 351 seconds.
My 3rd test used your suggestion of a true/false table for perfect squares. I collected the following data: MAX Bytes Time(s) Hit RateThe table method works well, but my 50g runs out of RAM with MAX=617. Even if I had the ~1MB of RAM required to hold a table large enough for a 100% hit rate the estimated time to solution is ~312 seconds. Faster than my 2nd test (mod filter), but slower than isqrt. Evidence that computing basic functions like sqrt on modern machines will be faster than RAM lookup tables.
Next I tried to combine methods. isqrt is so far ahead of the other methods that I expect that they may have little or no impact: Uni Time(s)Table(45%) + isqrt(55%) is a bit slower that just isqrt. I expect that more table hits vs. isqrt hits will be even slower. Mod filter (61%) + isqrt(39%) only improved by 1 second. The combination of the three (table(45%) + mod filter(34%) + isqrt(21%)) gained 1 second. IMHO, the most elegant solution is isqrt. It also has a small memory footprint. I've updated my original code above with all three optimizations, but left the table lookup and mod filter commented out.
P.S. I forgot to add that I ran all of the above at 192MHz. Running the 50g at the default of 75MHz, the table lookup may have performed the fastest. Even faster than isqrt. It is not uncommon for memory access performance to be independent of processor MHz. Edited: 20 Feb 2008, 8:39 p.m. after one or more responses were posted
Re: Valentine's Day 2008 Mini-Challenge ! part 3 - Paul Dale - 02-20-2008 Great analysis! I tried isqrt on my desktop machine and it was significantly slower than the table approach. Of course, the tables are relatively small compared to modern CPU caches so lookups will be fast. The ARM has a tiny cache and is very good at the kind of operations involved in the sqrt calculation.
Re: Valentine's Day 2008 Mini-Challenge ! part 3 - Egan Ford - 02-20-2008 You may want to try the isqrt that I used in my amended post. On my PC isqrt and table lookup was the same speed. Perhaps I have smaller L1/L2 caches.
I think table lookup will be faster at 75Mhz on the 50g. If I have time I will try it tonight.
Re: Valentine's Day 2008 Mini-Challenge ! - Rodger Rosenbaum - 02-21-2008 Can you give an example of two distinct (meaning you can't derive one from the other by just reordering) sets of 4 numbers which give the same pairwise sums?
Re: Valentine's Day 2008 Mini-Challenge ! part 3 - Egan Ford - 02-21-2008 Quote:Here are some 75Mhz/HPGCC2/50g numbers: isqrt 837sWhen running at slower processor speeds, table lookup adds the most benefit. I can (Re: Valentine's Day 2008 Mini-Challenge !) - Valentin Albillo - 02-21-2008 (1,4,6,7) and (2,3,5,8)
Best regards from V.
Re: I can (Re: Valentine's Day 2008 Mini-Challenge !) - Rodger Rosenbaum - 02-21-2008 I was wondering if he had discovered how to know if the sums have only one solution or two. Given 4 numbers {a, b, c, d}, if d = (b + c - a) then the pairwise sums generated from these 4 will have only one (exact) solution, otherwise there are two solutions. This means that almost any 4 numbers you type will also have a companion solution. But, notice that the set (1, 2, 3, 4), which would be a set a person might type generates a set of pairwise sums with only one solution! If there are two solutions, then if one of them is {a, b, c, d}, where d = (b + c - a - n), n = some number <> zero, the other solution is: { (2a + n)/2, (2b - n)/2, (2c - n)/2, (2d + n)/2 )
It appears that a necessary condition that any 6 numbers that actually have an exact solution will have a pair of solutions (which may not be distinct) is that at least two of the pairwise sums are the same, but this is not a sufficient condition.
Re: Valentine's Day 2008 Mini-Challenge ! - Rodger Rosenbaum - 02-21-2008 The 4 numbers 6 sums case can have a solution that appears to be unique, but isn't. It is a solution of multiplicity 2; for example the sums {3 4 3 5 4 5} which are generated from the 4 numbers {1 2 3 2}. It can be shown that: Given 4 numbers {a, b, c, d}, if d = (b + c - a) then the pairwise sums generated from these 4 will have only one (exact) solution, otherwise there are two solutions. If there are two solutions, then if one of them is {a, b, c, d}, where d = (b + c - a - n), n = some number <> zero, the other solution is: { (2a + n)/2, (2b - n)/2, (2c - n)/2, (2d + n)/2 ) If you start with the numbers {1 2 3 2} and let n = 2, then the expression above evaluates to {2 1 2 3}, which appears to be the same as what we started with, rearranged. The fact that using the espression with n=2 gives a set which generates the same sums, shows that it's really a solution of multiplicity 2. On the other hand, if you use the set {1 2 3 4} to generate the sums, there is really only one exact solution. The case where we start with 5 numbers has the solution using the matrix:
[ 1 1 0 0 0 ] [a] [smallest pairwise sum ] I use 4's in the 3rd row instead of 1's so that the element in the column vector is the sum of the pairwise sums, rather than that sum divided by 4. With this technique the only way determine if a solution is good is to regenerate the pairwise sums and see if you get what you started with. However, if you add a row to the matrix:
[ 1 1 0 0 0 ] [a] [smallest pairwise sum ] Now you can augment the 6x5 overdetermined matrix with the column matrix and see if the rank of the augmented matrix is larger than the rank of the 6x5 matrix alone. If the rank increases to 6, then there is no exact solution. If the rank of the augmented matrix is still 5, then the exact solution is the least squares solution to the overdetermined system. While this is theoretically satisfying, it's just about as easy to provisionally solve the system with the smaller matrix and test the solution. One might think this scheme could be applied to the larger N systems, but it doesn't work because there aren't enough known relationships to provide more rows in the matrix to increase the rank to N. For N starting numbers, consider the matrix of order (PERM(N,2) X N) whose rows have only two unity elements in each row. The PERM(N,2) rows have all possible combinations of columns containing 1's taken two at a time. For example, the N=5 case:
[ 1 1 0 0 0 ] I'll call this the MOC (matrix of combinations). The MOC can be used to generate the pairwise sums by postmultiplying the MOC by a column vector of the starting numbers [ a b c d e ]T. For example, MOC * [ 1 2 3 4 5 ] gives [ 3 4 5 6 5 6 7 7 8 9]T. And, the MOC can be used to solve the problem. Using an HP50, put [ 3 4 5 6 5 6 7 7 8 9 ]T on level 2 of the stack, and the 5th order MOC on level 1 and execute LSQ. See [ 1 2 3 4 5 ]T, the correct answer. In theory, this will solve the problem for any size set of pairwise sums. However in practice, a problem is that if the arrangement of the sums is not right, it won't work. But, in theory the solution can be found in a finite, though large, number of steps. The procedure is to augment the MOC with all possible permutations of the pairwise sums as a column vector. If the rank of the augmented MOC is increased, then there is no exact solution for that particular permutation of the sums. If the rank is not increased, then the least squares solution of the system is the desired solution. If all of the permutations of the column vector of sums increase the rank of the augmented matrix, then there is no exact solution. This is just feasible to do on a PC for the N=5 case. The procedure will find a maximum of 5! solutions with 10! permutations of the sums tested. The solutions are all the same set of numbers, in all possible permutations. Of course, if some of the sums are the same, then the number of (distinct) permutations is reduced.
You can see that the number of permutations to be considered rapidly gets out of hand as the order of the problem increases!
Re: Valentine's Day 2008 Mini-Challenge ! - Egan Ford - 02-21-2008 Quote:Hi Rodger, I experimented with this last weekend as I worked on my general solution for any N, but got sidetracked with parts 2 and 3. Here is what I discovered so far:
For any N there will be N*(N-1)pairwise sums. If N = 1, then there is one solution, if N = 2, there are infinite solutions. If N > 2 there is at least one solution. With random numbers I found that with N > 2 there was only one solution except for N = 4 where there was always 2 solutions. I looks like you found a special case for N = 4 that will give only one solution. That makes be wonder about N > 4 having multiple solutions. When brute force searching for solutions, if your NxN matrix A contains all ones in the first row, the first column and the diagonal, and the first value set in the vector b is the sum of all pairs/(N-1), then there are PERM(S,N-1) permutations to test. N! of the permutations will return the same correct answer. If any of the original numbers (x1, x2, ...) have duplicates then the number of correct identical solutions is > N!.
My brute force program has the option to find all solutions or quit after finding one. It is fast for N=3..7, slows a bit at 8, takes forever at 9. I can speed it up by using the two largest and smallest values reducing the number of permutations to test to PERM(S-4,N-5). For the original problem there is no permutations, just one way to solve it. For N = 6 there are only 2 tests as Thomas has already pointed out. If I have time I'll finish and post it this weekend. Edited: 21 Feb 2008, 1:20 p.m.
Re: Valentine's Day 2008 Mini-Challenge ! - Rodger Rosenbaum - 02-21-2008 Quote: This is, of course, equal to COMB(N,2). Makes one wonder about the N numbers case with sums taken 3 at a time, or 4 at a time, etc. The canonical method I gave in another post is a big time waster because we are only looking for N numbers, but we have COMB(N,2) equations. So a lot of the permutations are guaranteed not to have a solution. Having only N equations in N unknowns is better.
Quote: I also wonder, but the details of my derivation of the special case for N=4 makes me lean toward the notion that there are no multiple solutions for most of the higher order cases, and maybe not any.
Quote: Don't you mean: "...the number of correct identical solutions is < N!."? I assume you're referring to the fact that when there are duplicate original numbers, the sums include duplicates, and therefore the number of (distinct) permutations is reduced.
Quote: You must be doing this to get a solution for the N=9 case in fewer than the 10^12 permutations it would take otherwise! We need to take advantage of any sums or combinations thereof that we can use to reduce the order of the problem. I think the 5 we know, the 2 smallest and 2 largest sums and the sum of the sums, are all there are in the case of pairwise sums. I think the major reductions in time have been found. There may be a few small tweaks left.
Now, on to the sums of 3 at a time case!
Premature retreat (Re: Valentine's Day 2008 Mini-Challenge !) - Valentin Albillo - 02-21-2008 Hi, Rodger: Rodger posted:
You now know that for N=1,3,5 the solution is unique and for N=2,4 it's not. But what about arbitrary N ? Find that out and prove your savvy to the highly knowledgeable audience following this thread; it isn't trivial but that's why I call it a "mini-challenge" (full-fledged challenge, next April 1st) After all, this is intended as a mere training for the incoming "Spring Special". If the difficulties here make you go for a premature retreat, the ones there will make you run screaming for the hills ! ... :-)
Re: Valentine's Day 2008 Mini-Challenge ! - Rodger Rosenbaum - 02-21-2008 You said:
Quote: And I said in a responding post, at the end:
Quote: It looks like we can continue taking advantage of special properties for a while longer. For the case N = 6, we need the matrix (using Thomas' style):
[ 1 1 0 0 0 0 ] [ a ] [ s1 ] where the 3rd row has two possibilities, both of which must be tried: [ 0 1 1 0 0 0 ] and [ 1 0 0 1 0 0 0 ]; one of these equals the 3rd smallest sum. So two tests will solve the N=6 case. For the N=7 case, we need:
[ 1 1 0 0 0 0 0 ] [ a ] [ s1 ] Here we know that the 3rd (element in the set of ordered sums) sum is either a+d or b+c. If the 3rd is a+d, then the 4th is b+c OR a+e; if the 3rd is b+c then the 4th is a+d. So we try the solution with the 3rd and 4th rows as shown just above. If that doesn't work, then make row 3 a+d and try row 4 = b+c OR row 4 = a+e, leaving the 3rd and 4th sums in the same positions in the column vector. One of the three will give the solution. So we need three tests for the N=7 case. Thomas appears to have added a row both before and after the row of all ones and tried the 4 possible combinations. He didn't say exactly how he did it; he just showed the two extra rows. But I don't think you need 4 tests for the N=7 case; I think 3 will do it. For the case N=8, consider:
[ 1 1 0 0 0 0 0 0 ] [ a ] [ s1 ] I've added another row after the row of all ones. It can take on two possibilities, [ 0 0 0 0 1 1 0 ] and [0 0 0 1 0 0 1 ], and the corresponding quantity in the column vector is the 3rd sum from the end. For each of the three possibilities for rows 3 and 4, try each of the two possibilities for row 6. This will give the solution in 6 tries. For the N=9 case, add another row (it becomes row 6) after the all ones row. Then go through the three possibilities for rows 3 and 4, and rows 6 and 7. So we can solve the N=9 case with 9 tries. I hope I did this without too many stupid errors. This is much better than the PERM(S-4,N-5) tries that would be needed if we gave up using special cases earlier.
I suppose this kind of thing can be carried even further, but it is less systematic than the all permutations method (although much more efficient), and it becomes more difficult to decipher the possibilities.
Re: Valentine's Day 2008 Mini-Challenge ! - Egan Ford - 02-22-2008 Quote:Yes and no. If you consider the permutations of unique values then yes < N!, but if you consider all permutations based on position and allow duplicate pair sums, then > N!.
I forgot to mention that there was an error in my post, PERM(S-4,N-5) should be COMB(S-4,N-5).
Re: Premature retreat (Re: Valentine's Day 2008 Mini-Challenge !) - Egan Ford - 02-22-2008 Valentin, Rodger,
Here are two sets of 8 with the same pairwise sums. 1 5 7 9 9 11 13 17So, I'm going to make a guess. If N can be expressed as 2x where x is an integer, then the reversal of the pairwise sums may have multiple solutions. Edited: 22 Feb 2008, 7:19 p.m. after one or more responses were posted
Re: Valentine's Day 2008 Mini-Challenge ! - Egan Ford - 02-22-2008 My early PERM(S-4,N-5) should have been COMB(S-4,N-5).
I had some time late last night to work on this again. My current solution firsts sets up the matrix: | 1 1 0 ... |The first 2 rows are the smallest values, the last two the largest values, and the 3rd from last the sum of all pairs/(N-1). The remaining rows follow the pattern x1+x4, x1+x5, ... All that is left is to compute the COMB(S-4,N-5) combinations and test them in the remaining slots. There is no need to run permutations with each combination set since they should only be tested in increasing order to best match the pattern in A starting from the 3rd row down. There is no need to sort each combination array since the array is already sorted.
This solution is reasonably quick to find the first solution with N < 13. Reasonably quick being less time than to eat lunch. Finding all the solutions for N = 8, was very fast. Edited: 22 Feb 2008, 4:03 p.m.
Re: Premature retreat (Re: Valentine's Day 2008 Mini-Challenge !) - Steve Perkins - 02-25-2008 An interesting counter example to my best guess. I supposed that solutions were unique beyond N=5, and I felt fairly confident that this was true.
Guesses, feelings and hunches are not mathematical proofs. I clearly should have done a lot more investigating.
Re: Valentine's Day Mini-Challenges !: My original solutions & comments - Valentin Albillo - 02-25-2008
Hi all,
First notch
For the specific case of five numbers, there's no need to construct a system of linear equations, overdetermined or not.
My original program for the HP-71B does exactly that. I used arrays to input and output
1 DESTROY ALL @ OPTION BASE 1 @ N=10 @ DIM X(5),A(N) @ MAT INPUT A
For arbitrary N, the solution, when it exists, is unique except when N is a power of 2,
For N not a power of 2, there's no efficient method known to compute the unique solution,
Intermediate notch
This yields to brute force and I took that approach, doing very little thinking and
1 DESTROY ALL @ OPTION BASE 1 @ DIM T(9)
which is far, far from optimal but does the job if you simply let it run for a while (though
>RUNThe only "trick" worth mentioning in the above program is the use of CNORM to count how many different values are we dealing with, which is used as a cutoff at two places to save unnecessary looping or computing the determinants. This is still very far from optimal but I was feeling pretty lazy at the time ... The problem doesn't extend to cubes but I find it nice that the solution is unique.
The final notch
Another lazy effort on my part but at least this 10-liner for the HP-71B runs fast:
1 DESTROY ALL @ OPTION BASE 1 @ DIM Y(3) @ FOR N=0 TO 1000
as you can see, all sets of six sums are perfect squares, as required. Extensive
Thanks for your interest in this humble mini-challenge, you've shown tremendous
However, this was but a training for the incoming S&SMC#20 full-fledged challenge, Let's hope that momentous event doesn't find you affected with the lazy bug ! See you next April 1st ! :-) Best regards from V.
Edited to correct a typo Edited: 25 Feb 2008, 7:48 p.m.
|