Author |
Topic: Weighing Discs (Read 607 times) |
|
Margit
Guest
|
Not original and a variation on the 12 balls problem.
A nephew that I didn't know I had turned up over Christmas.
On asking him when his birthday was, he handed me 366 discs each one inscribed with a month/day so representing all possible days in a year. He also handed me a 2 pan weighing scale.
He then stated - "The disc representing my birthday is of a different weight to the rest of the discs (which have the same weight)"
He also stated "I was born in 1990".
What is the minimum number of weighings necessary to determine my nephew's birthday ?
|
|
 IP Logged |
|
|
|
MisatoAeris
Newbie
I'm just a little girl, I can't hurt you...
Gender: 
Posts: 20
|
 |
Re: Weighing Discs
« Reply #1 on: Jan 1st, 2005, 12:47pm » |
 Quote  Modify
|
If you are somehow incredibly lucky and just happen, on your first pick, to choose the correct disc, then 2 weighings.
1) weigh the correct (though you don't know it yet) disc and another one.
2).To find out which is different from the rest, lucky you pick the correct one again and some other random disc, weigh them, and voila! you know which one is different.
I, of course, may very possibly have erred, and not read the question properly. The answer may be something totally different, and one I do not have the time to ponder.
You, also, just may not be very lucky, and have to weigh the discs 366 times.
|
| « Last Edit: Jan 1st, 2005, 12:48pm by MisatoAeris » |
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
|
Re: Weighing Discs
« Reply #2 on: Jan 1st, 2005, 1:45pm » |
Quote Modify
|
The question asks for the number of weighings necessary in order be sure of identifying the different disc.
See the 12 Ball problem for an idea of what is required.
|
| « Last Edit: Jan 1st, 2005, 3:10pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Weighing Discs
« Reply #3 on: Jan 2nd, 2005, 12:32pm » |
Quote Modify
|
Who cares when the snot's birthday is? If this is how he answers a simple question, he doesn't deserve any gifts.
The only significance I can see in the year of his birth is that it wasn't a leap year, so you can rule out the Feb 29 marker immediately. But I don't see that this reduces the max number of weighings.
My strategy:
Divide the coins into 3 groups of 122 each. Compare two of the groups, then another 2. If in both cases the weight was unequal, then the desired disc is in the twice-weighed group. Else, it will the single-weighed group from the unequal weighing. In either case, you also now know if the disc is heavier or lighter than the rest (by whether or not its group was lighter or heavier than the others.) Discard the other two groups. Then repeat the following procedure until the coin is found:
Divide into 3 parts again, as evenly as possible. Two of the groups will always have the same number of coins. Weigh these two groups, and take the heavier or lighter one (according to whether the disc is heavy or light). If they are the same weight, choose the third group to continue with.
This will determine the correct disc in a maximum of 7 weighings (and a minimum of 6).
|
|
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
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Weighing Discs
« Reply #4 on: Jan 3rd, 2005, 3:14am » |
Quote Modify
|
According to the generalized 12-ball problem, you would need only 6 weighting with 363 disks. Just not enough.
PS: This means I agree with the solution given above.
|
| « Last Edit: Jan 3rd, 2005, 3:19am by Grimbal » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Weighing Discs
« Reply #5 on: Jan 3rd, 2005, 9:43am » |
Quote Modify
|
on Jan 1st, 2005, 12:47pm, MisatoAeris wrote:If you are somehow incredibly lucky and just happen, on your first pick, to choose the correct disc, then 2 weighings.
1) weigh the correct (though you don't know it yet) disc and another one.
2).To find out which is different from the rest, lucky you pick the correct one again and some other random disc, weigh them, and voila! you know which one is different.
|
|
You can do better than that in trusting to luck - the absolute best case is a single weighing: his birthday against the 29th of Feb.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Weighing Discs
« Reply #6 on: Jan 3rd, 2005, 10:07am » |
Quote Modify
|
Aha!
The nephew is born in 1990, which is NOT a leap year.
So, you have 365 possibilities, and the disk marked Feb 29 can be used as a reference weight, because it is known to be standard weight.
Now 6 weighings can offer 729 issues. But you have 2*365 = 730 possibilities, so you can not distinguish them all. But then, you are not required to tell whether the coin is too heavy or too light. So that it could be there is a solution, after all...
|
| « Last Edit: Jan 3rd, 2005, 10:08am by Grimbal » |
IP Logged |
|
|
|
Margit
Guest
|
Grimbal, the number of discs you propose would be correct if I needed to know if the disc was lighter or heavier. However I only need to identify the disc.
Furthermore :
Consider just 1 weighing. How many discs can I have and still determine a bad disc. The answer is 1 (the bad disc itself) which is the same as 0 weighings.
However, if I  ??, then I could ?
|
|
IP Logged |
|
|
|
Margit
Guest
|
Ah, missed Grimbals last post.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Weighing Discs
« Reply #9 on: Jan 3rd, 2005, 1:37pm » |
Quote Modify
|
OK, I think I got the solution in 6 weighings.
By the way, whenever I said "coin", I meant "disc".
::
Split the 366 discs into 3 sets of groups of 81, 27, 9, 3, 1, 1.
81+27+9+3+1+1 = 122. Call these A, B, C.
Call the groups A81, A27, A9, A3, A1, A0 (still with 1 disc), same for B81, B27, ... and C81, ... C1, C0
Use Feb 29 disc for A0.
- Weight the whole set A (left) and set B(right)
- Rotate the 81-groups, i.e. remove A81 from left pane, move B81 from right to left and add C81 to right pane.
- At this point, if the result is different, you know that the bad disc has moved, so it is in the 81-groups. In fact, you can tell which one it is, and even whether it is heavier or lighter. I'll leave this to the reader to prove. With this, you have 4 weighing left to find the biased disc among 81. You can find it doing a ternary search: split the heap in 3, weight 2 of them, if they don't balance you know which is heavier or lighter, if they do balance, the 3rd heap is the biased one. Do it 4 times and you are done.
- If between weighing 1 and 2 nothing changed, you know that the 81-groups are all standard, you can eliminate them. You know, without weighing, that removing these won't change the result of the weighing. So, without actually weighing again, you know the result of weighing the sets with the 81-groups removed.
- 3rd weighing: rotate the 27-groups as before and weight.
Again, if something changes, you can identify the special 27-group and you know how it differs. You have 3 weighings left to find the special disc, which is just perfect.
- If the result does not change with the 27-groups, remove them and rotate the 9-groups. If it changes now, you can pick one 9-group and you have 2 weighings to identify one of the 9 discs.
- If there is still no change with the 9-groups, rotate the 3-groups. If it changes, you have 1 weighing left to identify the special one among 3. If not, as before, remove the 3-discs.
If you reach here, you did 5 weighings and you have 6 1-groups left. A1 and A0 left, B1 and B0 right, and C1 and C0 off the scale. From the previous weighing, you know what would be the result of weighing these.
- Last weighing: rotate the 1-groups A1, B1, C1 and weight again. If the result changes, you can identify the one disc that has a different weight.
- Last, if the result has never changed, you know that the special disc is among B0 or C0. A0 is known to be standard. But you have no more weighing left! Luckily, you know the result of weighing A0 and B0. It is the same as with the 1-groups included, and, in fact, the same result as the one you got for all weighings. So, if all these weighings did balance, it means A0 equals B0 and therefore the special disc is C0. If they don't balance, it is B0 that is special.
Only for C0 you won't know whether it was lighter or heavier. In fact, you never put it on the scale.
::
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Weighing Discs
« Reply #10 on: Jan 5th, 2005, 11:20pm » |
Quote Modify
|
I don't know about the others, but I am really impressed with this ingenious Grimbal solution!
A very interesting problem with several subtle points. Thanks Margit for posting it!
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: Weighing Discs
« Reply #11 on: Jan 6th, 2005, 8:10am » |
Quote Modify
|
I'm particularly impressed by the way the answer is so obvious (with hindsight) - usually the mark of a particularly good problem - the way you think "I should have seen that" afterwards...
|
|
IP Logged |
|
|
|
Margit
Guest
|
Here is a small follow up.
It's known that the maximum number of discs whereby you can determine if one disc is lighter or heavier in "n" weighings is given by the formula (3n-3)/2.
And, for just detection by .. well you tell me 
Now I wonder if there is a formula for when we have the situation as in this puzzle? Moreover, is there a formula for when we need to detect lighter/heavier ?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Weighing Discs
« Reply #13 on: Jan 7th, 2005, 1:19am » |
Quote Modify
|
If you just have to find the special disk, it is one more. (weight the rest, if you don't locate the special disk, it is the extra one).
If you have one reference disk it is 2 more, as per my method (add the reference disc and one extra disc on the panes, if nothing moves, you can discriminate between the extra disc you weighted and the other extra disc). If you also count the reference disk, it is 3 more.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove