Author |
Topic: Forged Bags' Quick Identification (Read 3678 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Forged Bags' Quick Identification
« on: Oct 18th, 2003, 7:46am » |
 Quote  Modify
|
There are 10 bags, each containing the same number N of coins. Some bags contain only true coins, while others contain only forged coins. All true coins have the same weight; all forged coins also have the same weight. Both weights are known.
There is also a high precision scales available - using it, it is possible to get the weight of any number of coins at once.
What is the minimal N such that it is possbile to identify all the forged bags by just one weighting?
Additional question: generalize to an arbitrary number of bags.
|
|
 IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Forged Bags' Quick Identification
« Reply #1 on: Oct 18th, 2003, 9:32am » |
Quote Modify
|
I think it's already on the site somewhere.
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Forged Bags' Quick Identification
« Reply #2 on: Oct 18th, 2003, 12:30pm » |
Quote Modify
|
on Oct 18th, 2003, 9:32am, BNC wrote:| I think it's already on the site somewhere. |
|
BNC, could you please provide a link to the corresponding thread? Thanks...
|
|
IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Forged Bags' Quick Identification
« Reply #3 on: Oct 18th, 2003, 4:21pm » |
Quote Modify
|
I just searched for it, without luck....
Hmm. I guess I made a mistake. Sorry.
I'll give it this try: N=2[(number of bags)-1].
|
| « Last Edit: Oct 18th, 2003, 5:20pm by BNC » |
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Forged Bags' Quick Identification
« Reply #4 on: Oct 18th, 2003, 6:10pm » |
Quote Modify
|
How about a link to the puzzle itself?
The wording is different, but the same solution applies - except in your version there are a few more exceptions, I believe.
|
|
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
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Forged Bags' Quick Identification
« Reply #5 on: Oct 18th, 2003, 10:00pm » |
Quote Modify
|
Icarus,
While the puzzles are similar, I beleive the solution are different. I be more precise, the solution to this puzzle would fit the other, but not the other way around.
The "canonical" answer to the other puzzle calles for using n coins from the n'th machine. This will not work here; if, for example, you'll find the weight differes by 3d (d is the diff beween the true and forged coins), you can't tell if machine 3 is bad or both 1 and 2.
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Forged Bags' Quick Identification
« Reply #6 on: Oct 19th, 2003, 1:49am » |
Quote Modify
|
BNC is right regarding the apparent similiarity of the puzzles. The "COIN MACHINE WEIGHING" asks for identifying the only forged machine, while this puzzle asks to identify the arbitrary number of forged bags.
BNC, your answer is correct, but it's not optimal. After all, I put this puzzle in the HARD section, and I still think I was right.
Hint: For 10 bags, N is far less than 512.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Forged Bags' Quick Identification
« Reply #7 on: Oct 19th, 2003, 7:11pm » |
Quote Modify
|
I have managed to solve the problem completely for numbers of bags, B<6, including finding all "optimal" weighings for B<5. For all B, I have found a class of weighings that improves on the classic binary approach (where the binary isn't itself optimal).
My known optimal weighings are (for up to 5 bags)
::
{1}
{1,2}
{1,2,4} or {2,3,4}
{3,5,6,7}
{6,9,11,12,13}
::
and weighings giving upper bounds for 6-10
::
{11,17,20,22,23,24}
{22,33,39,42,44,45,46}
{42,64,75,81,84,86,87,88}
{84,126,148,159,165,168,170,171,172}
{165,249,291,313,324,330,333,335,336,337}
::
And the derivation of those upper bounds (which will also hopefully allow people to correct any errors in my working)
::
I started with the assumption (probably unjustified for large enough B) that for any two possible sets of bags of counterfeit coins, the weighing which produces a larger discrepancy represents the larger set. Given that, it makes sense to represent the weighing as a set of offsets ak from some constant value, cB, so for bag k of B, you weigh ak+cB coins. This divides the problem into two parts: finding a sequence {ak} such that no two finite subsets of the same size have the same sum, and finding corresponding values cB, the least values such that for any two subsets of {a1,...,aB} the difference between their sums is strictly less than cB times the difference in their sizes.
My solutions are then worked out inductively, using the following formulae:
a1=0
c1=1
ak=-ck-1
ck=Sumki=floor((k+1)/2)ai-Sumi=floor((k-1)/2)i =1ai+1
Actually, I used a lengthy process of tabulation to find the ck, but since it effectively involved considering the extreme values of the middle rows of the table each time, the above equation is equivalent (and hopefully faster)
::
I suspect that my upper bounds are possible to improve upon.
As a quick side problem, can anyone identify (with proof) the weighing strategy that uses fewest coins overall? In other words, what's the minimal number of coins you need to be able to fit onto the scales to still be able to identify all bags of counterfeit coins in a single weighing? (as a function of B in the general case)
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Forged Bags' Quick Identification
« Reply #8 on: Oct 20th, 2003, 2:53am » |
Quote Modify
|
on Oct 19th, 2003, 7:11pm, rmsgrey wrote:| I have managed to solve the problem completely for numbers of bags, B<6, including finding all "optimal" weighings for B<5. For all B, I have found a class of weighings that improves on the classic binary approach (where the binary isn't itself optimal). |
|
Bravo, rmsgrey! An excellent analysis. Here are a few comments:
Under your assumption (about the relation between the order of the set and its weight) your solution is optimal. It may be shown that it improves the binary approach by a factor of 0.6333… when B tends to infinity. The advantage of this assumption is that it allows decoding the weighting result in linear time.
Quote:| I suspect that my upper bounds are possible to improve upon. |
|
They can be improved only if your assumption is relaxed. Then, for instance, for B=10 the bags may contain as few as 308 coins. The class of sequences exists with the limiting improvement factor 0.4703… However, in this case the decoding will generally take exponential time.
By the way, both your weighting scheme and the one mentioned by me, are just the special cases of a general double-recurrent scheme proposed by Conway and Guy in late 1960’s. I will elaborate on it in one of my next posts.
Quote:| As a quick side problem, can anyone identify (with proof) the weighing strategy that uses fewest coins overall? In other words, what's the minimal number of coins you need to be able to fit onto the scales to still be able to identify all bags of counterfeit coins in a single weighing? (as a function of B in the general case) |
|
Hmm, that’s an interesting question… My guess: 2B - 1. Without proof, however…
|
| « Last Edit: Oct 20th, 2003, 2:54am by Barukh » |
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Forged Bags' Quick Identification
« Reply #9 on: Oct 20th, 2003, 4:33am » |
Quote Modify
|
I must admit that I avoided some of the details of your earlier posts, but it seems to me that you do not take into account that you know the weight difference of the two types of coin. Thus, with an appropriate number of bags and weight differential the optimum strategy should reduce to N as in the easier version of this problem. Your solutions seems to take the general case where you do not know the differential (at least until after you have weighed the bags).
|
|
IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Forged Bags' Quick Identification
« Reply #10 on: Oct 20th, 2003, 5:52am » |
Quote Modify
|
on Oct 19th, 2003, 1:49am, Barukh wrote: The "COIN MACHINE WEIGHING" asks for identifying the only forged machine, while this puzzle asks to identify the arbitrary number of forged bags.
|
|
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Forged Bags' Quick Identification
« Reply #11 on: Oct 20th, 2003, 8:47am » |
Quote Modify
|
on Oct 20th, 2003, 2:53am, Barukh wrote:
Hmm, that’s an interesting question… My guess: (...). Without proof, however…
|
|
That's the right answer, and the proof isn't hard.
Big Hint:
::each outcome needs a unique number of forged coins::
|
|
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Forged Bags' Quick Identification
« Reply #12 on: Oct 20th, 2003, 12:30pm » |
Quote Modify
|
Yes, of course, I see now.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Forged Bags' Quick Identification
« Reply #13 on: Oct 24th, 2003, 3:33am » |
Quote Modify
|
No further improvements to my actual numbers, but I've managed to come up with a simpler form for the recursive formulaI use to generate them.
::
The sequence of largest number of coins used from a single bag, cn is given by:
c0=0
cn+1=2*cn-cceiling(n/2)
As before, the offsets to generate the explicit weighing come from the same sequence, with the same formulae.
::
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Forged Bags' Quick Identification
« Reply #14 on: Oct 26th, 2003, 11:41am » |
Quote Modify
|
rmsgrey, it's amazing how close have you come to the essence... Here is a brief history of the problem.
[smiley=blacksquare.gif]
As rmsgrey correctly noticed, the problem reduces to finding the sequence of numbers a1, a2, …, aN, such that all the partial sums are distinct. Such a sequence is called SSD (abbreviate of subset-sum-distinct). The sequence of 2s powers is an example of a trivial SSD.
Paul Erdos was the first to study this in early 1930s. He gave lower bounds for aN. Then in 1967, John Conway and Richard Guy developed a scheme to generate a non-trivial SSD for every n. Here’s the algorithm:
1. Define the sequence {ui, i = 1,…,n} as follows: u0 = 0, u1 = 1, ui+1 = 2ui - un-m, where m = f(i) (see below),
2. Build the sequence ai = un - un-i, i = 1, …, n.
f(i) = [smiley=lfloor.gif]i/2[smiley=rfloor.gif] +1 leads to rmsgrey’s solution (I wonder, why there is a slight difference between this and rmsgrey’s formula). Conway & Guy used f(i) = integer closest to [sqrt](2i), which generally gives better results (i = 10 corresponds to a10 = 308 ).
It is interesting that Conway & Guy didn’t prove that their scheme produces SSD for arbitrary n. This was proved only in 1995.
[smiley=blacksquare.gif]
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print