## Welcome to BrainDen.com - Brain Teasers Forum

 Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-)
Guest Message by DevFuse

# 4 unknown coins - another weighing puzzle

14 replies to this topic

### #11 phil1882

phil1882

Senior Member

• Members
• 542 posts

Posted 28 November 2012 - 06:28 PM

hmm. i only get 47 total cases. there are 4! = 24 cases where all coins are a different weight, 12 cases where 2 coins are equal, 6 cases where 2 pairs are equal, 4 cases where 3 are equal, and 1 case where all coins are equal. am i missing something?
• 0

### #12 phil1882

phil1882

Senior Member

• Members
• 542 posts

Posted 28 November 2012 - 07:00 PM

edit nm i got it. i was only thinking of the heaviest being equal but any of the three positions can be equal.
• 0

### #13 CaptainEd

CaptainEd

Senior Member

• Members
• 1094 posts

Posted 28 November 2012 - 08:11 PM

Aye, Captain. You can interpret it that way. I put this condition there to exclude the possibility of one coin weighing as much as 2 others.

I think I see it more clearly now--any number of coins always weighs strictly more than a smaller number of coins.
• 0

### #14 phil1882

phil1882

Senior Member

• Members
• 542 posts

Posted 28 November 2012 - 09:30 PM

i tend to agree with curr3nts assessment. no way to get a guaranteed solve in 4. best i can do with 4...
Spoiler for

Edited by phil1882, 28 November 2012 - 09:31 PM.

• 0

### #15 Prime

Prime

Senior Member

• Members
• 872 posts
• Gender:Male
• Location:Illinois, US

Posted 22 December 2012 - 04:06 AM

This is Sort problem. Computer scientists have been tackling this very puzzle for the past 60 years or so, producing a great variety of algorithms.

Spoiler for One less

What you have suggested here seems like “Tree Sort” with self-balancing binary tree. The "worst case" order for such algorithm is O(n log n). That's as fast as it gets. Or, at least, that’s the present day theory.

• 0

Past prime, actually.

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users