Author |
Topic: A problem of weights... (Read 796 times) |
|
kcb2xxx
Newbie
Posts: 4
|
 |
A problem of weights...
« on: Jun 17th, 2005, 10:03am » |
 Quote  Modify
|
Hi,
Here's a puzzle I cam across some time ago...
You have a class
stoneweights{
int stones[n]={.....} //undefined number of stones.
int totalweight(); //returns total weight
int maxweight(); //returns max stone weight
stoneweights add();//adds a stone
stoneweights remove();//removes all stones of same weight
}
There is another 'split' function which tells you whether or not the stones can be divided into two subsets of equal weights. As in, returns either true or false.
Now, using the above 4 functions and the 'split' function you have to specify whether a weight 'k' can be weighed by a subset of the stones array.
The catch... you can't use loops/recursion  ...
Any bright ideas ?
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: A problem of weights...
« Reply #1 on: Jun 17th, 2005, 3:53pm » |
Quote Modify
|
add(totalweight()-2k);
return split();
|
|
IP Logged |
|
|
|
kcb2xxx
Newbie
Posts: 4
|
|
Re: A problem of weights...
« Reply #2 on: Jun 17th, 2005, 8:13pm » |
Quote Modify
|
What happens when 2k is greater than totalweight?
For example the weights are {1,3, 5} and k=8?
total weight=9 and 2k=16?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A problem of weights...
« Reply #3 on: Jun 17th, 2005, 11:58pm » |
Quote Modify
|
on Jun 17th, 2005, 8:13pm, kcb2xxx wrote:| What happens when 2k is greater than totalweight? |
|
Then IMHO adding 2k-totalweight would work.
A really bright idea, Grimbal! 
|
|
IP Logged |
|
|
|
kcb2xxx
Newbie
Posts: 4
|
|
Re: A problem of weights...
« Reply #4 on: Jun 18th, 2005, 12:38am » |
Quote Modify
|
Lol, yeah, I figured that out after a while . Thanks a lot guys... But what's the funda behind it that makes it work? Any explanations?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A problem of weights...
« Reply #5 on: Jun 18th, 2005, 6:01am » |
Quote Modify
|
| hidden: |
Lets call T the total weight
Assuming k <= T/2, the problem is to split T = A+k.
To use the split() function, we add a stone to make the second part equal to A. So, we add S = (A-k) which is T-2k.
If we can split T into A and k, then we can split T+S into 2 equal parts, namely A and k+S.
Inversely, if we can split T+S into 2 equal parts, T+S weighing T+T-2k, one half is T-k. Removing the stone S from the one part gives (T-k) - (T-2k) = k, so we have a split of T into (T-k) and k.
As mentionned earlier, if k is larger than half T, then we can apply the same reasoning with k'=(T-k).
And of course, if k>T, you can not split it.
|
|
|
IP Logged |
|
|
|
kcb2xxx
Newbie
Posts: 4
|
|
Re: A problem of weights...
« Reply #6 on: Jun 18th, 2005, 10:58am » |
Quote Modify
|
So basically if k<T/2 then its T-2k and if k>T/2 its 2k-T?
Thanks a lot again.
Regards
kcb.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A problem of weights...
« Reply #7 on: Jun 18th, 2005, 12:23pm » |
Quote Modify
|
and if k=T/2 it is still easier!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print