Discs

biwema · 2005-02-22, 22:55

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?

coolprimes · 2005-02-22, 23:11

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

Wacky · 2005-02-22, 23:25

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.

coolprimes · 2005-02-22, 23:26

Opps

You're right.

Uncwilly · 2005-02-22, 23:31

FYI: 1990 had only 365 days, therefore Feb 29 can be used as a fill (null) disk.

axn · 2005-03-02, 07:19

So, I've figured out how to do it in six weighings. Anybody wants to know ??

garo · 2005-03-02, 09:58

yeah sure. i bet there are many other lazy ones like me who would like to know the answer.

axn · 2005-03-03, 08:33

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

biwema · 2005-03-21, 22:59

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.

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 2×5 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Three discs	XYYXF	Puzzles	5	2008-11-27 20:49

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 2498₁₆ 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 2³·607 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 AC7₁₆ 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 2³·607 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.