Author |
Topic: Seven Weights (Read 1112 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
Seven Weights
« on: Feb 22nd, 2005, 6:47pm » |
 Quote  Modify
|
I came across this puzzle on a site that claimed it took 38 years for a definitive answer to be given. It was originally posed (as far as I know) by A. R. Legard in the [London] Sunday Times on 30 June 1963:
"On our last expedition to the interior," said the famous explorer, "we came across a tribe who had an interesting kind of Harvest Festival, in which every male member of the tribe had to contribute a levy of grain into the communal tribal store. Their unit of weight was roughly the same as our pound avoirdupois, and each tribesman had to contribute one pound of grain for every year of his age.
"The contributions were weighed on the tribe's ceremonial scales, using a set of seven ceremonial weights. Each of these weighed an integral number of pounds, and it was an essential part of the ritual that not more than three of them should be used for each weighing, though they need not all be in the same pan.
"We were told that if ever a tribesman lived to such an age that his contribution could no longer be weighed by using three weights only, the levy of grain would terminate for ever. And in the previous year, one old man had died only a few months short of attaining this critical age, greatly to the relief of the headsman of the tribe.
"The scientist with our expedition confirmed that the weights had been selected so that the critical age was the maximum possible."
What was the age of the old man when he died? And what were the weights of the seven ceremonial weights?
(I don't know the solution.)
Mathematically stated, the problem is to find a set S of seven integers such that the smallest positive integer M not representable as x [pm] y [pm] z for some x, y, z [in] S U {0} is as large as possible. (Until William gets the symbolry back up, the "[pm]" stands for "+ or -").
|
| « Last Edit: Feb 25th, 2005, 3:06pm by Icarus » |
 IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
markr
Guest
|
www.truthtree.com has this as one of their problems. I received full credit for my solution (list the weights), so I'm assuming I got it right. The theoretical max is 189 (the number of different ways you can populate the pans). I got 122 after hours and hours of CPU time running a program that started off in C, but had to be converted to assembly.
Taking into account the theoretical max, and looking at the distribution of weights for the solutions to the problem with 3-6 weights, I did a brute force search with different (fairly generous) ranges for each of the 7 stones.
Since hiding doesn't work, I won't publish my list unless somebody asks.
|
|
IP Logged |
|
|
|
Noke Lieu
Uberpuzzler
pen... paper... let's go! (and bit of plastic)
Gender:
Posts: 1884
|
|
Re: Seven Weights
« Reply #2 on: Feb 22nd, 2005, 10:11pm » |
Quote Modify
|
am convicing myself, at first glance, that the first three weights are 1, 3, 9,
Seems like a familiar pattern? But, obviously the next number isn't 27.
(although, disappointingly, you can get to 42 without any trouble using 1,2,4,8,16,32)
|
| « Last Edit: Feb 22nd, 2005, 11:24pm by Noke Lieu » |
IP Logged |
a shade of wit and the art of farce.
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Seven Weights
« Reply #3 on: Feb 23rd, 2005, 6:32am » |
Quote Modify
|
on Feb 22nd, 2005, 9:37pm, markr wrote:| www.truthtree.com has this as one of their problems. I received full credit for my solution (list the weights), so I'm assuming I got it right. The theoretical max is 189 (the number of different ways you can populate the pans). I got 122 after hours and hours of CPU time running a program that started off in C, but had to be converted to assembly. |
|
I got the correct answer, too.
I can't remember how I did it or even if I wrote a program, but I do know it required minutes rather than hours of time.
(The puzzles are at http://truthtree.com/mathdoor.html.)
.
|
| « Last Edit: Feb 25th, 2005, 8:45pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
markr
Guest
|
I'm interested in knowing an efficient method for solving this.
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Seven Weights
« Reply #5 on: Feb 23rd, 2005, 6:09pm » |
Quote Modify
|
1963! That riddle is older than almost everyone who uses this forum. Most likely, it took 38 years because it was a forgotten riddle, just like sometimes happens here for some that are quite solvable.
Since hide is not working... My guess is first five weights in increasing order are given by the first 7 digits right of decimal place in the decimal value of 1/7.292653454. The next 2 weights (still increasing order) are found from the digits of 1/1.314025912.
|
|
IP Logged |
|
|
|
markr
Guest
|
If you round to 7 digits (first part) instead of truncate, then that's what I got.
How'd you do it?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Seven Weights
« Reply #7 on: Feb 24th, 2005, 12:52am » |
Quote Modify
|
Here’s a simple approach which does not give an optimal solution, but does not require any computing hardware.
Assume we’ve got m units such that any weight from 1 to N may be weighted with at most two of them. Then, adding 2 more units of weights 2N+1 and 4N+2 we can weight any weight from 1 to 5N+2 with 3 units.
So, it remains to find 5 units with N as big as possible. In fact, I’ve found the sequence 1, 3, 7, 12, 17 when walking this morning at the Mediterranean sea shore  . This gives N=20 and 102 with 7 weights.
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Seven Weights
« Reply #8 on: Feb 24th, 2005, 6:40pm » |
Quote Modify
|
on Feb 23rd, 2005, 7:17pm, markr wrote:| If you round to 7 digits (first part) instead of truncate, then that's what I got. |
|
Yes, you need to round up. I was at the limit of my calculator's precision and didn't notice being a little low. I should have said 1/7.292653453.
Although Barukh's approach is more honorable than brute force, it will not lead to the solution, because with the weights giving 122 as the max, the relatively low weight of 17 can be made only by using the 3 heaviest weights. I have a comment on Icarus' rephrasing of the question as x[pm]y[pm]z: you can also use 1 or 2 weights, so x and x[pm]y are also acceptable.
I used a computer program to find the 7 weights, but didn't really go through an exhaustive search. Just used some reasonable guesses as to the range of the weights and checked a fraction of the possibilities. Assumed something like: the smallest weight is 1; the 2nd smallest is 2, 3, or 4; 3rd smallest is less than 12; 4th smallest is less than 50, ... That reduced the number of cased checked and the program found the weights in a few minutes. Of course, knowing the correct maximum given by markr saved me from wasting further effort once I got one for 122.
I first tried a C program in Linux with gcc. Converted to Java on Windows and it took 50% longer. Compiled the C program with MS Visual C++, ran on Windows and it took 50% longer than the Java program.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Seven Weights
« Reply #9 on: Feb 25th, 2005, 2:34am » |
Quote Modify
|
Nice!
on Feb 24th, 2005, 6:40pm, SWF wrote:| Of course, knowing the correct maximum given by markr saved me from wasting further effort once I got one for 122. |
|
Is 122 a proven maximum?
I am also curious, SWF, is it possible to use your program to find 5 units such that the maximim possible weight may be weighed with at most 2 units? Thanks.
Quote:| I first tried a C program in Linux with gcc. Converted to Java on Windows and it took 50% longer. Compiled the C program with MS Visual C++, ran on Windows and it took 50% longer than the Java program. |
|
This is strange... I know MS Visual C++ has a very good optimizer!
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Seven Weights
« Reply #10 on: Feb 25th, 2005, 2:57am » |
Quote Modify
|
on Feb 25th, 2005, 2:34am, Barukh wrote:This is strange... I know MS Visual C++ has a very good optimizer!
|
|
Maybe he compiled and ran in debug mode?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Seven Weights
« Reply #11 on: Feb 25th, 2005, 7:55am » |
Quote Modify
|
on Feb 25th, 2005, 2:57am, Grimbal wrote:
Maybe he compiled and ran in debug mode? |
|
Or maybe he included full Windows functionality rather than doing a straight console app. (or vice versa)
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Seven Weights
« Reply #12 on: Feb 25th, 2005, 9:27am » |
Quote Modify
|
I tried to use the fastest version of each program. I am not real familiar with Visual C++ compiler options, but the test case was with a console application, "Release" version not Debug. Also used the \O2 flag among others. This was with MS Visual C++ 6.0 and a version of gcc that is even older. Somebody else please give it a try and let us know the results. For the Java program, make sure to run with the "-server" flag, or else it will take more than twice as long.
For the program you can change the limits on the for() loops to examine more cases. Set nmax to the number of consecutive integers needed before printing out a solution. I have tried looking for cases with the biggest weight greater than nmax, but it does not help.
Barukh, for 5 weights combined 2 at a time, it finds 20 as the most consecutive, with 3 different solutions:
1 2 7 13 17; 1 2 8 12 17; 1 3 7 12 17
________________C Version_________________
#include <stdio.h>
#include <stdlib.h>
int a[7];
int nmax=122;
main(){
int chk();
for(a[0]=1;a[0]<=1;a[0]++){
for(a[1]=2;a[1]<=3;a[1]++){
for(a[2]=6;a[2]<=10;a[2]++){
for(a[3]=a[2];a[3]<=20;a[3]++){
for(a[4]=a[3];a[4]<=50;a[4]++){
for(a[5]=a[4];a[5]<=nmax;a[5]++){
for(a[6]=nmax;a[6]>a[5];a[6]--){
if(a[4]+a[5]+a[6]<nmax) break;
if(chk()){
printf("%d %d %d %d %d %d %d\n",a[0],a[1],a[2],a[3],a[4],a[5],a[6]);}
}}}}}}}
}
int chk1(int n)
{ int i1,i2,i3;
for(i1=0;i1<7;i1++){
for(i2=i1+1;i2<7;i2++){
for(i3=i2+1;i3<7;i3++){
if(a[i1]==n) return 1;
if(a[i2]==n) return 1;
if(a[i3]==n) return 1;
if(a[i2]+a[i3]==n) return 1;
if(a[i1]+a[i3]==n) return 1;
if(a[i1]+a[i2]==n) return 1;
if(-a[i2]+a[i3]==n) return 1;
if(-a[i1]+a[i3]==n) return 1;
if(-a[i1]+a[i2]==n) return 1;
if( a[i1]+a[i2]+a[i3]==n) return 1;
if( a[i1]+a[i2]-a[i3]==n) return 1;
if( a[i1]-a[i2]+a[i3]==n) return 1;
if(-a[i1]+a[i2]+a[i3]==n) return 1;
if(-a[i1]-a[i2]+a[i3]==n) return 1;
if(-a[i1]+a[i2]-a[i3]==n) return 1;
}}}
return 0;
}
int chk()
{ int i,chk1();
for(i=nmax;i>0;i--){if(chk1(i)==0) return 0;}
return 1;
}
____________Java Version__________
public class Q {
int[] a=new int[7];
int nmax=122;
public static void main(String[] args) {
Q q=new Q();
}
Q(){
for(a[0]=1;a[0]<=1;a[0]++){
for(a[1]=2;a[1]<=3;a[1]++){
for(a[2]=6;a[2]<=10;a[2]++){
for(a[3]=a[2];a[3]<=20;a[3]++){
for(a[4]=a[3];a[4]<=50;a[4]++){
for(a[5]=a[4];a[5]<=nmax;a[5]++){
for(a[6]=nmax;a[6]>a[5];a[6]--){
if(a[4]+a[5]+a[6]<nmax) break;
if(chk()){
System.out.println(a[0]+" "+a[1]+" "+a[2]+" "+a[3]+" "+a[4]+" "+a[5]+" "+a[6]); }
}}}}}}}
}
boolean chk() {
int i;
for(i=nmax;i>0;i--){ if(!chk1(i)) return false; }
return true;
}
boolean chk1(int n){
int i1,i2,i3;
for(i1=0;i1<7;i1++){
for(i2=i1+1;i2<7;i2++){
for(i3=i2+1;i3<7;i3++){
if(a[i1]==n) return true;
if(a[i2]==n) return true;
if(a[i3]==n) return true;
if(a[i2]+a[i3]==n) return true;
if(a[i1]+a[i3]==n) return true;
if(a[i1]+a[i2]==n) return true;
if(-a[i2]+a[i3]==n) return true;
if(-a[i1]+a[i3]==n) return true;
if(-a[i1]+a[i2]==n) return true;
if( a[i1]+a[i2]+a[i3]==n) return true;
if( a[i1]+a[i2]-a[i3]==n) return true;
if( a[i1]-a[i2]+a[i3]==n) return true;
if(-a[i1]+a[i2]+a[i3]==n) return true;
if(-a[i1]-a[i2]+a[i3]==n) return true;
if(-a[i1]+a[i2]-a[i3]==n) return true;
}}}
return false;
}
}
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Seven Weights
« Reply #13 on: Feb 25th, 2005, 2:25pm » |
Quote Modify
|
For 5 weights I get 49 with 1 3 7 12 36, and with 6 weights I get 84 with surprising 1 3 17 22 51 61. That is to say that searching with the limits for the third element set at [6;10] may be too restrictive.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Seven Weights
« Reply #14 on: Feb 25th, 2005, 3:05pm » |
Quote Modify
|
on Feb 24th, 2005, 6:40pm, SWF wrote:| I have a comment on Icarus' rephrasing of the question as x[pm]y[pm]z: you can also use 1 or 2 weights, so x and x[pm]y are also acceptable. |
|
Thanks. I actually thought of that after I posted, but by the time I could get around to correcting it, I had forgotten the correction I intended to make! 
It is corrected now.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Seven Weights
« Reply #15 on: Feb 28th, 2005, 6:52pm » |
Quote Modify
|
Is anyone going to try this program in Java and MS Visual C++? I am curious to see if the Java version is really faster or if I am inefficiently using the compiler.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Seven Weights
« Reply #16 on: Feb 28th, 2005, 8:59pm » |
Quote Modify
|
on Feb 28th, 2005, 6:52pm, SWF wrote:| Is anyone going to try this program in Java and MS Visual C++? I am curious to see if the Java version is really faster or if I am inefficiently using the compiler. |
|
First, isn't the last equality check in chk1() redundant?
Second, why start a[i+1] with a[i] instead of a[i] + 1?
With these fixes, on a 2.8 GHz P4 Linux machine (gcc 3.3.1 -O6) the C program runs 20.5 s.
By the way, the problem is related to the Golomb Ruler problem which has so far only an NP solution, so it is no wonder it was sitting on the back-burner for so long.
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Seven Weights
« Reply #17 on: Mar 1st, 2005, 5:51pm » |
Quote Modify
|
Yes, that last check is unecessary, since it always gives a negative value, like a couple of other permutations that were left out for the same reason. I did not start the loops at a[]+1 because I wasn't sure no two weights are equal. It is true that if you have two weights the same, x and x, you might was well use x and 2x instead for more possibilites, but I was already restricting the limits of the loops at the upper end. I wasn't certain and figured one extra value to check is not a big deal.
Here are the number of seconds it took on various computers with three different C++ compilers: Intel (icc), GNU (gcc), and Microsoft Visual C++ (mcc). The estimates I gave previously were not quite right. I suppose Java would lose ground for a more complicated program.
....................................icc ..... gcc .... mcc ..... Java
3.06 GHz (Linux) ........... 14.9 ... 20.9 .... X ........ 20.2
2.40 GHz (Win XP) ....... 20.4 .... X ...... 53.7 ..... 30.6
0.366 GHz (Win98*) ...... 138.6 .. 166.1 .. 330.5 .. 188.8
*Except the 0.366 GHz with gcc was under Linux
|
| « Last Edit: Mar 1st, 2005, 6:41pm by SWF » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Seven Weights
« Reply #18 on: Mar 3rd, 2005, 5:35am » |
Quote Modify
|
on Mar 1st, 2005, 5:51pm, SWF wrote:Here are the number of seconds it took on various computers with three different C++ compilers: Intel (icc), GNU (gcc), and Microsoft Visual C++ (mcc). The estimates I gave previously were not quite right. I suppose Java would lose ground for a more complicated program.
....................................icc ..... gcc .... mcc ..... Java
3.06 GHz (Linux) ........... 14.9 ... 20.9 .... X ........ 20.2
2.40 GHz (Win XP) ....... 20.4 .... X ...... 53.7 ..... 30.6
0.366 GHz (Win98*) ...... 138.6 .. 166.1 .. 330.5 .. 188.8
|
|
SWF, to make the experiment more clear, I ran your C program also in cygwin environment (GNU tools under Windows). Here’s what I got (cl is the MS VC++):
3.06 GHz Linux gcc 29 sec
1.80 GHz WinXP gcc 44 sec
1.80 GHz Win XP cl 34 sec
All the versions were compiled with –O2 switch. So, it looks like C++ does a better job than gcc. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove