wu :: forums - Print Page


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

        riddles >> medium >> Weighing Discs
        
(Message started by: Margit on Jan 1^st, 2005, 3:14am)

Title: Weighing Discs
Post by Margit on Jan 1^st, 2005, 3:14am

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 ?

Title: Re: Weighing Discs
Post by MisatoAeris on Jan 1^st, 2005, 12:47pm

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.

Title: Re: Weighing Discs
Post by THUDandBLUNDER on Jan 1^st, 2005, 1:45pm

The question asks for the number of weighings necessary in order be sure of identifying the different disc.
See the 12 Ball problem (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1050065099;start=0) for an idea of what is required.

Title: Re: Weighing Discs
Post by Icarus on Jan 2^nd, 2005, 12:32pm

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: [hide]
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).[/hide]

Title: Re: Weighing Discs
Post by Grimbal on Jan 3^rd, 2005, 3:14am

According to the generalized 12-ball problem, you would need only [hide]6[/hide] weighting with [hide]363[/hide] disks. Just not enough.

PS: This means I agree with the solution given above.

Title: Re: Weighing Discs
Post by rmsgrey on Jan 3^rd, 2005, 9:43am

on 01/01/05 at 12:47:18, MisatoAeris wrote:

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.

Title: Re: Weighing Discs
Post by Grimbal on Jan 3^rd, 2005, 10:07am

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

Title: Re: Weighing Discs
Post by Margit on Jan 3^rd, 2005, 10:48am

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 :
[hide]
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 ????
[/hide]

Title: Re: Weighing Discs
Post by Margit on Jan 3^rd, 2005, 10:50am

Ah, missed Grimbals last post.

Title: Re: Weighing Discs
Post by Grimbal on Jan 3^rd, 2005, 1:37pm

OK, I think I got the solution in 6 weighings.

By the way, whenever I said "coin", I meant "disc".

::[hide]
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.
[/hide]::

Title: Re: Weighing Discs
Post by Barukh on Jan 5^th, 2005, 11:20pm

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!

Title: Re: Weighing Discs
Post by rmsgrey on Jan 6^th, 2005, 8:10am

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

Title: Re: Weighing Discs
Post by Margit on Jan 6^th, 2005, 11:23am

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 [hide](3ⁿ-3)/2[/hide].
And, for just detection by .. well you tell me ;D

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 ?

Title: Re: Weighing Discs
Post by Grimbal on Jan 7^th, 2005, 1:19am

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.