mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2005-02-22, 22:55   #1
biwema
 
biwema's Avatar
 
Mar 2004

3·127 Posts
Default 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?
biwema is offline   Reply With Quote
Old 2005-02-22, 23:11   #2
coolprimes
 
Dec 2004

A16 Posts
Default

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
coolprimes is offline   Reply With Quote
Old 2005-02-22, 23:25   #3
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

100010000012 Posts
Default

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.
Wacky is offline   Reply With Quote
Old 2005-02-22, 23:26   #4
coolprimes
 
Dec 2004

2·5 Posts
Default

Opps You're right.
coolprimes is offline   Reply With Quote
Old 2005-02-22, 23:31   #5
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2×112×37 Posts
Default

FYI: 1990 had only 365 days, therefore Feb 29 can be used as a fill (null) disk.
Uncwilly is offline   Reply With Quote
Old 2005-03-02, 07:19   #6
axn
 
axn's Avatar
 
Jun 2003

2×5×479 Posts
Default

So, I've figured out how to do it in six weighings. Anybody wants to know ??
axn is offline   Reply With Quote
Old 2005-03-02, 09:58   #7
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

5×19×29 Posts
Default

yeah sure. i bet there are many other lazy ones like me who would like to know the answer.
garo is offline   Reply With Quote
Old 2005-03-03, 08:33   #8
axn
 
axn's Avatar
 
Jun 2003

2×5×479 Posts
Default

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 !!
axn is offline   Reply With Quote
Old 2005-03-21, 22:59   #9
biwema
 
biwema's Avatar
 
Mar 2004

1011111012 Posts
Default

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.
biwema is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 01:44.

Sun Dec 6 01:44:24 UTC 2020 up 2 days, 21:55, 0 users, load averages: 2.55, 2.55, 2.56

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.