wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Seven Weights
        
(Message started by: Icarus on Feb 22^nd, 2005, 6:47pm)

Title: Seven Weights
Post by Icarus on Feb 22^nd, 2005, 6:47pm

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 -").

Title: Re: Seven Weights
Post by markr on Feb 22^nd, 2005, 9:37pm

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.

Title: Re: Seven Weights
Post by Noke Lieu on Feb 22^nd, 2005, 10:11pm

am convicing myself, at first glance, that the first three weights are [hide] 1, 3, 9, [/hide]

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)

Title: Re: Seven Weights
Post by THUDandBLUNDER on Feb 23^rd, 2005, 6:32am

on 02/22/05 at 21:37:35, markr wrote:

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.)

.

Title: Re: Seven Weights
Post by markr on Feb 23^rd, 2005, 1:00pm

I'm interested in knowing an efficient method for solving this.

Title: Re: Seven Weights
Post by SWF on Feb 23^rd, 2005, 6:09pm

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.

Title: Re: Seven Weights
Post by markr on Feb 23^rd, 2005, 7:17pm

If you round to 7 digits (first part) instead of truncate, then that's what I got.

How'd you do it?

Title: Re: Seven Weights
Post by Barukh on Feb 24^th, 2005, 12:52am

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 :D. This gives N=20 and 102 with 7 weights.

Title: Re: Seven Weights
Post by SWF on Feb 24^th, 2005, 6:40pm

on 02/23/05 at 19:17:45, 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.

Title: Re: Seven Weights
Post by Barukh on Feb 25^th, 2005, 2:34am

Nice!

on 02/24/05 at 18:40:02, 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!

Title: Re: Seven Weights
Post by Grimbal on Feb 25^th, 2005, 2:57am

on 02/25/05 at 02:34:33, Barukh wrote:

This is strange... I know MS Visual C++ has a very good optimizer!

Maybe he compiled and ran in debug mode?

Title: Re: Seven Weights
Post by rmsgrey on Feb 25^th, 2005, 7:55am

on 02/25/05 at 02:57:51, 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)

Title: Re: Seven Weights
Post by SWF on Feb 25^th, 2005, 9:27am

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;
}
}

Title: Re: Seven Weights
Post by Leonid Broukhis on Feb 25^th, 2005, 2:25pm

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.

Title: Re: Seven Weights
Post by Icarus on Feb 25^th, 2005, 3:05pm

on 02/24/05 at 18:40:02, 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.

Title: Re: Seven Weights
Post by SWF on Feb 28^th, 2005, 6:52pm

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.

Title: Re: Seven Weights
Post by Leonid Broukhis on Feb 28^th, 2005, 8:59pm

on 02/28/05 at 18:52:47, 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.

Title: Re: Seven Weights
Post by SWF on Mar 1^st, 2005, 5:51pm

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

Title: Re: Seven Weights
Post by Barukh on Mar 3^rd, 2005, 5:35am

on 03/01/05 at 17:51:10, 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. :-/