mersenneforum.org Discs
 Register FAQ Search Today's Posts Mark Forums Read

 2005-02-22, 22:55 #1 biwema     Mar 2004 3·127 Posts Discs 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? What it the algorithm?
 2005-02-22, 23:11 #2 coolprimes   Dec 2004 128 Posts I think the answer is 6 weighings. On the first, you take one third on one side, one third on the other, and leave one third off. If one side weighs down more, that is the side that has the extra disk, and if none weighs down, then the pile not put on the scale is correct. You keep doing this, but when you have a pile not divisalbe by 3, you have the extra in the pile not on the scale. Taking the that has the most each time (worst case scenero) you get six weighings. Note: I put the answer in a spoiler Last fiddled with by coolprimes on 2005-02-22 at 23:16
2005-02-22, 23:25   #3
Wacky

Jun 2003
The Texas Hill Country

108210 Posts

Quote:
 Originally Posted by coolprimes If one side weighs down more, that is the side that has the extra disk, and if none weighs down, then the pile not put on the scale is correct.
Close but ....

Note that he states
Quote:
 The disc representing my birthday is of a different weight
. As a result, if one side is heavier, it may be caused by either (1) there is a heavy disc in that batch, or (2) there is a light disc on the other side.

 2005-02-22, 23:26 #4 coolprimes   Dec 2004 2·5 Posts Opps You're right.
 2005-02-22, 23:31 #5 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 7×29×43 Posts FYI: 1990 had only 365 days, therefore Feb 29 can be used as a fill (null) disk.
 2005-03-02, 07:19 #6 axn     Jun 2003 23×19×31 Posts So, I've figured out how to do it in six weighings. Anybody wants to know ??
 2005-03-02, 09:58 #7 garo     Aug 2002 Termonfeckin, IE 47168 Posts yeah sure. i bet there are many other lazy ones like me who would like to know the answer.
 2005-03-03, 08:33 #8 axn     Jun 2003 23×19×31 Posts Okay. You start out as coolprimes did. You split the discs into three piles. You take one third (122) on one side, one third on the other, and leave one third off. Make sure that Feb 29 is on one of the piles that is getting weighed. Assume that the scales do not balance (the case of a balanced weighing is left to the reader as an exercise ) Lets call the piles L and R (for Left & Right). Let the Feb 29 disc be on the L pile. Let the result be a Left-tilt of the scale (meaning L pile has a heavier disc Or R pile has a lighter disc) So we have 121 (122 minus Feb 29) discs on L pile and 122 discs on R pile of unknown status. Split each of the piles into 3 groups in the following way: | 1 | 2 | 3 --+---+---+--- L |40 |40 |41 --+---+---+--- R |41 |41 |40 Now weigh the 81 discs from group 1 against 81 from the group 2. (Weighing # 2) If it balances, the unknown disc is in group 3 (ie, L3 or R3). If it tilts to left, the unknown disc is in L1 or R2 (why R2, and not R1?) Like-wise, if it tilts to right, the unknown disc is in L2 or R1. In any case, you end up with an uncertain group of L41, R40 or L40, R41. Notice the asymmetry in size (3n+1, 3n+2) for this new group (and compare against the asymmetry of L121, R122) Repeat the process: Weighing # 3: Groups of 13 or 14 will be involved in comparisons (41 = 14 + 14 + 13, 40 = 13 + 13 + 14) Weighing # 4: Groups of 4 or 5 will be involved in comparisons (13 = 4 + 4 + 5, 14 = 5 + 5 + 4) Weighing # 5: Groups of 1 or 2 will be involved in comparisons (4 = 1 + 1 + 2, 5 = 2 + 2 + 1) Weighing # 6: Groups of 0 or 1 will be involved in comparisons (1 = 0 + 0 + 1, 2 = 1 + 1 + 0) Thus after 6 weighings, you have the answer !!
 2005-03-21, 22:59 #9 biwema     Mar 2004 3×127 Posts Well done, correct. By the way, you need the normal disc 'Feb29' as Uncwilly suggested. If you had just 365 discs, the 6-solution wouldn't always work.