Author |
Topic: Dud bullets (Read 1125 times) |
|
astaroth
Newbie
Gender: 
Posts: 3
|
 |
Dud bullets
« on: Aug 31st, 2006, 1:03am » |
 Quote  Modify
|
Hi Riddlers. For my debut, an awesome riddle, which took me weeks to solve  (I hope it's not already somewhere here, though I searched for it)
In a police storehouse there is a certain amount of ammunition boxes containing 8 identical bullets each.
A terrible mistake has been made today - someone has mistakenly put a box of false bullets among others. Duds are all identical, but are slightly lighter than normal bullets - good balance should show the difference. You happen to have one in your department - it has two scales and can show exact value of weight difference between them.
You decide to find the box of duds in no more than 3 weightings. What is the maximum number of ammo boxes in the storehouse allowing you to deal with this task?
|
|
 IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Dud bullets
« Reply #1 on: Aug 31st, 2006, 1:18am » |
Quote Modify
|
27 is doable, but is it optimal? Method:
| hidden: | Divide the 27 boxes in three groups of 9. Weigh two groups against eachother. If they balance, the lighter box is in the third group; otherwise, it is obviously in the lighter group.
9 boxes left. Divide them in three groups of 3 and proceed as above.
3 boxes left. Same thing: put two of them on the balance. If they balance, it's the other one; otherwise, it's the lighter one.
Depending on the capacity of your balance, you could replace each box by one bullet taken from it - remembering where it came from, of course. |
This method gives a maximum of 3n boxes in n weighings.
|
|
IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Dud bullets
« Reply #2 on: Aug 31st, 2006, 3:38am » |
Quote Modify
|
48 is also possibel, but I think it should be possible to improve, because one weighting is waisted on finding the weight of the bullet. It also gives the weight of the dud, which is not required.
Method:
| hidden: |
Divide the boxes into 3 subgroups of 16 each. Call them groups a, b, and c.
(weighting 1): weight a vs. b
According to this, you know with group contains the duds.
(weighting 2): weight a single good bulltet. Mark results.
(weighting 3): in the light group, separete into two sub-gruops of 8. From each sub-group take 1 bullet from 1st box, 2 from 2nd, etc. until 8 from 8th box. Weight against each-other. The diference should tell you with box has dudes, as well as the weight of the dud.
|
If you simply forgot to mention it, and the weight of both good and bad bullets in known in advance, this may be improved to 144.
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Dud bullets
« Reply #3 on: Aug 31st, 2006, 4:22am » |
Quote Modify
|
Ah... I missed the fact that the balance shows the weight difference... 
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Dud bullets
« Reply #4 on: Aug 31st, 2006, 4:27am » |
Quote Modify
|
on Aug 31st, 2006, 3:38am, BNC wrote:| The diference should tell you with box has dudes, as well as the weight of the dud. |
|
But how to we distinguish 1 dud weighing two grams less, from 2 duds each weighing one gram less than a regular bullet?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: Dud bullets
« Reply #5 on: Aug 31st, 2006, 6:11am » |
Quote Modify
|
I reckon you can get up to 615 boxes without knowing the weight difference to start with (assuming the scale-pans are big enough to hold 612 bullets, and you have some way of tracking which bullet comes from which box...)
| hidden: |
Weighing 1: take 1 bullet each from 289 boxes for the left pan, and 1 bullet each from another 289 boxes for the right pan, leaving 37 boxes unrepresented.
If the scale balances:
Weighing 2: take 1 bullet each from 17 of the untested boxes for the left pan, and 1 bullet each from another 17 untested boxes for the right pan, leaving 3 bullets untested.
If the scale balances again:
Weighing 3, weigh one untested box against another untested box, leaving one box untested. Balance means that the untested box is lighter; imbalance that the lighter box is lighter...
If the scale doesn't balance for both the first two weighings, then the difference in weight between the two sides the first time it fails to balance is the difference between the weight of a live bullet and that of a dud.
If the first weighing doesn't balance:
Weighing 2: take the group of 289 boxes that includes the duds, and divide them into 17 groups of 17 boxes. Take all 8 bullets from each of the first group, 7 bullets from each of the second, 6 from the third and so on down to 1 bullet each from the 8th group and put them on the left pan, and do similarly with another 8 groups for the right pan. The difference in weights compared to the shortfall of a single dud bullet will tell you which group contains the duds.
If either of the first two weighings doesn't balance:
Weighing 3: Take the 17 boxes that could be duds, and weigh 8 from the first, 7 from the second, etc against a similar pattern from another 8 boxes. Again, the difference in weight tells you which box is dud. |
I'm reasonably sure that's the theoretical maximum when you don't know the weight difference to start with. If you do know, then I reckon you can handle 4913 boxes (weighing up to 10404 bullets on each side):
| hidden: | Split into 17 equal groups and label them -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8 - put the appropriate number of bullets from each box in each group on one pan (negative numbers just mean putting that many bullets on the other pan instead). The difference in weight divided by the weight difference between live rounds and duds tells you which group the duds are in. Discard the other groups and repeat.
After 3 weighings, you'll be down to one box. |
Proof of optimality:
| hidden: |
With the difference in weight known (call it 1 unit), it's possible to distinguish 17 different outcomes for a single weighing (left side 8 units lighter, 7 lighter, 6, 5, 4, 3, 2, 1 unit lighter, both balanced, left side 1 unit heavier, 2 heavier, 3, 4, 5, 6, 7, 8 units heavier) so each weighing once the difference is know lets you divide the remaining boxes into 17 groups.
With the difference in weight unknown, there are only 3 distinguishable outcomes (left lighter, balanced, left heavier) of which two can also tell you the weight difference, so each weighing before the difference is know lets you divide the remainign boxes into 3 groups - 2 which can then be divided into 17 groups for subsequent weighings and one that can only be divided into 3 groups for the next weighing.
So with the weight difference known: 0 weighings will allow you to pick out the duds with 1 possibility; 1 weighing will let you pick out the duds from 17 possibles; 2 from 289; and 3 from 4913.
With the weight difference unknown: 0 weighings again lets you pick the dud box from 1 box remaining; 1 weighing lets you pick out the dud from 3; 2 from 17+17+3=37; and 3 from 289+289+37=615. |
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Dud bullets
« Reply #6 on: Aug 31st, 2006, 8:14am » |
Quote Modify
|
on Aug 31st, 2006, 6:11am, rmsgrey wrote:
With the difference in weight unknown, there are only 3 distinguishable outcomes (left lighter, balanced, left heavier) of which two can also tell you the weight difference, so each weighing before the difference is know lets you divide the remainign boxes into 3 groups - 2 which can then be divided into 17 groups for subsequent weighings and one that can only be divided into 3 groups for the next weighing. |
|
The problem with this argument is that the weighings give you more information that just which side is heavier, even if you don't know what to do with it immediately. So, while one weighing can certainly not find the dud box with more than 3 boxes, with multiple weighings, the combined information gives you more than what you would know from each weighing in isolation.
The maximum number of boxes you can handle is 4035, modulo possible arithmetic errors.
The solution:
| hidden: |
For each box, there are essentially 17 things we can do with it on each weighing: we can put 1 to 8 bullets on the left scale, for which we will assign the box a number -1 to -8; we can put 1 to 8 bullets on the right scale, for which we assign a number 1 to 8; or we can leave the bullets off, for which we assign 0. The three weighings give each box three numbers, and we define the set Sa,b,c, -8 <= a,b,c <= 8, as the set of boxes which are assigned the numbers a,b,c on the three weighings.
As rmsgrey has already posted, for us to discover which box is a dud in all cases, none of the sets Sa,b,c can have more than one box in it; if a particular Sa,b,c has two or more boxes, than if the weighing actually turns out to be (a,b,c), we won't know which of the boxes in Sa,b,c is the box with the duds. If we know the difference in weight between a regular bullet and a dud in advance, than we will know precisely which weighing (a,b,c) we actually measure, and the condition of none of the Sa,b,c having more than one box is a sufficient one. So the answer in this case is indeed 173 = 4913 boxes, with the solution being to put one box in each Sa,b,c.
But what about when we don't know the the difference in weight is in advance? In this case, we cannot distinguish weighings (a,b,c) and (d,e,f) if there is a rational number r such that d = ra, e = rb, and f = rc. So we define an equivalence relation for when this occurs; we would like to count the number of equivalence classes under this relation. For each such class, there is a unique weighing (a,b,c) such that a, b, and c are relatively prime, and the elements of the class are the weighings of the form (na, nb, nc) for positive integers n. So we would like to count the number of triples (a,b,c), -8 <= a,b,c <= 8, with (a,b,c) relatively prime. (Note that (0, 0, 0) is in an equivalence class all to itself, so we will include this in our set as well.)
Let C be the entire set of weighings, and let Cp be the set of weighings (a,b,c) where p | a,b,c. Let N be the set C \ C2 \ C3; by the principle of inclusion/exclusion,
|N| = |C| - |C2| - |C3| + |C2 int C3|
= |C| - |C2| - |C3| + |C6|
= 173 - 93 - 53 + 33
= 4086
We also want to get rid of C5 and C7; but we don't want to subtract off (0,0,0), in fact we need to add it back, so our final set S has
4086 - (C5 - 1) - (C7 - 1) + 1
= 4086 - (33 - 1) - (33 - 1) + 1
= 4035
elements.
It's clear that if we can manage to send one box to each equivalence class, we have our solution; the weighings will determine which equivalence class our box belongs to, and there will only be one such box. The only possible problem is making sure that there are an equal number of bullets on each side of the scale for all three weighings. The way to do it is to assign the boxes symmetrically; the obvious choice is to assign one box to each Sa,b,c with a,b,c relatively prime. Then Sa,b,c will get a box if and only if S-a,b,c gets a box, so the number of bullets on each side will be equal for the first weighing; we argue similarly for the second and third weighings. So we have a solution with 4035 boxes.
|
|
| « Last Edit: Aug 31st, 2006, 8:18am by Deedlit » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Dud bullets
« Reply #7 on: Aug 31st, 2006, 3:10pm » |
Quote Modify
|
I checked the calculations.
| hidden: |
The trick it to count all sets (a,b,c) where gcd(a,b,c)=1 or 0 (with the rule that gcd(...)>=0, gcd(0,x)=x and gcd(0,0) = 0.
I ran a small computer program and found 4035. If you don't know whether they are lighter or heavier then the factor r can be negative and you have to halve the cases (except for the special case (0,0,0)) giving 2018.
|
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Dud bullets
« Reply #8 on: Sep 1st, 2006, 3:57am » |
Quote Modify
|
Nicely done! 
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: Dud bullets
« Reply #9 on: Sep 1st, 2006, 8:27am » |
Quote Modify
|
Bother!
Oh well, at least mine is simpler to actually implement...
(and the grapes are probably sour anyway... )
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print