Purchase Solution

Algorithm to detect single bad coin using pan balance

Not what you're looking for?

Ask Custom Question

Eight coins are identical in appearance, but one coin is either heavier or lighter than the others, which all weigh the same.

Describe an algorithm that identifies the bad coin in at most three weighings and also determines whether it is heavier or lighter than the others, using only a pan balance.

Purchase this Solution
Solution Summary

Solution describes an algorithm to detect the single bad coin, interspersed with pseudo code, analysis and detailed explanations on hows and whys behind correct working of this algorithm.

Solution Preview

The algorithm description below has been interspersed with pseudo code, apart from the logic explaining hows and whys behind working of this algorithm.

Notation "W(X)" in the description indicates the weight of coins in set X.
Initially, the coins are labelled as C1, C2, C3, C4, C5, C6, C7 and C8.

1. Divide the given 8 coins into 3 sets of size (3,3,2) coins respectively i.e.

S1 = {C1, C2, C3}
S2 = {C4, C5, C6}
S3 = {C7, C8}

if (W(S1) == W(S2)) {
The bad coin is either C7 or C8. Go to step 2 to find it.
} else {
The bad coin is one of {C1,...,C6}. Go to step 3 to find it.
}

2. Since the coins in sets S1 and S2 i.e. {C1,..,C6} are of right weight, we pick up any coin from either of these two sets and refer to it as R.

if (W({C7}) != W({R})) {
C7 is the bad coin. It's weight relationship with R
determines whether it is heavier or lighter.

} else {
C8 is the bad coin. We ...

Purchase this Solution
Free BrainMass Quizzes
Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

View More Free Quizzes
Related BrainMass Solutions

  • Mathematics Problems

    Try to prove using deductive reasoning, the conjecture you made in part(c). 2. You have 13 coins which all look alike. Twelve coins weigh exactly the same but the other one is heavier. You have a pan balance.

  • Modular Arithmetic - Thinking Mathematically

    Check digit schemes are numbers appended to an identification number that allow the accuracy of information stored to be checked by an algorithm.

  • Research Works for Satellite Route Optimization

    Optimization Algorithm The AVS scheduler allows users with multiple, on-orbit vehicles & single or multiple ground terminals to develop a schedule rapidly for any length period that maps resource needs to time slots, using an optimization algorithm.

  • Discrete Mathematics and its Applications : Greedy Algorithms

    Use the greedy algorithm to make change using quarters, dimes, nickels, and pennies for: a) 87 cents. b) 49 cents. c) 99 cents. d) 33 cents. Please see the attached file for the fully formatted problems.

  • Probability and Real World Probability

    a failure of the system to detect the incoming missile (the very first status, where every single radar has a "-", indicating that it did not detect the incoming missile).

  • SARS virus and protein

    The 5′ leader sequence and 3′ noncoding region common to the gRNA and all sgRNAs are shown as filled boxes. The positions of the primers gF and gR used to detect gRNA and the primers sgF and sgR used to dedect sgRNA are shown as arrows.

  • Character Encoding in Data Link Protocol & Other Questions

    Although the first parity bit can detect even-numbered bits and the second parity bit can detect odd-numbered bits, this coding scheme can only detect ALL single bit errors for sure, that is, d=1. Therefore, the Hamming distance is d+1=2.

  • PR and Crisis Management

    In PR the most difficult situation is to react to a crisis. Their job becomes less about making the company look good product wise and more about helping the entity change what may be a bad perception to a better one.

  • Genetics: Exons, Sequencing, and Bioinformatics

    (A) PSI-BLAST uses CLUSTALW to construct a sequence alignment of the HSPs (B) PSI-BLAST is more sensitive than gapped BLAST to detect weak sequence homologs (C) PSI-BLAST can only be run for a single iteration (D) PSI-BLAST searches the sequence database

View More Related Solutions